自底向上的语法分析

  • 从分析树的底部(叶节点)向顶部(根节点)方向构造分析树

  • 可以看成是将输入串w归约为文法开始符号S的过程

  • 自顶向下的语法分析采用最左推导方式,自底向上的语法分析采用最左归约方式（反向构造最右推导）

  • 自底向上语法分析的通用框架:移入-归约分析(Shift-Reduce Parsing)

例:移入-归约分析

文法
① E → E+E 
② E → E*E 
③ E → (E) 
④ E → id

每次归约的符号串称为“句柄”

栈内符号串 + 剩余输入 =“规范句型”

移入-归约分析的工作过程

  • 在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止。

  • 然后，它将β归约为某个产生式的左部

  • 语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止

移入-归约分析器可采取的4种动作

  • 移入：将下一个输入符号移到栈的顶端
  • 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
  • 接收：宣布语法分析过程成功完成
  • 报错：发现一个语法错误，并调用错误恢复子例程

移入-归约分析中存在的问题

例

(1) →var :
(2) →i
(3) → , i
(4) →real | int

句柄：句型的最左直接短语

最后修改日期:2020年6月2日

留言

撰写回覆或留言