2左递归的消除 (1)直接左递归的消除 Paβ 改写为P→βP P 8 般地A→Ax12.AamB1324.Bn (≠E,β不以A开头) 改写为P→B1P|β2P P→1P|axP1||anP|e
2.左递归的消除 (1)直接左递归的消除 P→Pα│β 改写为:P→P＇ P＇ →αP＇│ε 一般地 A→A1 |A2 |…|Am|1 |2 |…|n （iε，j不以A开头） 改写为:P→1P’│ 2P’│. . .│ nP’ P’→1P’│2P’│. . .│mP’│ε
(2间接左递归的消除 P→Pa (a)将文法G的所有非终结符按任一给定的顺序排列设为 ala2. An
(2)间接左递归的消除 PPα (a)将文法G的所有非终结符按任一给定的顺序排列,设为 A1,A2,…An; +
(b)消除可能的左递归 for i =1 to n do begin for j: =1 to i-1 do 把一个形如A→>Aq的产生式改写为 A1→>81Q62(|62a 其中A>61621…16是A的所有产生式 消除A产生式的直接左递归 ene (c)化简
(b)消除可能的左递归; for i:=1 to n do begin for j:=1 to i-1 do 把一个形如Ai→Aj的产生式改写为 Ai→1|2|…|k 其中Aj→1 |2 |…|k是Aj的所有产生式; 消除Ai产生式的直接左递归 end (c)化简
以S→Ql|c Q→Rb|b R→Saa 为例按S,QR排列,或RQS排列
以 S→Qc│c Q→Rb│b R→Sa│a 为例,按S,Q,R排列,或R,Q,S排列
按S、Q、R排列,代入后 SQc c Q→Rb|b R→ Rbca bca ca a 消除R中的直接左递归 R→ bcar|caR'laR R→baR|e 文法产生的语言( bcalcala)(bca)* ccbcc
按S、Q、R排列, 代入后 S→Qc│c Q→Rb│b R→ Rbca│bca│ca│a 消除R中的直接左递归 R→ bcaR’│caR’│aR’ R’→ bcaR’│ 文法产生的语言:(bca|ca|a)(bca)*bc|bc|c