自下而上语法分析：二义文法的应用与归约

"二义文法的应用在编译原理中占据了一席之地，尽管它们不是LR文法，但在某些情况下，二义文法能够提供有用的解析机制。例如，文法E→E+E | E*E | (E) | i可以通过定义运算符*和+的优先级和结合性来解析简单的表达式。保留二义文法有时是有益的，因为它允许我们运用LR分析法的思路来处理这类文法产生的语言。本章主要探讨自下而上语法分析，即从输入串开始，通过归约操作最终得到文法的开始符号，也就是从语法树的叶子节点向上归约至树根。" 在自下而上分析中，我们将学习一种称为"移进-归约"的方法，它依赖于一个存储符号的栈。输入符号依次被移入栈中，当栈顶的符号组合匹配某个产生式的右部时，会执行归约操作，将这些符号替换为该产生式的左部。以文法S→aAcBe，A→b，A→Ab，B→d为例，输入串"abbcde"的解析过程将涉及多个移进和归约步骤。在这个过程中，我们需要确定何时以及如何进行归约，这是自下而上分析中的关键问题。 "可归约串"的概念是分析过程中的核心，其定义可以有多种方式，如算符优先分析中的"最左素短语"和规范归约分析中的"句柄"。规范归约是确定归约起点的一种方法，如果存在规则A→β，使得句型αAδ可以被归约为β，那么β被称为句型αAδ相对于规则A→β的直接短语，而句型的最左直接短语则称为句柄。在处理二义文法时，正确识别句柄对于避免分析过程中的歧义至关重要。 以文法E→T|E+T，T→F|T*F，F→i|(E)为例，我们分析句型"i*i+i"。它的短语是"iiii*ii*i+i"，直接短语是"iii"，句柄是"i"。这是因为根据文法，E可以归约为F，F再归约为i，形成句柄，使得整个表达式能够被正确解析。 二义文法的应用在于其能处理某些特定的解析需求，而自下而上的分析方法则通过移进和归约操作来构建语法树。理解和掌握自下而上分析的基本问题，如确定可归约串和使用句柄进行归约，是编译原理中不可或缺的部分，这对于解析二义文法和构造有效的解析器至关重要。