编译原理 LR(0)分析过程的实现

1、淮北师范大学编译原理课程设计课题名称：LR(O)分析过程的实现班级：2014级非师2班学号：20141202109姓名：夏涛目录1课程设计的目的22课程设计的内容及要求23实现原理23.1LR分析器结构23.2LR分析法寻找可归约句柄的依据33.3LR分析器的核心33.4LR分析器的总控程序43.5具体过程分析如下：43.6LR(0)分析表构造基本思想.43.7构造LR(0)分析表的方法53.7.1生成文法G的LR(0)项目53.7.2由项目构成识别文法活前缀的DFA53.7.3将所得DFA确定化53.7.4 LR(0)项目集规范簇的自动构造63.7.5 LR(0)分析表的构造算法.74算法实

2、现流程图75测试数据86结果输出及分析97软件运行环境及限制128心得体会139参考文献131课程设计的目的通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。2课程设计的内容及要求1. 可以使用任何语言来完成，例如：Java、C、C+。2. 文法采用常用的方式进行描述，例如：S-aA。3. 以文件方式读取文法。4. 求出项目集规范族(即所有的状态)。5. 给出状态间的关系。6. 给出LR(O)分析表。7. 给定的任意符号串判定是否是文

3、法中的句子，将分析过程用计算机打印出来。3实现原理3.1LR分析器结构LR分析器由三个部分组成：(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。(2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。32LR分析法寻找可归约句柄的依据1）规范归约的关键问题是找句柄。2）问题不在于“历史”与“现实”，而是如何基于“历史”对未来“展望”，“展望”可能存在相当多的可能性。3）

4、一般只是使用简化了的“展望”信息，以便能构造一个可行的分析算法。4）一个LR分析器实际上是一个带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态5）下推栈可用于存放由“历史”及相应“展望”信息形成的抽象状态。6）下推栈内的每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，因此。栈顶的状态可用于决定当前动作，即，LR分析器的每步动作可由栈顶状态和读头下符号唯一确定。3.3LR分析器的核心1、核心分析表2、分析表构成a）动作表（ACTION）ACTIONS,a表示在当前状态S下，面临读头下符号a所应采取的动作。b）转向表（GOTO）GO

5、TOS,X：若XeVT，表示在当前状态下，读入a应转向什么状态；若XeVN，表示当前栈顶句柄归约成X后，应转向什么状态。c）栈结构图SoI顶指针状态栈符号栈d）分析表格式动作GOTOala2-%AlA2.Am5051Sk3.4LR分析器的总控程序总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。1、移进把(Sm,ai)的下一状态S'二GOTOSm,ai连同读头下符号推进栈内，栈顶成(S',ai)，而读头前进一格；2、归约指用产生式Aut进行归约。若a的长度为丫，则弹出栈顶y项，使栈顶状态变为Sm-y,然后将(Sm-y,A)的下一状态S'=GOTOSm-y,A

6、连同非终结符A一起推进栈内，栈顶变为(S',A)。读头不动，即不改变现行输入符号。3、接受宣布分析成功，退出总控程序。4、报错报告输入串含有错误，调用相应错误错误处理程序。3.5具体过程分析如下：分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器结构：其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi,X=j表示，规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTIONi，a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1) 移进：actioni，a=Sj:状态j移入到状态栈，把a移入到文法符号栈，其中i,

7、j表示状态号。(2) 归约：actioni，a=rk:当在栈顶形成句柄时，则归约为相应的非终结符A,即文法中有A->B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R,并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3) 接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。36LR(0)分析表构造基本思想只根据

8、“历史”信息识别呈现于栈顶的句柄，而不考虑“展望”信息的状态。活前缀1、定义在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。2、归态活前缀活前缀的尾部正好是句柄之尾，这时可以进行归约。归约之后又会成为另一句型的活前缀。3、非归态活前缀句柄尚未形成，需要继续移进若干符号之后才能形成句柄。37构造LR(0)分析表的方法3.7.1生成文法G的LR(0)项目对文法G的每个产生式右部添加一个圆点，称为G的一个LR(O)项目(简称项目)3.7.2由项目构成识别文法活前缀的DFA1) 对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀。2)

9、 由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，这时，我们把“状态”称为“项目”。这些自动机的全体就是能识别所有活前缀的有限自动机。3.7.3将所得DFA确定化(1) 文法G的LR(0)项目生成在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目。例如，产生式ATXYZ对应四个项目AtXYZ预期要归约的句柄是XYZ，但都未进栈AtXYZ预期要归约的句柄是XYZ，仅X进栈AtXYZ预期要归约的句柄是XYZ，仅XY进栈At

10、XYZ已处于归态活前缀，XYZ可进行归约，这个项目也称为归约项目。(2) 产生式右部符号串的长度为n则可以分解为n+1个项目。产生式A£T只有一个项目At。由项目构成识别文法活前缀的NFA1、将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式S、tS,并令S'tS作为初态项目；2、凡圆点在串的最右边的项目称终态项目或称归约项目，而S'tS称为接受项目；3、设项目i为XTXlXi1XiXn,项目j为XtXIXiXi+1 Xn,则从项目i画一弧线射向j,标记为Xi,Xi是终结符则称为移进,Xi是非终结符则称为待约；4、若项目i为XaTAp,其中A是非终结

11、符，则从i项目画s弧射向所有Aty的项目，wyV*1) 构造出的NFA是包含有s串的NFA,可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA,这个DFA就是建立LR分析算法的基础。2) 相应DFA的每个状态是一个项目集，称作LR(O)项目集，整个状态集称为LR(0)项目集规范簇。3) 在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。4) 有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。5) 状态反映了识别句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。6) 手工构造文法的项目集规范3.7.4LR(O)项目集

12、规范簇的自动构造1、拓广文法增加S'tS产生式，使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目。2、定义和构造项目集的闭包设I是拓广文法G'的一个项目集，如下定义和构造I的闭包CLOSURE(I):a) I的任何项目都属于CLOSURE(I)；b) 若AqtBB属于CLOSURE(I),B是非终结符，则对任何关于B的产生式ByT,项目BTy也属于CLOSURE(I);c) 重复执行步骤b)直到CLOSURE(I)不再扩大为止。3、定义状态转换函数GOGO(I,X)定义为CLOSURE(J),其中I,J都是项目集，Xe(VNuVT),J=任何形如AutXB的项目

13、|AaTXepI。4、构造LR(0)项目集规范族的算法PROCITEMSETS-LR0C:=CLOSURE(S'TS)/*初态项目集*/DOFOR(对C中每个项目集I和G'中每个文法符号X)IF(GO(I,X)非空且不属于C)把GO(I,X)加入C中WHILEC仍然在扩大3.7.5LR(O)分析表的构造算法设C=IO,Il,In,以各项目集Ik(k=O,n)的k作为状态序号，并以包含S'TS的项目集作为初始状态，同时将G'文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：1、若项目Agtap属于Ik状态且GO(Ik,a)=Ij,a为终结符，则置

14、ACTIONk,a=Sj;即：移进a,并转向Ij状态。2、若项目Agtelk,则对任何终结符a(包括语句结束符#),置ACTIONk,a=rj;即根据j号产生式进行归约，其中，j为产生式Aut的编号。3、若项目S'tS属于Ik,则置ACTIONk,#=accept,简记为acc;4、若GO(Ik，A)=Ij,A是非终结符，则置GOTOk,A=j;5、分析表中凡不能用步骤1至4填入信息的空白项，均置上“出错标4算法实现流程图5测试数据终结符abcd非终结符EAB开始符E产生式E->aAE->bBA->cAA->dB->cBB->d6结果输出及分析下面是

15、你输入的文法G：非终结符号集合为：E,A,B终结符符号集合为：a,b,c,dGE:(1) E->aA(2) E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d下面是生成的拓广文法G'：非终结符号集合为：$,E,A,B终结符符号集合为：a,b,c,dG'E:(0)$->E(1)E->aA(2)E->bB(3) A->cA(4) A->d(5) B->cB(6) B->d该文法的项目如下：(1)$->.E(2)$->E.(3)E->.aA(4)E->a.

16、A(5)E->aA.(6)E->.bB(7)E->b.B(8)E->bB.(9)A->.cA(10)A->c.A(11) A->cA.(12) A->.d(13) A->d.(14) B->.cB(15) B->c.B(16) B->cB.(17) B->.d(18) B->d.LR(O)项目规范族如下:I0=1,3,6I1=2I2=4,9,12I3=7,14,17I4=5I5=10,9,12I6=13I7=8I8=15,14,17I9=18I10=11I11=16文法的LR(0)分析表状态ACTIONGOTO

17、abcd#EAB0S2S311acc2S5S643S8S974片片片片片5S5S6106R4R4R4R4R47R2R2R2R2R28S8S9119R6R6R6R6R610R3R3R3R3R311R5R5R5R5R514民lr(o)5£分靳表生成程序乎终结符集合|添加|删除|终结符集合|添加|删除|凶文法开始符号导入文法“1IJ产生式集合|添加|删除|E->aAE->bBA->cAA->dB->cBB->d生成分析表(0清除文法(保存文法(S)关闭|图一:读入文法图二：分析文法图三：分析句子：ad图四：生成树7软件运行环境及限制系统平台：WindowsXP/2000软件平台：VC+6.08心得体会归约的时候应该从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R,并把A移入文法符号栈内，j=G