Chomsky文法类型判断与左递归消除

"Chomsky文法类型判断及消除文法的左递归" 这段代码是用于处理Chomsky文法的程序，目的是判断输入的文法规则属于哪种类型的Chomsky文法，并消除文法中的左递归。Chomsky文法是一种形式语言理论，由美国语言学家诺姆·乔姆斯基提出，它将文法分为四种类型，分别是0型文法（无限制文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）和3型文法（正则文法）。 在程序中，首先定义了一些常量和结构体，如MAXS表示最大符号数，NONE和RELEFT用于标记判断结果，STR结构体用于存储文法规则的左右两侧字符串。接下来的函数包括： 1. `print` 函数：用于打印四元组形式的文法，即文法的非终结符集、终结符集、产生式集合以及起始符号。 2. `VNVT` 函数：计算非终结符集（VN）和终结符集（VT）。遍历所有产生式，将非终结符和终结符分别添加到对应的集合中。 3. `useless` 函数：删除无用的产生式。通过检查非终结符是否在任何产生式的右部出现，如果未出现，则该产生式被视为无用并被删除。 4. `getnew` 函数：生成新的非终结符，当需要新非终结符时，会找到当前未在非终结符集中出现的字符。 5. `releft` 函数：消除直接左递归。如果一个产生式的左部和右部的第一个符号相同，那么这个产生式是直接左递归的，可以通过引入新非终结符来消除。 6. `rreleft` 函数：消除间接左递归。首先检查是否存在间接左递归，然后通过替换产生式的方式逐步消除。 7. `zero` 和 `one` 函数：分别用于判断输入的文法是否为0型文法（无限制文法）和1型文法（上下文有关文法）。0型文法不允许有空的左部，而1型文法要求所有产生式的右部长度至少等于其左部长度。 整个程序的工作流程是先计算VN和VT，然后检查并消除左递归，最后根据文法规则的特点判断其类型。这个程序对于理解Chomsky文法的性质和消除左递归的技术具有一定的参考价值。