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

"本文主要介绍了扩充的BNF表示法在编译原理中语法分析的应用，以及如何通过这种方法解决文法的左递归问题。" 在编译原理中，语法分析是一个关键步骤，其目的是检查词法分析得到的符号串是否符合文法规则，构建语法树。这一过程分为自顶向下和自底向上的方法。本文主要关注的是自顶向下分析，特别是非确定的自顶向下分析法。这种方法从文法的开始符号出发，尝试为输入串建立一棵语法树。然而，对于形如`U→x1|x2|…|xn`的规则，可能会需要对所有规则进行试探，效率较低。 针对这个问题，文法的左递归和回溯的消除变得尤为重要。左递归是指非终结符直接或间接地在其自身的产生式左侧出现，这会导致分析过程中无限递归，降低效率。例如，文法`E→E+T|E-T|T`就是一个左递归的例子。消除左递归通常有两种方法：一是引入新的非终结符，将左递归转换为右递归；二是使用扩充的BNF表示法。 扩充的BNF表示法通过引入特殊符号来简化文法表达。例如，`{α}`表示`α`可以重复任意次数，`[α]`表示`α`可以存在也可以不存在，`(…)`用于分组。通过这种方式，可以有效地消除左递归，如将`N→ND|D`改写为`N→D{D}`，`D→0|1|2|…|9`。 以文法`A → Ac|Aad|bd|e`为例，使用扩充的BNF表示法可改写为`A → (bd|e) {c|ad}`。这种方法使得文法更易于分析，因为它消除了左递归，使得自顶向下分析更加高效且无回溯。 自顶向下分析的另一种形式是确定的自顶向下分析，它要求文法无左递归且无回溯，以提高分析速度。例如，通过消除左递归和回溯，我们可以将文法`E→E+T|E-T|T`和`T→T*F|T/F|F`，`F→(E)|i`转换为`E→TE’`，`E’→+TE’|-TE’|`，`T→FT’`，`T’→*FT’|/FT’|`，`F→(E)|i`的形式，这样分析器就能更有效地处理输入字符串。 总结来说，扩充的BNF表示法在编译原理的语法分析中起到了优化文法结构、消除左递归的作用，提高了自顶向下分析的效率。对于编写编译器或者解析器的开发者而言，掌握这种表示法是至关重要的，因为它能帮助构建更高效的解析机制。