您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 编译原理课程设计-LL1文法分析器设计C++语言实现
集美大学计算机工程学院编译原理课程设计报告选题名称:LL(1)文法分析院(系):计算机工程学院专业:计算机科学与技术班级:计算1412指导教师:付永刚学年学期:2016~2017学年第2学期2017年06月29日摘要:选题要求:根据某一文法编制调试LL(1)文法语法分分析程序,以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下:1、对语法规则有明确的定义;2、编写的分析程序能够对给定文法进行正确的语法分析;3、对输入给定的文法,手工计算FIRST、FOLLOW集合和select集合,应能判断识别是否为给定文法的句子,并给出推导过程。4、对输入给定的文法,由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺利完成语法分析过程。关键词:语法分析;FIRST集合;FOLLOW集合;分析表一、设计内容及要求(1)基于PL/0语言,通过编程判断该文法是否为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有推导AA…,则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。●直接左递归若文法中的某一产生式形如A→Aα,α∈V*,则称该文法是直接左递归的。消除直接左递归的方法:设有产生式是关于非终结符A的直接左递归:A→Aα|β(α,β∈V*,且β不以A开头)对A引入一个新的非终结符A′,把上式改写为:A→βA′A′→αA′|ε●间接左递归若文法中存在某一非终结符A,使得AA…至少需要两步推导,则称该文法是间接左递归的。消除间接左递归的方法:【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法:设有文法G10[S]:S→Aα|β⑴A→Sγ⑵因为SAα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)={X}(3)若X∈VN,且有产生式X→ε,则First(X)={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.预测分析方法预测分析方法是自顶向下分析的另一种方法,一个预测分析器是由三个部分组成:预测分析程序;先进后出栈;预测分析表。预测分析程序的框图如下:目录1系统分析...........................................................................................................................................................11.1选题要求...................................................................................................................................................11.2预期目标...................................................................................................................................................12.程序流程图......................................................................................................................................................12.1总流程图...................................................................................................................................................12.2FIRST集和FOLLOW集..............................................................................................................................22.3预测分析表流程......................................................................................................................................33.代码编写..........................................................................................................................................................33.1检查左递归...............................................................................................................................................33.2FIRST集合...................................................................................................................................................53.3FOLLOW集合.............................................................................................................................................63.4分析表输出...............................................................................................................................................84.程序调试.......................................................................................................................................................105.总结................................................................................................................................................................116.指导教师评语...............................................................................................................................................127.源码................................................................................................................................................................13正文:1.系统分析1.1选题要求根据某一文法编制调试LL(1)文法语法分分析程序,以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。1.2预期目标构造LL(1)文法语法分析程序,任意输入一个文法符号串,并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表,并按照预测分析算法对输入串进行语法分析,判别程序是否符合已知的语法规则,如果不符合(编译出错),则输出错误信息。2.程序流程图2.1.总流程图2.2.First集和Follow集的流程图2.3.预测分析表流程:3.代码编写3.1检查左递归:Parser&Parser::DelLeft(inti){intn=StrNum(content[i]);charc=RandChar();charz=content[i][0];ints=0;for(intk=1;k=n;k++){stringtmp=GetSub(k,content[i],'|');if(z==tmp[0])s=1;}if(s==0)return*this;cout文法句content[i]含有直接左递归,;while(1){if(Findchar(c,non)==-1)break;elsec=RandChar();}cout随机产生非终结符为:cendl;non.append(1,c);stringtemp;temp+=z;temp+=-;stringnext;next+=c;next+=-;for(intk=1;k=n;k++){stringt=GetSub(k,content[i],'|');if(z==t[0]){t.erase(0,1);t+=c;next+=t;next+='|';}else{if(t==^)t.clear();t+
本文标题:编译原理课程设计-LL1文法分析器设计C++语言实现
链接地址:https://www.777doc.com/doc-4363365 .html