编译原理课程设计指导书

《编译原理课程设计指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机工程学院编译原理课程设计指导书付永钢集美大学计算机工程学院计算机科学与技术教研室二O一四年六月前言《编译原理》是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设

2、计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。本指导书在全面把握教学大纲及教材精神的基础上，共设计了4个题目，不是用一个独立的例子涵盖这些知识点，而是按层次逐步深入。为了使学生理解它们之间如何相互配合，设计要求使用接近实际需要的方式编程。重点放在编译程序的基本特征上，结合实际应用，通过详细的实例，循序渐进地启发学生完成设计。课程设计比教学实验复杂，涉及的深度较广，并更加实用。目的是通过课程设计的综合训练，培养学生实际分析问题、编程和动手能力。最终目标是通过课程设计的形式，帮助学生系统地掌握该门课

3、程的主要内容，更好地完成教学任务。书中给出的实例概念清楚，体系完整，内容丰富，采用循序渐进的方式，提高学生实际动手能力，完成“知识+实践=技能”的整个学习过程。目录前言2选题一LL（1）语法分析4选题二LR(1)语法分析6选题三SLR(1)语法分析7选题四PL/0语言及其编译器的改进8附录AVISUALC++6.0简介13附录BC/C++常用函数28附录C课程设计操作规程63附录D文档要求与规范66选题一LL（1）语法分析器的设计与开发一、设计内容及要求(1)基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First(

4、)、Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a)∩SELECT(A:=b)=Ø。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AÞ

5、A…，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα

6、β（α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A→βA′A′→αA′

7、ε●间接左递归若文法中存在某一非终结符A，使得AÞA…至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法G10[S]：S→Aα

8、β⑴

9、A→Sγ⑵因为SÞAαÞSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：S→Sγα

10、β⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′

11、ε2.计算First集(1)若X∈VT，则First(X)={X}(2)若X∈VN，且有产生式X→a…,a∈VT则First(X)={X}(3)若X∈VN，且有产生式X→ε,则First(X)={X}(4)若X，Y1，Y2，…，Yn都∈VN，而由产生式X→Y1Y2…Yn。当Y1，

12、Y2，…，Yi-1都能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε},First(Y2)-{ε},…,First(Yi)都包含在First(X)中(5)当(4)中所有Yi都能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}反复使用上述步骤直到每个符合的First集合不再增大为止。3.计算Follow集对文法中的每个A∈VN，计算Follw(A)：(1)设S为文法的开始符合，把{#}加入Follow(S)中；(2)若A→αBβ是一个产生式，则把First(β)的

13、非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；(3)反复使用以上步骤直到每个非终结符号的Fo