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

《编译原理 lr(0)分析过程的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、淮北师范大学编译原理课程设计课题名称：LR(0)分析过程的实现班级：2014级非师2班学号：20141202109姓名:夏涛13目录1．课程设计的目的12．课程设计的内容及要求13．实现原理13.1LR分析器结构13.2LR分析法寻找可归约句柄的依据23.3LR分析器的核心23.4LR分析器的总控程序33.5具体过程分析如下：33.6LR(0)分析表构造基本思想43.7构造LR(0)分析表的方法43.7.1生成文法G的LR(0)项目43.7.2由项目构成识别文法活前缀的DFA43.7.3将所得DFA确定化43.7.4LR(0)项目集规范簇的自动构造53.7.5LR(0)分析表的

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

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

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

5、]表示在当前状态S下，面临读头下符号a所应采取的动作。b)转向表(GOTO)GOTO[S，X]：若XÎVT，表示在当前状态下，读入a应转向什么状态；若XÎVN，表示当前栈顶句柄归约成X后，应转向什么状态。c)栈结构图d)分析表格式133.4LR分析器的总控程序总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。1、移进把(Sm,ai)的下一状态S‘=GOTO[Sm，ai]连同读头下符号推进栈内，栈顶成(S’,ai)，而读头前进一格；2、归约指用产生式Aa®进行归约。若a的长度为g，则弹出栈顶g项，使栈顶状态变为Sm-g，然后将(Sm-g,A)的下一状态S’=GOTO[

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

7、到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A->B的产生式，若B的长度为R(即

8、B

9、=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4)报错:当遇到状态