编译原理课程设计LL(1)语法分析器的构造.doc

安 徽 工 程 科 技 学 院 设 计 专 用 纸ll(1)语法分析器的构造摘 要语法分析的主要任务是接收词法分析程序识别出来的单词符由某种号串，判断它们是否语言的文法产生，即判断被识别的符号串是否为某语法部分。 一般语法分析常用自顶向下方法中的ll分析法，采用种方法时，语法分程序将按自左向右的顺序扫描输入的的符号串，并在此过程中产生一个句子的最左推导，即ll是指自左向右扫描，自左向右分析和匹配输入串。经过分析，我们使用vc+作为前端开发工具，在分析语法成分时比较方便直观，更便于操作。运行程序的同时不断修正改进程序，直至的到最优源程序。关 键 字 语法分析 文法 自顶向下分析 ll(1)分析 最左推导abstractgrammatical analysis of the main tasks was to receive lexical analysis procedure to identify the words from a website, string, and judge whether they have a grammar of the language, that is, judging by the series of symbols to identify whether a grammar part. general syntax analysis commonly used top-down methods of ll analysis, using methods, grammar hours will be from the procedures of the order left-to-right scanning input string of symbols, and in the process produced one of the most left the sentence is derived, ll is scanned from left to right, from left to right analysis and matching input strings. after analysis, we use vc + + as a front-end development tool for the analysis of syntax ingredients more convenient visual, more easy to operate. operational procedures at the same time constantly improving procedures, until the source of optimal. key wordsgrammatical analysis grammar top-down analysis ll (1) analysis most left derivation目录摘要.1引言.3第一章 设计目的4第二章 设计的内容和要求5 2.1 设计内容.5 2.2 设计要求.5 2.3 设计实现的功能.5第三章 设计任务的组织和分工.6 3.1 小组的任务分工.6 3.2 本人主要工作.6第四章 系统设计.9 4.1 总体设计.9 4.2 详细设计.9第五章 运行与测试结果.22 5.1 一组测试数据.22 5.2 界面实现情况.23第六章 结论.27课程设计心得.28参考文献29致谢30附录（核心代码清单）.31引言编译器的构造工具是根据用户输入的语言的文法，编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。随着计算机应用范围的扩大，在软件自动生成，文档处理，特定专业的语言等领域，编译器的构造工具这一技术显得越来越重要。一个编译程序在对某个源程序完成了词法分析工作之后，就进入语法分析阶段，分析检查源程序是否是语法上正确的程序，并生成相应的内部中间表示供下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查正是语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子时语法树建立的方式，有自顶向下与自底向上两大类分析技术。本课程设计讨论自顶向下的情况。本次课程设计所做的工作是用vc要建立一个针对ll(1)文法的编译器的编译器。本文既可以以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用ll(1)分析，于是对输入的文件用递归下降的分析方法在内存中建立它的存储结构，然后分别计算所输入的文法的非终结符号是否可以生成空，每个非终结符号的first集合，每个非终结符号的follow集合，以及每个规则的predict集合，接着判断任意一个非终结符号的任意两个规则的predict集的交集是不是都为空，如果是则输入文法可以用递归下降法分析，否则不可以，用户应该对所输入的文法作适当的修改，使其满足ll(1)文法分析的要求，。如果所输入的文法可以用递归下降法分析，生成相应文法的语法分析程序。也可以自行添加文法，本课程设计有根据相应文法自动生成分析表和语法树，并将分析信息和结果保存到一个外部文件中的的功能，能灵活实现语法编译器的相应功能。第一章 设计目的一、通过本次课程设计，加深了我对编译原理这门课程的理解和掌握，是我明白了分析器的原理、构造及其实现方法。基本掌握了ll(1)分析法的原理和使用方法。本次课程设计主要任务是根据ll(1)分析表,求句子的预测分析过程，实现编译器的构造。此次设计需使用电子文档的格式，为加深即将迎来的毕业设计做准备，使我们提前熟悉写毕业设计的基本格式、流程和方法。二、课程设计实践的主要是为巩固我们所学基础专业课程知识、进行编译系统基本技能训练、培养实践动手能力，从而掌握编译系统的基本工作原理、基本方法和基本开发技术，最终达到具有一定的编译系统的实际开发能力有重要意义。概括来说课程设计主要为实现一下目的：1.帮助我们深入理解编译原理的有关理论和巩固编译原理相关知识。2. 巩固我们学习的编译原理、程序设计语言、数据结构等课程的基础知识，训练学生分析和解决编译系统的相关问题的能力，提高学生的综合素质。3. 从软件工程的角度来看，编译原理课程设计是一个很好的实例，可以训练我们软件设计的能力以及编码调试能力。第二章 设计的内容和要求2.1 设计内容1、构造ll(1)分析表2、求句子的预测分析过程2.2 设计要求1、提交一份课程设计电子文档；2、通过该课程设计要学会用消除左递归的方法来使文法满足进行确定自顶向下分析的条件。3、学会用c/c+高级程序设计语言来设计一个ll（1）分析法的语法分析器；4、通过该课程设计，加深对语法分析理论的理解，培养动手实践的能力。2.3 设计实现的功能本次课程设计主要实现语法分析器的构造，该语法分析器能够分析词法分析器的结果，即单词二元式。在输入单词二元式后，能输出分析的结果。第三章 设计任务的组织和分工3.1 小组任务分工学好姓名职务任务组长判断输入表达式id和num的字串是否超过最大长度3.2 本人主要工作我的主要工作是判断ll（1）语法分析器中分析器构造当中的输入表达式中的id(字母)和num(数字)的字串是否超过最大长度。本课程设计共用时一周。第一天领题目，第二天与组员讨论课题，分配任务、查找资料。第三天算法的编写，第四天编码和模块的测试，第五天参与文档的编写。我所有的工作中不是本组中最难的，但是我的工作室确保表达式长度的正确范围，这是整个课程设计中的必不可少的一个关键步骤。我们在网上查了大量资料，也阅读了大量的参考书，但是关于表达式的长度范围的判断都是一笔带过，很笼统，讲的不详细，没有具体讲到方法，所以实现起来有点小困难。表达式长度范围的判断虽不是主要的功能，却也是实现过程中的一个关键。判断输入表达式中id（字母）和num（数字）的字串是否超过最大长度的实现过程：一、 首先定义一些变量和常量(1) 定义整型变量：ip,bp,width(2) 定义字符变量：a(3) 标记flag1,flag2为常量(4) 过长标记为：toolong=false二、 说明(1)、a=strip表示用一维数组存储表达式，当ip=0时，表示为表达式的第一个字符。三、 判断表达式长度的流程图输入一个表达式ip=0;ip+=width;strip!=0&(!toolong)a=strip(a=+ | a=- | a=* | a=/ | a=( | a=) | a=#)?bp=ip;width=0;ip+=width;width=1is_id(a) 否 是flag1=flag2=id,a为字母flag1=flag2=num,a为数字bp+ a=strb;width+接下一页循环 接下一页图 接上一页图 widthidnum_maxlen 否 是is_id(a) 否 toolong=teuea是否为字母否break 是 flag2=idflag=numflag2=otherbp+四、判断字符ch是否为构成id的字母的流程图输入一个表达式(ch = a & ch = a & ch = 0 & ch abc b-ibb c-defgc d-d e-eh f-de g-t假定输入符号串为x=abdet。按自顶向下分析技术，让识别符号s为根结点，试图从它出发向下构造语法树。让一个指针指向第一个输入符号a，并从s向下分支，有语法树如图3-1所示。期望s的子结点符号串与输入符号串相匹配。s的最左第一个子结点为a，与指针指向的输入符号相匹配，因此，指针调整到指向第二个输入符号，让s的第二个子结点b与输入符号串相匹配。由于b是非终结符，从b引出分支。关于b的规则有两个，排除人的因素，先按第一选择做分支消去匹配输入符号串，得到图3-2所示的语法树。b的最左子结点i与指针指向的输入符号b 不匹配，删去所做分支，而按第二选择重做分支去匹配符号串，这时语法树如图3-3所示。现在b的唯一子结点与指针指向的输入符号b正相匹配。让指针调整到指向下一输入符号（b），并让s的第三个子结点c去与其余输入符号（det）进行匹配。既可按c的第一选择de作分支，又可按照第一子结点d做分支，他的子结点正好与指针指向的输入符号串d相匹配，指针右移，并对e做分支。所得语法树如图3-4所示。显然当进行到e的第二子结点h时与指针最终所指向的t不相匹配，d可匹配，但e不匹配，也即c当前选择是错误的，应回头选择其他选择。为此抹去从c所做的这一分支，且指针退回到原来正待与c去匹配的哪个输入符号（d）的位置，这正是试探c的选择时的初始位置。现在c的第二选择fg从c从做分支。类似与前述步骤，重新让c的各子结点去与输入符号串的其他部分（det）相匹配，最终可画出如图3-5所示的语法树。f的两个子结点与输入符号d 和e相匹配，而g的子结点与其余的唯一输入符号t相匹配，因此，c完成了与输入符号串的其余部分det的匹配。这时发现指针已指向最右输入符号，s也再无子结点，所以完成了输入符号串x的语法树的构造，表明x是文法gs的句子。sabc图3-1 字符串语法树sabcib图3-2 分支消去匹配符号串语法树sbcba 图3-3 第二选择语法树scbabdedeh图3-4 对e做分支语法树 scbabfged t 图3-5 最终语法树以上主要为讲述语法树的构造思想，由于要笼统讲述所有文法对应句子的语法树确实存在一定的困难，所以希望以点铺面，其他文法句子的语法树可以根据该思想而设计出。构造语法树在本系统中是隐含在句子的分析过程中，构造句子的语法树就相应的写出来句子的分析过程。第四章 系统设计4.1 总体设计 ll（1）分析器的构造构造ll(1)预测分析表构造句子的分析过程读入文法 图4-1 总体设计框图4.2 详细设计一 系统设计框图及主要函数说明 本系统主要实现的功能是构造ll（1）预测分析表，并根据其分析句子的分析过程。而其中关联的first、follow的构造只是隐含的分析过程，不需要具体实现，通过他们来建立预测分析表，这是本次课程设计需要重点实现的。(1) 构造分析表模块说明函数名 main( )功能 :(1)调用函数grammer( )读入文法; (2)调用函数ll1判断ll(1)文法 (3)调用函数mm()构造分析表与之相关的模块名:读入文法模块, ll(1)文法模块,构造分析表模块(2) 读入文法模块说明函数名 grammer()功能 : (1)调用函数recur()分解含有左递归的产生式 (2)调用函数non-re()分解不含有左递归的产生式 (3)调用函数merge()将字符串合并(3) 句子分析即总控程序模块函数名 : analyze ()功能 :调用函数mm（）构造的分析表与之相关的模块名 求读入文法模块,ll（1）文法模块,构造分析表模块主程序模块图读入文法模块ll（1）文法判断模块（本程序不具体实现）first集判断模块（隐含）序follow集判断模（隐含）select集的求解（隐含）构造ll（1）预测分析表构造句子的预测分析过程 图4-2 系统设计框图二、系统模块设计 1、ll（1）预测分析表的构造 （1）、相关理论介绍 预测分析方法是自顶向下分析的另一种方法，有叫ll（1）文法。一个预测分析器是由三部分组成： a、预测分析程序 b、先进后出栈 c、预测分析表 其中只有预测分析表与文法有关，而分析表又可用一个矩阵m（或称二维数组）表示。矩阵ma,a中的下标a表示非终结符，a为终结符或句子括号“#”，矩阵元素ma,a中的内容是一条关于a的产生式，表明当用非终结符a向下推导时，面临输入符a时，所应采取的候选产生式，当元素内容物产生式时则表明用a为左部向下推导时遇到了不该遇到的符号，因此元素内容为转向出错处理的信息。 （2） 算法描述及流程图 在构造完文法的first集、follow集和select后构造预测分析表：对每个终结符或“#”号用a表示。 若a属于select（a-a），则把a-a放入ma,a标上出错标记。 a、构造预测分析表的流程图m2020初始化，“#”加入ternum中for i=0 to count-1找出与leftifor j=0 to strlen(selecti-1)selectij在termin串中for k=0totermink=selectij跳出for k=0的循环将在产生式中序号i赋给mmk是是图4-3 预测分析表构造流程图b、现以表达式文法为例构造预测分析表：表达式文法为：e-e+t|tt-t*f|ff-i|(e)通过求解该文法的first集和follow集得到select集合如下：select(e-te)= （, i select(e-+te)= + select(e-)= ),# select(t-ft)= （, i select(t-*ft)= * select(t-)= +,),# select(f-(e)= （ select(f-i)= i 此例的预测分析表如下表4.1：表4.1 表达式文法的预测分析表i+*()#e-te-tee-+te-t-ft-ftt-*ft-f-i-(e)（3）实验代码 构造预测分析表的过程核心算法框架如下：mm() for(i=0;i=19;i+) for(j=0;j=19;j+) mij=-1; i=strlen(termin); termini=#; /*将#加入终结符数组*/ termini+1=0; for(i=0;i=count-1;i+) for(m=0;m+) if(non_term=lefti) break; /*m为产生式左部非终结符的序号*/ for(j=0;j=strlen(selecti)-1;j+) if(in(selectij,termin)=1) for(k=0;k+) if(termink=selectij) break; /*k为产生式右部终结符的序号*/ mmk=i; 2、文法读入模块（1）相关理论知识介绍文法的读入主要要注意文法的格式的正确性，在该模块中主要要实现对基本输入格式正误的判断。（2） 算法描述及流程图（见图4-4）本模块主要为实现从键盘读入文法，系统实现该读入文法的正误进行判断。下图是该模块实现的相应程序的流程图：定义两个变量i,jbegin（接下页的图）i=count-1in(lefti,non_ter=0printf(“nerror!”)validity=0return(0)j=strlen(righti)-1in(rightij,non_ter)=0&in(rightij,termin)=0&rightij!=printf(nerror2!)return(0)j+i+return(0) 图4-4 判断读入文法正误流程图（3）实现代码 judge() int i,j; for(i=0;i=count-1;i+) if(in(lefti,non_ter)=0) /*若左部不在非终结符中，报错*/ printf(nerror1!); validity=0; return(0); for(j=0;jtet-ftf-i“i”匹配t-e-+te“+”匹配t-ftf-i“i”匹配t-*ft“*”匹配f-i“i”匹配t-e-接受（3）本模块主要实现代码syntax() printf(请输入该文法的句型：); scanf(%s,str); getchar(); i=strlen(str); stri=#; stri+1=0; s0=#; s1=start; s2=0; j=0; ch=strj; while(1) if(in(sstrlen(s)-1,termin)=1) if(sstrlen(s)-1!=ch) printf(n该符号串不是文法的句型！); return; else if(sstrlen(s)-1=#) printf(n该符号串是文法的句型.); return; else sstrlen(s)-1=0; j+; ch=strj; else for(i=0;i+) if(non_teri=sstrlen(s)-1) break; for(k=0;k+) if(termink=ch) break; if(k=strlen(termin) printf(n词法错误！); return; if(mik=-1) printf(n语法错误！); return; else m=mik; if(rightm0=) sstrlen(s)-1=0; else p=strlen(s)-1; q=p; for(n=strlen(rightm)-1;n=0;n-) sp+=rightmn; sq+strlen(rightm)=0; printf(ns:%s str:,s); for(p=j;p=strlen(str)-1;p+) printf(%c,strp); printf( ); 第五章 运行与测试结果5.1、一组测试数据产生式集：sahhamdhdmabm$aamae测试字符串： aaabd预测分析表：adbe#ssahhhamdhdmmabm$m$mabaaamae分析过程步骤分析栈剩余输入字符使用产生式或匹配1#saaabd#sah2#haaaabd#a匹配3#haabd#hamd4#dmaaabd#a匹配5#dmabd#mab6#dbaabd#aam7#dbmaabd#a匹配8#dbmbd#m$9#dbbd#b匹配10#dd#d匹配11#分析成功结论：字符串aaabd是该文法的句子5.2、界面实现情况a.程序运行的主窗体如下，通过此主窗体可以以文件的形式导入ll(1)文法也可通过“添加”按键自由添加构造文法 通过点击“自带文法导入”按键后，导入事先准备好的文法，运行结果如下图所示：b.然后点击“构造分析表”按键，如果导入的文法是ll(1)文法，则生成预测分析表，如下面两图所示：c.如果导入的文法不是ll(1)文法，则运行结果如下图所示：如果输入的是ll(1)文法，则点击“分析句子”按键，将打开句子分析对话框，如果输入的句子为预定文法的句子，则运行结果如下图所示：如果输入的句子不符合预定文法的句子，则运行结果如下图所示： d.点击“查看语法树”按键将打开语法树显示界面,如果输入的句子符合预定文法的要求，则运行结果如下：否则运行界面显示内容为空。第六章 结论一、本系统主要实现了以下功能：1、 实现来对ll（1）预测分析表的构造： 构造表达式文法的预测分析表，使得该文法变的一目了然，也是对该文法是ll(1)文法的进一步肯定。从而为判断输入符号串是否为该文法的句型。2、 实现了对根据预测分析表实现对句子的分析功能。界面的建立也是判断一个系统的好坏。拥有一个好得界面，不仅使整个系统看起来简洁明朗，而且还可以使用户的查询工作更加方便。在这个系统中我们提供了三个界面，它们分别是分析过程界面、分析句子界面和语法树分析界面，相信通过这三个界面，用户可以很清楚的看到所给文法每一步的求解过程。二、系统实现情况1、总的来说系统基本实现了对相应的功能，但仍存在一定的问题，需要进一步深入考虑。2、课程设计总共持续一个星期左右，时间不算长，由于时间限制和本人能力这两方面，系统不能做到较完美的。3、课程设计由于时间本人能力所限，界面设计不是很完善，在主窗体中的三个“添加”模块之间本应互为关联的，但在设计时没有很好的实现，导致添加时不能分辨正误。4、在通过“自带文法导入”按键导入文法时，如果文法有误，系统只实现提示错误而不能具体的提示是哪部分出错，因此此部分功能没有很好的实现有待改进。5、系统其他功能的实现较完善，例如分析表的构造、句子的分析、语法树的构造等都很好的实现了其应有的功能。课程设计心得本文所描述的ll(1)预测分析器的构造系统，能够完成对一个文法预测分析表的构造和对句子进行分析的功能。系统提供了来三个相对完整的界面,使用户基本可以相对轻松和容易的完成对某一句子的分析。此次课程设计帮助我复习了自顶向下语法分析方法的知识。 但是由于课程设计时间较短，仅一个星期左右，导致该系统还有许多未能实现，比如对所输入的文法，系统只能对英文的大小写，数字以及一些标点符号进行辨别，而对汉字和其它一些文字无法辨别，用户界面不够美观等问题。这些都有待于日后做进一步改善。本次课程设计是和班级同学组成四人组完成本次任务的，相对一个人来说，确实轻松了许多，但同时也发现，有时候人多了常会造成意见不一致。这次课程设计让我体会到了：小组任务需要我们能够体会到团队合作精神和学会独立完成指定任务。通过本次课程设计，我有如下些许体会：1. 学习要有扎实的基础。如果不掌握起码的课本知识，就算勉强做出来的系统也是再简单不过的，很难写出高水平的程序。而这一点又是我们所缺乏的。 2. 不随便乱钻牛角尖。当遇到障碍的时候，暂时放下手中的任务，适当的放松自己，也许很快就会发现那些难题其实并不像想象中的那么难以解决。 3. 多与别人交流，学会团队协作的能力。小组分工是难得的机会，三人行必有我师。 一个人做一个系统，可能常会考虑不全，所以应该尽量多交流，这样就能使系统做到尽量完善。4. 良好的编程风格。在编写电子文档时，注意养成良好的习惯，代码的缩进编排，变量的命名规则要始终保持一致。如果注释和代码不一致，那就更加糟糕。 文档编写接近尾声，课程设计也快打上句点了，会受这一个星期的课程设计，像来真是受益匪浅。我们小组四名成员，唯我一个女生，所以荣幸的当上了小组组长，而我确实失职，没能很好地召集小组成员。在今后的日子里我会尽量让自己深入懂得团队合作的精神。课程设计初期，遇到的麻烦确实不少，虽然上了一学期编译了，课本知识掌握也还可以，但面对这样一个相对较大的系统，确实盲目了些许时候，最后通过网络、图书馆以及和其同学的共同讨论，才真正明白了此次实现的实现原理和方法，才有了这个还不是很完善的系统的出现。参考文献1 编译原理 张素琴 吕映芝等 清华大学出版社 2006.102 程序设计语言编译 陈火旺 刘春林等 国防工业出版社 2004.13 编译技术课程设计与上机指导 霍林 重庆大学出版社 2001.94 编译程序构造原理和实现技术 金成植 高等教育出版社 2001.6 第二版5. 编译原理 陈意云 中国科学技术大学出版社 1997.126 编译程序设计原理，杜淑敏、王永宁等，北京大学出版社，19867.c+程序设计教程钱能.北京：清华大学出版社，20058.计算机编译原理张幸儿.北京：科学出版社 2003致谢首先，感谢汪国武老师能在此次课程设计中给我这样一个锻炼的机会，课程设计的完成离不开汪老师的悉心指导和关怀。在本次课程设计中，我从汪国武老师身上学到了很多东西。汪老师认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我们受益匪浅。他无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。另外，在系统开发过程中，同组的同学也给与我不少帮助，如果没有他们的努力，凭我一个人的力量是不能按时完成这次课程设计的。在此我一并表示对他们的衷心感谢。附录(核心代码清单)：#include#include#includeint count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各产生式右部的first和左部的follow集合*/char first15050; /*所有单个符号的first集合*/char select