消除左递归与回溯：自顶向下语法分析

"本资源主要介绍了编译原理中的扩充的BNF表示法，以及与语法分析相关的概念，包括自顶向下分析法、左递归和回溯的消除。" 在编译原理中，语法分析是将词法分析得到的符号序列进行解析，以构建抽象语法树或等效结构，确保输入的符号序列符合语法规则，同时检测并报告语法错误。语法分析通常有两种主要方法：自顶向下分析和自底向上分析。自顶向下分析从文法的开始符号出发，尝试构建输入串的语法树；而自底向上分析则是从输入串开始，通过归约操作逐步构建到文法的开始符号。 扩充的BNF（扩展巴科斯范式）是一种用于形式化描述语言语法的形式化方法，它引入了三个新的专用符号来增强表达能力： 1. 花括号 `{}`：用于表示符号串可以重复任意次数。例如，`N → ND|D` 可以改写为 `N → D{D}`，表示 `N` 可以由一个或多个 `D` 组成，消除了左递归的情况。 2. 方括号 `[]`：表示符号串是可选的。例如，如果有一个规则 `A → α[B]`，那么 `B` 可以出现也可以不出现。 3. 圆括号 `()`：用于提因子，将一组选择合并成一个整体。例如，`A → ax|ay|…|aw` 可以改写为 `A → a(x|y|…|w)`，使规则更简洁。 自顶向下分析方法面临的主要挑战是左递归和回溯问题。左递归是指非终结符能直接或间接地在其自身的产生式中出现，这会导致无限循环，降低分析效率。消除左递归通常通过引入新非终结符，将左递归规则转化为右递归。例如，对于左递归的文法 `E → E+T`，可以转换为 `E → T'E'`，其中 `E'` 表示可能的加法操作。 回溯是当分析过程中遇到无法匹配的符号时，退回到先前的决策点并尝试其他路径。消除回溯也需要对文法进行改造，使其在分析过程中尽可能少地需要回溯。 扩充的BNF表示法的专用符号，如花括号、方括号和圆括号，能够更有效地表示复杂的语法结构，简化文法规则，同时帮助消除左递归，提高自顶向下分析的效率。这些工具在编写编译器或解释器时非常有用，因为它们能够帮助设计者更清晰地定义语言的语法规则，并减少解析过程中的错误和复杂性。