消除文法中左递归规则 消除直接左递归 形如:P→Pa|β a非8,a,β不以P打头 改写为:P→βQ OL 其中Q为新增加的非终结符 16
16 消除文法中左递归规则 消除直接左递归 形如：P → P α| β α非， α，β不以P打头 改写为：P → βQ Q → αQ| 其中Q为新增加的非终结符
消除文法中左递归规则 例:E→E+TT T→T米F|F F→(E)a G[E:(1)E→TE(2)E→+TE′ (3)E"→(4) (5)T→*T(6)T→E (7)F→(E)(8)F→a 17
17 消除文法中左递归规则 例:E → E+T|T T →T*F|F F →(E)| a G[ E]: (1) E → TE’ (2) E’ → +TE’ (3) E’ → (4) T → FT’ (5) T’ → *FT’ (6) T’ → (7) F → (E) (8) F →a
消除一般左递归要求文法: 1无回路(A=>+A)2.无空产生式 (1).以某种顺序将文法非终结符排列A1A2An (2) for i::1 to n do begin forj:=1toⅰ-1do 用A->a1a2r…lak「替代 形如A>A的规则,其中 A->x1l2…|∝k是关于A的全部产生式; 消除A规则的直接左递归; end (3)化简由2得到的文法 18
18 消除一般左递归要求文法: 1.无回路(A(=>+(A) 2.无空产生式 （1） .以某种顺序将文法非终结符排列A1 ,A2 …An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai -->1 | 2 r…| k r替代 形如Ai --> Aj r的规则,其中 Aj --> 1 | 2…| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由2得到的文法
回溯的原因 例G[S]: S→XAy A→ab|a 若当前输入串为xay,首先构造的推导S→XAy 个匹配 进一步推导对A可选择A→ab替换,得S→XAy→Xaby xay Xabi 个匹配个 Ⅺa都已匹配,当前面临输入符为y与b不能匹配,所以将输入串 指针退回到a,对A的替换重新选用下一个产生式A→a进行 试探,S→XAy→Xay输入串中当前符a得到匹配,指针向前 移动到y,与语法树中y匹配,匹配成功。 由于相同左部的产生式的右部开始符号相同而引起回溯。 19
19 回溯的原因 例G[S]: S→xAy A→ab｜a 若当前输入串为xay，首先构造的推导SxAy 匹配 进一步推导对A可选择A→ab替换，得SxAy xaby xay xaby 匹配 xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串 指针退回到a，对A的替换重新选用下一个产生式A→a进行 试探， SxAy xay输入串中当前符a得到匹配，指针向前 移动到y，与语法树中y匹配，匹配成功。 由于相同左部的产生式的右部开始符号相同而引起回溯
在自上而下的分析方法中如何选择使用哪个产生 式进行推导? 假定要被代换的最左非终结符号是B,且有n条 规则:B→A1|A2|An,那么如何确定用哪个右 部去替代B?---什么信息用于 Parser做正确选 择?(输入串,文法特点)
20 在自上而下的分析方法中如何选择使用哪个产生 式进行推导？ 假定要被代换的最左非终结符号是B，且有n条 规则：B→A1|A2|…|An，那么如何确定用哪个右 部去替代B？-------什么信息用于Parser做正确选 择?(输入串,文法特点)