压缩文法的等价变换与多余规则删除

"这篇文档是欧阳蕊同学关于编译原理实验二——压缩文法的等价变换的课程报告。实验目标是理解并实现如何识别和删除文法中的多余规则，以便压缩文法。报告详细介绍了实验原理、内容及实现方法，并对难点进行了小结。" 在编译原理中，文法的压缩是一个重要的概念，特别是对于上下文无关文法（2型文法）的优化。实验中提到的“多余规则”是指那些在任何句子推导过程中都不会被使用的规则。这类规则分为两种类型：不可到达型和不可终止型。不可到达型是非终结符从未出现在任何规则的右部，因此在推导过程中无法触及；而不可终止型是指非终结符无法推导出终结符号串，即它们无法直接或间接产生语言的任何部分。 实验中采用Java语言实现了一个程序，用于判断和删除这些多余规则。程序的核心在于动态数组，用于存储输入的非终结符、终结符和规则。在处理过程中，首先找出可到达的和可终止的非终结符，然后通过排除法确定不可到达和不可终止的非终结符，从而找到并移除多余规则。实现这一过程时，对于可终止非终结符的判断尤为复杂，需要使用嵌套的循环和条件语句，通过对非终结符是否能直接或间接推导出终结符号来判断其可终止性。 实验小结部分，作者指出判断可到达非终结符相对简单，而判断可终止非终结符则更为复杂，因为这涉及到多层递归和逻辑推理。在这个过程中，作者可能采用了递归或迭代的方式来遍历文法规则，确保所有可能的推导路径都被考虑。 这个实验不仅帮助学生深入理解了文法压缩的原理，还锻炼了他们将理论知识转化为实际代码的能力，对于编译器设计和实现有着重要的实践意义。通过这样的实验，可以更好地掌握编译原理中的关键概念，为将来构建更高效、更精简的编译器打下坚实基础。