3编译原理课程

淮阴工学院编译原理课程设计指导书江苏·淮阴工学院·计算机工程系二OO八年二月前言《编译原理》是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。本指导书在全面把握教学大纲及教材精神的基础上，共设计了6个题目，不是用一个独立的例子涵盖这些知识点，而是按层次逐步深入。为了使学生理解它们之间如何相互配合，设计要求使用接近实际需要的方式编程。重点放在编译程序的基本特征上，结合实际应用，通过详细的实例，循序渐进地启发学生完成设计。课程设计比教学实验复杂，涉及的深度较广，并更加实用。目的是通过课程设计的综合训练，培养学生实际分析问题、编程和动手能力。最终目标是通过课程设计的形式，帮助学生系统地掌握该门课程的主要内容，更好地完成教学任务。书中给出的实例概念清楚，体系完整，内容丰富，采用循序渐进的方式，提高学生实际动手能力，完成“知识+实践=技能”的整个学习过程。目录前言2选题一有穷自动机的化简与确定化4选题二LL（1）语法分析5选题三算符优先分析法7选题四LR(0)语法分析8选题五SLR(1)语法分析9选题六逆波兰式的生成10附录AVISUALC++6.0简介12附录BC/C++常用函数27附录C课程设计操作规程62附录D文档要求与规范65选题一有穷自动机的化简与确定化一、设计内容及要求1.可以使用任何语言来完成，例如：C、C++。2.以文件方式读取自动机。3.判断读取的自动机是确定的还是不确定的自动机。4.若是不确定的自动机，将自动机确定化。5.将确定化后的自动机最小化。6.输入测试字符串，输出测试结果二、实现原理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的最小划分，然后从各个等价子集中选取一个代表状态，消去各等价子集中的非代表状态，这样就实现了DFA的最小化的目的。主要步骤：forv(q,p)∈F×(Q-F)do标记可区分状态表中的表项(q,p);/*p和q不可合并*/forv(q,p)∈F×F∪(Q-F)×(Q-F)且q≠pdoifEa∈∑，可区分状态表中的表项(δ(q,a),δ(p,a))已被标记thenbegin标记可区分状态表中的表项(q,p);递归的标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项。endelseforva∈∑doifδ(q,a)≠δ(p,a)且与(q,p)与(δ(q,a),δ(p,a))不是同一个状态对then将(q,p)放在(δ(q,a),δ(p,a))的关联链表上。选题二LL（1）语法分析一、设计内容及要求(1)一切LL(1)文法；含有直接左递归但可以转化为LL(1)文法的文法；含有间接左递归但可以转化为LL(1)文法的文法(2)计算出文法的First()Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a)∩SELECT(A:=b)=Ø。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AA…，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα|β（α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A→βA′A′→αA′|ε●间接左递归若文法中存在某一非终结符A，使得AA…至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法G10[S]：S→Aα|β⑴A→Sγ⑵因为SAαSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：S→Sγα|β⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′|ε2.计算First集(1)若X∈VT，则First(X)={X}(2)若X∈VN，且有产生式X→a…,a∈VT则First(X)={a}(3)若X∈VN，且有产生式X→ε,则First(X)={ε}(4)若X，Y1，Y2，…，Yn都∈VN，而由产生式X→Y1Y2…Yn。当Y1，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(β)的非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；(3)反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4.预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：选题三算符优先分析法一、实验内容与要求已知文法：E→E+T∣E–T∣TT→T*F∣T/F∣FF→(E)∣i(E)∣i∣d（其中d表示0-9的数字，i表示字母，大小写均包含）根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。(1)可以使用任何语言来完成，例如：Java、C++。(2)构造此文法的分析过程(3)输入测试字符串，输出测试结果二、实验原理1.算符优先分析算法算法原理（1）初始化栈：k=1;S[k]=‘#’；（2）依次从输入串中读入符号a：①当前单词若为标识符，则a值为i，若为常数则a值为d；其它a直接取单词值。②若a大于等于栈顶第一个终结符的优先级，则a进栈；③若a小于栈顶第一个终结符的优先级，则重复做：i)找出最左子串S[j]S[j-1]=…=S[k]a；ii)把S[j-1]…S[k]归约为某个N；iii)将归约后的非终结符N入栈；④出错处理。若输入串扫描完毕，且栈中呈现#S，且a为#，则符合语法要求，否则就不符合语法要求。选题四LR(0)语法分析一、实验内容与要求（1）录入合法的LR(0)文法，（2）将输出LR(0)分析表，（3）可以对输入的句子进行语法分析。二、实验原理1.LR分析表的构造（1）若A→·a∈Ik，且GO(Ik,a)=Ij(a∈VT)，则置ACTION[k,a]=sj；（2）若A→·∈Ik，则对任意终结符a（包括#）置ACTION[k,a]=rj（j为产生式A→的编号）；（3）若项目S'→S·∈Ik，则置ACTION[k,#]=acc；（4）若GO(Ik,A)=Ij(A∈VN)，则置GOTO[k,A]=j；（5）不能用上述方法填入内容的单元均置为“出错标志”（用空白表示）。2.LR分析算法描述将S0移进状态栈，#移进符号栈，S为状态栈栈顶状态a=getsym()//读入第一个符号给awhile(ACTION[S,a]!=acc){ifACTION[S,a]=Si{PUSHi,a(分别进栈);a=getsym();//读入下一个符号给a}elseifACTION[S,a]=rj(第j条产生式为A→β){将状态栈和符号栈分别弹出|β|项;push(A);将GOTO[S’,A]移进状态栈（S’为当前栈顶状态）;}elseerror();}选题五SLR(1)语法分析一、实验内容与要求已知控制语句、算术表达式、布尔表达式的文法如下：2.算术表达式1）EE+E2）EE*E3）E(E)4）Ei（1）构造相应文法的SLR分析表，（2）构造相应的符合以上三种文法的简单代码段（3）可以对此代码段进行SLR语法分析。二、实验原理SLR（1）分析法的引入是当文法的LR(0)项目集规范族中存在移进-归约冲突或归约-归约冲突时，可以通过向前查看一个符号的办法来进行处理，以解决冲突。SLR（1）分析法与LR（0）分析法的不同主要是在于分析表的构造上，而分析算法上相同1.SLR（1）分析表的构造（1）若A→·a∈Ik，且GO(Ik,a)=Ij，a∈VT，则置ACTION[k,a]=sj；（2）若A→·∈Ik，则对任何终结符a（包括#），且满足a∈FOLLOW(A)时，置ACTION[k,a]=rj（j为产生式A→的编号）；（3）若项目S'→S·属于Ik，则置ACTION[k,#]=acc；（4）若GO(Ik,A)=Ij(A∈VN)，则置GOTO[k,A]=j；（5）不能用上述方法填入内容的单元均置为“出错标志”（用空白表示）。选题六逆波兰式的生成一、实验内容与要求已知文法如下：ESSSorBSBBBandCBCCnotCC(S)CidC(idrelopid)（1）录入合法的SLR(1)文法；（2）构造SLR(1)分析表；（3）对输入的句子进行SLR语法分析；（4）对经过SLR语法分析正确的句子构造相应的逆波兰式。二、实验原理SLR分析方法同上；1.逆波兰式构造的一般步骤：从左到右扫描后缀表达式各个符号，每碰到运算对象时就把它推进栈，每碰到一个K元运算符时，就取出栈顶的K个运算对象进行相应的运算，并且用运算结果去替换栈顶的K个运算对象，然后再继续扫描表达式中余留符号,如此等等，直到整个表达式计算完毕为止。当上述过程结束后，整个表达式之值将留于栈顶。运算符进栈运算符栈退栈波兰表示运算对象表达式比栈顶高进栈，比栈顶低或相同的退栈附录AVisualC++6.0简介考虑到目前大多数初学者使用的都是PC机和Windows操作系统，我们以VisualC++作为推荐的C++编译器。A.1VisualC++集成开发环境VisualC++软件包包含了许多独立的组件，如编辑器、编译器、调试器，以及各种各样为开发Windows环境下的C/C++程序而设计的工具。其