合工大编译原理课程设计报告：《集合 LASTVT(P)构造算法的程序实现》

合工大编译原理课程设计报告 设计题目：《集合 LASTVT(P)构造算法的程序实现》 学生姓名：XXX 学号：XXX 专业班级：计算机科学与技术 20 指导教师：李宏芒 完成日期：2022.6.20 编译原理课程设计报告 一、设计目的及设计要求 题目要求设计一个程序，实现教材 P.91 中的 LASTVT(P) 集合的构造算法。对于任一给定的算符文法 G，程序需要输出所有非终结符 P 的 LASTVT(P)。为了增加任务量，本设计还扩展了求解 FIRSTVT(P) 的功能。 二、开发环境描述 开发语言：C 软件：CodeBlocks 20.03 三、设计内容、主要算法描述 在设计程序之前，我们先回顾一下课堂上学过的求解 LASTVT 的三个方法： 1. 若有 T→…a 或 a∈LASTVT(T)； 2. T→…aR，则 a∈LASTVT(T)； 3. 若 a∈LASTVT(R)，且有产生式 T→…R，则 a∈LASTVT(T)； 基于以上三条规则，我们设计了以下主要算法： 1. 首先，读入算符文法 G，并初始化一个集合表 LASTVT，用于储存所有非终结符 P 的 LASTVT(P)。 2. 遍历每一个产生式 P→αR（其中 R 可以为空），根据规则2和规则3将产生式右部的符号的 FIRSTVT 或 LASTVT 加入到 LASTVT(P) 中。如果右部为空，则将 FOLLOWVT(P) 加入到 LASTVT(P) 中。 3. 重复上述步骤，直到所有产生式都被遍历过并且没有新的非终结符的 LASTVT(P) 需要更新。 扩展内容：在构造 LASTVT(P) 的基础上，我们还实现了求解 FIRSTVT(P) 的功能。算法与构造 LASTVT(P) 的算法类似，只是规则的应用稍有不同。具体步骤如下： 1. 初始化一个集合表 FIRSTVT，用于储存所有非终结符 P 的 FIRSTVT(P)。 2. 遍历每一个产生式 P→αR（其中 R 可以为空），根据规则1和规则3将产生式右部的符号的 FIRSTVT 或 LASTVT 加入到 FIRSTVT(P) 中。如果右部为空，则将 FOLLOWVT(P) 加入到 FIRSTVT(P) 中。 3. 重复上述步骤，直到所有产生式都被遍历过并且没有新的非终结符的 FIRSTVT(P) 需要更新。 四、程序代码实现 在程序代码实现中，我们利用 C 语言的数据结构和算法来实现上述算法。具体的代码实现可以参考附件中提供的完整代码。 五、测试结果及分析 我们针对不同的算符文法进行了测试，并输出了每个非终结符的 LASTVT 和 FIRSTVT。通过对比测试结果和理论预期，可以验证我们的程序实现的正确性。 六、总结 通过本次课程设计，我们成功实现了《集合 LASTVT(P)构造算法的程序实现》这一题目要求，并进一步在程序中添加了求解 FIRSTVT(P) 的功能。通过这个设计，我们巩固了课堂学习的知识，加深了对算符文法和相关算法的理解。 在实践过程中，我们发现算符文法的集合 LASTVT(P) 和 FIRSTVT(P) 的构造算法是有一定规律可循的，可以通过合理的规则和迭代操作来实现。这不仅有助于加深对编译原理知识的理解，还可以为实际的编译器设计提供一定的参考和思路。 通过这次课程设计，我们不仅获得了编译原理知识的实际运用经验，也提升了编程能力和问题解决能力。希望在以后的学习和实践中，能够继续提升自己的编程技能，为实际的软件开发和编译器设计做出更多的贡献。