《编译原理4.3.1-左递归的消除》由会员分享，可在线阅读，更多相关《编译原理4.3.1-左递归的消除（8页珍藏版）》请在金锄头文库上搜索。
1、第四章 语法分析 - 自上而下分析4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL(1)分析中的错误处理4.3 LL(1)分析法4.3.1 左递归的消除 4.3.2 消除回溯、提左公因子 4.3.3 LL(1)分析条件4.3.1 左递归的消除 直接左递归 : PP 间接左递归 : P P +a) 消除直接左递归 P P| PP PP|PP1| P2 | Pm | 1 | 2 | n P 1 P|2 P|n P P1 P|2 P|m P | 补充例: 消除直接左递归 G： SSa|b 可改写为：
2、G :SbS SaS|b) 消除间接左递归 G: (1) AaB (2) ABb (3) BAc (4) Bd G: (1)AaB (2)ABb (3)B(aBc|d)B (4)BbcB | 补充例G: (1) AaB(2) ABb(3) BaBcBBb c (4) Bd c) 消除文法中一切左递归将非终结符排序为P1，P2，Pn FOR i=1 TO n DO FOR j= 1 TO i-1 DO 若Pj的所有产生式为: Pj1|2|k把形如Pi Pj的规则改写为： Pi 1 | 2 | k 消除Pi中的一切直接左递归 化简文法, 删除无用产生式要求: 文法不 含回路P P , 不含以为为右 部的产产生式+例4.3: 消除一切左递归G: (1) SQc|c(2) QRb|b(3) RSa|a G1: SQc|c QRb|b R(bca|ca|a)R RbcaR| G2: S(abc|bc|c)S SabcS| QSab|ab|b RSa|a 补充例无用产生式，应删除排序: R、Q、S排序: S、Q、RG1和G2等价
