LR分析图查看

编译原理实验报告

实验名称

实验时间2011年6月13日

院系计算机科学与技术

班级08计算机科技一班

学号e10814065

姓名王全鸿

1.试验目的

输入：任意的压缩了的上下文无关文法。输出：相应的lr（0）分析表。

2.实验原理

在lr分析工作过程中的任何时候，栈里的文法符号（自栈底而上）x1x2…xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

构造识别文法活前缀dfa有3种方法：

（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造nfa再确定为dfa；

（2）求出文法的所有项目，按一定规则构造识别活前缀的nfa再确定化为dfa；（3）使用闭包函数（closure）和转向函数（go（i，x））构造文法g’的lr（0）的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的dfa。

对于lr（0）文法，我们可以直接从它的项目集规范族c和活前缀识别自动机的状态转换函数go构造出lr分析表。下面是构造lr（0）分析表的算法。

假定c={i0，i1，…，in}，令每个项目集ik的下标k为分析器的一个状态，因此，g'的lr（0）分析表含有状态0，1，…，n。令那个含有项目s'→.s的ik的下标k为初态。action子表和goto子表可按如下方法构造：

（1）若项目a→α.aβ属于ik且go（ik，a）=ij，a为终结符，则置action[k，a]为“把状态j和符号a移进栈”，简记为“sj”；

（2）若项目a→α.属于ik，那么，对任何终结符a，置action[k，a]为“用产生式a→α进行规约”，简记为“rj”；其中，假定a→α为文法g'的第j个产生式；（3）若项目s'→s.属于ik，则置action[k，#]为“接受”，简记为“acc”；（4）若go（ik，a）=ij，a为非终结符，则置goto[k，a]=j；

（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出错标志”。

按上述算法构造的含有action和goto两部分的分析表，如果每个入口不含多重定义，则称它为文法g的一张lr（0）分析表。具有lr（0）表的文法g称为一个lr（0）文法，lr（0）文法是无二义的。

3.实验内容

（1）实现计算闭包closure（i）的算法；（2）实现转向函数go（q，a）的算法；（3）构造文法项目集函数createprojectset；定义数据结构：

typedefstruct{selemtype*base，*top;intstacksize;}sqstack;

structgrammer{char**g;charvt[127];

};