LR文法分析.docVIP

实验名称：LR（0）文法分析 实验目的： 输入：任意的压缩了的上下文无关文法。 输出：相应的LR（0）分析表。 二、实验原理： 对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念——文法的规范句型“活前缀”。 这种句柄之后不含任何符号的前缀称为活前缀。 在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。 对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。 假若一个文法G的拓广文法的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。该自动机的状态集合即为该文法的LR（0）项目集规范族。 构造识别文法活前缀DFA有3种方法： （1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA； （2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA； （3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。 符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。 活前缀与句柄的关系如下： （1）活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。 （2）活前缀只含句柄的一部分符号，表明A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。 （3）活前缀不含有句柄的任何符号，此时期望A→β的右部所推出的符号串。 在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式A( xyz有如下项目：A(.xyz，A(x.yz，A(xy.z，A(xyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。 （1）A→β.刻划产生式A→β的右部β已出现在栈顶。 （2）A→β1.β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。 （3）A→.β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串。 （4）对于A→ε的LR(0)项目只有A→．。 设文法G=（VT，VN，S，P）是一个上下文无关文法，若存在一个规范推导SAw12w（其中A12P），则称项目A12对活前缀=1是有效的，即LR(0) 有效项目。 从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。 不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类： （1）归约项目： 表现形式：A→a. 这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按A→a进行归约。 （2）接受项目： 表现形式：→a. 其中是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a，用→a进行归约，则整个分析成功。 （3）移进项目： 表现形式：A→a.（bVT） 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。 （4）待约项目： 表现形式：A→α.Bβ （BVN） 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。 在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。 由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法： （1）规定含有文法开始符号的产生式（设→A）的第一个L