LR(0)文法分析

《LR(0)文法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、------------------------------------------作者xxxx------------------------------------------日期xxxxLR(0)文法分析【精品文档】实验名称：LR（0）文法分析一、实验目的：输入：任意的压缩了的上下文无关文法。输出：相应的LR（0）分析表。二、实验原理：对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念——文法的规范句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2…Xm应该构

2、成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。假若一个文法G的拓广文法的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。该自动机的状态集合即为该文

3、法的LR（0）项目集规范族。构造识别文法活前缀DFA有3种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA；（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所

4、以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。活前缀与句柄的关系如下：（1）活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。（2）活前缀只含句柄的一部分符号，表明A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。【精品文档】【精品文档】（3）活前缀不含有句柄的任何符号，此时期望A→β的右部所推出的符号串。在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式A®xyz有如下项目：A®.xyz，A®，A®，A®xyz.。为刻划分析过程中的文法的每一个产生式的右部符

5、号已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。（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)项目指明了在分析过程中的某一步我们看到产生式的多大部

6、分被识别，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)项目表示

7、分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。（4）待约项目：表现形式：A→α.Bβ（BVN）这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。在给出LR(0)项目的定义和分类之后，我们从这些LR(0)【精品文档】【精品文档】项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所