安徽大学编译原理：Chomsky文法类型判断实验详解

实验一主要关注的是Chomsky文法类型判断，这是一种理论框架，由诺姆·乔姆斯基（Noam Chomsky）提出，用于分类不同类型的上下文无关文法（Context-Free Grammar, CFG）。在编程实验中，参与者需要掌握以下四种文法类型： 1. **0型文法（Type-0 grammar, Regular Grammar）** - 这种文法允许产生式左右部由“非终结符”和“终结符”混合构成，但左部不能为空。它的特点是可以通过有限状态机（Finite State Automaton, FSA）来识别。 2. **1型文法（Type-1 grammar, Linear-bounded Context-free Grammar, LBCFG）** - 在0型文法的基础上，要求右部的符号长度必须大于左部（不包括空）。这意味着不是所有可能的终结符序列都能被生成。 3. **2型文法（Type-2 grammar, Context-sensitive Grammar, CSG）** - 2型文法进一步限定左部只能包含一个非终结符，使得语法结构更加明确，生成的语言通常比1型文法更为复杂，但仍属于上下文无关。 4. **3型文法（Type-3 grammar, Unrestricted Grammar, UG）** - 也称为递归正规文法（Recursively Enumerable Grammar, REG），其产生式的形式为A->Aa|a或A->aA|a，这种文法可以描述部分递归语言，比2型文法更为强大，但不能描述所有递归语言。 实验的核心任务是编写一个C语言程序，输入一组文法规则，根据规则判断其属于哪一种Chomsky文法类型。程序中定义了结构体`node`来存储每个规则的信息，并使用计数器`t0`, `t1`, `t2`, 和 `t3` 分别记录0型、1型、2型和3型文法的规则数量。通过遍历输入的文法规则，检查它们是否满足特定类型的条件，如左部为空、右部长度、非终结符的存在等，最终输出对应类型的计数。 例如，在输入的文法表达式中，通过查找"->"符号来确定产生式的分隔，然后分析左部和右部的特性，判断是哪种文法类型。如果遇到"3型文法"特有的递归模式，如"A->Aa|a"，需要额外检查以确认它是真正的3型文法，而不是其他形式的规则。 总结来说，这个实验着重于理解文法类型的概念，以及如何在实际编程中实现对这些类型的识别和分类，这对于理解编译原理和语言理论有重要意义。通过实践，学生不仅加深了对理论的理解，还提高了编程技能。