LR0项目集族和LR0分析表的构造课件

第五章语法分析5.1自下而上分析基本问题5.2算符优先分析

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

:符号串的头活前缀

:规范句型的一个前缀,这种前缀不包含句柄之后的任何符号.*可归前缀:包含句柄的活前缀.一、前缀、活前缀前缀:符号串的头规范

推导

序列 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当栈顶出现可归前缀即可归约规范

推导

序列 S =>aAcBeε,a步骤符号栈剩余输入串动作1#abbcde#移进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#的规范归约过程步符号栈剩余动作1#abbcde#移进2#abbcde#移进S'=>S=>aAcBe=>aAcde=>aAbcde=>abbcde规范

推导

序列识别句型#abbcde#所有活前缀的DFASabaAbaAcdaAcBeεεεεε确定化最小化0245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]利用DFA进行移近-归约分析(见黑板)S'=>S规范

推导

序列识别句型#abbcde#所有活前acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩阵表示一个LR分析器实质上是一个DFAacebd#SAB0211234346556787小结识别文法所有活前缀的DFALR分析表LR分析小结识别文法所有活前缀的DFALR分析表LR分析二、构造识别文法所有活前缀的DFA

1.LR(0)项目2.构造识别文法所有活前缀的DFA3.LR(0)项目的分类求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串二、构造识别文法所有活前缀的DFA1.LR(0)项目求出1.LR(0)项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A→ε,仅有项目A→·

例:产生式AXYZ

对应的项目有

A·XYZ AX·YZ AXY·Z AXYZ·一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关1.LR(0)项目在文法G中每个产生式的右部适当位置添加一补充例对应的项目:(1)S·aAd (2)Sa·Ad (3)SaA·d (4)SaAd·

(5)A·bc(6)Ab·c(7)Abc·借助项目构造识别文法活前缀的DFAG:

SaAd

Abc补充例对应的项目:2.构造识别文法所有活前缀的DFA1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系3).确定化最小化2.构造识别文法所有活前缀的DFA1).文法的每个项目都例5.8p105G':

S'→E

E→aA|bB

A→cA|d

B→cB|d更正1．S'→·E

2．S'→E· 11.E→·bB

3．E→·aA

12.E→b·B

4．E→a·A

13.E→bB·

5．E→aA·

14.B→·cB

6．A→·cA

15.B→c·B

7．A→c·A

16.B→cB·

8．A→cA·

17.B→·d

9．A→·d

18.B→d·10.A→d·文法的项目:1).文法的每个项目都为NFA的一个状态例5.8p105G': 2).确定状态之间的转换关系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ状态i状态j出自同一产生式2).确定状态之间的转换关系XiX→X1X2…Xi-1·X项目1为初态

P106NFA1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·每个状态都为活前缀识别态◎句柄识别态(可归前缀识别态):圆点在最后的项目句子识别态

aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε项目1P106NFA1．S'→·E每个状态都为活前缀识别态p106识别一个文法活前缀的DFA3).确定化

最小化每个状态是一个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族p106识别一个文法活前缀的DFA3).确定化

3.LR(0)项目的分类移进项目:

A→α·aβ

分析时把a移进符号栈待约项目:

A→α·Bβ 用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析归约项目:

A→α·

表明一个产生式的右部已分析完，句柄已形成可以归约接受项目:

S'→S·

表明已分析成功3.LR(0)项目的分类移进项目:A→α·aβ 三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三1.拓广文法2.项目集I的闭包函数CLOSURE(I)3.状态转换函数GO(I,X)4.构造文法的LR(0)项目集规范族1.拓广文法21可编辑21可编辑1.拓广文法原文法G的开始符号为S,在G中加S'→S

后得新的文法G'， 则称 G'为原文法G的拓广文法。使文法的开始符号不出现在任何产生式右部，当栈顶出现S′,则分析完成。注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。1.拓广文法原文法G的开始符号为S,2.项目集I的闭包函数CLOSURE(I)a)I的项目均在CLOSURE(I)中。b)

若A→α·Bβ属于CLOSURE(I),则每一形如B→·γ的项目也属于CLOSURE(I)c)

重复b)直到CLOSURE(I)不再扩大。NFA:状态集合I的ε-闭包ε-closure(I)εA→α·BβB→·γ2.项目集I的闭包函数CLOSURE(I)a)I的项目aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε补充例I＝{S'→·E}CLOSURE(I)={S'→·E,E→·aA,E→·bB}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311aεεE*εεεεεεεAcAddcBbB7863410593.状态转换函数GO(I,X)GO(I,X)=CLOSURE(J)

,X∈(VN∪VT), J={A→αX·β|A→α·Xβ∈I}XA→α·XβA→αX·β若状态I识别活前缀γ,则状态J识别活前缀γX

状态I状态JNFA:状态集合I的a弧转换3.状态转换函数GO(I,X)GO(I,X)=CLaεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε补充例I＝{S'→·E,E→·aA,E→·bB

}GO(I,a)=CLOSURE({E→a·A}) ={E→a·A

,A→·cA,A→·d

}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311469aεεE*εεεεεεεAcAddcBbB7863410594.构造文法的LR(0)项目集规范族C={I0,I1,……,In}核:圆点不在产生式右部最左边的项目称为核a)置项目S'→·S为初态集的核，然后对核求闭包，CLOSURE({S'→·S}）得到初态的项目集。b)对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)求出新状态J的项目集。c)重复b)直到不出现新的项目为止。4.构造文法的LR(0)项目集规范族C={I0,I1,……算法Procedureitemsets(G')

Begin C:={CLOSURE({S'·S})}

Repeat

for

C中的每一个I和每一个X

do

if

GO(I,X)非空且不属于Cthen

把GO(I,X)放入C中

until

C不再增大endp107初态的项目集应用状态转换函数得到新的项目集算法Procedureitemsets(G')G':

S'→E

E→aA|bB

A→cA|d B→cB|dI0:

S'•E

E•aAE•bBI8:

Bc•B

B•cBB•dI3:

Eb•B

B•cBB•dI2:Ea•A

A•cAA•dI1:

S'E•I5:Ac•A

A•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B识别文法所有活前缀的DFALR(0)项目集规范族{I0,I1,…,I11}G':S'→EI0:S'•EI8:四、有效项目*如果存在规范推导则项目A1·2

对活前缀1

是有效的。如果2，应该移进如果2=

，应该用产生式A1归约*RR12AS'四、有效项目*如果存在规范推导*RR12AI0:S'•EE•aAE•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cAA•dI1:S'E•I4:Ac•A

A•cAA•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

BG':

S'→EE→aA|bBA→cA|dB→cB|d项目集I5对活前缀bc有效考虑如下规范推导(1)

SE

bB

bcB(2)

SE

bB

bcB

bccB(3)SE

bB

bcB

bcdI0:S'•EI5:Bc•BI3:Eb•B图5.7p106识别文法活前缀的DFA从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集I0:S'•E

E•aAE•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cAA•dI1:S'E•I4:Ac•A

A•cAA•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B图5.7p106识别文法从初态出发,经读出活前缀γ后,而到LR分析理论的一条基本定理p108在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。LR分析理论的一条基本定理p108在任何时候，分析栈中I0:S'•EE•aAE•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cA

A•dI1:S'E•I4:Ac•A

A•cAA•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B同一个项目可能对好几个活前缀都有效G':

S'→EE→aA|bBA→cA|dB→cB|dI0:S'•EI5:Bc•BI3:Eb•B同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号,或许能够获得解决。同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们移进-归约冲突

一个项目集中移进和归约项目同时存在： A→α·aβ B→γ·归约-归约冲突 一个项目集中归约和归约项目同时存在:

A→β· B→γ·五、LR(0)分析表的构造移进-归约冲突五、LR(0)分析表的构造LR(0)文法假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况 ①既含移进项目又含归约项目 ②或者含有多个归约项目 则称G是一个LR(0)文法。LR(0)文法规范族的每个项目集不包含任何冲突项目(移进-归约冲突、归约-归约冲突)。LR(0)文法假若一个文法G的拓广文法G的活前缀识别自动机LR(0)分析表的构造假设已构造出LR(0)项目集规范族为:C={I0,I1,…,In}令包含S'→·S

项目的集合Ik的下标k为分析器的初始状态。LR(0)分析表的构造假设已构造出LR(0)项目集规范族为:a)

若项目A→α·aβ属于Ik,且GO(Ik,a)=Ij

则置ACTION[k,a]为Sjb)

若项目A→α·

属于Ik，则对任何终结符a和‘#’

置ACTION[k,a]和ACTION[k,#]为“rj”,j为在文法G'中某产生式A→α的序号。c)若项目S'→S·

属于Ik, 则置ACTION[k,#]为“acc”/接受d)

若GO(Ik,A)＝Ij，则置GOTO[k,A]

为"j"e)

凡不能用上述方法填入的元素,均填上“报错标志”/“空白”a)若项目A→α·aβ属于Ik,且GO(Ik,a)I0:

S'•E

E•aAE•bBI8:

Bc•B

B•cBB•dI3:

Eb•B

B•cBB•dI2:Ea•A

A•cAA•dI1:

S'E•I5:Ac•A

A•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B(0)S'→E

(1)E→aA

(2)E→bB

(3)A→cA(4)A→d(5)B→cB(6)B→d构造LR(0)分析表过程见黑板I0:S'•EI8:Bc•BI3:Eb•B根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分析表为LR(0)分析表能用LR(0)分析表的分析器称为LR(0)分析器根据这种方法构造的LR(0)分析表不含多重定义时，称这样的分42可编辑42可编辑第五章语法分析5.1自下而上分析基本问题5.2算符优先分析

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

:符号串的头活前缀

:规范句型的一个前缀,这种前缀不包含句柄之后的任何符号.*可归前缀:包含句柄的活前缀.一、前缀、活前缀前缀:符号串的头规范

推导

序列 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当栈顶出现可归前缀即可归约规范

推导

序列 S =>aAcBeε,a步骤符号栈剩余输入串动作1#abbcde#移进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#的规范归约过程步符号栈剩余动作1#abbcde#移进2#abbcde#移进S'=>S=>aAcBe=>aAcde=>aAbcde=>abbcde规范

推导

序列识别句型#abbcde#所有活前缀的DFASabaAbaAcdaAcBeεεεεε确定化最小化0245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]利用DFA进行移近-归约分析(见黑板)S'=>S规范

推导

序列识别句型#abbcde#所有活前acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩阵表示一个LR分析器实质上是一个DFAacebd#SAB0211234346556787小结识别文法所有活前缀的DFALR分析表LR分析小结识别文法所有活前缀的DFALR分析表LR分析二、构造识别文法所有活前缀的DFA

1.LR(0)项目2.构造识别文法所有活前缀的DFA3.LR(0)项目的分类求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串二、构造识别文法所有活前缀的DFA1.LR(0)项目求出1.LR(0)项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目.对空产生式A→ε,仅有项目A→·

例:产生式AXYZ

对应的项目有

A·XYZ AX·YZ AXY·Z AXYZ·一个产生式可对应的项目个数是它的右部符号长度加1每个项目的含义与圆点的位置有关1.LR(0)项目在文法G中每个产生式的右部适当位置添加一补充例对应的项目:(1)S·aAd (2)Sa·Ad (3)SaA·d (4)SaAd·

(5)A·bc(6)Ab·c(7)Abc·借助项目构造识别文法活前缀的DFAG:

SaAd

Abc补充例对应的项目:2.构造识别文法所有活前缀的DFA1).文法的每个项目都为NFA的一个状态2).确定状态之间的转换关系3).确定化最小化2.构造识别文法所有活前缀的DFA1).文法的每个项目都例5.8p105G':

S'→E

E→aA|bB

A→cA|d

B→cB|d更正1．S'→·E

2．S'→E· 11.E→·bB

3．E→·aA

12.E→b·B

4．E→a·A

13.E→bB·

5．E→aA·

14.B→·cB

6．A→·cA

15.B→c·B

7．A→c·A

16.B→cB·

8．A→cA·

17.B→·d

9．A→·d

18.B→d·10.A→d·文法的项目:1).文法的每个项目都为NFA的一个状态例5.8p105G': 2).确定状态之间的转换关系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ状态i状态j出自同一产生式2).确定状态之间的转换关系XiX→X1X2…Xi-1·X项目1为初态

P106NFA1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·每个状态都为活前缀识别态◎句柄识别态(可归前缀识别态):圆点在最后的项目句子识别态

aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε项目1P106NFA1．S'→·E每个状态都为活前缀识别态p106识别一个文法活前缀的DFA3).确定化

最小化每个状态是一个项目集,称作LR(0)项目集整个状态集称为LR(0)项目集规范族p106识别一个文法活前缀的DFA3).确定化

3.LR(0)项目的分类移进项目:

A→α·aβ

分析时把a移进符号栈待约项目:

A→α·Bβ 用产生式A的右部归约时,首先要将B的产生式右部归约为B,对A的右部才能继续进行分析归约项目:

A→α·

表明一个产生式的右部已分析完，句柄已形成可以归约接受项目:

S'→S·

表明已分析成功3.LR(0)项目的分类移进项目:A→α·aβ 三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三种方法*求出活前缀的正规表达式，然后由此正规表达式构造NFA,再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前缀的NFA,再确定化为DFA。通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。三、LR(0)项目集规范族的构造构造识别文法活前缀DFA的三1.拓广文法2.项目集I的闭包函数CLOSURE(I)3.状态转换函数GO(I,X)4.构造文法的LR(0)项目集规范族1.拓广文法63可编辑21可编辑1.拓广文法原文法G的开始符号为S,在G中加S'→S

后得新的文法G'， 则称 G'为原文法G的拓广文法。使文法的开始符号不出现在任何产生式右部，当栈顶出现S′,则分析完成。注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。1.拓广文法原文法G的开始符号为S,2.项目集I的闭包函数CLOSURE(I)a)I的项目均在CLOSURE(I)中。b)

若A→α·Bβ属于CLOSURE(I),则每一形如B→·γ的项目也属于CLOSURE(I)c)

重复b)直到CLOSURE(I)不再扩大。NFA:状态集合I的ε-闭包ε-closure(I)εA→α·BβB→·γ2.项目集I的闭包函数CLOSURE(I)a)I的项目aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε补充例I＝{S'→·E}CLOSURE(I)={S'→·E,E→·aA,E→·bB}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311aεεE*εεεεεεεAcAddcBbB7863410593.状态转换函数GO(I,X)GO(I,X)=CLOSURE(J)

,X∈(VN∪VT), J={A→αX·β|A→α·Xβ∈I}XA→α·XβA→αX·β若状态I识别活前缀γ,则状态J识别活前缀γX

状态I状态JNFA:状态集合I的a弧转换3.状态转换函数GO(I,X)GO(I,X)=CLaεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε补充例I＝{S'→·E,E→·aA,E→·bB

}GO(I,a)=CLOSURE({E→a·A}) ={E→a·A

,A→·cA,A→·d

}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311469aεεE*εεεεεεεAcAddcBbB7863410594.构造文法的LR(0)项目集规范族C={I0,I1,……,In}核:圆点不在产生式右部最左边的项目称为核a)置项目S'→·S为初态集的核，然后对核求闭包，CLOSURE({S'→·S}）得到初态的项目集。b)对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)求出新状态J的项目集。c)重复b)直到不出现新的项目为止。4.构造文法的LR(0)项目集规范族C={I0,I1,……算法Procedureitemsets(G')

Begin C:={CLOSURE({S'·S})}

Repeat

for

C中的每一个I和每一个X

do

if

GO(I,X)非空且不属于Cthen

把GO(I,X)放入C中

until

C不再增大endp107初态的项目集应用状态转换函数得到新的项目集算法Procedureitemsets(G')G':

S'→E

E→aA|bB

A→cA|d B→cB|dI0:

S'•E

E•aAE•bBI8:

Bc•B

B•cBB•dI3:

Eb•B

B•cBB•dI2:Ea•A

A•cAA•dI1:

S'E•I5:Ac•A

A•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B识别文法所有活前缀的DFALR(0)项目集规范族{I0,I1,…,I11}G':S'→EI0:S'•EI8:四、有效项目*如果存在规范推导则项目A1·2

对活前缀1

是有效的。如果2，应该移进如果2=

，应该用产生式A1归约*RR12AS'四、有效项目*如果存在规范推导*RR12AI0:S'•EE•aAE•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cAA•dI1:S'E•I4:Ac•A

A•cAA•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

BG':

S'→EE→aA|bBA→cA|dB→cB|d项目集I5对活前缀bc有效考虑如下规范推导(1)

SE

bB

bcB(2)

SE

bB

bcB

bccB(3)SE

bB

bcB

bcdI0:S'•EI5:Bc•BI3:Eb•B图5.7p106识别文法活前缀的DFA从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集I0:S'•E

E•aAE•bBI5:Bc•B

B•cB

B•dI3:Eb•B

B•cB

B•dI2:Ea•A

A•cAA•dI1:S'E•I4:Ac•A

A•cAA•dI8:AcA•I10:Ad

•I6:EaA

•I7:EbB•I11:Bd

•I9:BcB•

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B图5.7p106识别文法从初态出发,经读出活前缀γ后,而到LR分析理论的一条基本定理p108在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。LR分析理论的一条基本定理p108在任何时候，分析栈中I0:S'•EE•aA