编辑: wtshxd 2019-07-17

且只能识别活前缀.LR(0)项目规范族C={DFA的状态}LR(0)有效项目项目A????,如果有则项目A???? 对活前缀??有效.对同一活前缀有效的(多个)LR(0)项目均在同一个项目集合(状态)中;

而且同一LR(0)项目可以对多个活前缀有效(即该项目可以出现在不同的项目集合中). LR(0)有效项目如果项目A???B?对活前缀??有效,即有最右推导如果B??∈P 则有以下最右推导, 显然,项目B???对活前缀??也有效.项目A???B?和B???应在同一个状态(项目集合) 这就是closure()函数 LR(0)有效项目如果项目A???X?∈I对活前缀??有效,则项目A??X??∈J=goto(I,X)显然对活前缀??X有效. e.g.22 识别文法G2活前缀的DFA 拓展文法G2(0)E'

?E(1)E?E + T(2)E?T(3)T?T * F(4)T?F(5)F?( E )(6)F? id DFA的初态I0= closure({E'

??E})E'

? ? EE ? ? E + TE ? ? TT ? ? T * FT ? ? FF ? ? ( E )F ? ? id I1:E'

?E ? E ?E ? + T I2:E?T? T?T? * F I3:T ? F ? I4:F?(?E) E??E + T E??T T??T * F T??F F??(E) F??id I5:F ? id ? I0:E'

? ? E E ? ? E + T E ? ? T T ? ? T * F T ? ? F F ? ? (E) F ? ? id I7:T?T * ?F F??(E) F??id I6:E?E + ? T T??T * F T??F F??(E) F??id I8:F?(E?) E?E ? + T I11:F?(E) ? I9:E?E + T ? T?T ? * F I10:T?T*F? E T id F ( + * ( E T F id T F ( id F ( id ) + * e.g.23 对活前缀E+T*有效的LR(0)项目 E+T*的识别路径:I0->

E I1->

+ I6->

T I9->

* I7项目集合(状态)I7中的项目对E+T*有效: T?T *?F F??(E)F??id E?E+T ?E+T*?F E?E+T ?E+T*F ?E+T*?(E) E?E+T ?E+T*F ?E+T*?id ?=E+ ?= T* ?=F ?=E+T* ?= ? ?=(E) 或id LR(0)分析仅取决于当前(栈顶)状态,由状态本身所包含的信息决定下一步动作.如, LR(0)分析方法 I7:T?T * ?F // 转移 F??(E)移进下一输入符号 F??id // 移进下一输入符号 至于移入栈顶的符号不是 ( 或id,则报错 I10:T?T*F? // 归约(不论下一输入符号是谁) LR(0)分析方法 LR(0)分析表的构造- 若A???a?∈I,且goto(I,a)=J,则action[I,a]=sJ - 若A??? ∈ I,则action[I,a] = r A??,a∈VT或$- 若S'

?S? ∈ I,则action[I,$] = acc- 若goto(I,B)=K,则GOTO[I,B]=K- 其它为空白/error文法G是LR(0)的,如果它的LR(0)分析表项没有多重定义-即动作冲突;

或者它的LR(0)项目规范族中的任一状态不能同时含有移进和归约的LR(0)项目.e.g.23中表达式文法G2不是LR(0)文法.如状态I

1、I

2、I9中有移进-归约冲突.(分析表略) SLR(1)分析 LR(0)分析能力很弱!解决LR(0)分析冲突通过向前看一个符号(当前输入符)来解决-移进-归约冲突 若状态I中同时含有移进和归约的LR(0)项目,如, A???a? B??? 则 约定仅在当前输入符号∈Follow(B)时进行归约-因为完成B的分析后,读到的输入符号应该是B的后继符号.而当前输入符号是a时则进行移进.如果a∈ Follow(B),冲突仍然存在! SLR(1)分析 解决LR(0)分析冲突通过向前看一个符号(当前输入符)来解决-归约-归约冲突 若状态I中同时含有两个(或两个以上)归约LR(0)项目,如,A??? B??? 则 约定仅在当前输入符号∈Follow(A)时进行按A??归约;

仅当前输入符号∈Follow(B)时进行按B??归约;

如果Follow(A)? Follow(B) ? ?,冲突仍然存在! SLR(1)分析 SLR(1)分析表构造- 若A???a?∈I,且goto(I,a)=J,则action[I,a]=sJ - 若A??? ∈ I,则action[I,b] = r A??,b∈Follow(A)- 若S'

?S? ∈ I,则action[I,$]........

下载(注:源文件不在本站服务器,都将跳转到源网站下载)
备用下载
发帖评论
相关话题
发布一个新话题