第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL(1)分析中的错误处理4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左公因子4.3.3LL(1)分析条件4.3.1左递归的消除•直接左递归:P→Pβ•间接左递归:PP+a)消除直接左递归P→Pα|βP→βP'P'→αP'|εP→Pα1|Pα2|…|Pαm|β1|β2|…|βnP→β1P'|β2P'|…|βnP'P'→α1P'|α2P'|…|αmP'|ε补充例:消除直接左递归G：S→Sa|b可改写为：G':S→bS'S'→aS'|εb)消除间接左递归G:(1)A→aB(2)A→Bb(3)B→Ac(4)B→dG'':(1)A→aB(2)A→Bb(3)B→(aBc|d)B'(4)B'→bcB'|ε补充例G':(1)A→aB(2)A→Bb(3)B→aBcB→Bbc(4)B→dc)消除文法中一切左递归将非终结符排序为P1，P2，…，PnFORi=1TOnDO{FORj=1TOi-1DO{若Pj的所有产生式为:Pj→δ1|δ2|…|δk把形如Pi→Pjγ的规则改写为：Pi→δ1γ|δ2γ|…|δkγ}消除Pi中的一切直接左递归}化简文法,删除无用产生式要求:文法不含回路PP,不含以ε为右部的产生式+例4.3:消除一切左递归G:(1)S→Qc|c(2)Q→Rb|b(3)R→Sa|aG1:S→Qc|cQ→Rb|bR→(bca|ca|a)R'R'→bcaR'|εG2:S→(abc|bc|c)S′S'→abcS′|εQ→Sab|ab|bR→Sa|a补充例无用产生式，应删除排序:R、Q、S排序:S、Q、RG1和G2等价
