资源描述:
《自顶向下的句法分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第4章自顶向下的句法分析自顶向下分析方法递归下降分析法LL(1)分析法自底向上分析方法算符优先分析法LR分析法4.1句法分析器概述句法分析是编译程序的核心部分。任务:识别由词法分析得出的单词序列是否是合法的句子。理论基础:上下文无关文法和下推自动机句法分析方法:自顶向下(top-down)的句法分析:反复使用不同产生式进行推导以谋求与输入符号串相匹配。自底向上(bottom-up)的句法分析:对输入符号串寻找不同产生式进行归约直到文法开始符号。注:这里所说的输入符号指词法分析所识别的单词。确定的
2、自顶向下分析思想例文法G1[S]:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程:SpApcAdpccAddpccaddSpASpAcAdSpAcAdcAdSpAcAdcAda文法G1[S]:SpA
3、qBAcAd
4、aBdB
5、b文法的特点:每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符开始。文法G2[S]:SApSBqAaAcABbBdBW=ccap自顶向下的推导过程:SAp
6、cApccApccapSApSApcASApcAcASApcAcAa文法G2[S]:SAp
7、BqAa
8、cABb
9、dB文法的特点:每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部,那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。为了实现确定的(即无回溯的)自顶向下分析,则要求文法满足下述两个条件:(1)文法不含左递归直接左递归:AA…间接左递归:AB…,B+A左递归文法使自上而下分析工作陷入死循环。例如,如果有产生式EE+TEE+TE+T+T
10、E+T+T+T…(2)无回溯,对文法的任一非终结符号,当其产生式右部有多个候选式可供选择时,各候选式所推导出的终结符号串的首字符集合要两两不相交。例如,如果有文法G[S]:SxAyAab∣a输入串xay的分析就需要回溯。带回溯的自顶向下分析方法实际上是一种穷举的试探方法,其分析效率极低。消除左递归1.直接左递归方法是引入一个新的非终结符,把含有左递归的产生式改为右递归。设关于A的产生式为AA1∣A2∣…∣Am∣1∣2∣…∣n其中,每个i都不为且每个j都不以A开头,则消除
11、A的直接左递归就是将其改写为:例如,含有直接左递归的表达式文法G[E]为:G[E]:EE+T∣TTT*F∣FF(E)∣i消去直接左递归后得到文法G'[E]为:G'[E]:ETE'E'+TE'∣TFT'T'*FT'∣F(E)∣i2.间接左递归将间接左递归变为直接左递归,然后消除直接左递归。如文法G[A]含有间接左递归:AaBAaBAaBABbABbABbBAcBaBcBaBcB'
12、dB'BdBBbcB'bcB'
13、εBd消除文法中一切左递归的算法要求:
14、无回路(即不存在A+A的推导)充分条件:文法不含形如AA的有害产生式,也不含A的空产生式。(1)将所有非终结符排序:A1、A2、…、An;(2)for(i=1;i<=n;i++){for(j=1;j<=i−1;j++){若Aj的所有产生式为:Aj1
15、2
16、…
17、k则把形如AiAjr的产生式变换为:Ai1r
18、2r
19、…
20、kr}消除Ai规则中的一切直接左递归;}(3)删除无用的产生式这里第二步所做的工作是:a)若产生式出现直接左递归则用消除直接左递归的方法消除掉。b)若产生式右部
21、最左符号是非终结符且其序号大于左部的非终结符,则不处理。c)若序号小于左部的非终结符,则将这序号小的非终结符用其右部串来取代,然后消除新的直接左递归。注意:1)若非终结符排列顺序不同,改写后的文法也不同,但它们是等价的。2)开始符号不能改变。例:对下面文法消除左递归:(1)SQc
22、c(2)QRb
23、b(3)RSa
24、a1)对非终结符排序:S、Q、R2)把(1)代入(3)得:(4)RQca
25、ca
26、a再把(2)代入(4)得:(5)RRbca
27、bca
28、ca
29、a对(5)消除直接左递归得:(6)R
30、bcaR'
31、caR'
32、aR'(7)R'bcaR'
33、得到不含左递归的文法:(1)、(2)、(6)、(7)对非终结符也可以有不同的排序。1)对非终结符重新排序:R、Q、S2)把(3)代入(2)得:(4')QSab
34、ab
35、b再把(4')代入(1)得:(5')SSabc
36、abc
37、bc
38、c对(5')消除直接左递归得:(6')SabcS'
39、bcS'
40、cS'(7')S'abcS'
41、得到不含左递归的文法:(6')、(7')(1)SQc
42、c(2)QRb
43、b(3)RSa
44、a消除回溯产生回溯的原因