编译原理课程设计报告--LR（0）分析法的实现.doc

评语： 课程设计成绩 考 勤 软 件 报 告 答 辩 总 成 绩 教师签名： 《编译原理》课程设计报告 LR(0)分析法的实现 学院（系）： 班 级： 学生姓名： 学号 指导教师： 时间： 从2007 年12月17日 到2007年 12月29日 目录 1．课程设计的目的 1 2．课程设计的内容及要求 1 3．实现原理 1 3.1 LR分析器结构 1 3.2 LR分析法寻找可归约句柄的依据 2 3.3 LR分析器的核心 2 3.4 LR分析器的总控程序 3 3.5 具体过程分析如下： 3 3.6 LR(0)分析表构造基本思想 4 3.7 构造LR(0)分析表的方法 4 3.7.1生成文法G的LR(0)项目 4 3.7.2 由项目构成识别文法活前缀的DFA 4 3.7.3将所得DFA确定化 4 3.7.4 LR(0)项目集规范簇的自动构造 5 3.7.5 LR(0)分析表的构造算法 6 4．算法实现流程图 6 5．测试数据 8 6．结果输出及分析 9 7．软件运行环境及限制 12 8．心得体会 13 9．参考文献 13 1．课程设计的目的 通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。 2．课程设计的内容及要求 可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。 求出项目集规范族（即所有的状态）。 给出状态间的关系。 给出LR(0)分析表。 给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。 3．实现原理 3.1 LR分析器结构 LR分析器由三个部分组成： (1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。 (2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO） 表两个部分，它们都可用二维数组表示。 (3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 3.2 LR分析法寻找可归约句柄的依据 1)规范归约的关键问题是找句柄。 2)问题不在于“历史”与“现实”，而是如何基于“历史”对未来“展望”，“展望”可能存在相当多的可能性。 3)一般只是使用简化了的“展望”信息，以便能构造一个可行的分析算法。 4)一个LR分析器实际上是一个带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态 5)下推栈可用于存放由“历史”及相应“展望”信息形成的抽象状态。 6)下推栈内的每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，因此。栈顶的状态可用于决定当前动作，即，LR分析器的每步动作可由栈顶状态和读头下符号唯一确定。 3.3 LR分析器的核心 1、核心 分析表 2、分析表构成 a)动作表(ACTION) ACTION[S,a]表示在当前状态S下，面临读头下符号a所应采取的动作。 b)转向表(GOTO) GOTO[S，X]：若X(VT，表示在当前状态下，读入a应转向什么状态；若X(VN，表示当前栈顶句柄归约成X后，应转向什么状态。 c)栈结构图 d)分析表格式 3.4 LR分析器的总控程序 总控程序的动作是根据当前栈顶状态Sm和读头下符号ai查表决定。 1、移进 把(Sm, ai)的下一状态S‘=GOTO[Sm，ai]连同读头下符号推进栈内，栈顶成(S’, ai)，而读头前进一格； 2、归约 指用产生式A((进行归约。若(的长度为(，则弹出栈顶(项，使栈顶状态变为Sm- (，然后将(Sm- (,A)的下一状态S’=GOTO[Sm- (,A]连同非终结符A一起推进栈内，栈顶变为(S’,A)。读头不动，即不改变现行输入符号。 3、接受 宣布分析成功，退出总控程序。 4、报错 报告输入串含有错误，调用相应错误错误处理程序。 3.5 具体过程分析如下： 分析器的动作就是由栈顶状态和当前输入符号所决定。 LR分析器结构： 其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非