评语： 课程设计成绩 考 勤 软 件 报 告 答 辩 总 成 绩 教师签名：
《编译原理》课程设计报告
LR(0)分析法的实现
学院（系）： 班 级： 学生姓名： 学号 指导教师：
时间： 从2007 年12月17日 到2007年 12月29日
0
目录
1．课程设计的目的 .........................................................................2 2．课程设计的内容及要求 ..............................................................2 3．实现原理 ....................................................................................2 3.1 LR分析器结构 ...........................................................................2 3.2 LR分析法寻找可归约句柄的依据 .......................................3 3.3 LR分析器的核心 .................................................................3 3.4 LR分析器的总控程序 ..........................................................4 3.5 具体过程分析如下： ...........................................................4 3.6 LR(0)分析表构造基本思想 ...................................................4 3.7 构造LR(0)分析表的方法 .....................................................5 3.7.1生成文法G的LR(0)项目 ............................................5 3.7.2 由项目构成识别文法活前缀的DFA............................5 3.7.3将所得DFA确定化 ......................................................5 3.7.4 LR(0)项目集规范簇的自动构造 ...................................6 3.7.5 LR(0)分析表的构造算法 ..............................................7 4．算法实现流程图 .........................................................................7 5．测试数据 ....................................................................................8 6．结果输出及分析 .........................................................................9 7．软件运行环境及限制................................................................12 8．心得体会 ..................................................................................13 9．参考文献 .................................................................................. 13
1
1．课程设计的目的
通过课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。
2．课程设计的内容及要求
1. 2. 3. 4. 5. 6. 7.
可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。
求出项目集规范族（即所有的状态）。 给出状态间的关系。 给出LR(0)分析表。
给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。
3．实现原理 3.1 LR分析器结构
LR分析器由三个部分组成：
(1) 总控程序，也可称驱动程序。对所有的LR分析器总控程序都是相同的。 (2) 分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分
析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO） 表两个部分，它们都可用二维数组表示。
(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
2
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
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为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：
(1) 移进：action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2) 归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A->B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3) 接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
3.6 LR(0)分析表构造基本思想
只根据“历史”信息识别呈现于栈顶的句柄，而不考虑“展望”信息的状态。 活前缀 1、定义
4