LL1文法判定系统设计与实现

"LL 1 课程设计是一个项目，旨在开发一个系统，用于判定输入的文法是否符合LL(1)规范。系统采用图形界面，用户可以输入文法，然后系统会判断文法是否为2型文法。如果是2型文法，系统会找出所有能推导出空符号串的非终结符，并计算每个非终结符的FIRST集和FOLLOW集，最终确定文法是否满足LL(1)条件。这个设计旨在增强学生的软件工程、面向对象编程实践，同时提高他们的问题解决能力和综合应用技能。" 在这个项目中，涉及的知识点包括： 1. **LL(1)文法**：LL(1)是一种自左至右的解析方法，其中“L”表示从左到右扫描输入，“L”也代表Left-to-right，“1”表示只看一个输入符号进行预测。LL(1)文法是一种上下文无关文法，解析表中每个非终结符在每个输入符号下只有一个动作，这确保了解析的唯一性。 2. **文法类型**：系统需判定输入的文法是否为2型文法，即是否是上下文无关文法。2型文法是Chomsky分类中的类型-2文法，它可以生成所有可计算语言。 3. **非终结符和空符号串**：非终结符是文法中的符号，代表更复杂的结构，系统需要找出所有能推导出空符号串（ε）的非终结符。 4. **FIRST集和FOLLOW集**： - **FIRST集**：对于文法中的每个产生式，FIRST集包含所有可能出现在该产生式起始位置的符号，包括终结符和非终结符，以及如果起始符号能推导出ε，则ε也在其中。 - **FOLLOW集**：对于文法中的每个非终结符，FOLLOW集包含所有可能出现在该非终结符后面的终结符，根据文法规则，这些终结符可以在解析过程中出现在非终结符的后面。 5. **预测分析表**：这是LL(1)解析器的核心，用于指导解析过程。表中的每个单元格记录了对于某个非终结符和当前输入符号，解析器应该采取的动作（通常是转移到下一个非终结符或产生输出）。 6. **程序设计**： - **menu()** 函数设计人机交互界面，提供选择不同功能的菜单。 - **Ch()** 函数获取非终结符之外的输入符号。 - **merge()** 函数合并符号串，处理ε操作。 - **recur()** 和 **non_re()** 分别用于处理和分解含左递归和不含左递归的产生式。 - **judge()** 判断文法的正确性。 - **syntax()** 检查输入串是否满足文法。 - **chargrammar()** 读取文法的定义。 - **FOLLOW()** 计算非终结符的FOLLOW集。 - **first2()** 计算单个符号的FIRST集。 - **FIRST()** 计算产生式右部的FIRST集。 - **ll1()** 判定文法是否为LL(1)文法。 7. **面向对象编程**：整个系统的设计和实现体现了面向对象的思想，每个函数都对应一个特定的职责，如类的方法，实现了模块化和可重用性。 8. **软件工程**：项目实施遵循软件工程的原则，包括需求分析、设计、编码、测试和维护，以确保软件质量。 通过这个项目，学生不仅能学习到理论知识，还能提升编程技能，增强实际问题解决能力，符合计算机科学与技术本科专业的培养目标。