设 l í {a,b,c}* 是满足下述条件的符号串构成的语言,编译原理习题解答 南京邮电大学版.doc...

《编译原理》习题解答：

第一次作业：

P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？

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

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

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

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

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

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

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

P14 3、编译程序是由哪些部分组成？试述各部分的功能？

答：编译程序主要由8个部分组成：(1)词法分析程序；(2)语法分析程序；(3)语义分析程序；(4)中间代码生成；(5)代码优化程序；(6)目标代码生成程序；(7)错误检查和处理程序；(8)信息表管理程序。具体功能见P7-9。

P14 4、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

P15 5、编译程序分遍由哪些因素决定？

答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。

补充：1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？

答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。

补充：2、赋值语句： A：= 5 * C的语法和语义指的是什么？

答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。

第二次作业：

P38 1、设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 3、令A＝{0，1，2}，写出集合A+和A*的七个最短符号串。

A+：0，1，2，00，01，02，10(有多种可能)

A*：ε，0，1，2，00，01，02(有多种可能)

P38 5、试证明：A+＝A A*＝A*A。

证明：A+＝A1∪A2∪……∪An∪……

A*＝A0(即{ε})∪A+

A A*＝A(A0∪A+ )＝A∪A2∪A3∪A4……＝A+＝A+∪A＝(A0∪A+ )A＝A*A(证毕)

P38 7、设有文法G[S]：

S∷＝A

A∷＝B | IF A THEN A ELSE A

B∷＝C | B+C | +C

C∷＝D | C*D | *D

D∷＝X | (A) | -D 试写出VN和VT。

VN＝{S，A，B，C，D}

VT＝{IF，THEN，ELSE，+，*，X，(，)，-}

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

S∷＝aAb

A∷＝BcA | B

B∷＝idt |ε

试问下列符号串(1)aidtcBcAb (3)ab (5)aidtcidtcidtb 是否为该文法的句型或句子。

(1)SaAbaBcAbaidtcAbaidtcBcAb 句型但不是句子；

(3)SaAbaBbaεbab 是句型也是句子；

(5)SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。

P39 10、给定文法：

S∷＝aB | bA

A∷＝aS | bAA | a

B∷＝bS | aBB|b 该文法所描述的语言是什么？

L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。

P39 11、试分别描述下列文法所产生的语言(文法开始符号为S)：

(1) S∷＝0S | 01

(2) S∷＝aaS | bc

(3) S:: =aSd | aAd

A:: =aAc | bc

(4) S:: =AB

A:: =aAb | ab

B:: =cBd | ε

(1) L(G)＝{0n1| n≥1}； {解题思路：将文法转换为正规表达式}

(2) L(G)＝{a2nbc | n≥0}；

(3) L(G)＝{aibcjdk | i, j, k≥1, i=j+k-1}；或者 L(G)＝{aj+k-1bcjdk | j, k≥1}；

(4) L(G)＝{anbncmdm | m≥0, n≥1}。

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

(1){ abna | n=0，1，2，3……}

(2){ anbn | n=1，2，3，4……}

(3){ aban | n≥1}

(4){ anbam | n, m≥1}

(5){ anbmcp | n，m，p≥0}

(6){ ambmcp | m，p≥0}

(1)G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，

P：S∷＝aAa 或 S∷＝aB

A∷＝bA |ε B∷＝bB | a

(2)G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b}，

P：S∷＝aSb |ε

(3)G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，

P：S∷＝abA 或 S∷＝Sa | aba

A∷＝aA | a

(4)G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，

P：S∷＝aS | 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 |ε

(6)G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b，c}，

P：S∷＝aSbA |ε

A∷＝cA |ε

第三次作业：

P39 15. 设文法G规则为：

S：：=AB

B：：=a|Sb

A：：=Aa|bB

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

(2)baabaab (3)bBABb

(2) S

A B

A a S b

b B A B

a b B a

a

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

S

(3)

A B

b B

S b

A B

短语bB, AB, ABb，bBABb

简单短语bB, AB，

句柄bB

P40 18. 分别对i+i*i 和i+i+i中每一个句子构造两棵语法树，从而证明下述文法G[]是二义的。

：：=i|()|

：：=+|-|*|/

1． i+i*i

i +

i * i

* i

i + i

由于句子i+i*i可构造两棵不同的语法树，所以证明该文法是二义的。

2. i+i+i

i +

i + i

+ i

i + i

由于句子i+i+i可构造两棵不同的语法树，所以证明该文法是二义的。

P40 19. 证明下述文法是二义的

1) S::=iSeS|iS|i

2) S::=iEtS| iEtSeS|a E::=b 存在句子ibtibtaeibta或者ibtibtaea有两颗不同的语法树

3) S::=A|B

A::=aCbA|a

B::=BCC|a

C::=ba (最简单的就是a为句型)

1) 对于句子iiieii可构造两棵不同的语法树，所以证明该文法是二义的。

S

i S e S

i S i S

i i

S

i S

i S e S

i i S

i

3) 对于句子ababa可构造两棵不同的语法树，所以证明该文法是二义的。

S

A

a C b A

b a a

S

B

B C C

a b a b a

P41 21. 令文法N：：=D|ND

D：：=0|1|2|3|4|5|6|7|8|9

给出句子0127，34，568最左推导和最右推导。

解：0127的最左推导N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127

0127的最右推导N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127

34的最左推导N=>ND=>DD=>3D=>34

34的最右推导N=>ND=>N4=>D4=>34

568的最左推导N=>ND=>NDD=>DDD=>5DD=>56D=>568

568的最右推导N=>ND=>N8=>ND8=>N68=>D68=>568

P41 23. 设有文法如下：

::=V1

V1::=V2|V1iV2

V2::=V3|V2+V3|iV3

V3::=)V1*|(

试分析句子(, )(*, i(, (+(, (+(i(, (+)(i(*i(。

解 => V1=>V2=>V3=>(

=> V1=>V2=>V3=>)V1*=>)V2*=>)V3*=>)(*

=> V1=>V2=>iV3=>i(

=> V1=>V2=>V2+V3=>V3+V3=>(+V3=>(+(

=> V1=>V1iV2=> V1iV3=> V1i(=>V2i(=>V2+V3i(=>V2+( i(=>V3+( i(=>(+(i(

=> V1=>V1iV2=> V2iV2=> V2+V3iV2=> V3+V3iV2=> (+V3iV2=>(+)V1*iV2

=>(+) V1iV2*iV2=>(+) V2iV2*iV2=>(+) V3iV2*iV2=>(+) (iV2*iV2=>(+) (iV2*iV2=>(+) (iV3*iV2=>(+) (i(*iV2=>(+) (i(*iV3=>(+) (i(*i(

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

1.S::=aB B::= cB B::=b C::=c

2.S::=aB B::=bC C::=c C::=ε

3.S::=aAb aA::=aB aA::=aaA B::=b A::=a

4.S::=aCd aC::=B aC::=aaA B::=b

5.S::=AB A::=a B::=bC B::=b C::=c

6. S::=AB A::=a B::=bC C::=c C::=ε

7. S::=aA S::= ε A::=aA A::=aB A::=a B::=b

8. S::=aA S::= ε A::=bAb A::=a

正规文法 1 2 7 或者 1

上下文无关文法 5 6 8 或者 2 5 6 7 8

上下文有关文法 3

短语结构文法 4

P41 26. 给出产生下列语言L(G)={W|W∈{0，1}+且W不含相邻1}的正规文法。

G=({S, A, B}, {0, 1}, P, S)

P: S::=0|1|0S|1A

A::=0|0S

解题思路一：写出满足要求的符号串，例如0，1，00，01，10，000，101，010，001等，根据符号串从左至右的次序画出状态转换图，然后根据状态转换图来推导出文法。这将会得到S::=0|1|0S|1A|0Z|1Z A::=0|0S|0Z 经过分析其中Z为多余状态可删去。

S

Z

1

0

0

1

0

0

A

解题思路二：写出其正规表达式(0|10)*(10|0|1)【如果仅有(0|10)*的话推导不出1，因为是连接关系，后面缺了10的话就会以1结尾，同样的道理还要推导出0，所以得到此正规式】，画出转换系统，然后根据转换系统来推导出文法。也可以根据正规表达式直接写文法，例如正规表达式(0|10)*(10|0|1)可以看成是a*b，推导出A::= (0|10)A|10|0|1，即A::= 0A|1B|10|0|1，其中B::=0A，但是10此项不符合正规文法的选项，可以进行改写从而得到A::= 0A|1B|0|1 B::=0A|0。

P41 27. 给出一个产生下列语言 L(G)＝{W|W∈{a,b}*且W中含a的个数是b个数两倍的前后文无关文法。

文法G=({S, A, B}, {a, b}, P, S)

P: S::=AAB|ABA|BAA|ε

A::=aS

B::=bS

或者

S::=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSaa|baSa|baaS|ε

或者

S::=aaB|aBa|Baa|ε

B::=SbS

P41 28. 给出一个产生下列语言L(G)={w | w∈{a, b, c}+且w由相同个数的a，b，c组成的前后文有关文法。

文法G=({S, A, B}, {a, b, c}, P, S)

P: S::= ABC

A::=aS | a

B::=bS | b

C::=cS | c

AB::=BA

BC::=CB

AC::=CA

P42 29. 用扩充的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}

第四次作业：

P74 2. 什么叫超前搜索？扫描缓冲区的作用是什么？

词法分析程序在识别单词的时候，为进一步判明情况，确定下一步要做什么，一般采用超前读字符的方法，称超前搜索，扫描缓冲区的作用是为了识别单词符号。

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

Z：：=Be

B：：=Af

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

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

P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下：

S：：=bA A：：=bB A：：=aA A：：=b B：：=a

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

第五次作业：

P74 6. 构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？

Z：：=A0 A：：=A0|Z1|0

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

A := Z1 A := B1

A := A01

Z := A0 B := A0

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

此时利用书上规则，其对应的右线性文法为：A：：=0A|0B|0 Z：：=0A B：：=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}

S

Z’

0

0

1

A

0

Z

S’

ε

ε

显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；也可以通过求解正规表达式得到A=0(0|01)*，Z=0(0|01)*0

那么如何构造其相应的有穷自动机呢？

先构造其转换系统：

根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：(其中S’可以忽略，结果是一样的)

I

I0

I1

S

0 1

{S’, S}

{A}

Ф

0

1 Ф

{A}

{A, Z, Z’}

Ф

1

2 Ф

{A, Z, Z’}

{A, Z, Z’}

{A}

2

2 1

1

2

0

1

0

0

0

则其相应的DFA为：

P74 7. 构造一个DFA，它接受{0，1}上所有满足下述条件的字符串，其条件是：字符串中每个1都有0直接跟在右边，然后，再构造该语言的正规文法。【其它解法可参考P41-26题】

0

解(一)：其状态转换图为 (状态S表示空串开始，状态A表明串的末尾是1，状态Z表示串的末尾是0)

0

1

S

Z

A

0

1

DFA=({S，A，Z}，{0，1}，M，S，{Z})

其中M： M(S，0)=Z M(S，1)= A

M(A，0)=Z

M(Z，0)=Z M(Z，1)=A

该语言的正规文法G[Z]为：

右线性文法：//S：：=0|1A|0Z 左线性文法：

A：：=0|0Z A：：=1|Z1

Z：：=0|1A|0Z Z：：=0|A0|Z0

若终止状态只引入不引出则适合构造右线性文法，若开始状态只引出不引入则适合构造左线性文法，若终态和初态均既有引入又有引出，则构造文法要注意。

解(二)：可以先写出该文法的正规表达式为(0 | 10)*，根据该正规式构造转换系统

S

Z

A

ε

ε

0

1

B

0

A

0

1

B

0

对于该转换系统可以采用子集法将其转变为DFA，再根据DFA写出其正规文法；但是注意观察后，发现开始状态S通过ε到达A状态，可以直接删去S状态，由A状态作为新的开始状态，同理，只有A状态通过ε才能到达终止状态Z，因此可以删去Z状态，由A状态作为终止状态。这样，A状态就既为开始状态又为终止状态。可画出化简后的转换图。可写出右线性文法为：

A：：=0|0A|1B B：：=0|0S

P74 8. 设 (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)U M(B，a)= {A，B}U = {A，B}

故 M’([A，B]，a)= [A，B]

由于M({A，B}，b)= M(A，b)U M(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如下所示：

P74 9. 设有穷自动机M = ({S, A, E}, {a, b, c}, M, S, {E})，其中M定义为

M (S, c) = A M (A, b) = A M (A, a) = E 请构造一个左线性文法。

解：先求右线性文法

S→cA A→bA A→a | aE {A→aE实际上是多余的规则，应该去掉}

其左线性文法G=(VN, VT, P, S)

VN = {A, S} VT = {a, b, c} 根据书上左右线性文法的转换规则，得到

P: A→c A→Ab S→Aa {E→Aa实际上是多余的规则，应该去掉}

画出状态转换图之后就非常清晰。

P74 10. 已知正规文法G = ({S, B, C}, {a, b, c}, P, S)，其中P内包含如下产生式：

S::=aS | aB ……①

B::=bB | bC ……②

C::=cC | c ……③ 请构造一个等价的有穷自动机。

解：M=({S, B, C, T}, {a, b, c}, M, {S}, {T})

M (S, a)=S M (S, a)=B M (S, b)= M (S, c)=

M (B, a)= M (B, b)=B M (B, b)=C M (B, c)=

M (C, a)= M (C, b)= M (C, c)=T M (C, c)=C

第六次作业：

P74 11. 构造下列正规式相应的DFA：

(1)1(0|1)*101 【老课本】

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

S

Z

1(0|1)*101

S

1

5

3

4

Z

1

1

0

1

(0|1)*

S

1

5

3

4

Z

1

1

0

1

2

ε

ε

0

1

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

I

I0

I1

K

0 1

{S}

Ф

{1, 2, 3}

0

Ф 1

{1, 2, 3}

{2, 3}

{2, 3, 4}

1

2 3

{2, 3}

{2, 3}

{2, 3, 4}

2

2 3

{2, 3, 4}

{2, 3, 5}

{2, 3, 4}

3

4 3

{2, 3, 5}

{2, 3}

{2, 3, 4, Z}

4

2 5

{2, 3, 4, Z}

{2, 3, 5}

{2, 3, 4}

5

4 3

其对应的DFA状态转换图为：

0

5

1

1

2

3

1

0

0

1

1

4

0

0

1

1

0

0

5

1

1, 2

3

4

0

1

1

1

1

0

0

0

现在对该DFA进行化简，最终得到下列化简后的状态转换图(先将其分成两组——终态组{5}和非终态组{0, 1, 2, 3, 4}，再根据是否可继续划分来确定最后的组数)：

(1)(0 | 11*0)* 【新课本】

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

S

Z

(0 | 11*0)*

S

Z

ε

1

0

ε

2

1

3

ε

1

0

ε

4

S

Z

ε

1

0

ε

11*0

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

I

I0

I1

K

0 1

{S, 1, Z}

{1, Z}

{2, 3, 4}

0

1 2

{1, Z}

{1, Z}

{2, 3, 4}

1

1 2

{2, 3, 4}

{1, Z}

{3, 4}

2

1 3

{3, 4}

{1, Z}

{3, 4}

3

1 3

1

1

3

0

0

0

0

1

0

1

1

2

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

1

0

0

1

0

1

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

1

0

a

a, b

a

图3.24 NFA状态转换图

解：设(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]}

1

0

a

b

a

a

2

b

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

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

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

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

1

0, 2

a

b

a

P74 13. 构造下列正规式的DFA：

(1)b(a|b)*bab

此题的与P74第11题基本一样，见上；

P74 15. 用两种方法将(NFA) M = ({X, Y, Z}, {0, 1}, M, {X}, {Z})，构造相应的DFA，其中：

M (X, 0) = {Z} M (X, 1) = {X} M (Y, 0) = {X, Y}

M (Y, 1) = Ф M (Z, 0) = {X, Z} M (Z, 1) = {Y}

X

Z

1

0

1

0

0

0

Y

0

第一种方法：先画出其状态转换图，利用非子集法：

假设(DFA) M’=(K’, VT’, M’, S’, Z’)，其中K’={[X], [Y], [Z], [X,Y], [X, Z], [Y, Z], [X, Y, Z]}，VT’={0, 1}，M’的规则如下表：

I

I0

I1

K

0 1

[X]

[Z]

[X]

0

2 0

[Y]

[X, Y]

Ф

1

3 Ф

[Z]

[X, Z]

[Y]

2

4 1

[X, Y]

[X, Y, Z]

[X]

3

6 0

[X, Z]

[X, Z]

[X, Y]

4

4 3

[Y, Z]

[X, Y, Z]

[Y]

5

6 1

[X, Y, Z]

[X, Y, Z]

[X, Y]

6

6 3

其中[Y, Z]为不可到达状态，应该删去，所以S’={[X]}，Z’={[Z], [X, Z], [X, Y, Z]}，再进行化简，发现4和6两状态等价，最后其DFA如下所示：

0

1

1

0

0

0

1

3

0

1

1

2

4, 6

0

X

Z’

1

0

1

0

0

0

Y

0

Z

S

ε

ε

第二种方法：先构造其对应的转换系统：

由上述转换系统可得状态转换集、状态子集转换矩阵如下表所示：

I

I0

I1

K

0 1

{S, X}

{Z, Z’}

{X}

0

1 2

{Z, Z’}

{X, Z, Z’}

{Y}

1

3 4

{X}

{Z, Z’}

{X}

2

1 2

{X, Z, Z’}

{X, Z, Z’}

{X, Y}

3

3 5

{Y}

{X, Y}

Ф

4

5 Ф

{X, Y}

{X, Y, Z, Z’}

{X}

5

6 2

{X, Y, Z, Z’}

{X, Y, Z, Z’}

{X, Y}

6

6 5

1

4

1

0

5

0

0

0

1

0

1

3, 6

1

0, 2

先化简，分为非终态集 {2, 4, 5, 0} 和终态集 {6, 1, 3}，易于发现可划分为{0, 2}，{1}，{3, 6}，{4}，{5}，其DFA如下所示：

P74 16. 已知e1= (a|b)*，e2=(a*b*)*，试证明e1= e2。

证明：L(e1)=L((a|b)*)= (L (a|b))*= (L (a)∪L(b))*={a, b}*；

L(e2)= L((a*b*)*)= (L (a*b*))*=(L(a*)L(b*))*={{a}*{b}*}*={a, b}*；

因此e1= e2(得证)

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

S::=cC | a ……①

A::=cA | aB ……②

B::=aB | c ……③

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

P74 19. Σ＝{a, b}，写出下列正规集：

(1)(a | b)*(aa | bb)(a | b)*

解：L((a | b)*(aa | bb)(a | b)*) = L((a | b)*) L((aa | bb)) L((a | b)*) =(L (a | b))* {aa, bb} (L (a | b))* = {a, b}*{aa, bb}{a, b}*

P75 20. 证明下列关系式成立，其中A、B是任意正规表达式。

(1)A | A = A (3)A* = ε| AA* (4)(AB)*A = A(BA)*

(1)解：L(A | A) = L(A)∪L(A) = L(A)，所以A | A = A；

(3)解：L(A*) = (L(A))*，L(ε| AA*) ={ε}∪ L(A)L(A*) = (L(A))*，所以A* = ε| AA*；

(4)解：(AB)*A = ((AB)0 ∪(AB)1∪(AB)2∪……)A = A∪ABA∪ABABA∪…… = A((BA)0 ∪(BA)1∪(BA)2∪……) = A(BA)*。

第七次作业：

P142 1. 试分别消除下列文法的直接左递归(采用两种方法——重复法和改写法)

(1)G[E]:

E::=T | EAT ……①

T::=F | TMF ……②

F::=(E) | i ……③

A::=+ | - ……④

M::=* | / ……⑤

解：先采用“重复法”： 再采用“改写法”：

E::=T{AT} E::=TE’

T::=F{MF} E’::= ATE’ | ε

F::=(E) | i T::=FT’

A::=+ | - T’::=MFT’ | ε

M::=* | / F::=(E) | i

A::=+ | -

M::=* | /

(4)G[Z]:

Z::=V1 ……①

V1::=V2 | V1iV2 ……②

V2::=V3 | V2+V3 ……③

V3::=)V1* | ( ……④

解：先采用“重复法”： 再采用“改写法”：

Z::=V1 Z::=V1

V1::=V2 {iV2} V1::=V2 V1’

V2::=V3 {+V3} V1’::=i V2 V1’ | ε

V3::=)V1* | ( V2::=V3 V2’

V2’::=+V3 V2’ | ε

V3::=)V1* | (

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

(2)G[Z]:

Z::=AZ | b ……①

A::=Z A | a ……②

解(一)：将②式代入①式可得，Z::=ZAZ | aZ | b 消除左递归后得到：

Z::=(aZ | b)Z’

Z’::=AZZ’ | ε

A::=ZA | a

解(二)：将①式代入②式可得，A::= AZA | bA | a 消除左递归后得到：

Z::= AZ | b

A::=bAA’ | aA’

A’::=ZAA’ |ε

P142 4. 试分别用两种方法(框图法和类Pascal语言或类C语言)写一个识别下面文法句子的递归子程序

文法G[A]:

A::=[B ……①

B::=X] | BA ……②

X::=Xa | Xb | a | b ……③

解：消除该文法的左递归和回溯，得到文法如下：

A::=[B

B::=X]B’

B’::=AB’ |ε

X::=aX’ | bX’

X’::= aX’ | bX’ |ε

用类Pascal语言写出其递归子程序：

P(A): SCIN

IF ch=’[‘ THEN READ (ch) ELSE ERROR

P(B)

SCOUT

P(B): SCIN

P(X)

IF ch=’]‘ THEN READ (ch) ELSE ERROR

P(B’)

SCOUT

P(B’): SCIN

IF ch=’#’ THEN SCOUT

ELSE P(A)

P(B’)

SCOUT

P(X): SCIN

IF ch=’a‘ THEN { READ (ch) P(X’) }

ELSE

IF ch=’b‘ THEN { READ (ch) P(X’) }

ELSE ERROR

SCOUT

P(X’): SCIN

IF ch=’]’ THEN SCOUT

ELSE

IF ch=’a‘ THEN { READ (ch) P(X’) }

ELSE

IF ch=’b‘ THEN { READ (ch) P(X’) }

ELSE ERROR

SCOUT

用框图法来表述：(此处仅给出P(A)和P(X’)的框图形式，其余相似从略)

当消除左递归和回溯之后，可能某些非终结符号例如U的右部会出现ε的情况，书上的处理方法是ε将自动获得匹配，并无对此类规则的具体处理方法，实际上应该求出FOLLOW(U)，对于FOLLOW(U)中的每个终结符号进行判定，例如此例中的P(X’)，否则将无法判定出[a]

SCIN

1

ch=]?

=

3

2

READ

P(X’)

SCOUT

<>

4

10

7

ch=a?

=

5

P(X’)

<>

6

ch=b?

=

8

READ

<>

9

ERROR

P(A): P(X’):

SCIN

1

ch=[?

<>

3

ERROR

2

READ

P(B)

SCOUT

=

4

5

6

第八次作业：

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

E::=TE’

E’::=+E |ε

T::=FT’

T’::=T |ε

F::=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)构造文法分析表

a

b

+

*

(

)

∧

#

E

E→TE’

E→TE’

E→TE’

E→TE’

E’

E’→+E

展开阅读全文

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！