南邮《编译原理》习题解答.docx

资源描述

南邮《编译原理》习题解答.docx

《南邮《编译原理》习题解答.docx》由会员分享，可在线阅读，更多相关《南邮《编译原理》习题解答.docx（42页珍藏版）》请在冰点文库上搜索。

南邮《编译原理》习题解答.docx

南邮《编译原理》习题解答

《编译原理》习题解答：

第一次作业：

P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？

它们之间可能有何种关系？

答：

被翻译的程序称为源程序；

翻译出来的程序称为目标程序或目标代码；

将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；

把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；

解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；

编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：

汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。

P143、编译程序是由哪些部分组成？

试述各部分的功能？

答：

编译程序主要由8个部分组成：

（1）词法分析程序；

（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。

具体功能见P7-9。

P144、语法分析和语义分析有什么不同？

试举例说明。

答：

语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：

对变量x：

=y符合语法规则就通过。

语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

补充：

为什么要对单词进行内部编码？

其原则是什么？

对标识符是如何进行内部编码的？

答：

内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：

长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。

对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。

第二次作业：

P381、设T1＝{11，010}，T2＝{0，01，1001}，计算：

T2T1，T1*，T2+。

T2T1＝{011，0010，0111，01010，100111，1001010}

T1*＝{ε，11，010，1111，11010，01011，010010……}

T2+＝{0，01，1001，00，001，01001，010，0101……}

P38-398、设有文法G[S]：

S∷＝aAb

A∷＝BcA|B

B∷＝idt|ε

试问下列符号串

（1）aidtcBcAb

（2）aidtccb（4）abidt是否为该文法的句型或句子。

（1）S

aAb

aBcAb

aidtcAb

aidtcBcAb句型但不是句子；

（2）S

aAb

aBcAb

aidtcAb

aidtcBcAb

aidtccAb

aidtccBb

aidtccb；是句型也是句子；

（4）该文法的句子或句型的最后一个字符串一定是字符“b”；

第三次作业：

P3911、试分别描述下列文法所产生的语言（文法开始符号为S）：

（1）S∷＝0S|01

（2）S∷＝aaS|bc

（1）L（G）＝{0n1|n≥1}；{解题思路：

将文法转换为正规表达式}

（2）L（G）＝{a2nbc|n≥0}。

P3912、试分别构造产生下列语言的文法：

（1）{abna|n=0，1，2，3……}

（3）{aban|n≥1}

（5）{anbmcp|n，m，p≥0}

（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，

P：

S∷＝aAa

A∷＝bA|ε

（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，

P：

S∷＝abA

A∷＝aA|a

（5）①G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，

P：

S∷＝ABC

A∷＝aA|ε

B∷＝bB|ε

C∷＝cC|ε

②G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b，c}，

P：

S∷＝aS|bS|cS|ε

P3915.设文法G规则为：

S：

：

=AB

B：

：

=a|Sb

A：

：

=Aa|bB

对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。

（2）baabaab（3）bBABb

解

（2）S

AaSb

bBAB

abBa

句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄a

（3）

短语bB,AB,ABb，bBABb

简单短语bB,AB，

句柄bB

第四次作业

P4124.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？

1.S:

=aBB:

=cBB:

=bC:

2.S:

=aBB:

=bCC:

=cC:

=ε

3.S:

=aAbaA:

=aBaA:

=aaAB:

=bA:

4.S:

=aCdaC:

=BaC:

=aaAB:

5.S:

=ABA:

=aB:

=bCB:

=bC:

6.S:

=ABA:

=aB:

=bCC:

=cC:

=ε

7.S:

=aAS:

=εA:

=aAA:

=aBA:

=aB:

8.S:

=aAS:

=εA:

=bAbA:

短语结构文法（0）4

上下文有关文法

（1）3

上下文无关文法

（2）568或者25678

正规文法（3）127或者1

P4229.用扩充的BNF表示以下文法规则：

1．Z:

=AB|AC|A

2．A:

=BC|BCD|AXZ|AXY

3．S:

=aABb|ab

4．A:

=Aab|ε

解:

1．Z:

=A（B|C|ε）:

=A[B|C]

2．A:

=BC（ε|D）|{X（Z|Y）}:

=BC[D]|{X（Z|Y）}

3．A:

=a（（AB|ε）b）:

=a[AB]b

4．A:

={ab|ε}:

={ab}

第五次作业：

P744.画出下列文法的状态图：

Z：

：

=Be

B：

：

=Af

A：

：

=e|Ae并使用该状态图检查下列句子是否该文法的合法句子：

f,eeff,eefe。

由状态图可知只有eefe是该文法的合法句子。

P745.设右线性文法G=（{S,A,B},{a,b},S,P），其中P组成如下：

S：

：

=bAA：

：

=bBA：

：

=aAA：

：

=bB：

：

画出该文法的状态转换图。

P746.构造下述文法G[Z]的自动机，该自动机是确定的吗？

它相应的语言是什么？

Z：

：

=A0A：

：

=A0|Z1|0

解1：

将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z：

：

=A0A：

：

=A0|B1|0B：

：

=A0，具体为：

=Z1A:

=B1

=A01

=A0B:

=A0

将所得的新左线性文法转换成右线性文法：

此时利用书上规则，其对应的右线性文法为：

A：

：

=0A|0B|0Z：

：

=0AB：

：

=1A

解2：

先画出该文法状态转换图：

NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}）

其中M：

M（S，0）={A}M（S，1）=ø

M（A，0）={A，Z}M（A，1）=ø

M（Z，0）=øM（Z，1）={A}

显然该文法的自动机是非确定的；它相应的语言为：

{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；那么如何构造其相应的有穷自动机呢？

先构造其转换系统：

根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：

{S’,S}

{A}

1Ф

{A}

{A,Z,Z’}

2Ф

{A,Z,Z’}

{A}

则其相应的DFA为：

P748.设（NFA）M=（{A,B},{a,b},M,{A},{B}），其中M定义如下：

M（A,a）={A,B}M（A,b）={B}M（B,a）=øM（B,b）={A,B}

请构造相应确定有穷自动机（DFA）M’。

解：

构造一个如下的自动机（DFA）M’，（DFA）M’={K,{a,b},M’,S,Z}

K的元素是[A][B][A,B]

由于M（A,a）={A,B}，故有M’（[A],a）=[A,B]

同样M’（[A]，b）=[B]

M’（[B]，a）=ø

M’（[B]，b）=[A，B]

由于M（{A，B}，a）=M（A，a）UM（B，a）={A，B}Uø={A，B}

故M’（[A，B]，a）=[A，B]

由于M（{A，B}，b）=M（A，b）UM（B，b）={B}U{A，B}={A，B}

故M’（[A，B]，b）=[A，B]

S=[A]，终态集Z={[A，B]，[B]}

重新定义：

令0=[A]1=[B]2=[A,B]，则DFA如下所示：

可以进一步化简，把M’的状态分成终态组{1，2}和非终态组{0}

由于{1，2}a={1，2}b={2}

{1，2}，不能再划分。

至此，整个划分含有两组{1，2}{0}

令状态1代表{1，2}，化简如图：

第六次作业：

P7411

（1）（0|11*0）*

解：

先构造该正规式的转换系统：

（0|11*0）*

11*0

由上述转换系统可得状态转换集K={S,1,2,3,4,Z}，状态子集转换矩阵如下表所示：

{S,1,Z}

{1,Z}

{2,3,4}

{1,Z}

{2,3,4}

{1,Z}

{3,4}

{1,Z}

{3,4}

由状态子集转换矩阵可知，状态0和1是等价的，而状态2和3是等价的，因此，合并等价状态之后只剩下2个状态，也即是最少状态的DFA。

P7412.将图3.24非确定有穷自动机NFA确定化和最少化。

图3.24NFA状态转换图

解：

设（DFA）M={K,VT,M,S,Z}，其中，K={[0],[0,1],[1]}，VT={a,b}，M：

M（[1],a）=[0]M（[1],b）=ФM（[0,1],a）=[0,1]M（[0,1],b）=[1]

M（[0],a）=[0,1]M（[0],b）=[1]

S=[1]，Z={[0],[0,1]}

令[0,1]=2，则其相应的状态转换图为：

现在对该DFA进行化简，先把状态分为两组：

终态组{0,2}和非终态组{1}，易于发现{0,2}

不可以继续划分，因此化简后的状态转换图如下：

0,2

P7418.根据下面正规文法构造等价的正规表达式：

=cC|a……①

=cA|aB……②

=aB|c……③

=aS|aA|bB|cC|a……④

解：

由③式可得B=aB+c→B=a*c

由②式可得A=cA+aB→A=c*aa*c

由①式可得S=cC+a

由④式可得C=aS+aA+bB+cC+a→C=c*（aS+aA+bB+a）→

C=c*（aS+ac*aa*c+ba*c+a）→S=cc*（aS+ac*aa*c+ba*c+a）+a=cc*aS+cc*（ac*aa*c+ba*c+a）+a=（cc*a）*（cc*（ac*aa*c+ba*c+a）+a）=（cc*a）*（cc*（ac*aa*c|ba*c|a）|a）另一种答案是S=c（ac|c）*（ac*aa*c|ba*c|aa|a）|a

第七次作业：

P1421.试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法）

（1）G[E]:

=T|EAT……①

=F|TMF……②

=（E）|i……③

=+|-……④

=*|/……⑤

解：

先采用“重复法”：

再采用“改写法”：

=T{AT}E:

=TE’

=F{MF}E’:

=ATE’|ε

=（E）|iT:

=FT’

=+|-T’:

=MFT’|ε

=*|/F:

=（E）|i

=+|-

=*|/

P1422.试分别消除下列文法的间接左递归

（2）G[Z]:

=AZ|b……①

=ZA|a……②

解：

将②式代入①式可得，Z:

=ZAZ|aZ|b消除左递归后得到：

=（aZ|b）Z’

Z’:

=AZZ’|ε

=ZA|a

P1435.对下面的文法G[E]:

=TE’

E’:

=+E|ε

=FT’

T’:

=T|ε

=PF’

F’:

=*F’|ε

P∷＝（E）|a|b|∧

（1）计算这个文法的每个非终结符号的FIRST和FOLLOW；

（2）证明这个文法是LL

（1）文法；

（3）构造它的LL

（1）分析表并分析符号串a*b+b;

解:

（1）构造FIRST集：

FIRST（E’）={+,ε}

FIRST（F’）={*,ε}

FIRST（E）=FIRST（T）=FIRST（F）=FIRST（P）={（，a，b，∧}

FIRST（T’）={（，a，b,ε，∧}

构造FOLLOW集：

规则一

＃∈FOLLOW（E）FOLLOW（E）={#}

规则二

）∈FOLLOW（E）FOLLOE（E）={），#}

FIRST（E’）-{ε}

FOLLOW（T）FOLLOW（T）={+}

FIRST（T’）-{ε}

FOLLOW（F）FOLLOW（F）={（，a，b，∧}

FIRST（F’）-{ε}

FOLLOW（P）FOLLOW（P）={*}

规则三

FOLLOW（E）

FOLLOW（E’）FOLLOW（E’）={#，）}

FOLLOW（E）

FOLLOW（T）FOLLOW（T）={＋，＃，）}

FOLLOW（T）

FOLLOW（T’）FOLLOW（T’）={＋，＃，）}

FOLLOW（T）

FOLLOW（F）FOLLOW（F）={（，），a，b，＋，＃，∧}

FOLLOW（F）

FOLLOW（F’）FOLLOW（F’）={（，），a，b，＋，＃，∧}

FOLLOW（F）

FOLLOW（P）FOLLOW（P）={（，），a，b，＋，＃，∧,*}

最后结果为：

FIRST（E’）={+,ε}

FIRST（F’）={*,ε}

FIRST（E）=FIRST（T）=FIRST（F）=FIRST（P）={（，a，b，∧}

FIRST（T’）={（，a，b,ε，∧）

FOLLOE（E）={）,＃}

FOLLOW（E’）={＃，）}

FOLLOW（T）={＋，＃，）}

FOLLOW（T’）={＋，＃，）}

FOLLOW（F）={（，），a，b，＋，＃，∧}

FOLLOW（F’）={（，），a，b，＋，＃，∧}

FOLLOW（P）={（，），a，b，＋，＃，∧,*}

（2）证明该文法是LL

（1）文法：

证明：

对于规则E’:

=+E|ε，T’:

=T|ε，F’:

=*F’|ε（仅有一边能推出空串）

有FIRST（+E）={+}∩FIRST（ε）=ø，FIRST（T）={（,a,b,∧}∩FIRST（ε）=ø

FIRST（*F’）={*}∩FIRST（ε）=ø，FIRST（+E）={+}∩FOLLOW（E’）={#,）}=ø

FIRST（T）={（,a,b,∧}∩FOLLOW（T’）={+,#,）}=ø

FIRST（*F’）={*}∩FOLLOW（F’）={（，），a，b，＋，＃，∧}=ø

所以该文法是LL

（1）文法。

（3）构造文法分析表

（

）

∧

E→TE’

E’

E’→+E

E’→ε

T→FT’

T’

T’→T

T’→ε

T’→T

T’→ε

T’→T

T’→ε

F→PF’

F’

F’→ε

F’→*F’

F’→ε

P→a

P→b

P→（E）

P→∧

下面分析符号串a*b+b

步骤分析栈余留输入串所用的产生式

1#Ea*b+b#E→TE’

2#E’Ta*b+b#T→FT’

3#E’T’Fa*b+b#F→PF’

4#E’T’F’Pa*b+b#P→a

5#E’T’F’aa*b+b#

6#E’T’F’*b+b#F’→*F’

7#E’T’F’**b+b#

8#E’T’F’b+b#F’→ε

9#E’T’b+b#T’→T

10#E’Tb+b#T→FT’

11#E’T’Fb+b#F→PF’

12#E’T’F’Pb+b#P→b

13#E’T’F’bb+b#

14#E’T’F’+b#F’→ε

15#E’T’+b#T’→ε

16#E’+b#E’→+E

17#E++b#

18#Eb#E→TE’

19#E’Tb#T→FT’

20#E’T’Fb#F→PF’

21#E’T’F’Pb#P→b

22#E’T’F’bb#

23#E’T’F’#F’→ε

24#E’T’#T’→ε

25#E’#E’→ε

26##成功

所以符号串a*b+b是该文法的句子；

P1446.对下列文法，构造相应的FIRST和FOLLOW：

（1）S∷＝aAd

A∷＝BC

B∷＝b|ε

C∷＝c|ε

（2）A∷＝BCc|gDB

B∷＝ε|bCDE

C∷＝DaB|ca

D∷＝ε|dD

E∷＝gAf|c

解：

（1）

构造FIRST集

FIRST（S）={a}

FIRST（B）={b，ε}

FIRST（C）={c，ε}

FIRST（A）={b，c，ε}

构造FOLLOW集

规则一

＃∈FOLLOW（S）FOLLOW（S）={#}

规则二

d∈FOLLOW（A）FOLLOE（A）={d}

FIRST（C）-{ε}

FOLLOW（B）FOLLOW（B）={c}

规则三

FOLLOW（A）

FOLLOW（B）FOLLOW（B）={d，c}

FOLLOW（A）

FOLLOW（C）FOLLOW（C）={d}

最后结果为：

FIRST（S）={a}

FIRST（A）={b，c，ε}

FIRST（B）={b，ε}

FIRST（C）={c，ε}

FOLLOW（S）={#}

FOLLOW（A）={d}

FOLLOW（B）={d，c}

FOLLOW（C）={d}

（2）

构造FIRST集

规则二

FIRST（A）={g},

FIRST（B）={b，ε},

FIRST（C）={c},

FIRST（D）={d，ε},

FIRST（E）={g，c}.

规则三

FIRST（A）={g，b，c},

FIRST（C）={a，c，d},

FIRST（A）={a，b，c，d，g}.

构造FOLLOW集

规则一

＃∈FOLLOW（A）FOLLOW（A）={#}

规则二

f∈FOLLOW（A）FOLLOE（A）={f，＃}

c∈FOLLOW（C）FOLLOE（C）={c}

a∈FOLLOW（D）FOLLOE（D）={a}

FIRST（Cc）-{ε}

FOLLOW（B）FOLLOW（B）={c，d，a}

FIRST（B）-{ε}

FOLLOW（D）FOLLOW（D）={b，a}

FIRST（DE）-{ε}

FOLLOW（C）FOLLOW（C）={d，g，c}

FIRST（E）

FOLLOW（D）FOLLOW（D）={b，c，a，g}

规则三

FOLLOW（A）

FOLLOW（B）FOLLOW（B）={a，c，d，f，#}

FOLLOW（A）

FOLLOW（D）FOLLOW（D）={a，b，c，f，g，＃}

FOLLOW（B）

FOLLOW（E）FOLLOW（E）={a，c，d，f，#}

FOLLOW（C）

FOLLOW（B）FOLLOW（B）={a，c，d，g，f，#}

FOLLOW（B）

FOLLOW（E）FOLLOW（E）={a，c，d，g，f，#}

最后结果为：

FIRST（A）={a，b，c，d，g},

FIRST（B）={b，ε},

FIRST（C）={a，c，d},

FIRST（D）={d，ε},

FIRST（E）={g，c},

FOLLOE（A）={f，＃}

FOLLOW（B）={a，c，d，g，f，#},

FOLLOW（C）={d，g，c},

FOLLOW（D）={a，b，c，f，g，＃},

FOLLOW（E）={a，c，d，g，f，#}.

P1449.设已给文法G[S]:

S∷＝SaB|bB

A∷＝Sa

B∷＝Ac

（1）将此文法改写为LL

（1）文法

（4）构造LL

（1）分析表

解：

此题消除左递归之后，构造LL

（1）分析表存在“多重入口”问题，故采用以下方法：

（1）改写为LL

（1）文法：

S∷＝bB{aB}

A∷＝Sa

B∷＝Ac

（4）

FIRST（S）={b},

FIRST（A）={b},

FIRST（B）={b},

FOLLOE（S）={a，＃},

FOLLOW（A）={c},

FOLLOW（B）={a，＃}.

展开阅读全文