淮阴工学院编译原理课程设计指导书王文豪江苏·淮阴工学院·计算机工程系二OO九年三月前言《编译原理》是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。本指导书在全面把握教学大纲及教材精神的基础上，共设计了6个题目，不是用一个独立的例子涵盖这些知识点，而是按层次逐步深入。为了使学生理解它们之间如何相互配合，设计要求使用接近实际需要的方式编程。重点放在编译程序的基本特征上，结合实际应用，通过详细的实例，循序渐进地启发学生完成设计。课程设计比教学实验复杂，涉及的深度较广，并更加实用。目的是通过课程设计的综合训练，培养学生实际分析问题、编程和动手能力。最终目标是通过课程设计的形式，帮助学生系统地掌握该门课程的主要内容，更好地完成教学任务。书中给出的实例概念清楚，体系完整，内容丰富，采用循序渐进的方式，提高学生实际动手能力，完成“知识+实践=技能”的整个学习过程。目录TOC\o"1-1"\h\zHYPERLINK\l"_Toc196974440"前言PAGEREF_Toc196974440\h2HYPERLINK\l"_Toc196974441"选题一有穷自动机的化简与确定化PAGEREF_Toc196974441\h4HYPERLINK\l"_Toc196974442"选题二LL（1）语法分析PAGEREF_Toc196974442\h5HYPERLINK\l"_Toc196974443"选题三算符优先分析法PAGEREF_Toc196974443\h7HYPERLINK\l"_Toc196974444"选题四LR(0)语法分析PAGEREF_Toc196974444\h8HYPERLINK\l"_Toc196974445"选题五SLR(1)语法分析PAGEREF_Toc196974445\h9HYPERLINK\l"_Toc196974446"选题六逆波兰式的生成PAGEREF_Toc196974446\h10HYPERLINK\l"_Toc196974447"附录AVisualC++6.0简介PAGEREF_Toc196974447\h11HYPERLINK\l"_Toc196974448"附录BC/C++常用函数PAGEREF_Toc196974448\h26HYPERLINK\l"_Toc196974449"附录C课程设计操作规程PAGEREF_Toc196974449\h61HYPERLINK\l"_Toc196974450"附录D文档要求与规范PAGEREF_Toc196974450\h64选题一有穷自动机的化简与确定化一、设计内容及要求可以使用任何语言来完成，例如：C、C++。以文件方式读取自动机。判断读取的自动机是确定的还是不确定的自动机。若是不确定的自动机，将自动机确定化。将确定化后的自动机最小化。输入测试字符串，输出测试结果二、实现原理1.确定化（子集法）(1)置Q’,F’为空集；(2)令q0’=[ε_CLOSURE({q0})],并把[q0]置为未标记后加入到Q’中；(3)如果Q’中存在未标记状态[q1,q2,…,qi],则对每个a∈∑定义：d‘([q1,q2,…qi],a)=[p1,p2,…,pj]当且仅当d({q1,q2,…qi},a)={r1,r2,…,rk},ε_CLOSURE({r1,r2,…,rk})={p1,p2,…,pj}。如果[p1,p2,…,pj]不在Q’中，则把它置为未标记后加入到Q’中；如果p1,p2,…,pj中至少有一个是M的终态，则同时把[p1,p2,…,pj]加入到F’中；然后给Q’中的状态[q1,q2,…,qi]加上标记；(4)重复执行3，直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止；(5)重新命名Q’中的状态，然后获得等价的DFAM’2.DFA的最小化利用等价关系找出状态集Q上的所有最大等价状态子集，即找出Q的最小划分