【精品】LR(0)分析表

《【精品】LR(0)分析表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、自动生成LR(0)分析表姓名：彦清学号：E10914127一、实验目的输入：任意的压缩了的上下文无关文法。输出：相应的LR(0)分析表。二、实验原理对于LR文法，我们可以口动构造相应的LR分析表。为了构造LR分析表,我们需要定义一个重要概念一一文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程屮的任何时候，栈里的文法符号(自栈底而上)X/2…Xm应该构成活前缀，把输入串的剩余部分配上Z斤即应成为规范句型(如果整个输入串确实构成一个句了)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个

2、文法G,我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个口动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程屮，如果分析的句子是正确的，栈里的文法符号(自栈底而±)始终构成活前缀。假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项冃集)不存在下述情况：(1)既含移进项口又含归约项口；(2)含有多个归约项口，则称G是一个LR(0)文法。该自动机的状态集合即为该文法的LR(0)项目集规范族。构造识別文法活前缀DFA有3种方法：(1)根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；(2)求出文法

3、的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；(3)使用闭包函数(CLOSURE)和转向函数(GO(I,X))构造文法G，的LR(0)的项H集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFAo符号串的前缀是指该符号串的任意首部，包括空串£。例如，对于符号串abc,其前缀有£,a,ab,abco如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄Z后的任何符号。Z所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：(1)活前缀已含有句柄的全部符号，表明产生式A-B的

4、右部B已出现在栈顶。(2)活前缀只含句柄的一部分符号，表明A->B1B2的右部子串Bi己出现在栈顶，期待从输入串中看到B2推出的符号。(3)活前缀不含有句柄的任何符号，此时期望A->P的右部所推出的符号串。在文法G的每个产生式的右部(候选式)的任何位置上添加-•个圆点，所构成的每个产生式称为LR(0)项冃。如产生式Atxyz有如下项冃：A—.xyz,ATx.yz,A->xy.z,ATxy乙。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)，可以用这种标有岡点的产生式来确定。(1)A-B.刻划产生式A-B的右部B已出现在栈顶。(2)A-

5、Bi.fh亥ij划A-B1B2的右部子串Bi已出现在栈顶，期待从输入串中看到B2推出的符号。(3)A->.P刻划没有句柄的任何符号在栈顶，此时期望A-B的右部所推出的符号串。(4)对于A-£的LR(0)项日只有A-.。设文法G二(Vt，Vn,S,P)是一个上下文无关文法，若存在一个规范推导S=>aAw=>apip2w(其屮A—pip2wP)，则称项口A—>卩1•卩2对活前缀y=api是有nnnn效的，即LR(0)有效项目。从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项H中的圆点可看成是分析栈栈顶与输入串的分界

6、线，圆点左边为己进入分析栈的部分，右边是当前输入或继续扫描的符号串。不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同,将其分为四类:(1)归约项表现形式：A->a.这类LR(0)项日表示句柄a恰好包含在栈屮，即当前栈顶的部分内容构成了所期望的句柄，应按A-a进行归约。(2)接受项th表现形式：S-a.其屮S是文法惟一的开始符号。这类LR(0)项口实际是特殊的归约项目，表示分析栈屮内容恰好为a,用S-a进行归约，则整个分析成功。(3)移进项目:表现形式：A-*a.b0(bGVT)这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为

7、构成恰好有句柄的活前级，需将b移进分析栈。(4)待约项目：表现形式：A->a.BP(BgVn)这类LR(0)项冃表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串屮的相应内容先归约到Bo在给出LR(0)项冃的定义和分类Z后，我们从这些LR(0)项冃出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限口动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。由文法G的LR(0)项冃构造识别文法G的所有活前缀的非确定有限自动机的方法：(1)规定含有文法开始符号的产生式(设A)的第一个LR