1、第九讲 语法分析 自下而上分析1 概念与基本问题 自下而上分析法 - 从输入串开始，逐步进行归约，直到归到文法的开始符；或者说，从语法树的末端开始，步步向上 “归约 ”，直到根结点。算符优先分析法 句柄归约法 自上而下递归下降分析法 预测分析（ 1） 归约与分析树 归约“移进 归约 ” - 将输入符号一个个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换为该产生式的左部符号E.G. 设有文法 G:(1) S - aAcBe (2) A - b(3) A - Ab (4) B - d希望将输入串 abbcde归约到 S.解释 P84图 5.1的归约过程关键概念 : 引进可
2、归约串概念 : 句柄 最左素短语b. 分析树 (分析过程可用一棵树表示 )等同语法树：采用规范归约方法（句柄归约）自下而上分析过程 ,每步归约都可画一棵子树 ,随着归约的完成 ,这些子树被连成一棵统一的树称分析树 .如移进归约过程A A B Sb A b d a A c B eb A b d第 3步 5步 8步 第 10步b(2) 规范归约 短语 （ P85） 例子见 P85设 G是一文法， S是文法的开始符，若 是 G的一个句型，如果 S *= A 且 A += , 则说 为相对于非终结符 A的短语 .特别地 , 若 A = , 则说 是句型 相对于规则A- 的直接短语 . 一个句型的最左直
3、接短语称该句型的句柄 .b. 规范归约 (最左归约 )设 是文法 G的一个句子 ,我们称序列 n, n-1, , 0是 的 一个规范归约 ,如果此序列满足 :(1) n= (2) 0 为文法开始符 ,即 0 = S(3) 对任何 i(0 i n), i-1是从 i经把 句柄替换为相应产生式的左部符号而得 .c. 规范推导 (最右推导 )规范推导所得句型称规范句型d. 规范归约是规范推导的逆过程e. 句柄和归约可通过修剪语法树而得 (P87)一个句型的句柄是这个句型的语法树中最左那棵子树端末结的自左至右排列 .该子树只有 (而且必须有 )父子两代 , 没有第三代 .S S S Sa A c B e a A c B e a A c B e a A c B eA b d A b d db b为句柄 (剪去 ) 其余类推 S(3) 符号栈的使用与分析树的表示 分析器工作过程 (使用符号栈 ) P88初始： 符号栈 输入串# #过程：移进、归约 /反复进行终态： 符号栈 输入串# S # /S表示开始符号总之，语法分析对符号栈的使用有四类操作： “移进 ”、 “归约 ”、 “接受 ”和 “出错处理 ”。移进 -由输入串吃进一个符号到栈中；归约 -栈顶可归约串用适当符号去替换；接受 -宣布分析成功。可看作特殊归约形式 分析树自学
