编译原理 第11讲(第五章).ppt

1 第5章自顶向下语法分析方法 5 1确定的自顶向下分析思想5 2LL 1 文法判别FIRST和FOLLOW集定义和计算5 3非LL 1 文法的改造 2 自上而下的语法分析面临的问题 实现考虑 回朔文法的左递归性S Sa 3 自上而下分析对文法的要求 例文法G0 S 1 S Sa 2 S b分析baa是不是文法的句子按照自上而下的分析思想选用产生式 1 来推导S Sa语法树末端结点最左符号为非终结符 所以选用 1 继续推导S Sa Saa此时语法树末端结点最左符号仍为非终结符 所以选用 1 继续推导S Sa Saa Saaa问题 试图用S匹配输入串时 出现 在没有读入任何输入符号的情况下 又得重新要求S去进行新的匹配原因 文法含有左递归 4 自上而下分析的进一步讨论 自上而下分析也称面向目标的分析方法 也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子 若能构造出推导则表明输入串是给定文法的句子 否则表明该输入不是给定文法的句子 自上而下分析对文法的要求 文法不能含有左递归规则 自上而下分析又可分为确定的和不确定的两种不确定的分析方法称为带回溯的分析方法 这种方法实际上是一种穷举的试探方法确定的分析方法需对文法有一定的限制 5 选 自上而下的语法分析 左递归规则 G S S Sa S bL ban n 1 W baaaSbSSaSa 6 选 左递归 关于非终结符P的规则 直接左递归若P P V 且 不以P开头一般左递归若P P S AaA Sb 7 选 消除文法中左递归规则 消除直接左递归形如 P P 非 不以P打头改写为 P QQ Q 其中Q为新增加的非终结符 8 选 消除文法中左递归规则 例 E E T TT T F FF E aG E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 9 选 消除一般左递归要求文法 1 无回路 A A 2 无空产生式 1 以某种顺序将文法非终结符排列A1 A2 An 2 fori 1tondobeginforj 1toi 1do用Ai 1 2r kr替代形如Ai Ajr的规则 其中Aj 1 2 k是关于Aj的全部产生式 消除Ai规则的直接左递归 end 3 化简由2得到的文法 10 选 回溯的原因 例G S S xAyA ab a若当前输入串为xay 首先构造的推导S xAy 匹配 进一步推导对A可选择A ab替换 得S xAy xabyxayxaby 匹配 xa都已匹配 当前面临输入符为y与b不能匹配 所以将输入串指针退回到a 对A的替换重新选用下一个产生式A a进行试探 S xAy xay输入串中当前符a得到匹配 指针向前移动到y 与语法树中y匹配 匹配成功 由于相同左部的产生式的右部开始符号相同而引起回溯 11 5 3非LL 1 文法的改造 消除左递归提左公因子将产生式 变换为 BB 12 E E T TT T F FF i E FIRST E i FIRST T i FIRST F i 消左递归E TE E TE E E T E TT F T FF i E FIRST E FIRST T FIRST F i 提左公因子E T E T F T 13 消除左递归和提左公因子并不一定都能将非LL 1 文法改造为LL 1 的 S ifCtS ifCtSeSC b提左因子S ifCtSAA eS First集Follow集Sif eAe eCbtM A e A eSA 14 LL 1 分析中的一种错误处理办法 发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶 面临的输入符为a 但分析表M的M A a 为空 应急 恢复策略跳过输入串中的一些符号直至遇到 同步符号 为止 同步符号的选择1把FOLLOW A 中的所有符号作为A的同步符号 跳过输入串中的一些符号直至遇到这些 同步符号 把A从栈中弹出 可使分析继续2把FIRST A 中的符号加到A的同步符号集 当FIRST A 中的符号在输入中出现时 可根据A恢复分析 15 G E 1 E TE 2 E TE 3 E 4 T FT 5 T FT 6 T 7 F E 8 F a 16 练习 1 对文法G S S a T T T S S 1 给出 a a a 和 a a a a 的最左推导 2 对文法G进行改写 改写后的文法G 是否LL 1 若是 给出它的递归下降分析程序和预测分析表 并描述对输入串 a a 的分析过程 2 已知文法G S S MH aH LSo K dML L eHfM K bLM判断G是否是LL 1 文法 如果是 构造LL 1 分