发布时间 : 星期一 文章LR(0)语法分析更新完毕开始阅读ed0b9161ddccda38376baf2f
编译原理课程设计报告
1、用构造一个状态转换函数实现状态转换。
2、再通过函数构造一个移进－归约函数实现移进规约动作。 3、采用构造一个打印LR分析器的工作过程函数实现输出。
在规范规约的过程中，一方面记住已移进和规约出的整个符号串，另一方面根据所用的产生式推测可能碰到的输入符号。每一项ACTION(s，a)所规定的动作不外是下述四种可能之一：
（1）移进：把（s，a）的下一个转态s’ = GOTO(s，X)和输入符号a推进栈，下一输入符号变成现行输入符号。
（2）规约：指用某一产生式A→β 进行规约。假若β的长度为r，规约的动作是A，去除栈顶的r个项，使状态Sm-r 变成栈顶状态，然后把（Sm-r，A）的下一状态s’ = GOTO(Sm-r,A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着β（= Xm-r+1…Xm）已呈现于栈顶而且是一个相对于A的句柄。
（3）接受：宣布分析成功，停止分析器的工作。 （4）报错：发现源程序含有错误，调用出错处理程序。
2．3 总体方案
本课题是由一个四人的团队去完成的，所以，每个小组成员分配了不同的工作共同完成这个项目。
2．4 功能模块框图
运行程序 给出该程序所运用的文法和LR分析表 用户输入字符串 程序给出结果 图2.2功能模块框图
3 系统设计
5
编译原理课程设计报告
3．1 算法描述
1、已知文法G (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i
2、LR(0)分析表的构造算法如下：
假设已构造出LR(0)项目集规范族为：C={I0,I1, … , In}
其中Ik为项目集的名字，k为状态名，令包含S′→·S项目的集合Ik的下标k为分析器的初始状态。那么分析表的ACTION表和GOTO表构造步骤为：
(1) 若项目A→α·aβ属于Ik且转换函数GO(Ik,a)= Ij，当a为终结符时则置ACTION[k,a]为Sj，其动作含意为将终结符a移进符号栈，状态j进入状态栈，(相当状态k时遇a转向状态j)。
(2) 若项目A→α· 属于Ik，则对任何终结符a 和'#'号置ACTION[k,a]和ACTION[k,#]为\，j为在文法G′中某产生式A→α的序号。rj动作的含义是把当前文法符号栈顶的符号串α归约为A，并状态栈指针从栈顶向下移动|α|的长度 , 文法符号栈从栈顶弹出|α|个符号，非终结符A变为当前面临的符号。
(3) 若GO(Ik,A)＝Ij，则置GOTO[k,A]为\，其中A为非终结符，表示当前状态为\时，遇文法符号A时状态应转向j，因此A移入文法符号栈，j移入状态栈。
(4) 若项目S′→S·属于Ik，则置ACTION[k,#]为\，表示接受。
(5) 凡不能用上述方法填入的分析表的元素，均应填上\报错标志\。为了表的清晰我们仅用空白表示错误标志。
根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表，能用LR(0)分析表的分析器称为LR(0)分析器，能构造LR(0)分析表的文法称为LR(0)文法。
3、产生如图2-1所示的LR分析表
6
编译原理课程设计报告
这张分析表包括两个部分，一是“动作”（ACTION）表，另一是“状态转换”（GOTO）表。ACTION(S,a)规定了当状态S面临输入符号a时应采取什么动作。GOTO（S，X）规定了状态S面对文法符号X（终结符或非终结符）时下一状态是什么。显然，GOTO(S，X)定义了一个以文法符号为字母表的DFA。
每一项ACTION(S，a)所规定的动作不外是下述四种可能之一：
（1）移进把（S，a）的下一个转态S’=GOTO(S，X)和输入符号a推进栈，下一输入符号变成现行输入符号。
（2）规约指用某一产生式A→β进行规约。假若β的长度为r，规约的动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r，A）的下一状态S’=GOTO(Sm-r,A)和文法符号A推进栈。规约动作不改变现行输入符号。执行规约动作意味着β（=Xm-r+1…Xm）已呈现于栈顶而且是一个相对于A的句柄。
（3）接受宣布分析成功，停止分析器的工作。 （4）报错发现源程序含有错误，调用出错处理程序。
一个LR分析器的工作过程可看成是栈里的状态序列，已规约串和输入串所构成的三元式的变化过程。分析开始时的初始三元式为：(S0, #, a1a2……an#)。
其中，S0为分析器的初态；＃为句子的左括号；a1a2……an为输入串；其后的＃为结束符（句子右括号）。分析过程每步的结果可表示为：（S0S1……Sm，#X1X2……Xm ai, ai+1……an#）。
3.2 实现方法
3.2.1 构造分析表
LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。LR分析器的每一步工作是由栈顶状态和现行输入符号所唯一决定的。构造一个int型二维数组table[13][9],用于存放LR分析表。并初始化。作者这样规定：
0～11 表示 状态Sj，其中0对应S0，1对应S1…… 21～26 表示 规约Rj，其中21对应R1，22对应R2…… 12 表示 “接受”。 -1 表示 规约出错，报错。
7
编译原理课程设计报告
3.2.2程序设计关键
（1）在输入串(句子)输入的过程中，涉及到一个压栈的问题。但是输入串压入的字符顺序刚好与原理中的字符串模型刚好相反，这样需要先弹出的反而在栈底。为了既要保证字符串输入，又要让输入的字符串存储顺序与输入的字符串相反。采取以下措施：
先将输入的字符串压入符号栈symbol中，然后符号栈弹出的字符再压入输入串栈instr中，这样实现了输入串的倒序存储。
（2）状态栈和符号栈输出（遍历）过程均采取自栈底到栈顶的顺序，而输入串栈则是采取自栈顶到栈底的顺序输出。 3.2.3 LR(0)项目集规范族的构造
识别活前辍的NFA我们可以利用子集法将其确定化。对确定化后的DFA如果把每个子集中所含状态集对应的项目写在新的状态中。
对于构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集规范族，我们可以分析每个状态中项目集的构成，不难发现如下规律：
若状态中包含形如A→α·Bβ的项目，则形如B→·γ的项目也在此状态内。例如：0状态中项目集为{S′→·E，E→·aA, E→·bB}。
回顾由NFA确定化到DFA时，E→·aA和E→·bB正是属于S′→·E的闭包中。因而，可引入闭包函数(CLOSURE)来求DFA一个状态的项目集。
若文法G已拓广为G′，而S为文法G的开始符号，拓广后增加产生式S′→S。如果I是文法G′的一个项目集，定义和构造I的闭包CLOSURE(I)如下：
(1) I的项目均在CLOSURE(I)中。
(2) 若A→α·Bβ属于CLOSURE(I)，则每一形如B→·γ的项目也属于
CLOSURE(I)。(3) 重复(2)直到不出现新的项目为止。即CLOSURE(I)不再扩大。 由此，我们可以很容易构造出初态的闭包，即S′→·S属于I，再按上述三点求其闭包。
回顾在构造识别活前缀的NFA时，其两个相邻状态对应的项目是出自同一个产生式，只是圆点的位置相差1，箭弧上的标记为前一个状态和后一个状态对应项目圆点间的符号，(除了箭弧上标记为ε的外)。
由于识别活前缀的DFA的每个状态是一个项目集，项目集中的每个项目都不
8