资源描述:
《编译原理语法分析 从上至下.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、编译方法中国人民大学信息学院陈文萍1第四章语法分析——自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL(1)分析中的错误处理24.1语法分析器的功能语法分析器的地位分类自上而下分析自下而上分析词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析树34.2自上而下分析定义:也称面向目标的分析方法,从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子。主旨:对任何输入串,试图用一切可能的办法,从文法开始符号着
2、手,自上而下地为输入串构造一棵语法树。本质上是一个试探过程,反复使用不同的产生式谋求匹配输入串的过程。4自上而下分析的问题(1)左递归例:例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想,选用产生式(1)来推导SSa,语法树末端结点最左符号为非终结符,所以选用(1)继续推导SSaSaa此时语法树末端结点最左符号为非终结符,所以选用(1)继续推导SSaSSaSSSa试图用S匹配输入串时,出现:在没有识别任何输入符号的情况下,又得重新要求S去进行新的匹配,分析过程陷入无限循环5
3、自上而下分析的问题(2)回溯例:G[S]:S→xAy,A→ab|a若当前输入串为xay,首先构造的推导SxAy匹配进一步推导对A可选择A→ab替换,得SxAyxabyxayxaby匹配xa都已匹配,当前面临输入符为y与b不能匹配,所以将输入串指针退回到a,对A的替换重新选用下一个产生式A→a进行试探,SxAyxay输入串中当前符a得到匹配,指针向前移动到y,与语法树中y匹配,匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。6自上而下分析的问题(3)分析过程中,匹配成功可能是暂时的。最终分析不成功,很
4、难知道输入串中出错的确切位置。带回溯,效率低,代价高74.3LL(1)分析法左递归的消除消除回溯LL(1)分析条件8直接左递归的消除左递归:一个文法是含有左递归的,如果存在非终结符P,P=>+Pα形如:P→Pα
5、β,其中α不为,β不以P打头消除直接左递归改写为:P→βP’,P’→αP’
6、一般来说,若P→Pα1
7、Pα2
8、…
9、Pαm
10、β1
11、β2
12、…
13、βn,αi不为,βi不以P打头,消除直接左递归就把规则改写为:P→β1P’
14、β2P’
15、…
16、βnP’P‘→α1P’
17、α2P’
18、…
19、αmP’
20、例:E→E+T
21、T,T→T*F
22、F,F→
23、(E)
24、i消除直接左递归后变为:E→TE’E’→+TE’
25、T→FT’T’→*FT’
26、F→(E)
27、i9文法左递归的消除消除一个文法左递归:对文法的要求无回路()不含以为右部的产生式消除左递归算法:(1)以某种顺序将文法非终结符排列P1,P2……Pn(2)fori:=1tondobeginforj:=1toi-1do用Pi-->1r
28、2r…
29、kr替代形如Pi-->Pjr的规则其中Pj-->1
30、2…
31、k是关于Pj的全部产生式;消除Pi规则的直接左递归;end(3)化简由2得到的文法10左递归的消除例,文法S→Qc
32、c
33、,Q→Rb
34、b,R→Sa
35、a1,非终结符排序为:S,Q,R2,替换规则对于S,无需替换,S→Qc
36、c对于Q,无需替换,Q→Rb
37、b关于R,替换为,R→Rbca
38、bca
39、ca
40、a,消除直接左递归为R→bcaR’
41、caR’
42、aR’,R’→bcaR’
43、非终结符的顺序不同,文法的形式可能不同,但都是等价的11消除回溯不回溯,对文法的要求设G是一个不含左递归的文法,对G的所有非终结符的每个候选,它的终结首符集FIRST()为FIRST()={a
44、=>*a…,a∈VT},若=>*ε则规定ε∈FIRST()若非终结符A的所有候选
45、首符集两两不相交,即A的任何两个不同候选α和β,FIRST(α)∩FIRST(β)=,则可消除回溯改造文法的方法:提左公因子将产生式Aβ1
46、…
47、βn
48、1
49、…
50、m变换为:AB
51、1
52、…
53、mBβ1
54、…
55、βn12LL(1)分析条件例如:文法:E→TE’,E’→+TE’
56、,T→FT’,T’→*FT’
57、,F→(E)
58、i输入串i+i,语法分析树FIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(FT’)={(,i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}
59、ETE’iTE’+T’FFT’εiεε13LL(1)分析条件S是文法G的开始符号,对G的任何非终结,定义FOLLOW(A)={aS=>*…Aa…且a∈VT},若S=>*…A,则#∈FOLLOW(A)一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任