消除左递归：扩展BNF在编译原理中的应用

"这篇资料是关于中南民族大学编译原理课程的复习材料，主要讨论如何用扩展的巴克斯范式(BNF)消除左递归。扩展BNF允许更灵活地表示符号串的重复次数，并且可以用于解决直接左递归的问题。复习提纲涵盖了编译程序的基本结构、文法的分类和特点、句型和语法树的理解、推导方法、二义性文法的识别、上下文相关的分析方法，以及确定性有限自动机(DFA)和非确定性有限自动机(NFA)的相关概念。" 在编译原理中，消除左递归是构建解析器时的关键步骤，因为左递归可能导致无限循环，使得解析过程无法正常完成。扩展的巴克斯范式(EBNF)是一种扩展的语法表示形式，它通过引入{}和{x}mn来增强基本的巴克斯范式(BNF)。例如，"{<字母>|<数字>}07"表示字母或数字可以重复0到7次，这有助于明确表示标识符的长度限制。 文法的分类包括0型文法(短语文法，PSG)、1型文法(上下文有关文法，CSG)、2型文法(上下文无关文法，CFG)和3型文法(正规文法，RG)。其中，2型文法是最常用的一种，它在编程语言的语法描述中扮演重要角色。文法的最左推导和最右推导是理解文法结构和解析过程的重要概念，它们用于从文法的开始符号生成句子或者从句子归约为开始符号。 对于消除左递归，通常采用直接左递归和间接左递归的处理方法。例如，直接左递归如 `<无符号整数> -> <数字><无符号整数>` 可以改写为非左递归的形式，如 `<无符号整数> -> <数字><非零无符号整数>|<数字>`，然后定义 `<非零无符号整数>` 为 `<数字><非零无符号整数>|ε`。这种方法避免了解析过程中无限递归的情况。 在分析方法上，自上而下分析（如LL解析）是从文法的开始符号开始，尝试匹配输入符号，构建语法树；而自下而上分析（如LR解析）则是从输入符号开始，通过归约操作逐步向文法的开始符号靠近。这两种方法各有优缺点，适用于不同类型的文法和解析需求。 此外，DFA和NFA是形式语言理论中的重要概念，它们用于识别正规语言。DFA是每个状态都只有一个出边的有限自动机，而NFA则允许一个状态有多条出边，对于语言的识别能力更为强大，但可能需要更多的计算资源。 复习提纲中还提到了二义性文法和语言，这是指一个文法或语言可以有多种解释或推导路径，导致解析不唯一。二义性是文法设计中需要避免的问题，因为它会导致编译错误或不易理解的程序行为。通过调整文法结构，可以设计出无二义的等价文法，以确保解析的唯一性。 编译原理的学习涵盖了语言的语法结构、解析策略、自动机理论等多个方面，这些知识是理解和构建编译器的基础。通过深入理解和实践这些概念，可以更好地设计和实现编程语言的编译器或解释器。