编译原理 作业答案.docx

编译原理 作业答案.docx

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

编译原理作业答案

《编译原理》第一次作业参考答案

一、下列正则表达式定义了什么语言（用尽可能简短的自然语言描述）？

1.b*（ab*ab*）*

所有含有偶数个a的由a和b组成的字符串.

2.c*a（a|c）*b（a|b|c）*|c*b（b|c）*a（a|b|c）*

答案一：

所有至少含有1个a和1个b的由a，b和c组成的字符串.

答案二：

所有含有子序列ab或子序列ba的由a，b和c组成的字符串.

说明：

答案一要比答案二更好，因为用自然语言描述是为了便于和非专业的人员交流，而非专业人员很可能不知道什么是“子序列”，所以相比较而言，答案一要更“自然”.

二、设字母表∑={a,b}，用正则表达式（只使用a，b，，|，*，+，？

）描述下列语言：

1.不包含子串ab的所有字符串.

b*a*

2.不包含子串abb的所有字符串.

b*（ab?

）*

3.不包含子序列abb的所有字符串.

b*a*b?

a*

注意：

关于子串（substring）和子序列（subsequence）的区别可以参考课本第119页方框中的内容.

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第二次作业参考答案

一、考虑以下NFA：

1.这一NFA接受什么语言（用自然语言描述）？

所有只含有字母a和b，并且a出现偶数次或b出现偶数次的字符串.

2.构造接受同一语言的DFA.

答案一（直接构造通常得到这一答案）：

答案二（由NFA构造DFA得到这一答案）：

二、正则语言补运算

3.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.

4.画出一个DFA，该DFA恰好识别所有不含011子串的所有二进制串.

规律：

构造语言L的补语言L’的DFA，可以先构造出接受L的DFA，再把这一DFA的接受状态改为非接受状态，非接受状态改为接受状态，就可以得到识别L’的DFA.

说明：

在上述两题中的D状态，无论输入什么符号，都不可能再到达接受状态，这样的状态称为“死状态”.在画DFA时，有时为了简明起见，“死状态”及其相应的弧（上图中的绿色部分）也可不画出.

5.再证明：

对任一正则表达式R，一定存在另一正则表达式R'，使得L（R'）是L（R）的补集.

证明：

根据正则表达式与DFA的等价性，一定存在识别语言L（R）的DFA.设这一DFA为M，则将M的所有接受状态改为非接受状态，所有非接受状态改为接受状态，得到新的DFAM’.易知M’识别语言L（R）的补集.再由正则表达式与DFA的等价性知必存在正则表达式R’，使得L（R’）是L（R）的补集.

三、设有一门小小语言仅含z、o、/（斜杠）3个符号，该语言中的一个注释由/o开始、以o/结束，并且注释禁止嵌套.

1.请给出单个正则表达式，它仅与一个完整的注释匹配，除此之外不匹配任何其他串.书写正则表达式时，要求仅使用最基本的正则表达式算子（，|，*，+，？

）.

参考答案一：

/o（o*z|/）*o+/

思路：

基本思路是除了最后一个o/，在注释中不能出现o后面紧跟着/的情况；还有需要考虑的是最后一个o/之前也可以出现若干个o.

参考答案二（梁晓聪、梁劲、梁伟斌等人提供）：

/o/*（z/*|o）*o/

2.给出识别上述正则表达式所定义语言的确定有限自动机（DFA）.你可根据问题直接构造DFA，不必运用机械的算法从上一小题的正则表达式转换得到DFA.

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第三次作业参考答案

一、考虑以下DFA的状态迁移表，其中0，1为输入符号，A~H代表状态：

0

1

A

B

A

B

A

C

C

D

B

D

D

A

E

D

F

F

G

E

G

F

G

H

G

D

其中A为初始状态，D为接受状态，请画出与此DFA等价的最小DFA，并在新的DFA状态中标明它对应的原DFA状态的子集.

说明：

有些同学没有画出状态H，因为无法从初始状态到达状态H.从实用上讲，这是没有问题的.不过，如果根据算法的步骤执行，最后是应该有状态H的.

二、考虑所有含有3个状态（设为p，q，r）的DFA.设只有r是接受状态.至于哪一个状态是初始状态与本问题无关.输入符号只有0和1.这样的DFA总共有729种不同的状态迁移函数，因为对于每一状态和每一输入符号，可能迁移到3个状态中的一个，所以总共有3^6=729种可能.在这729个DFA中，有多少个p和q是不可区分的（indistinguishable）？

解释你的答案.

解：

考虑对于p和q，在输入符号为0时的情况，在这种情况下有5种可能使p和q无法区分：

p和q在输入0时同时迁移到r（1种可能），或者p和q在输入0时，都迁移到p或q（4种可能）.

类似地，在输入符号为1时，也有5种可能使p和q无法区分.

如果再考虑r的迁移，r的任何迁移对问题没有影响.于是r在输入0和输入1时各有3种可能的迁移，总共有3*3=9种迁移.

因此，总共有5*5*9=225个DFA，其中p和q是不可区分的.

三、证明：

所有仅含有字符a，且长度为素数的字符串组成的集合不是正则语言.

证明：

用反证法.

假设含有素数个a的字符串组成的集合是正则语言，则必存在一个DFA接受这一语言，设此DFA为D.由于D的状态数有限，而素数有无限多个，所以必存在两个不同的素数p和q（设p

考虑仅含有字母a，长度为p+p（q-p）的字符串T.T从初始状态出发，经过p个a到达状态s，再经过（q-p）个a仍然到达s；同样，经过p（q-p）个a后仍然到达s.因此，从初始状态出发，经过p+p（q-p）个a后必然到达状态s.由于p+p（q-p）=p（q-p+1）是合数，而s为接受状态，因而得出矛盾.原命题得证.

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第四次作业参考答案

一、用上下文无关文法描述下列语言：

1.定义在字母表∑={a,b}上，所有首字符和尾字符相同的非空字符串.

SaTa|bTb|a|b

TaT|bT|є

说明：

1.用T来产生定义在字母表∑={a,b}上的任意字符串；

2.注意不要漏了单个a和单个b的情况.

2.L={0i1j|i≤j≤2i且i≥0}.

S0S1|0S11|є

3.定义在字母表∑={0,1}上，所有含有相同个数的0和1的字符串（包括空串）.

S0S1|1S0|SS|є

思路：

分两种情况考虑.

1）如果首尾字母不同，那么这一字符串去掉首尾字母仍应该属于我们要定义的语言，因此有S0S1|1S0；

2）如果首尾字母相同，那么这一字符串必定可以分成两部分，每一部分都属于我们要定义的语言，因此有SSS.

二、考虑以下文法：

SaABe

AAbc|b

Bd

1.用最左推导（leftmostderivation）推导出句子abbcde.

S==>aABe==>aAbcBe==>abbcBe==>abbcde

2.用最右推导（rightmostderivation）推导出句子abbcde.

S==>aABe==>aAde==>aAbcde==>abbcde

3.画出句子abbcde对应的分析树（parsetree）.

三、考虑以下文法：

SaSb

SaS

S

1.这一文法产生什么语言（用自然语言描述）？

所有n个a后紧接m个b，且n>=m的字符串.

2.证明这一文法是二义的.

对于输入串aab，有如下两棵不同的分析树

3.写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.

答案一：

SaSb|T

TaT|

答案二：

STS’

TaT|

S’aS’b|

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第五次作业参考答案

一、考虑以下文法：

SaTUV|bV

TU|UU

U|bV

V|cV

写出每个非终端符号的FIRST集和FOLLOW集.

FIRST（S）={a,b}FIRST（T）={є,b}FIRST（U）={є,b}FIRST（V）={є,c}

FOLLOW（S）={$}FOLLOW（T）={b,c,$}FOLLOW（U）={b,c,$}FOLLOW（V）={b,c,$}

二、考虑以下文法：

S（L）|a

LL,S|S

1.消除文法的左递归.

S（L）|a

LSL’

L’,SL’|

2.构造文法的LL

（1）分析表.

FIRST（S）={‘（‘,‘a’}FIRST（L）={‘（‘,‘a’}FIRST（L’）={‘,’,}

FOLLOW（S）={‘$’,‘,’,‘）’}FOLLOW（L）={‘）’}FOLLOW（L’）={‘）’}

NON-TERMINAL

INPUTSYMBOL

（

）

a

$

S

S（L）

Sa

L

LSL’

LSL’

L’

L’

L’,SL’

3.对于句子（a,（a,a）），给出语法分析的详细过程（参照课本228页的图4.21）.

MATCHED

STACK

INPUT

ACTION

S$

（a,（a,a））$

（L）$

（a,（a,a））$

outputS（L）

（

L）$

a,（a,a））$

（

SL’）$

a,（a,a））$

outputLSL’

（

aL’）$

a,（a,a））$

outputSa

（a

L’）$

（a,a））$

（a

SL’）$

（a,a））$

outputL’,SL’

（a,

SL’）$

（a,a））$

（a,

（L）L’）$

（a,a））$

outputS（L）

（a,（

L）L’）$

a,a））$

（a,（

SL’）L’）$

a,a））$

outputLSL’

（a,（

aL’）L’）$

a,a））$

outputSa

（a,（a

L’）L’）$

a））$

（a,（a

SL’）L’）$

a））$

outputL’,SL’

（a,（a,

SL’）L’）$

a））$

（a,（a,

aL’）L’）$

a））$

outputSa

（a,（a,a

L’）L’）$

））$

（a,（a,a

）L’）$

））$

outputL’

（a,（a,a）

L’）$

）$

（a,（a,a）

）$

）$

outputL’

（a,（a,a））

$

$

三、考虑以下文法：

SaSbS|bSaS|

这一文法是否是LL

（1）文法？

给出理由.

这一文法不是LL

（1）文法，因为S有产生式S，但FIRST（S）={a,b,}，FOLLOW（S）={a,b}，因而FIRST（S）∩FOLLOW（S）≠.根据LL

（1）文法的定义知这一文法不是LL

（1）文法.

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第六次作业参考答案

一、考虑以下文法：

（0）E’E

（1）EE+T

（2）ET

（3）TTF

（4）TF

（5）FF*

（6）Fa

（7）Fb

1.写出每个非终端符号的FIRST集和FOLLOW集.

FIRST（E’）=FIRST（E）=FIRST（T）=FIRST（F）={a,b}

FOLLOW（E’）={$}FOLLOW（E）={+,$}FOLLOW（T）={+,$,a,b}FOLLOW（F）={+,*,$,a,b}

2.构造识别这一文法所有活前缀（viableprefixes）的LR（0）自动机（参照课本4.6.2节图4.31）.

3.构造这一文法的SLR分析表（参照课本4.6.3节图4.37）.

STATE

ACTION

GOTO

a

b

+

*

$

E

T

F

0

s4

s5

1

2

3

1

s6

accept

2

s4

s5

r2

r2

7

3

r4

r4

r4

s8

r4

4

r6

r6

r6

r6

r6

5

r7

r7

r7

r7

r7

6

s4

s5

9

3

7

r3

r3

r3

s8

r3

8

r5

r5

r5

r5

r5

9

s4

s5

r1

r1

7

4.给出SLR分析器识别输入串a+ab*的过程（参照课本4.6.4节图4.38）

STACK

SYMBOLS

INPUT

ACTION

（1）

0

a+ab*$

shift

（2）

04

a

+ab*$

reducebyFa

（3）

03

F

+ab*$

reducebyTF

（4）

02

T

+ab*$

reducebyET

（5）

01

E

+ab*$

shift

（6）

016

E+

ab*$

shift

（7）

0164

E+a

b*$

reducebyFa

（8）

0163

E+F

b*$

reducebyTF

（9）

0169

E+T

b*$

shift

（10）

01695

E+Tb

*$

reducebyFb

（11）

01697

E+TF

*$

shift

（12）

016978

E+TF*

$

reducebyFF*

（13）

01697

E+TF

$

reducebyTTF

（14）

0169

E+T

$

reducebyEE+T

（15）

01

E

$

accept

~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~~\（≧▽≦）/~

《编译原理》第八次作业参考答案

一、考虑以下语法制导定义（SyntaxDirectedDefinition）：

语法规则

语义规则

SABCD

S.val=A.val+B.val+C.val+D.val

AgBa

A.val=B.val*5

BB1b

B.val=B1.val*2

Bb

B.val=2

CC1c

C.val=C1.val*3

Cc

C.val=3

Dd

D.val=1

对于输入串gbbabbccd构造带注释的分析树（annotatedparsetree）.

最终答案：

34

二、以下文法定义了二进制浮点数常量的语法规则：

SL.L|L

LLB|B

B0|1

试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号S相关联的一个综合属性value中。

例如，对于输入串101.101，S的value属性值结果应该是5.625。

要求在编写语法制导定义时，不得改写文法！

参见05级期末考答案.

三、选做课本Exercise5.3.2和Exercise5.3.3中的一题.

Exercise5.3.2

产生式

语义规则

EE1+T

E.expr=E1.expr+‘+’+T.expr

E.op=‘+’

ET

E.expr=T.expr

E.op=T.op

TT1*F

if（T1.op==‘+’）

if（F.op==‘+’）T.expr=‘（‘+T1.expr+‘）’+’*’+‘（‘+F.expr+‘）’

elseT.expr=‘（‘+T1.expr+‘）’+’*’+F.expr

elseif（F.op==‘+’）T.expr=T1.expr+’*’+‘（‘+F.expr+‘）’

T.op=’*’

T->F

T.expr=F.expr

T.op=F.op

F（E）

F.expr=E.expr

F.op=E.op

Fletter

F.expr=letter.lexval

F.op=‘n’

Exercise5.3.3

产生式

语义规则

EE1+T

E.expr=E1.expr+‘+’+T.expr

E.deri=E1.deri+‘+’+T.deri

ET

E.expr=T.expr

E.deri=T.deri

TT1*F

T.expr=T1.expr+’*’+F.expr

T.deri=‘（’+T1.expr+’*’+F.deri+‘+’+T1.deri+‘*’+F.expr+‘）’

T->F

T.expr=F.expr

T.deri=F.deri

F（E）

F.expr=E.expr

F.deri=‘（‘+E.deri+‘）’

Fid

F.expr=id

F.deri=‘0’

Fx

F.expr=x.val

F.deri=‘1’