LR(0)算法的实现及应用

编译原理报告LR(0)算法的实现及应用学生姓名：学号：专业：计算机科学与技术学院：计算机学院完成时间：2016年11月20【分工】胡安忠：整个程序的架构设计；冯扬：项目集规范族的构造；刘以：分析表中ACTION、GOTO函数的实现；罗子成：分析表的输出及文法输入函数；【问题描述】选题名为LR0算法的实现，LR0分析法的归约过程是规范推到的逆过程，即规范归约的过程。LR0分析法的作用是对给出一种能根据当前分析栈中符号串（通常以状态表示）就可以唯一确定分析器的动作是移进还是规约和用哪个规则规约，因而也就能唯一确定句柄。并且LR0算法是LR1，SLR1，LALR1算法的基础。1.2、LR(0)算法研究的现状LR(0)算法[1]是一种基础的语法分析算法[1]，无论国内还是国外都有对其的研究。由于其限制条件并不适合大多数高级语言的要求，所以在LR0算法基础上对这种规范归约[2]进行了演化出现了LR1[1]，SLR1[1]，LALR1[1]等算法。并且现在主流编译器的词法分析基于LALR[1]原理产生的YACC(YetAnotherCompiler—Compiler)，是一个经典的生成语法分析器的工具。输入L语言的YACC[1]规格说明，产生L语言语法分析器。根据产生的L语言语法分析器就可以分析L语言的输入串是否符合语法【设计的目的】在做LR(0)文法毕业设计中主要的目的是实现LR(0)算法的实现，主要工作是程序的实现。在程序程序实现过程中主要有一下几个阶段：1总体设计，2核心算法的设计，3数据结构的设计，4编码的实现及调试。【LR(0)文法的工作原理】#此部分为小组成员共同完成部分。LR分析法是一种自下而上进行规范归约的语法分析法，L指从左到右扫描输入符号串，R是指构造最右推导的逆过程。对大多数无二义性上下文无关文法描述的语言都可用它进行有效的分析。主要分析器有LR（0），SLR（1），LR（1），LALR（1）。LR（0）：在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采取的分析动作。所能分析的LR（0）文法要求文法的每一个LR（0）的每一个项目集都不包含项目冲突。1、术语的定义：○1句柄：一个句型的最左直接短语称为该句型的句柄，句柄是规范归约的可归约串。○2字符串前缀:是指字符串的任意首部。如abc的前缀有、a、ab、abc。○3活前缀：指规范句型的一个前缀，这种前缀不包含句柄之后的任何号。若S′αAωαβω是文法G′中的一个规范推导，G′是G的拓广文法，符号串γ是αβ的前缀，则称γ是G的，也是G′的一个活前缀。其中规范推导是最左推导。○4最左推导：每次替换是总是选择最左边的非终结符进行替换。○5项目：我们把文法G中右部添加一个圆点的产生式称为文法G的一个LR(0)项目。例如：产生式A→XYZ有四个LR(0)项目：A→.XYZA→X.YZA→XY.ZA→XYZ.每个项目的含义与圆点的位置有关:概括地说，圆点的左部表示分析过程的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别的部分。只要已扫描过的部分保持可归约成一个规范句型的活前缀，那就意味着所扫描过的部分是正确的。为此，我们把构造识别文法所有活前缀的有限自动机NFA[1]的每个状态由LR(0)项目构成。项目可以分成归约项目，移进项目，待约项目，和接受项目。○6归约项目：形如A→α.的项目，其中，(VTVN)*。它表示栈顶已形成句柄α,下一步动作应该是归约。○7移进项目：形如A→α.aβ的项目。其中，aVT，,β(VTVN)*。它表示期待从输入串中移进一个符号，已待形成句柄。○8待约项目：形如A→α.Bβ的项目。其中，BVN，,β(VTVN)*。它表示期待从输入串中进行归约而得到B，然后进一步得到A的全部右部。○9接受项目：形如S’→α.的项目。S’是文法开始符，以S’为左部的规则只有一个（通过对一般文法拓广得到的），所以，该归约项目是一个特殊的归约项目，它表示整个句子已分析完毕，可以接受○10项目集：是项目根据闭包算法求出的由多个项目组成的集合。例如文法：S’→SS→AS→BA→aAbA→cB→aBbB→d假设项目集I初始时是{S’→.S}，则根据闭包算法时求出的项目集是CLOSURE(I)={S’→.S,S→.A,S→.B,A→.aAb,A→.c,B→.aBb,B→.d}=I0其中I0就是I求出的项目集。2、LR(0)算法的总体原理：一个LR分析器由3个部分组成：(1)总控程序：对所有的LR分析器总控程序都是相同的。(2)分析表：不同的文法分析表将不同，分析方法将也不同；(3)分析栈：文法符号栈和相应的状态栈，存放“历史”和“展望”信息。图2.1如图2.1实质上是一个带先进后出存储器（栈）的确定有限状态自动机[1]。它的每一步工作都是由栈顶状态和现行输入符号唯一确定的。其中“状态”综合了历史（已归约和移进的整个符号串）和展望（可能的输入符号）信息。总控程序根据栈顶状态，和输入的字符串，及已经构造好的分析表来判断输入的当前字符是否是正确的，如果正确就按照分析表中的内容执行下一部的动作。【LR(0)算法实例笔算结果】例:文法是E-TAA-+TAA-T-FBB-*FBB-F-(E)F-i对上述文法进行拓展分解后，求闭包集，go函数，进而求得项目集规范族形成如下的图2.2：图2.2//每一个方框中代表一个状态，每个状态中包含若干个项目。每个项目圆点后的字符是该状态可以识别的字符。例如图2.2中的I0状态中的项目S-.S，圆点后的字符是S，说明状态I0可以识别字符S。带箭头的线为方向线，箭头方向是头，不带箭头的是尾。每条方向线连接两个状态，每条方向线旁边有一个字符。每条方向线表示某一状态遇到一个字符转换到另一个状态。例如图2.2中在状态I0和I1之间有一个方向线，方向线上有一个字符S，这表示状态I0遇到输入字符S后，转换到I1状态。//根据上述的状态转换图，又可以生成如下的图2.3图2.3如图2.3所示：S表示动作为移进，S后面的数字表示移后进入的状态。r表示动作归约，R后面的数字表示用哪一个产生式进行归约。acc表示分析正确。【算法的设计】【总体设计】算法主要包括以下主要模块：#实现分析表LR0算法的实现输入文法产生式闭包集算法，go函数的实现项目集规范族的构建#此部分为我所做的整个程序的架构设计。【数据结构设计】1、设计数据结构FormulaType，用于存储产生式：typedefstruct{charleft;//产生式左部charright[10];//产生式右部intrightnum;//产生式右部字符数}FormulaType;2、设计数据结构GrammerType,用于存储文法typedefstruct{FormulaTypeformula[20];//存储文法中的产生式intformulanum;//存储文法中的产生式个数charvt[10];//存储文法中的终结符charvn[10];//存储文法中的非终结符intvtnum;//存储文法中的终结符个数intvnnum;//存储文法中的非终结符个数charstartv;//存储文法的开始符号}GrammerType;//文法存储结构3、设计数据结构ItemType,用于项目typedefstruct{intfno;//产生式编号intpoint;//圆点位置}ItemType;//项目结构4、设计数据结构ItemType,用于存储项目集typedefstruct{intitemsetno;//项目集编号intitemnum;//项目集中的项目数ItemTypeitem[10];//项目集中的项目}ItemSetType;//项目集存储结构5、设计数据结构ItemSetsType,用于存储项目集族typedefstruct{ItemSetType*set[20];//项目集指针intitemsetnum;//项目集数}ItemSetsType;//项目集簇6、设计数据结构ActionType,用于存储分析表中的动作类型及状态typedefstruct{charact;//动作intstate;//状态}ActionType;//ACTION表结构7、设计数据结构LRlistType，用于存储分析表typedefstruct{ActionTypeactiontable[20][10];//存储分析表中的actiontable表intgototable[20][10];//存储分析表中的gototable表}LRlistType;//分析表8、设计数据结构stacktype,用于存储分析栈的类型typedefstructStackType//分析表中，栈的类型{intstate;//存储状态charch;//存储字符}stacktype;9、设计数据结构stack,用于定义分析栈typedefstructStack//用来定义栈{stacktypestackarry[maxsize];inttop;}stack;#【所有代码】#includestdio.h#includestdlib.h#includeiostream#includestringusingnamespacestd;#pragmawarning(disable:4996)#definemaxsize50/*****************************************************/////存储结构/***************************************************/structFormulaType{charleft;//产生式左部charright[10];//产生式右部intrightnum;//产生式右部字符数};structGrammerType{FormulaTypeformula[20];intformulanum;charvt[10];charvn[10];intvtnum;intvnnum;charstartv;};//文法存储结构structItemType{intfno;//产生式编号intpoint;//圆点位置};//项目结构typedefstruct{intitemsetno;//项目集编号intitemnum;//项目集中的项目数ItemTypeitem[10];//项目集中的项目}ItemSetType;//项目集存储结构structItemSetsType{ItemSetType*set[20];//项目集指针intitemsetnum;//项目集数};//项目集簇structActionType{charact;//动作intstate;//状态};//ACTION表结构structLRlistType{ActionTypeactiontable[20][10];intgototable[20][10];};//分析表structStackType//分析表中，栈的类型{intstate;charch;};typedefstructStack//用来定义栈{StackTypestackarry[maxsize];inttop;}stack;/*****************************************************/////函数声明/***************************************************/voidinitgrammer();//初始化文法voidinitformula();//产生式初始化voidreadvt();//读产生式的终结符voidreadvn();//读产生式的非终结符voidreadgrammer();//读入产生式voidreadformular(charformular[]);//读入产生式voiddispose(charformular[]);//处理