第五章自顶向下语法分析方法.ppt

本章小结 两种自顶向下分析方法： 递归子程序法 预测分析法 一种文法：LL(1)文法 判别方法 非LL(1)到LL(1)的转换 如果文法具有间接左递归，则也将发生上述问题， 只不过环的圈子兜得更大。 要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。 （1）消除直接左递归 将左递归规则改为右递归规则 若：P→P?|? 则可改写为：P→?P’ P’→?P’|ε 例12 已知G[E]： E→T*F|T/F|F 　 T→F|T*F|T/F 解：左递归改为右递归得： E→T*F|T/F|F T→FT’ T’→*FT’|/FT’|ε （2）消除间接左递归 例13 S→Aa|b A→Sd 根源：最左循环依赖 解决思路：试图改为单向依赖 更改依赖方向基本方法：产生式代入，先把间接左递归转化为直接左递归 S→Sda|b 再消除直接左递归 S→bS’ S’→daS’|ε 消 除 所 有 左 递 归 的 算 法 1.把G的非终结符整理成某种顺序A1，A2，……An ，使得： A1 → δ1|δ2|……δk A2→ A1 r…… A3 → A2u | A1v….. ……. 2. for ( i=1;i=n;i++) for (j=1;j=i-1;j++) 把每个形如Ai→Ajr的规则替换成 Ai →(δ1|δ2|……δk) r 其中Aj →δ1|δ2|……δk是当前全部Aj 的规则 消除Ai规则中的直接左递归 3.化简由2得到的文法即可。 间接左递归 直接左递归 消除 直接左递归 一般左递归也可以通过改写法予以消除。 （3）消除文法中一切左递归的算法 删去从文法开始符号不可达的非终结符产生式。 例14 文法G：(1)S→Qc|c (2)Q→Rb|b (3)R→Sa|a 将非终结符排序 ：R，Q，S 对R：产生式(3)不含直接左递归，所以保持不变 对Q：把(3)代入(2)得(2’)Q→Sab|ab|b，无直接左递归 对S：把(2’)代入(1)得 (1’) S→Sabc|abc|bc|c，有直接左递归，消除直接左递归得 S→abcS’|bcS’|cS’ S’ →abcS’|ε 处理结果为：R→Sa|a Q→Sab|ab|b S→abcS’|bcS’|cS’ S’ →abcS’|ε 由于Q，R是不可到达的非终结符，其产生式应删除。 最终得文法G’：S→abcS’|bcS’|cS’ S’→abcS’|ε 示例说明： 当非终结符顺序为R，Q，S，消除左递归的最终结果为： S→abcS’|bcS’|cS’ S’→abcS’|ε 若非终结符顺序为S，Q，R，则消除左递归的最终结果为： S→Qc|c Q→Rb|b R→bcaR’|caR’|aR’ R’→bcaR’|ε 结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。 5.4　不确定的自顶向下分析思想 不确定的自顶向下分析也称带回溯的自顶向下分析 定义： 不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。 1.由于相同左部产生式的右部FIRST集交集不为空而引起回溯 例15设有文法S→xAy，A→ab|a，对输入串w=xay，推导 树为 S x A y S x A y b a S x A y 回溯 a S x A y 由于A的两条产生式：A→ab 和A→a 右部First集交集不为空，从而引起回溯 2.由于相同左部非终结符的右部存在能导出　　　ε的产生式，且该非终结符的FOLLOW集中含有其他产生式右部FIRST集的元素 例16 文法G：S→aAS， S→b，A→bAS，A→ε 输入串w=ab，推导树为: S a A S 回溯 S a A S S a A S S b A S a A S ε b