编译原理5.3.2-LR项目集族和LR分析表的构造

《编译原理5.3.2-LR项目集族和LR分析表的构造》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章语法分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC5.3LR分析5.3.1LR分析器5.3.2LR(0)项目集族＆LR(0)分析表的构造5.3.3SLR分析表的构造5.3.4规范LR分析表的构造5.3.5LALR分析表的构造5.3.6二义文法的应用5.3.2LR(0)项目集族＆LR(0)分析表的构造一、前缀、活前缀p104二、构造识别文法所有活前缀的DFAp104三、LR(0)项目集规范族的构造p106四、有效项目p108五、LR(0)分析表的构造p109一、前缀、活前缀前缀:符

2、号串的头活前缀:规范句型的一个前缀,这种前缀不包含句柄之后的任何符号.*可归前缀:包含句柄的活前缀.规范推导序列S=>aAcBe=>aAcde=>aAbcde=>abbcdeε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe活前缀可归前缀ab,aAb,aAcd,aAcBe补充例:找出句型#abbcde#的所有活前缀G:S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]abbcdeAABS当栈顶出现可归前缀即可归约步骤符号栈剩余输入串动作1#abbcd

3、e#移进2#abbcde#移进3#abbcde#归约A→b4#aAbcde#移进5#aAbcde#归约A→Ab6#aAcde#移进7#aAcde#移进8#aAcde#归约B→d9#aAcBe#移进10#aAcBe#归约S→aAcBe11#S#接受abbcdeAABS栈里的文法符号与剩余符号串一起构成了规范句型栈里的文法符号构成活前缀S=>aAcBe=>aAcde=>aAbcde=>abbcde规范推导序列#abbcde#的规范归约过程二、构造识别文法所有活前缀的DFA1.LR(0)项目2.构造识别文法所有活前缀

4、的DFA3.LR(0)项目的分类1.LR(0)项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A→ε,仅有项目A→·例:产生式AXYZ对应的项目有A·XYZAX·YZAXY·ZAXYZ·一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关补充例:若有产生式SaAd,Abc对应的项目:(1)S·aAd(2)Sa·Ad(3)SaA·d(4)SaAd·(5)A·bc(6)Ab·c(7)Abc·2.构造识别文法所有活前缀的DFA1).文法的每个项目

5、都为NFA的一个状态2).确定状态之间的转换关系3).确定化最小化例5.8p105G':S'→EE→aA

6、bBA→cA

7、dB→cB

8、d更正1．S'→·E2．S'→E·11.E→·bB3．E→·aA12.E→b·B4．E→a·A13.E→bB·5．E→aA·14.B→·cB6．A→·cA15.B→c·B7．A→c·A16.B→cB·8．A→cA·17.B→·d9．A→·d18.B→d·10.A→d·文法的项目:1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系XiX→X1X2…Xi-1·Xi…X

9、nX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ状态i状态j出自同一产生式项目1为初态P106NFA1．S'→·E2．S'→E·3．E→·aA4．E→a·A5．E→aA·6．A→·cA7．A→c·A8．A→cA·9．A→·d10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B16.B→cB·17.B→·d18.B→d·每个状态都为活前缀识别态◎句柄识别态(可归前缀识别态):圆点在最后的项目句子识别态p106识别一个文法活前缀的DFA3).确定化最小化每个状态是一

10、个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族3.LR(0)项目的分类移进项目:A→α·aβ分析时把a移进符号栈待约项目:A→α·Bβ用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析归约项目:A→α·表明一个产生式的右部已分析完，句柄已形成可以归约接受项目:S'→S·表明已分析成功三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀

11、的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。1.拓广文法2.项目集I的闭包函数CLOSURE(I)3.状态转换函数GO(I,X)4.构造文法的LR(0)项目集规范族1.拓广文法原文法G的开始符号为S,在G中加S'→S后得新的文法G'，则称G‘为原文法G的拓广文法