编译原理 第11讲(第五章).ppt

《编译原理 第11讲(第五章).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自顶向下语法分析方法5.1确定的自顶向下分析思想5.2LL(1)文法判别FIRST和FOLLOW集定义和计算5.3非LL(1)文法的改造1自上而下的语法分析面临的问题-实现考虑回朔文法的左递归性S→Sa2自上而下分析对文法的要求例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来推导SSa语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaaSaa

2、a问题——试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配原因——文法含有左递归3自上而下分析的进一步讨论自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求－文法不能含有左递归规则。自上而下分析又可分为确定的和不确定的两种不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法确定的分析方法需对文法有一

3、定的限制4（选）自上而下的语法分析－左递归规则G[S]:S→SaS→bL={ban

4、n≥1}W=baaaSbSSaSa5（选）左递归－关于非终结符P的规则直接左递归若P→Pα

5、βα、β∈V*且α、β不以P开头一般左递归若P=>*PαS→AaA→Sb…6（选）消除文法中左递归规则消除直接左递归形如：P→Pα

6、βα非，α，β不以P打头改写为：P→βQQ→αQ

7、其中Q为新增加的非终结符7（选）消除文法中左递归规则例:E→E+T

8、TT→T*F

9、FF→(E)

10、aG[E]:(1)E→TE’

11、(2)E’→+TE’(3)E’→(4)T→FT’(5)T’→*FT’(6)T’→(7)F→(E)(8)F→a8（选）消除一般左递归要求文法:1.无回路(A(=>+(A)2.无空产生式（1）.以某种顺序将文法非终结符排列A1,A2…An（2）fori:=1tondobeginforj:=1toi-1do用Ai-->1

12、2r…

13、kr替代形如Ai-->Ajr的规则,其中Aj-->1

14、2…

15、k是关于Aj的全部产生式;消除Ai规则的直接左递归;end;（3）化简由2得到的文法9（选）回溯的原因例G[S

16、]:S→xAyA→ab｜a若当前输入串为xay，首先构造的推导SxAy匹配进一步推导对A可选择A→ab替换，得SxAyxabyxayxaby匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，SxAyxay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。105.3非LL(1)文法的改造消除左递归提左公因子将产生式Ａβ

17、变换为：ＡBBβ

18、

19、11E→E+T｜TT→T*F｜FF→i｜(E)FIRST(E)=｛(,i｝FIRST(T)=｛(,i｝FIRST(F)=｛(,i｝消左递归E–>TE’E’–>+TE’E’–>E→T+E｜TT→F*T｜FF→i｜(E)FIRST(E)=FIRST(T)=FIRST(F)=｛(,i｝提左公因子E→T(+E｜)T→F(*T｜)12消除左递归和提左公因子并不一定都能将非LL(1)文法改造为LL(1)的S→ifCtS

20、ifCtSeSC→b提左因子S→ifCtSAA→eS

21、First集Follow集Sif#,e

22、Ae,#,eCbtM[A,e]={A→eSA→}13LL(1)分析中的一种错误处理办法发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶，面临的输入符为a，但分析表M的M[A,a]为空“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。同步符号的选择1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析14G

23、[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>(4)T–>FT’(5)T’–>*FT’(6)T’–>(7)F–>(E)(8)F–>aa+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)synsyn15练习1.对文法G［S］S→a

24、∧

25、(T)T→T,S

26、S（1）给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。