安徽大学编译原理实验：左递归消除实例

本篇文档是安徽大学编译原理课程的实验报告，主题聚焦于消除文法左递归。实验日期为2012年4月27日，目标是帮助学生深入理解上下文无关文法（Context-Free Grammar, CFG）的概念及其与其它文法类型的区别，以及如何识别和处理左递归问题。 实验内容主要包括以下几个关键部分： 1. **上下文无关文法的理解**：学生被要求掌握上下文无关文法的定义，这种文法的特点是产生式中的变量在右边可以被任意长度的词项替换，但不能包含变量本身在左侧直接或间接地出现。这是与递归无关的关键特性。 2. **文法类型判断与举例**：学生需要熟练运用所学知识，判断给定的文法是否为上下文无关文法，并能根据要求编写相应的文法实例。 3. **左递归检测与消除**：实验的核心任务之一是识别是否存在左递归，即非终结符A在产生式A -> αAβ中直接或通过其他产生式间接地出现在A的直接左边。消除左递归的方法包括直接左递归消除（通过规范化变换，如Yacc算法）和间接左递归消除（通常涉及构造新的非终结符来代替原始递归链）。 **程序代码示例**： 在提供的代码片段中，名为`killzdg.cpp`的程序用于消除左递归，作者是杨向东宇，学号E10914012。代码中定义了`grammar`类，包含生产规则（`production`）、符号索引（`symbolidx`和`symboltable`）、标记符号（`symbolmark`）等数据结构。`addSymbol`函数用于添加新符号，并在后续处理左递归时可能被调用。 消除左递归的过程涉及以下几个步骤： - 初始化变量如`symbnum`和`genint`，用于存储符号数量和生成器的整数值。 - 使用`multimap`存储生产规则，其中键是非终结符，值是词项串。 - 通过`symbolidx`映射非终结符到索引，`symboltable`反向映射索引到非终结符，`symbolmark`用于标记已处理过的符号。 消除左递归的具体实现细节未在给定部分提供，但通常会利用算法如LR（Left-to-right）或LL（Leftmost derivation）分析，将原左递归形式转换为无左递归的新文法，或者通过替换技术（如Yacc的`reduce/reduce`冲突解决机制）来确保解析的有效性。 本实验通过实际操作加深了学生对上下文无关文法和左递归处理的理解，锻炼了编程技能，并有助于他们在编译原理的实际应用中处理语法分析问题。