编译原理_复习笔记第五章

第五章 自下而上语法分析

自下而上分析法(Bottom-up)

• 核心概念：基于输入字符串展开分析, 逐步推进缩减操作直至抵达文法的起始符号位置. 亦即从语法树末端节点出发构建语法结构图示. 核心问题在于确定哪些字符是可缩减的位置.

• 所谓归约就是遵循文法中的产生式规则若一个串中出现了某个产生式的右部那么就会将那个产生式的右部替换为其左部符号

  • 归约方法分为两种不同的自下而上分析方法

运算符优先级解析法：基于运算顺序和结合规律进行语法解析。适用于处理数学表达式。

• 初始元素被视为可缩减的串

• 基于LR的方法：规范化地进行解析–保证每一次解析都使用当前句子的主干来进行

• 规范归约的过程遵循从开始符号逆向进行的操作步骤, 即为规范推导过程（由于所有的句柄均为最左可归约符, 因此逆向执行后得到的规范推导即为最右推导）

  • 句柄被视为可归约串

基于'移进-归约'原理的解析过程如下：首先将输入逐个字符地推入解析栈，在特定条件下将连续匹配某产生式右部的部分替换为其左部非终结符符号；一旦解析栈中仅存文法起始符且输入全部被处理，则判定'输入字符串属于合法语句'。

• 短语：假设S是文法G的起始符号，在文法G的一个句型αßδ中（其中α、ß、δ均为任意长度字符串），如果有A=>*ß，则称ß为该句型对非终结符A的一个短语。
  • 句柄：特别地，在上