第六七章作业与习题参考答案.docx

资源描述

第六七章作业与习题参考答案.docx

《第六七章作业与习题参考答案.docx》由会员分享，可在线阅读，更多相关《第六七章作业与习题参考答案.docx（27页珍藏版）》请在冰点文库上搜索。

第六七章作业与习题参考答案.docx

第六七章作业与习题参考答案

第七章LR分析法

第1题已知文法

　　A→aAd|aAb|ε

　　判断该文法是否是SLR

（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。

文法：

　　A→aAd|aAb|ε

　　拓广文法为G′，增加产生式S′→A

　　若产生式排序为：

　　0　S'→A

　　1　A→aAd

　　2　A→aAb

　　3　A→ε

　　由产生式知：

　　First（S'）={ε,a}

　　First（A）={ε,a}

　　Follow（S'）={#}

　　Follow（A）={d,b,#}

　　G′的LR（0）项目集族及识别活前缀的DFA如下图所示：

在I0中：

A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR（0）文法。

在I0、I2中：

Follow（A）∩{a}={d，b，#}∩{a}=

所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR

（1）文法。

构造的SLR

（1）分析表如下：

题目1的SLR

（1）分析表

状态（State）

Action

Goto

a　　　d　　b　　#　

S2　　r3　　r3　　r3

　　　　　　　　　acc

S2　　r3　　r3　　r3

S4　　S5

　　　r1　　r1　　r1

　　r2　　r2　　r2

题目1对输入串ab#的分析过程

状态栈（statestack）

文法符号栈

剩余输入串

（inputleft）

动作（action）

Goto

023

0235

#aA

#aAb

ab#....

b#....

#....

r3（A→ε）

r2（A→aAb）

acc

分析成功，说明输入串ab是题目1文法的句子

第2题若有定义二进制数的文法如下：

　　S→L.L|L

　　L→LB|B

　　B→0|1

（1）试为该文法构造LR分析表，并说明属哪类LR分析表。

（2）给出输入串101.110的分析过程。

　解：

文法：

　　S→L.L|L

　　L→LB|B

　　B→0|1

　　拓广文法为G′，增加产生式S′→S

　　若产生式排序为：

　　0　S'→S

　　1　S→L.L

　　2　S→L

　　3　L→LB

4　L→B

　　5　B→0

　　6　B→1

　　由产生式知：

　　First（S'）={0,1}

　　First（S）={0,1}

　　First（L）={0,1}

　　First（B）={0,1}

　　Follow（S'）={#}

　　Follow（S）={#}

　　Follow（L）={.,0,1,#}

　　Follow（B）={.,0,1,#}

　　G′的LR（0）项目集族及识别活前缀的DFA如下图所示：

在I2中：

B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约冲突，因此所给文法不是LR（0）文法。

在I2、I8中：

Follow（s）∩{0，1}={#}∩{0，1}=

所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR

（1）文法。

构造的SLR

（1）分析表如下：

题目2的SLR

（1）分析表

状态（State）

Action

Goto

·　　0　　　1　　#

S　L　B

S4　　S5

　　　　　　　　　acc

S6　　S4　　S5　　r2

r4　　r4　　r4　　r4

r5　　r5　　r5　　r5

r6　　r6　　r6　　r6

S4　　S5

r3　　r3　　r3　　r3

　　　S4　　S5　　r1

1　2　3

　　8　3

题目2对输入串101.110#的分析过程

状态栈（statestack）

文法符号栈

剩余输入串

（inputleft）

动作（action）

024

027

025

027

026

0265

0263

0268

02685

02687

0268

02684

02687

#L0

#LB

#L1

#LB

#L.

#L.1

#L.B

#L.L

#L.L1

#L.LB

#L.L

#L.L0

#L.LB

101.110#....

01.110#....

1.110#....

.110#....

110#....

10#....

0#....

#....

Shift

Reduceby:

B→1

Reduceby:

S→LB

Shift

Reduceby:

B→0

Reduceby:

S→LB

Shift

Reduceby:

B→1

Reduceby:

S→LB

Shift

Reduceby:

B→1

Reduceby:

S→B

Shift

Reduceby:

B→1

Reduceby:

S→LB

Shift

Reduceby:

B→0

Reduceby:

S→L.L

分析成功，说明输入串101.110是题目2文法的句子。

3．考虑文法：

SAS|bASA|a

（1）列出该文法所有的LR（0）项目。

（2）按

（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。

（3）此文法是SLR

（1）的吗？

，若是，构造他的SLR分析表

（4）这个文法是LALR或LR

（1）的吗？

解：

（1）构造增广文法，S’S

文法的LR（0）项目有：

1.S’.S2.S’S.3.S.AS4.SA.S

5.SAS.6.S.b7.Sb.8.A.SA

9.AS.A10.ASA.11.A.a12.Aa.

（2）所产生的NFA略。

由规则构造所需的DFA:

SSA

ASS

则LR（0）项目集规范族为：

C＝｛I0,I1,I2,I3,I4,I5,I6,I7｝

（3）可以看到I1,I6,I7存在着移进－归约的冲突。

冲突是不能用SLR

（1）的方法来解决。

比如I6:

对于状态SAS.和S.b

Follow（S）={#,a,b}与{b}相交不为空。

所以以上文法不是SLR

（1）文法。

（4）为验证该文法是否为LALR或LR

（1）的，构造LR

（1）项目集。

对于I5,产生了移进－归约矛盾，所以这个文法不是LR

（1）文法。

于是也不是LALR文法。

第6题

　　文法：

　　S→UTa|Tb

　　T→S|Sc|d

　　U→US|e

　　拓广文法为G'，增加产生式S'→S

　　若产生式排序为：

　　0　S'→S

　　1　S→UTa

　　2　S→Tb

　　3　T→S

　　4　T→Sc

　　5　T→d

　　6　U→US

　　7　U→e

　　由产生式知：

　　First（S'）={d,e}

　　First（S）={d,e}

　　First（U）={e}

　　First（T）={d,e}

　　Follow（S'）={#}

　　Follow（S）={a,b,c,d,e,#}

　　Follow（U）={d,e}

　　Follow（T）={a,b}

　　G′的LR（0）项目集族及识别活前缀的DFA如下图所示：

在I1中：

S'→S.为接受项目，T→S.为归约项目，T→S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR（0）文法。

在I1中：

Follow（S'）∩Follow（T）={#}∩{a，b}=

Follow（T）∩{c}={a，b}∩{c}=

在I8中：

Follow（U）∩Follow（T）∩{c}={d,e}∩{a，b}∩{c}=

所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR

（1）文法。

构造的SLR

（1）分析表如下：

题目3的SLR

（1）分析表

状态（State）

Action

Goto

a　　b　　c　　d　　e　　　#

S　U　T

　　　　　　S5　　S4

r3　　r3　　S6　　　　　　　　Acc

　　　　　　S5　　S4

S9..................

　　　　　　r7　　r7

r5　　r5........................

r4　　r4.........................

S10　　S9.........................

r3　　r3.　　S6　　r6　　r6......

r2　　r2.　　r2　　r2　　r2　　r2

r1　　r1.　　r1　　r1　　r1　　r1

1　2　3

8　2　7

第8题

　　文法：

SA#　　A→BaBb|DbDa　　B→ε　　D→ε

　证明该文法是LR

（1）但不是SLR

（1）。

　　解：

若产生式排序为：

　　0　S'→A#　　1　A→BaBb　　2　A→DbDa　　3　B→ε　　4　D→ε

　　由产生式知：

　　First（S'）={a,b}

　　First（A）={a,b}

　　First（B）={ε}

　　First（D）={ε}

　　Follow（S'）={#}

　　Follow（A）={#}

　　Follow（B）={a,b}

　　Follow（D）={a,b}

　　G′的LR

（1）项目集族及识别活前缀的DFA如下图所示：

在I0中：

B→.,a和T→.，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B→ε归约，为b时用产生式D→ε归约，所以该文法是LR

（1）文法。

若不看搜索符，在I0中项目B→.和T→.为归约-归约冲突，而

Follow（B）∩Follow（D）={a,b}∩{a,b}≠

，冲突不能用Follow集解决，所以该文法不是SLR

（1）文法。

构造的LR

（1）分析表如下：

题目4的LR

（1）分析表

State

Action

Goto

a　.　b　.　#

A　　B　　D

r3　　r4......

　　　　　　Acc

S4............

r4............

S9............

1　　2　　3

10．判断下列各题所示文法是否为LR类文法，若是请说明是LR（0）、SLR

（1）、LALR

（1）或LR

（1）的哪一种，并构造相应分析表

（１）SABAaBa|εBbAb|ε

（3）SaAd|eBd|aBr|eArAaBa

（5）AaB|εBAb|a

（6）S（SR|aR.SR|）

（1）解：

对于该文法构造LR（0）项目规范族：

I0:

S’.SI1:

S’S.I3:

Aa.BaI5:

Bb.AbI6:

AaB.a

S.ABI2:

SA.BB.bAbA.aBaI7:

AaBa.

A.aBaB.bAbB.A.I8:

BbA.b

A->.B.I4:

SAB.I9:

BbAb.

可见存在着移进－归约冲突，这个文法不是LR（0）文法。

考虑用SLR

（1）来解决问题：

构造SLR

（1）分析表，发现该文法是SLR

（1）文法。

状态

ACTION

GOTO

acc

（3）解：

先构造该文法的LR（0）项目集规范族：

I0:

S’.SI1:

S’S.I3:

Se.BdI5:

SaB.rI9:

SaAd.

S.AdI2:

Sa.AdB.aI6:

Aa.I10:

SaBr.

S.eBdSa.BrSe.ArBa.I11:

SeBd.

S.aBrA.aA.aI7:

SeB.dI12:

SeAr.

S.eArB.aI4:

SaA.dI8:

SeA.r

该文法存在着归约-归约冲突，所以不是LR（0）文法。

对于状态I6:

Aa.

Ba.

Follow（A）={dr}Follow（B）={dr}

两个集合相交不为空，所以该文法也不是SLR

（1）文法。

构造该文法的LR

（1）文法可得该文法是LR

（1）的。

I0:

S’S,#I2:

Sa.Ad,#I4:

SaA.d,#I10:

SaAd.,#

S.aAd,#Sa.Br,#I5:

SaB.r,#I11:

SaBr.,#

S.eBd,#A.a,dI6:

Aa.,dI12:

SeBd.,#

S.aBr,#B.a,rBb.,rI13:

SeAr.,#

S.eAr,#I3:

Se.Bd,#I7:

SeB.d,#

I1:

S’S.,#Se.Ar,#I8:

SeA.r,#

B.a,dI9:

Ba.,d

A.a,rAa.,r

构造LR

（1）分析表（略）。

（5）解：

构造LR（0）的分析表：

I0:

S.AI3:

S->aB.I6:

B->AB.

A.aBI4:

B->A.b

A.I5:

B->a.

I1:

S->A.A->a.B

I2:

S->a.BB->.Ab

B->.AbB->.a

B->.aA->.aB

A->.aBA->.

A->.

可以看到存在着移进－归约的冲突，不是LR（0）文法。

在I0中Follow（A）与{ｂ}相交不为空。

所以也不为SLR

（1）文法。

构造该文法的LR

（1）项目集规范族：

I0:

S->.A,#I4:

B->A.b,#I9:

B->a.,b

A->.aB,#I5:

B->a.,#A->a.B,b

A->.,#A->a.B,bB->.Ab,b

I1:

S->A.,#B->.Ab,bB->.a,b

I2:

A->a.B,#B->.a,bA->.aB,b

B->.Ab,#,B->.aB,bA->.,b

B->.a,#A->.aB,bI10:

B->AB.,b

A->.aB,bI6:

B->Ab.,#

A->.,bI7:

A->aB.,b

I3:

A->aB.,#I8:

B->A.b,b

其中存在冲突，所以文法也不是LR

（1）文法。

（6）解：

将文法拓广后得：

（0）S’S

（1）S（SR

（2）Sa

（3）R.SR

（4）R）

构造LR（0）的项目集规范族：

一个文法是LR（0）文法一定也是SLR

（1）文法，也是LR

（1）文法。

但反之则不一定成立。

I0~~I9无冲突项目，所以此文法是LR（0）文法。

构造其LR

（1）的DFA（构造过程中，在建立好初态集后，立即产生所有新状态的核集合，然后再逐步扩充）：

状态

核集合

项目集（核集合+闭包增加项目）

S′→•S,#

S•S，#

S•（SR，#

S•a，#

SS•,#

S（•SR，#

S（•SR,#

S•（SR,./）

S•a,./）

S•a，#

S（S•R,#

R•.SR,#

R•）,#

S（•SR,./）

S•（SR,./）--I5

S•a,./）--I6

Sa•,./）

S（SR•,#

R.•SR,#

S•（SR,./）--I5

S•a,./）--I6

R）•,#

I10

S（S•R,./）

R•.SR,./）

R•）,./）

I11

R.S•R,#

R•.SR,#--I8

R•）,#--I9

I12

S（SR•,./）

I13

R.•SR,./）

S•（SR,./）--I5

S•a,./）--I6

I14

R）•,./）

I15

R.SR•,#

I16

R.S•R,./）

R•.SR,./）--I13

R•）,./）--I14

I17

R.SR•,./）

无移进-规约冲突和规约-规约冲突，此文法是LR

（1）文法。

对同心集合并，得LALR

（1）项目集规范族：

状态

核集合

项目集（核集合+闭包增加项目）

S′→•S,#

S•S，#

S•（SR，#

S•a，#

SS•,#

I2,5

S（•SR，#

S（•SR,./）/#

S•（SR,./）

S•a,./）

I3,6

S•a，#

S•a，./）/#

I4,10

S（S•R,#

S（S•R,./）/#

R•.SR,#

R•）,#

I7,12

S（SR•,#

S（SR•,./）/#

I8,13

R.•SR,#

R.•SR,./）/#

S•（SR,./）--I5

S•a,./）--I6

I9,14

R）•,#

R）•,./）/#

I11,16

R.S•R,#

R.S•R,./）/#

R•.SR,#--I8

R•）,#--I9

I15,17

R.SR•,#

R.SR•,./）/#

同心集合并后无冲突，其项目集的个数与LR（0）相同，此文法是LALR

（1）文法。

11.设文法G[S]为：

SAS|εAaA|b

（1）证明G[S]是LR

（1）文法

（2）构造出它的LR

（1）分析表

（3）给出输入符号串abab#的分析过程

一个文法不是SLR

（1）时，不能证明它是LR

（1）的

解：

将文法改写为拓广文法：

（0）S’→S

（1）SAS

（2）Sε（3）AaA（4）Ab

构造其LR

（1）项目集规范族：

状态

核集合

项目集（核集合+闭包增加项目）

S′→•S,#

S•S，#

S•AS，#

S•，#

A•aA,a/b/#

A•b,a/b/#

SS•,#

SA•S，#

S•AS，#--I2

S•，#

A•aA,a/b/#--I3

A•b,a/b/#--I4

Aa•A,a/b/#

A•aA,a/b/#--I3

A•b,a/b/#--I4

Ab•,a/b/#

SAS•，#

AaA•,a/b/#

（1）分析表：

状态

ACTION

GOTO

acc

对abab#的分析过程：

步骤

状态栈

符号栈

输入串

ACTION

GOTO

abab#

bab#

034

#ab

ab#

036

#aA

ab#

展开阅读全文

第六七章 作业与习题参考答案.docx

第六七章作业与习题参考答案.docx