中山大学编译器构造实验：压缩与删除文法规则

"中山大学数据科学与计算机学院的本科生实验报告，主要涉及编译器构造课程，由陈炬桦老师授课。实验内容包括输入文法的压缩，自产生式文法的识别与删除，以及不可达文法的处理。报告提供了输入格式、输出格式以及算法流程，并附有测试数据和程序代码示例。" 该实验报告的核心知识点集中在编译器构造中的文法处理，具体包括以下几个方面： 1. **文法与产生式**：文法是描述编程语言结构的形式化系统，由一组产生式构成。产生式定义了非终结符如何转换为终结符或其它非终结符的规则。在实验中，用户需要输入开始符号、非终结符、终结符及一系列产生式。 2. **自产生式文法**：如果一个非终结符可以通过自身直接或间接地推导出自身，那么这个非终结符参与的产生式就是自产生式。自产生式文法可能导致无限循环，在编译器设计中需要被识别和处理。 3. **不可达文法和非终结符**：在给定的文法中，如果某个非终结符无法通过任何产生式推导到句子（即最终只包含终结符的序列），则称该非终结符为不可达。这样的非终结符和它们相关的产生式对解析过程无用，可以被删除以简化文法。 4. **算法描述**：报告中提到的算法主要包括读取和存储输入数据，遍历产生式以识别并删除自产生式，找出并删除不可达非终结符及其相关产生式，最后删除所有不可达非终结符并输出压缩后的文法。 5. **可达性判断**：`reachable`函数用于判断一个非终结符是否可以通过产生式达到，这是识别自产生式和不可达非终结符的关键步骤。 6. **不可达状态检查**：`is_unreached`函数检查非终结符是否在已知的不可达非终结符列表中，辅助进行不可达文法的识别。 7. **流程图**：虽然实际流程图未给出，但通常流程图会展示算法执行的逻辑顺序，帮助理解代码的运行过程。 8. **程序代码**：报告中给出了部分C++代码，包括结构体定义（如VN、VT和PS用于存储非终结符、终结符和产生式信息）和关键函数实现（如`reachable`和`is_unreached`），这展示了实际问题的解决方法。 9. **测试数据**：提供测试数据用于验证算法的正确性，确保程序能正确处理各种情况的输入。 通过这个实验，学生可以深入理解编译器构造中的文法压缩技术，提高对自产生式和不可达文法的理解，同时锻炼了编写程序解决问题的能力。