毕业设计（论文）-简单的编译原理语法分析器的实现.doc

简单的编译原理语法分析器的实现摘 要编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。在编译原理的教学过程中，算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等，这些过程往往需要占用大量时间来分析、制表等。本软件的主要任务就是利用程序来完成算法的上述相关过程，以达到高效，直观的效果。本文旨在介绍语法分析方法中的一种自上而下的分析方法ll(1)分析法。所谓ll(1)分析法是指语法分析是按自左至右的顺序向前查看一个输入字符串，并分析过程中产生句子的最左推导。关键词：编译；语法分析；ll(1)算法；演示the design and implementation of a syntax analyzer based on compilation theory abstractthe compiler generally is made up of the lexical analyzer program, the syntax analysis program, the semantics analysis program, the inter-language production procedure, the goal code production procedure, the code optimization procedure, the form executive program and the procedure of disposing mistakes. in the teaching process of compiler principle, all algorithm explanation needs to be explain clearly, including algorithm condition judgment, grammar analytical table structure process, grammar analytical table concrete production, in view of grammar sentence analysis process and so on. these processes often take much time to analyze, the scheduling and so on. this program mainly work is to complete the algorithm which take advantage of the procedure to deal with those above mentioned processes , in order to save time. the paper aims at introducing a syntax analytical method named ll(1) algorithm which from the up to down. the syntax analyzer analyzes the character string beginning from the left to right one word each time and educes the most left deduction of the sentence in the analyze course.key words: compiler; grammar analysis; ll(1) algorithm; demonstrate目 录论文总页数：22页1引言11.1项目背景11.2目标11.3名词解释11.4算法简介21.4.1自顶向下分析21.4.2 递归子程序31.4.3 ll（k）分析方法41.4.4 ll（1）分析方法41.4.5ll(1)分析表52 系统流程图62.1程序流程图62.2 系统模块流程图73 系统实施73.1文件读取模块83.1.1文件读取使用的commondialog控件介绍83.1.2文法左递归的判断93.2算法分析模块93.2.1求select集93.2.2求first集103.2.3求follow集103.3分析表构造模块123.3.1构造文法分析表123.3.2a:=a规则133.3.3a:=d规则133.3.4a:=规则133.4句子分析模块133.4.1读取句子143.4.2分析句子144 特殊问题及解决方法144.1 select集的求解154.1.1 问题描述154.1.2 解决方案154.1.3 解决结果154.2为listbox添加水平滚动条154.2.1 问题描述154.2.2 解决方案154.2.3 解决结果165 结果测试165.1测试正确文法165.2测试错误文法19结 论20参考文献201引言1.1项目背景编译原理是计算机专业中最难的一门课程,在理论上它要求学生掌握有关形势语言和自动机的抽象概念,在技术上要求学生能够熟练地利用各种数据结构进行编程。编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。在编译原理的教学过程中，语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。这些过程往往需要占用大量时间来分析、制表等。教学主要是对这些过程的讲解和分析，没有必要花这么多的时间来做这些工作。本软件的主要任务就是利用程序来完成算法的上述相关过程，节约教学时间。1.2目标一个编译原理语法分析器的设计与实现1.主要通过文本方式获取相关文法，并实现以下相关操作：2.判断文法是否符合ll（1）的要求3.获取文法的终结符和非终结符4.求文法的select集（其中包括first集和follow集的求解）并判断select集是否符合ll（1）算法的要求5.根据文法和select集构造文法分析表6.根据文法分析表判断输入的句子是否符合文法1.3名词解释 语法分析：逐一分析词法分析所得的属性字，检查其中的语法错误，如果没有发现语法错误， 则给出正确的语法结构。句子的分析：句子的分析实际就是分析源程序中的语句是否符合给定的文法。文法：对语言结构的定义和描述，即在形式上用于描述和规定语言结构。由若干条规则组成。规则：为一个二元组，通常格式为u：=x或ux；其中u为规则的左部，是一个符号；x是规则的右部，是一贯有穷字符串。规则又称为产生式。bnf表示法：即巴科斯范式表示法，它引进了符号“|”，符号“|”表示“或”。运用符号“|”把相同左部的规则缩写在一起，这样显得文法更为紧凑。文法gz：规则的非空有穷集合，其中z为文法的识别符号或开始符号，它至少要在一条规则的左部出现。字汇表：在文法中，由全部规则的左部和右部中的所有符号组成的符号集。非终结符：文法中出现在规则左部的符号，它们组成的集合称为非终结符集。终结符：文法中凡不属于非终结符集的符号，它们组成的集合称为终结符集。递归：同一操作或一组操作的连续重复，其实质上是处理过程的性质，在这种过程的每一步都要用到它自身的上一步或上几步的结果。递归定义：在定义某种事物时又用到其本身。直接左递归规则：型如u：=uy的规则称为直接左递归规则。first集：首符号集。follow集：向前看集。select集：可选集。ll（1）文法：对于文法g（s），其每个非终结符的不同规则具有不相交的select集，则称该文法为ll（1）文法。1.4算法简介1.4.1自顶向下分析对于文法gz，给顶一个待分析的句子(字符串)，自顶向下分析的基本思想是从识别符号z开始，根据文法试着建立一个推导序列，若得到所给的句子，则句子得到识别，表明其结构符合文法，如果经过各种推导都不能得到所分析的句子，则该符号串不符合文法。或者说，从根结点出发，自上而下地建立一颗语法树，其未端结点按从左到右的顺序连接起来，构成给定的符号串，则符号串得到识别。例：设有文法gn和符号串25 n dnn:=d|ndd:=0|1|2|9 根据文法有：5dnnddd2d25； 因此我们说25符合此文法 2 图1 gn过程分析 自顶向下分析的难点及解决办法：1.自顶向下分析的难点对于形如:u:=x1|x2|xn 的规则,可能需要对所有的规则都要试探。2.难点的解决办法该解决办法是把文法中每个非终结符号a的右部称为a的候选式，对候选式的选择，则根据当前输入符号来决定。方法：首先对文法的每个规则a:=b求可选集 select(a:=b)。当eb时，则对于当前输入的符号a，若有afirst(b)，则可以选用规则a:=b进行推导。若对于某非终止符号有n条规则（即有n个候选式）的处理方法：1.首符号集不相同的解决办法对于文法，有a:=x1|x2|xn，其右部的n个候选式的首符号集均不相同:即first(xi) first(xj)= (ij)，对于待分析的符号串，如果最左的非终结符号为a，若其句子中对应的下一个符号（当前输入符号）为a，且有afirst(xk)，则选择规则a:=xk来作为推导的候选式。例：设有文法gz，和句子bbabaaxz:=av|bzv:=baz|xselect(z :=av)=a;select(z :=bz)=b;select(v :=baz)=b;select(v :=x)=x;z bz bbz bbav bbabaz bbabaavbbabaax (babaax) (abaax) (baax) (ax) (x) 2.首符号相同的解决办法对于文法，有a:= x1|x2|xn，若有first(xi) first(xj) (ij)，采用试探法：即从首字符中有输入符号的多个候选式中任选一个来试探，如果不成功，就换另一个接着试。试探法有可能形成回溯现象。对于回溯现象，可以通过“左提因子方法”对文法进行修改来消除。1.4.2 递归子程序递归子程序方法：这里讲的递归子程序方法是一种自顶向下的编译方法，其思想是通过对源程序的每个语法成分编制一个处理子程序，通过子程序调用来对源程序进行语法和语义分析。递归子程序及其调用：常用的子程序的种类有3种：1、简单子程序，2、嵌套子程序，3、递归子程序。三种子程序的返回地址保护方法：1.所有简单子程序可以公用一个 返回地址保护单元。2.嵌套子程序各自有各自的返回地址保护单元，不得随意公用。3.对于递归子程序，由于返回地址保护单元数目不明确，一般采用堆栈形式。方法是在内存中开辟一个保护栈，每次进入递归子程序时，就把当前返回地址送入保护栈，相应地，每次退出递归子程序时，就取栈顶的返回地址作为其返回地址。同时入栈和出栈的还有相应的递归子程序中需要保护的工作单元。递归子程序调用时，入口与出口的工作：(1)递归入口工作：当前返回地址送保护栈；递归子程序中（调用程序）不允许被破坏的工作单元内容送保护栈。(2)递归出口工作：恢复保护在栈顶中的工作单元的原来内容，并上退保护栈；取保护在栈顶中的返回地址进行返回，并退保护栈。1.4.3 ll（k）分析方法ll(k)分析方法是一种自顶向下的分析技术。这种分析方法从左到右扫描源程序（输入串），同时从识别符号开始生成句子的最左推导（规范推导），向前看k个符号，便能确定当前应选择怎样的规则。当k=1时，既是ll（1）分析方法。1.4.4 ll（1）分析方法1.ll（1）方法的思想：根据输入串的当前输入符号，确定用某规则进行推导，当推导的第一个符号与输入串的当前符号匹配时，就把输入串的下一个字符作为当前输入字符，直到推导出输入串。根据输入串向前的1个符号来确定推导规则时，就是ll（1）方法。2.ll(1)分析方法的逻辑结构第 19 页 共 22页a1 a2 a3 ai am # x1分析表控制器.xn-1图2 ll(1)分析方法的逻辑结构1.4.5ll(1)分析表ll(1)分析表是分析方法的核心,它确定了推导所使用的规则。1.ll(1)分析过程假设分析过程中当前句型的右端部分为：x1x2xm，(xiv)输入流（待分析串）的右端部分为：y1y2yn，(yivt)此时有以下3种情况：(1)当x1vn，则根据当前输入符号y1选择相应的规则去替换x1;(2)当x1vt时，则查看x1与y1是否相同，若x1与y1相同，则分别删去x1和y1，然后继续向前分析；不相同表示不相配，为出错。(3)若上述两个字符串均为空，则表示全部匹配，输入串被识别。 现在我们把句型的右端部分逆向放入一分析堆栈中，使x1成为栈顶，利用分析栈，当栈顶符号与输入串当前符号相匹配时，则从栈顶删除该符号。然后再把相应的规则逆向压入栈顶，替换原栈顶的非终结符。 2.ll(1)分析表的构造ll(1)分析表：它是用来反映分析栈中的元素与输入串中元素的一种匹配关系。如果分析栈中的元素为a，输入元素为a，则其匹配关系记为ll(a,a)ll(1)分析矩阵：一种用来反映这种匹配关系的矩阵表示，该矩阵称为ll(1)分析矩阵。首先进行介绍与ll(1)分析有关的3个操作约定：(1)n表示继续下一个符号；(2)p表示重读当前符号，也即不读入下一符号；(3)r(b)表示用b的逆串替换栈顶符号。构造ll(1)分析表的方法如下：1.对于a:=ab，(avt)，则 令 ll(a,a)=r(b)/n *r(b)/n：表示用b的逆串替换后，继续读入下一个符号。 当b为e时，即：a:=a，有：ll(a,a)=r(e)/n 2.对于a:=db，(dvn)，且有 select(a:=db)=b1,b2,bn ， 则 ll(a,bi)=r(db)/p，(i=1,2,n) *r(db)/p：表示用db的逆串替换a后，重读当前符号3.对于a:=e，且有 select(a:=e)= b1,b2,bn 则 ll(a, bi)=r(e)/p4.对于每一个avt，a不出现于规则右部的首部， 则令 ll(a,a)=r(e)/n5.对于#，令ll(#,#)=acc 表示分析结束，输入串得到识别。6.非上述5种情况，则置出错，分析表中用空白表示。2 系统流程图2.1程序流程图项目的程序流程图如图3所示：程序开始调用打开对话框输入文法优化输入的文法并判断文法合法性获取文法的终结符和非终结符对文法求select集并判断select集合法性构造文法分析表输入并分析句子结束图3 程序流程图2.2 系统模块流程图系统的模块流程图如图4所示：ll(1)算法演示系统文法输入文法分析句子输入与分析文法分析表构造获取终结符和非终结符求文法的select集判断select集的合法性求first集求follow集图4系统模块流程图3 系统实施一个编译原理语法分析器的设计与实现主要分为四个模块：1文件读取模块文件读取模块主要完成将记事本中的待分析文法读入到内存中的功能。其中包括了对可能出现的文法bnf表示法的判断以及对文法中是否存在直接左递归规则的判断。2算法分析模块算法分析模块是一个编译原理语法分析器的设计与实现中的关键模块。本模块包含了ll（1）算法中的大部分重要数据和信息，其中包括获取输入文法的终结符集和非终结符集，对文法中每一条规则求select集（select集的求解又包括求first集或者follow集），以及对select集合法性的判断，即同一非终结符所对应的不同规则的select集中不能有相同的终结符。3分析表构造模块分析表构造模块的主要功能是将算法分析模块所求解出的符合ll（1）算法规则的文法的select集转化成文法分析表，以便下一模块的调用。4句子分析模块句子分析模块是整个一个编译原理语法分析器的设计与实现的主体演示模块，包括句子读取、句子合法性判断、句子分析等部分。其中句子合法性的判断又分为句子中是否有文法终结符以外的符号和句子是否符合文法规则的判断。下面将对以上四个模块的具体实现技术、数据结构及关键程序片段进行详细的说明。3.1文件读取模块本模块通过调用vb中commondialog控件的showopen方法启动打开文件对话框，获取需要读取的文件的路径，再调用open命令打开文件，将文件中保存的文法读入内存，用二维数组进行保存。3.1.1文件读取使用的commondialog控件介绍commondialog 控件提供诸如打开和保存文件、设置打印选项、选择颜色和字体等操作的一组标准对话框。调用打开文件对话框的具体代码如下：dim p_name as string 文件路径form1.commondialog1.cancelerror = trueon error goto errform1.commondialog1.filter = text(*.txt)|*.txtform1.commondialog1.filterindex = 1form1.commondialog1.showopen 用 showopen 方法显示对话框p_name = form1.commondialog1.filename 用 filename 属性获取选定文件的名称3.1.2文法左递归的判断文法中使用递归规则以后，可以用有限的规则刻划无限语言，但不利的是对与具有左递归性的文法，不能采用自顶向下的分析算法。一般含有左递归规则的文法形式为u:=xuy，若x=e, 则有u:=uy，即为左递归规则。由于消除左递归算法的复杂性和毕业设计时间所限，所以本软件没有这项功能，只是对直接左递归进行错误判断。do while wf(j, 0) empty 判断文法是否有左递归 if wf(j, 0) = wf(j, 1) then msgbox ！错误！文法有左递归存在，不符合ll(1)的要求, vbapplicationmodal, 错误 exit sub end if j = j + 1loop3.2算法分析模块本模块首先获取文法的终结符集和非终结符集，分别用一维数组进行保存；然后在对文法的每一条规则求select集，并将select集保存到二维数组中；最后对select集做相关判断，以确定所读入的文法是否符合ll（1）文法的规则。程序中所用到的公有数据成员有：public hs as integer 文法的行数public zj as integer 终结符的个数public nz as integer 非终结符的个数public slt(50, 50) as string select集dim f(50) as string 用与临时存放select集中元素的数组public zjf(50) as string 终结符集public nzj(250) as string 非终结符集3.2.1求select集设有文法gs，并有规则a:=b，则该规则的可选集为：select(a:=b)= 具体实现代码如下： if wf(a, 0) = empty then exit for elseif wf(a, 1) = then 为空字符串 call follow(a, fo) i = 0 do while f(i) empty slt(a, i) = f(i) f(i) = empty i = i + 1 slt(a, i) = empty loop else call first(a, fo) 3.2.2求first集首符号集既求解文法每条规则右边的第一个符号并且必须是终结符，因为文法使用数组存放，所以既求文法每行规则的第2个字符既可；如果规则左边第一个字符为非终结符，则通过循环对该非终结符再求首符号集。for i = 0 to zj if wf(a, 1) = zjf(i) then 判断第a条规则右边的首符号是否是终结符 for p = 0 to fo 判断wf(i,j+1)在f()中是否已经存在 if wf(a, 1) = f(p) then b = 1 exit for end if next p if b = 1 then b = 0 else f(fo) = wf(a, 1) fo = fo + 1 f(fo) = empty end if 3.2.3求follow集求向前看集主要分两种情况，一种是可以直接循环推导出终结符；第二种是推出的还是非终结符的，如果推出的还是非终结符的就循环对该非终结符再求向前看集；第三种情况是不能对该非终结符求向前看集，但是可以通过对该非终结符推导出的第二个非终结符求向前看集的方法求出终结符。c = 0: b = 0if wf(a, 0) = wf(0, 0) then 判断是不是对文法起始符求follow集 for p = 0 to fo 判断wf(i,j+1)在f()中是否已经存在 if f(p) = # then b = 1 exit for end if next p if b = 1 then b = 0 else f(fo) = # fo = fo + 1 f(fo) = empty end ifend iffor i = 0 to hs j = 1 do while wf(i, j) empty if wf(a, 0) = wf(i, j) then if wf(i, j + 1) = empty and a i then call follow(i, fo) else for m = 0 to zj 判断wf(i,j+1)是不是终结符 if wf(i, j + 1) = zjf(m) then for p = 0 to fo 判断wf(i,j+1)在f()中是否已经存在 if wf(i, j + 1) = f(p) then b = 1 exit for end if next p if b = 1 then b = 0 else f(fo) = wf(i, j + 1) fo = fo + 1 f(fo) = empty end if c = 1 exit for end if next m if c = 1 then c = 0 else for n = 0 to hs 查找wf(i,j+1)对应的非终结符在文法的第几行 if wf(i, j + 1) = wf(n, 0) then call first(n, fo) 3.3分析表构造模块在已经得到文法select集的前提下，以次为依据，对文法的三种类型的规则：a:=a型、a:=d型、a:=型分别构造分析表，并用一个三维数组保存。形如fxb（y，x，z），其中，y表示分析表的第y行，x表示第x列，z表示第y行第x列所对应的格子中的第z个数据。3.3.1构造文法分析表在求解select集完成后，结果按照非终结符放入分析表y轴，没有出现在对应规则右部首部的终结符放入分析表y轴，终结符放入分析表x轴等规则放置。如图5。放入分析表y轴放入分析表x轴终结符 文法可选集非终结符文法分析表放入分析表y轴未出现在对应规则右部首部的终结符 图5 分析表构造流程3.3.2a:=a规则对于a:=ab，(avt)，则 令 ll(a,a)=r(b)/n *r(b)/n：表示用b的逆串替换后，继续读入下一个符号。当b为e时，即：a:=a，有：ll(a,a)=r(e)/n 3.3.3a:=d规则对于a:=db，(dvn)，且有 select(a:=db)=b1,b2,bn ，则 ll(a,bi)=rdb)/p，(i=1,2,n) *r(db)/p：表示用db的(逆串替换a后，重读当前符号3.3.4a:=规则对于a:=e，且有 select(a:=e)= b1,b2,bn则 ll(a, bi)=r(e)/p3.4句子分析模块本部分主要通过vb中的inputbox对话框读入待分析句子，并与分析表进行对照，逐步分析所输入的句子是否符合文法。分析过程均用一维数组进行保存。相关程序片段如下：程序中所用到的公有数据成员有：dim fxz(50) as string 存放句子分析过程中的分析栈dim fhz(50) as string 存放句子分析过程中的输入符号栈3.4.1读取句子public sub juzi_read(str as string) 读取句子fhz(0) = emptyi = 0a = mid(str, 1, 1)do while a empty fhz(i) = a a = mid(str, i + 2, 1) i = i + 1 fhz(i) = emptyloopif fhz(0) = empty then exit subend iffhz(i) = #fhz(i + 1) = emptycall fenxi_chrend sub3.4.2分析句子现在我们把句型的右端部分逆向放入一分析堆栈中，使x1成为栈顶，利用分析栈，当栈顶符号与输入串当前符号相匹配时，则从栈顶删除该符号。然后再把相应的规则逆向压入栈顶，替换原栈顶的非终结符。 do while fenxibiao.fxb(i, j, k) empty select case fenxibiao.fxb(i, j, k) case acc exit sub case fxz(a) = empty case /n fhz(b) = b = b + 1 a = a - 1 exit for case /p a = a - 1 exit for case else fxz(a) = fenxibiao.fxb(i, j, k) a = a + 1 fxz(a) = empty e