北京邮电大学软件学院编译原理实验：语法分析与LR分析程序设计

本篇实验报告是北京邮电大学软件学院2016-2017学年第一学期编译原理课程的一部分，由学生肖逸敏（学号2014211990）独立完成。实验的核心内容是设计和实现一个语法分析程序，针对一种算法表达式的文法进行解析。该文法规定了算术表达式的结构，包括E（表达式）、T（项）和F（因子）的生成规则，如E可以转化为E+T、E-T等，T可以转化为T*F、T/F，F可以是标识符、圆括号包围的表达式或数字。 实验的主要目标是： 1. **构造DFA**：实现自底向上的分析，首先需要构建一个确定有限自动机（DFA），识别所有可能的活前缀，即输入字符串的子串，这些子串在文法中具有特定的含义。 2. **LR分析表**：接下来，学生需构造LR分析表，这是基于 LR（Left-to-right）分析方法，用于解析上下文无关文法的一种技术，它帮助确定在处理输入时的状态转移和动作。 3. **编程实现LR分析程序**：根据算法4.3的描述，肖逸敏需要编写代码实现LR分析器，这涉及到状态机的设计和执行，以正确地处理输入表达式。 实验环境中，学生使用了Visual Studio 2013作为开发工具。实验结果显示，肖逸敏已经完成了识别所有活前缀的DFA构造，以及LR分析表的创建。他还提供了代码片段，展示了如何使用栈数据结构处理文法的产生式，以及如何通过布尔变量is_stick判断非状态元素，并根据文法动态构建新的状态。 报告附录部分包含了实验的深入细节： - **采用的LR文法**：展示了整个文法规则集，包括S（start符号）、E、T和F的各个分支。 - **预测分析表**：通常是一个二维数组，用于存储在特定状态下读取下一个输入符号时的动作和可能进入的新状态。 - **栈操作细节**：展示了如何处理括号和非终结符的特殊情况，如遇到'('时，可能需要检查是否匹配')'，同时维护栈中的状态。 这个实验着重于理论与实践的结合，让学生理解并运用编译原理中的DFA和LR分析技术，对算法表达式进行有效的语法分析。通过这个过程，学生不仅提升了编程技能，还加深了对编译器构造原理的理解。