第5章自顶向下语法方法(6学时)合编.ppt

例11：消除文法G[A] 的一切左递归。 S→Qc|cQ→Rb|bR→Sa|a 解：终结符排序为：S,Q,R (1)对于S：无直接左递归（不用消除） (2)对于Q：右部不含S开头的产生式 无直接左递归（不用消除） (3)对于R：右部含S开头的产生式，则： S?Qc Q?Rb R?Qca S?c Q?b R?ca R?a 右部含Q开头的产生式： S?Qc Q?Rb R?Rbca S?c Q?b R?bca R?ca R?a 消除直接左递归： S?Qc Q?Rb R?(bca|ca|a)R’ S?c Q?b R’?bcaR’|ε (4) 考察是否存在无用产生式：没有“无用产生式”，所以不用删除。 5.5 确定的自顶向下分析方法 递归子程序法: 主要思想： 对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。 优点： 简单、直观、易于构造。（PL/0的语法分析） 缺点： 对文法要求高，必须满足LL(1)文法； 由于递归调用多，速度慢，占用空间多。 5.5 确定的自顶向下分析方法 预测分析法: 预测分析器的组成： 预测分析程序、先进后出栈、预测分析表 预测分析法的步骤： （1）提取左公共因子，消除左递归 （2）判断文法是否为LL(1)文法 （3）若是，构造预测分析表； 否则，不能进行“确定的自顶向下”分析 （4）预测分析程序根据“预测分析表”并利用“分析栈”，对输入串进行分析 例12：文法G[E]: E?E+T|T 构造预测分析表。 T?T*F|F F?i|(E) 解： （1）消除左递归： VN排列为 E,T,F 消除E一切直接左递归： E?TE’ T?T*F F?i E’?+TE’|ε T?F F?(E) 消除T的一切直接左递归： E?TE’ T?FT’ F?i E’?+TE’|ε T’?*FT’|ε F?(E) F没有左递归。 文法无左公共因子。 所以，提取左公共因子和消除左递归后的文法为： E?TE’ T?FT’ F?i E’?+TE’ T’?*FT’ F?(E) E’?ε T’?ε （2）判断改写后的文法是否为LL(1)文法： 可推导出ε的VN表： E E’ T T’ F 否 是 否 是 否 求First集： First(E)={ i , ( } First(E’)={ + , ε } First(T)={ i , ( } First(T’)={ * , ε } First(F)={ i , ( } First( TE’ )=First(T)={ i , ( } First( FT’ )=First(F)={ i , ( } 求Follow集： Follow(E)= { # , ) } Follow(E’)=Follow(E)∪Follow(E’) = { # , )} Follow(T)=(First(E’)-{ε}) ∪Follow(E’)={+, #, )} Follow(T’)= Follow(T)∪Follow(T’) = {+, #, )} Follow(F)=(First(T’)-{ε})∪Follow(T)∪Follow(T’) ={ *, +, #, ) } 求各产生式的SELECT集： SELECT(E?TE’) = First(TE’) = { i , ( } SELECT(E’?+TE’) = First(+TE’) = { + } SELECT(E’?ε ) = Follow(E’) ={ #,)} SELECT(T?FT’) = First(FT’) = { i , ( } SELECT(T’?*FT’) = First(*FT’) = { * } SELECT(T’?ε )= Follow(T’)={ +,#,)} SELECT(F?(E) ) = First((E)) = { ( } SELECT(F?i) = First(i) = { i } 判定： SELECT(E’?+TE’) ∩ SELECT(E’?ε ) = φ SELECT(T’?*FT’) ∩ SELECT(T’?ε ) = φ SELECT(F?(E) ) ∩ SELECT(F?i) = φ ? 所以该文法是LL(1)文法，可以使用预测分析法。 （3）构造预测分析表： 构造预测分析表的方法： 对每个VT或“#”用符号a表示。 若a∈SELECT（A?α），则把A