作业题解答.docx

作业题解答.docx

《作业题解答.docx》由会员分享，可在线阅读，更多相关《作业题解答.docx（22页珍藏版）》请在冰点文库上搜索。

作业题解答

作业题：

文法与语言部分：

P45第5

（1）

（2）题

解：

（1）引入符号类标记d表示1~9中任一数字；引入符号类标记f表示0,2,4,6,8中任一数字。

则可用正规式r=d*|f刻划上述语言。

由r构造出的等价文法为：

G[S]其中P集如下：

S→f|dS。

（2）引入符号类标记d表示1~9中任一数字；引入符号类标记f表示0,2,4,6,8中任一数字。

则可用正规式r=（d0*）*（d0*0|f）刻划上述语言。

由r构造出的等价右线性文法为：

G[S]其中P集如下：

S→CAA→dB|fB→0B|0C→DC|εD→dEE→0E|ε

2、P45第7题（用S取代表达式）

证明：

构造文法Σ上的符号串i+i*i。

由于上述文法对该符号串存在如下两棵语法树：

故证得该文法是一个二义文法。

3、P45第11题

解：

（1）证明：

∵E＝〉E+T＝〉E+T*F即存在从文法开始符到该符号串的推导。

∴命题得证。

（2）该句型的语法树为：

∴该句型的所有短语为：

T*F、E+T*F

该句型的直接短语为：

T*F

该句型的句柄为：

T*F

4、P45第13题

（1）、解：

最左推导：

S⇒ABS⇒aBS⇒aSBBS⇒aBBS⇒abBS⇒abbS⇒abbAa⇒abbaa

最右推导：

S⇒ABS⇒ABAa⇒ABaa⇒ASBBaa⇒ASBbaa⇒ASbbaa⇒Abbaa⇒abbaa

（2）解：

P：

{S→ABS,A→a,B→SBB,S→ε,B→b,S→Aa}

（3）解：

短语有：

a,b,bb,aa,abbaa；直接短语：

a,b；句柄：

a

补1、消除下列文法中多余ε—产生式。

S→aAS|bA→cS|ε

解：

由算法令：

W1={A}则W2={A}=W1∴W={A}∵S∈W∴ε∈L（G）考察文法中每一产生式进行等价改造如下：

S→aAS∵a∈WA∈WS∈W∴将A取A与ε代入得：

S—>aSS—>aAS

S→b∵b∈W∴S—>b

A→cS∵c∈WS∈W∴A—>cS

A→ε∴消去

综上所述改造后的等价文法为：

G’[S]其P’如下：

S—>aSS—>aASS—>bA—>cS

补2、消除下列文法G[S]中的有害、多余产生式。

P：

S→aB|BCA→aA|d|aDbB→DB|CD→BC→b

解：

由于P中不含有X—>X形式的产生式故无有害产生式。

由算法：

消除不可终止的产生式如下：

令V’N={}∵A—>d∈VTC—>d∈VT∴V’N={A,C}又∵S—>aB有a∈VTB∈V’N∴V’N={A,C,S,B}又∵D—>B∈V’N∴V’N={A,C,S,B,D}=VN∴该文法不含不可终止的产生式。

消除不可达的产生式如下：

由算法令V’N={S}规则1{S,B,C}规则2.1{S,B,C,D}V’T={}规则1{a}规则2.2{a,b}∵S∈V’N中考察

S—产生式S→aB|BC∴B,C∈V’Na∈V’T又B∈V’N中考察B—产生式B→DB|C∴D∈V’N

又C∈V’N中考察C—产生式C→b∴b∈V’T又D∈V’N中考察D—产生式D→B∴B∈V’N至此V’N不再增大。

考察P中每一产生式：

S→aB|BC∵S,B,C∈V’Na∈V’T∴S—产生式均在P’中；

A→aA|d|aDb∵A∈V’N∴A—产生式均不在P’中；B→DB|C∵D,B,C∈V’N∴B—产生式均在P’中；C→b∵b∈V’T∴C—产生式均在P’中；D→B∵B∈V’N∴B—产生式均在P’中。

综上所述化简后等价文法为G’[S]其P：

S→aB|BCB→DB|CD→BC→b。

词法分析部分：

1、P66第1、

（1）题

解：

思路：

正规式—>NFA—>DFA—>最小DFA—>状态转换矩阵

正规式—>NFA：

由算法三条规则构造如下：

给状态命名并整理得NFA如下：

NFA—>DFA：

由算法构造如下：

ε_closure（0）={0}未标记，标记为：

q0;含初态对应DFA部分为：

T={q0，0}=φT={q0，1}={1}

ε_closure（{q0，1}）={1,2,3}未标记，标记为：

q1；对应DFA部分为：

ε_closure（{q1，0}）={2,3}未标记，标记为：

q2；对应DFA部分为：

ε_closure（{q1，1}）={2,3,4}未标记，标记为：

q3；对应DFA部分为：

ε_closure（{q2，0}）={2,3}已标记为：

q2；对应DFA部分为：

ε_closure（{q2，1}）={2,3,4}已标记为：

q3；对应DFA部分为：

ε_closure（{q3，0}）={2,3,5}未标记，标记为：

q4；对应DFA部分为：

ε_closure（{q3，1}）={2,3,4}已标记为：

q3；对应DFA部分为：

ε_closure（{q4，0}）={2,3}已标记为：

q2；对应DFA部分为：

ε_closure（{q4，1}）={2,3,4,6,}未标记，标记为：

q5；包含终态对应DFA部分为：

ε_closure（{q5，0}）={2,3,5}已标记为：

q4；对应DFA部分为：

ε_closure（{q5，1}）={2,3,4}已标记为：

q3；对应DFA部分为：

至此不再有未标记的状态。

因而，

DFA构造结束，对DFA重命名得DFA如下：

DFA—>最小DFA：

由算法构造如下：

为方便求解首先构造DFA的状态转换矩阵如下：

接受符

状态

0

1

0（初态）

1

1

2

3

2

2

3

3

4

3

4

2

5

5（终态）

4

3

记π=π0：

{0，1，2，3，4}、{5}考察{0，1，2，3，4}∵{0}0=φ而{1，2，3，4}0={3，5}≠φ∴划分出0状态形成新的划分πnew={0}、{1，2，3，4}、{5}≠π故记πnew=π重新考察π；{1，2，3，4}∵{4}1={5}而{1，2，3}1={3}∴划分出4状态形成新的划分πnew={0}、{1，2，3}、{4}、{5}≠π故记πnew=π重新考察π；{1，2，3}∵{1，2}0={2}而{3}0={4}∴划分出3状态形成新的划分πnew={0}、{1，2}、{3}、{4}、{5}≠π故记πnew=π重新考察π；{1，2}∵{1，2}0={2}又{1，2}1={3}∴1、2状态不可区分。

至此，πnew=π划分结束。

将1、2状态合并取2状态作为代表状态。

作上述处理后并对状态名重新命名后所获得的最小DFA见下图：

最小DFA状态转换矩阵为：

∑

状态

0

1

0（初态）

1

1

1

2

2

3

2

3

1

4

4（终态）

3

2

2．P67第7题

解：

思路：

化简G－＞NFA－＞DFA－＞最小DFA

化简：

有害规则：

无；不可终止：

无；不可达：

E、F

故化简为文法G[s]为：

P：

S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aA

构造G[s]－＞NFA

构造相应等价DFA的状态转换图为（图1）详细解答过程同上题（略）

等价的最小DFA的状态转换图为（图2）其等价的状态转换矩阵见下表：

详细解答过程同上题（略）

状态

Σ

0

1

2

3

a

1

1

1

1

b

1

2

3

3

补1、有状态转换矩阵如下：

∑

状态

a

b

S（初态）

A

B

A

C

A

B

B

C

C（终态）

C

C

1）、构造等价状态转换图。

2）、构造等价3型文法。

3）、用自然语言描述其识别的输入串特征。

解：

由算法等价状态转换图为：

由算法等价3型文法为：

G[S]P：

S→aA|bBA→aC|bAB→aB|bCC→aC|bC|ε

输入串特征：

（ab*a|ba*b）（a|b）*即两个a中间夹有限个b或两个b中间夹有限个a后再跟任意的ab串的串。

3、P67第10题

解：

左线性文法→NFA

NFA确定化：

因存在f（A,0）=A与f（A,0）=S故为NFA。

确定化为如下DFA：

该自动机识别的语言为：

0（0|1）*即以0开头的二进制数字串。

确定的自顶而下的语法分析法部分：

1、P91第2题

补、手工构造对输入串a*（b+a）的自顶向下预测分析过程。

解：

由算法求能导出ε的VN。

由算法W1={E’、T’、F’}则Wk=W1∴W={E’、T’、F’}

由算法求first（VN）：

VN

与VN有关的产生式

first（VN）包含关系

结果

E

E→TE’≠>ε

First（TE）=first（T）

（、a、b、^

T

T→FT’

First（FT’）=first（F）

（、a、b、^

F

F→PF’≠>ε

First（PF’）=first（P）

（、a、b、^

P

P→（E）

a

b

^

First（（E））={（）

{a}

{b}

{^}

（、a、b、^

E’

E’→+E

ε

First（+E）={+}

{ε}

+、ε

T’

T’→T

ε

First（T）

{ε}

（、a、b、^、ε

F’

F’→*F’

ε

First（*F’）={*}

{ε}

*、ε

由算法求follow（VN）：

VN

右部包含VN

有关的产生式

follow（VN）包含关系

结果

E

开始符

E’→+E

P→（E）

#

follow（E’）

）

）、#

T

E→TE’

T’→T

First（E’）-{ε}∪follow（E）={+}∪follow（E）

Follow（T’）

+、）、#

F

T→FT’

First（T’）-{ε}∪follow（T）={^、（、a、b）∪follow（T）

（、a、b、^、+、）#

P

F→PF’

First（F’）-{ε}∪follow（F）={*}∪follow（F）

（、a、b、*、^、+、）#

E’

E→TE’

Follow（E）

）、#

T’

T→FT’

Follow（T）

+、）、#

F’

F→PF’

F’→*F’

Follow（F）

Follow（F’）

（、a、b、^、+、）#

由算法求SELECT（P）：

同左部产生式

右部ε规则

SELECT（P）包含关系

结果

E’→+E

≠>ε

first（+E）

+

E’→ε

=ε

{ε}∪follow（E’）

ε、（、#

T’→T

≠>ε

first（T）

（、a、b、^

T’→ε

=ε

{ε}∪follow（T’）

ε、+、）#

F’→*F’

≠>ε

first（*F’）

*

F’→ε

=ε

{ε}∪follow（F’）

ε、（、a、b、^、+、）、#

P→（E）

≠>ε

first（（E））

（

P→^

≠>ε

first（^）

^

P→a

≠>ε

first（a）

a

P→b

≠>ε

first（b）

b

E→TE’

≠>ε

first（TE’）=first（T）

（、a、b、^

T→FT’

≠>ε

first（FT’）=first（F）

（、a、b、^

F→PF’

≠>ε

first（PF’）=first（P）

（、a、b、^

由于该文法的每个非终结符号的不同产生式的SELECT集均两两不相交，故该文法是一个LL

（1）文法。

由SELECT（P）可构造该文法的预测分析表（只存储产生式右部）如下：

+

*

（

）

a

b

^

#

E

TE’

TE’

TE’

TE’

T

FT’

FT’

FT’

FT’

E’

+E

ε

ε

F

PF’

PF’

PF’

PF’

T’

ε

T

ε

T

T

T

ε

P

（E）

a

b

^

F’

ε

*F’

ε

ε

ε

ε

ε

ε

分析过程（略）

2、P92第6（6）题

由算法消除直接左公因子：

H→b（（M）|ε）<=>H→bAA→（M）|ε

消除直接左递归：

M→MaH|H<=>M→HBB→aHB|ε

由于M→HB可能含有间接左公因子故改写为：

M—>（（M）|bA）B<=>M—>（M）B|bAB

因此，改写后文法为：

M→（M）B|bABA→（M）|εB→aHB|εH→（M）|bA

由算法可知ε不是L（G）的句子故文法可进一步化简为：

M→（M）B|bABA→（M）B→aHBH→（M）|bA

由算法可判断该文法是一个LL

（1）文法。

3、P92第7（3）题

对该文法消除左公因子与左递归后化简得等价文法如下：

G[S]：

P：

{S→bS’,S’→BA’a|ε,A’→aBA’|ε,B→ab}改造获得成功，因存在SELECT（A’→aBA’）={a}∩SELECT（A’→ε）={a}≠∅故该文法不是一个LL

（1）文法。

算符优先部分：

1、P116第1题

解：

考虑句子结束符，故引入产生式S’→#S#

根据定义求=关系：

考察产生式右部……ab……或……aBb……得；

#S#,（T）故#=#；（=）。

求<关系：

求非终结符的firstvt集：

VN

Firstvt（VN）

S’

#

S

a,^,（

T

a,^,（,，

考虑产生式右部以终结符在前非终结符在后的相邻符号对有：

#S；#

求>关系：

求非终结符的lastvt集：

VN

lastvt（VN）

S’

#

S

a,^,）

T

a,^,）,，

考虑产生式右部以非终结符在前非终结符在后的相邻符号对有：

S#：

lastvt（S）>#T）：

lastvt（T）>）T,：

lastvt（T）>,

综上所述该文法的优先关系表为：

a

^

（

）

#

a

>

>

>

^

>

>

>

（

<

<

<

=

<

）

>

>

>

<

<

<

>

>

#

<

<

<

=

由于该文法不含有ε—产生式；不含有U—>……AB……的产生式。

故该文法是一个不含有ε—产生式算符文法。

考察优先关系表可知该文法任意一对终结符之间至多存在三种优先关系中的一种故该文法是一个算符优先文法。

用floyd迭代法求其优先函数为：

迭代

次数

a

^

（

）

#

0

F

1

1

1

1

1

1

G

1

1

1

1

1

1

1

F

2

2

1

3

3

1

G

2

2

2

1

2

1

2

F

3

3

1

3

3

1

G

4

4

4

1

2

1

3

F

3

3

1

3

3

1

G

4

4

4

1

2

1

故其优先函数为：

a

^

（

）

#

F

3

3

1

3

3

1

G

4

4

4

1

2

1

对输入串的算符优先分析过程。

步

骤

分析栈

优先

关系

当前

符号

余留

输入串

分析

动作

1

#

<

（

a,（a,a））#

移进

2

#（

<

a

（a,a））#

移进

3

#（a

>

（a,a））#

归约

4

#（F

<

（a,a））#

移进

5

#（F,

<

（

a,a））#

移进

6

#（F,（

<

a

a））#

移进

7

#（F,（a

>

a））#

归约

8

#（F,（F

<

a））#

移进

9

#（F,（F,

<

a

））#

移进

10

#（F,（F,a

>

）

）#

归约

11

#（F,（F,F

>

）

）#

归约

12

#（F,（F

=

）

）#

移进

13

#（F,（F）

>

）

#

归约

14

#（F,F

>

）

#

归约

15

#（F

=

）

#

移进

16

#（F）

>

#

归约

17

#F

=

#

接受

对句子的最右推导为：

该句型的所有短语：

aa,a（a,a）a,（a,a）（a,（a,a））

直接短语、句柄、素短语和最左素短语均为：

a

LR语法分析部分：

P152第3题。

解：

文法拓展与化简后的LR（0）文法项目集如右：

由文法项目法构造出的LR（0）识别活前缀NFA为：

该NFA确定化为：

由于在I1中存在归约—移进冲突，又FOLLOW（S’）={#}∩移进符集{a,b}=∅；另在I4中存在归约—移进冲突，又FOLLOW（A）={b}∩移进符集{a,b}≠∅。

故该文法不是一个SLR

（1）文法。

审查该文法，不难发现该文法是一个左右递归的文法，即是一个二义性文法，故也不是一个LR

（1）或LALR

（1）文法。

2、P154第15题。

解：

利用文法项目集规范簇+转换函数法构造其LR（0）识别活前缀DFA如下：

利用已得的该文法LR（0）识别活前缀DFA构造其LR（0）分析表如下：

利用LR

（1）项目集规范簇+转换函数法构造其LR

（1）识别活前缀DFA如下：

利用已得的该文法LR

（1）识别活前缀DFA构造其LR

（1）分析表如下：

对LR

（1）识别活前缀DFA利用LALR

（1）合并同心集规则改造获得LALR

（1）识别活前缀DFA如下：

利用已得的LALR

（1）识别活前缀DFA构造该文法的LALR

（1）分析表如下：

三种分析法对给定输入串的分析算法基本相同，限于篇幅不再给出参考答案。

3、P153第11题。

其解法与上述第2题相似，故不再给出参考答案。

语义分析和中间代码生成部分：

1、P188第1（3）题

解：

其后缀表达式形式为：

abcde/+*+

2、P188第2题

解：

三元式序列

间接三元式序列

四元式序列

①

（+,a,b）

执行表

三元式表

（+,a,b,t1）

②

（+,c,d）

①

①

（+,a,b）

（+,c,d,t2）

③

（+,a,b）

②

②

（+,c,d）

（+,a,b,t3）

④

（+,③,c）

③

③

（+,①,c）

（+,t3,c,t4）

⑤

（-,①,~）

④

④

（-,①,~）

（-,t1,~,t5）

⑥

（*,⑤,②）

⑤

⑤

（*,④,②）

（*,t5,t2,t6）

⑦

（-,⑥,④）

⑥

⑥

（-,⑤,③）

（-,t6,t4,t7）

备注：

以上作业题解答仅作同学们参考；同学们可在求解过程中使用不同的正确方法作解。

另由于时间仓促，错漏之处在所难免，恳请同学们指正以便修订。

甚谢！

最后，衷心的祝贺同学们取得优异成绩并致暑假愉快！

！

！

周文公元二零零六年五月于芜湖