当前位置：文档库 › 王汝传编译原理习题答案

王汝传编译原理习题答案

《编译原理》习题答案：

第一次：

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∪……∪A n∪……

A*＝A0（即{ε}）∪A+

A A*＝A（A0∪A+）＝A∪A+＝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 试写出V N和V T。

V N＝{S，A，B，C，D}

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

P38-39

8、设有文法G[S]：

S∷＝aAb

A∷＝BcA | B

B∷＝idt |ε

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

（1）S?aAb?aBcAb?aidtcAb?aidtcBcAb 句型但不是句子；

（3）S?aAb?aBb?aεb?ab 是句型也是句子；

（5）S?aAb?aBcAb?aidtcAb?aidtcBcAb?aidtcidtcBb?aidtcidtcidtb句型也是句子。

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

（1）L(G)＝{0n1| n≥1}；

（2）L(G)＝{a2n bc | n≥0}。

P39

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

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

（3）{ aba n | n≥1}

（5）{ a n b m c p | n，m，p≥0}

（1）G＝{V N，V T，P，S}，V N＝{S，A }，V T＝{a，b}，

P：S∷＝aAa

A∷＝bA |ε

（3）G＝{V N，V T，P，S}，V N＝{S，A }，V T＝{a，b}，

P：S∷＝abA

A∷＝aA |ε或A∷＝aA | a

（5）①G＝{V N，V T，P，S}，V N＝{S，A ，B，C}，V T＝{a，b，c}，P：S∷＝ABC

A∷＝aA |ε

B∷＝bB |ε

C∷＝cC |ε

②G＝{V N，V T，P，S}，V N＝{S，T，C}，V T＝{a，b，c}，

P：S∷＝TC

T∷＝aTb |ε

C∷＝cC |ε

③G＝{V N，V T，P，S}，V N＝{S }，V T＝{a，b，c}，

P：S∷＝aS | bS | cS |ε

第三次作业：

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 a

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

（3）

A B

b B

S b

A B

短语bB, AB, ABb，

简单短语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

3) S::=A|B

A::=aCbA|a

B::=BCC|a

C::=ba

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

i S e S

i S i S

i i

i S

i S e S

i i S

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

a C

b A

b a a

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 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|0B|1A

A::=0|0S

B::=0|1

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

或者

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

1．Z::=AB|AC|A

2．A::=BC|BCD|AXZ|AXY

3．S::=aABa|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

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

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

则其相应的DFA 为：

P74 7. 构造一个DFA 每个1都有0直接跟在右边，然后，再构造该语言的正规文法。

解：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 左线性文法：//S ：：=0|A0|Z0

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

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}

S 的元素是[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 如下所示：

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

由于{1，2}a={1，2}b={2} {1，2}，不能再划分。至此，整个划分含有两组{1，2}{0} 令状态1代表{1，2}，化简如图：

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

其左线性文法G=（V N, V T, P, S）

V N={A, S} V T={a, b, c}

P: A→c A→Ab S→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

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

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

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

a 图3.24 NFA 状态转换图

解：设(DFA)M = {K, V T, M, S, Z}，其中，K={[0], [0, 1], [1]}，V T ={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]}

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}

假设(DFA) M’=(K’, V T’, M’, S’, Z’)，其中K’={[X], [Y], [Z], [X,Y], [X, Z], [Y, Z], [X, Y, Z]}，

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

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

P74 16. 已知e 1= (a|b)*，e 2=(a*b*)*，试证明e 1= e 2。

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

L(e 2)= L((a*b*)*)= (L (a*b*))*=(L(a*)L(b*))*={{a}*{b}*}*={a, b}*；因此e 1= e 2（得证）

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)

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*

（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*；

第七次作业：

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

（1）G[E]:

E::=T | EAT ……①

T::=F | TMF ……②

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

A::=+ | - ……④

M::=* | / ……⑤

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

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

T::=T{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::=V1Z::=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

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 ’)的框图形式，其余相似从略）

P(A): P(X ’):

第八次作业：

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

E::=TE ’

ch=[? <> 3

ERROR

ch=ε? ch=b?

<> 9 ERROR

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’)={+, #, }}∩FIRST(ε)= ?

FIRST(*F’)={*}∩FIRST(ε)= ?，FIRST(+E)={+}∩FOLLOW(E’)= {#, )}=?

FIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, #, )}=?

FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=?

所以该文法是LL（1）文法。

（3）构造文法分析表

P144 6. 对下列文法，构造相应的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)={ε，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，#}.

P144 9. 设已给文法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，＃}.

编译原理课后习题答案(第三版)

精品文档第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************

王汝传编译原理习题答案

《编译原理》习题答案：第一次： 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……}

(完整版)编译原理课后习题答案

第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。（1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答：（1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab

编译原理复习题及答案

编译原理复习题及答案一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba

编译原理习题解答

第二章：习题2-4 Table表 var x,y; procedure p; var a; procedure q; var b; begin b:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end; begin call p; end 根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，而表中各部分的含义，

第三章文法和语言 5. 写一文法，使其语言是偶正整数的集合要求： (1)允许0打头 (2)不允许0打头解： (1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: S→PD|D P->NP|N D→0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: S→PD|P0|D P->NR|N R->QR|Q D→2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9 6. 已知文法G： <表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。试给出下述表达式的推导及语法树。 (1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i); (6)i+i*i。解： (1)v=<表达式>=><项>=><因子>=>i=w (2)v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w (3)v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w (4)v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项> =><因子>*<因子>+<因子>=>i*i+i=w (5)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>) => i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w (6)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项> =>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w 语法树见下图:

编译原理课后答案

第二章 2.3叙述由下列正规式描述的语言 (a) 0(0|1)*0 在字母表{0, 1}上,以0开头和结尾的长度至少是2的01 串 (b) ((ε|0)1*)* 在字母表{0, 1}上,所有的01串,包括空串 (c) (0|1)*0(0|1)(0|1) 在字母表{0, 1}上,倒数第三位是0的01串 (d) 0*10*10*10* 在字母表{0, 1}上,含有3个1的01串 (e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 在字母表{0, 1}上,含有偶数个0和偶数个1的01串 2.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。［解答］ other → a | b | … other指除了*以外C语言中的其它字符 other1 → a | b | … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1）因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：由此可以写出其正规文法为： S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1 在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得： S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00| 11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|1

编译原理课后习题答案-清华大学-第二版

第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”就是为了。 a．提高程序得执行效率 b．使程序得结构更加清晰 c．利用有限得机器内存并提高机器得执行效率 d．利用有限得机器内存但降低了机器得执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都就是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能就是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序得意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器得输入就是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循得就是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序就是对。 a．汇编程序得翻译b．高级语言程序得解释执行 c．机器语言得执行d．高级语言得翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。

编译原理课后习题答案

第1 章 1、编译过程包括哪几个主要阶段及每个阶段的功能。答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。第2 章 1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(()),()(())等，甚至包括0 对括号）文法为：S→(L)|LS|L L→S| ε 2 、已知文法G ：E→E+T|E-T|T T→T*F|T/F|F F→(E) |i （1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。（2）i-i+i 哪个算符优先。【解答】（1）最左推导：E?E+T?T+T? F+T ? i+T ? i+T*F ? i+F*F ?i+i*F ?i+i*i E?T?T*F? F*F ? i*F ? i*(E) ? i*(E-T) ? i*(T-T) ? i*(F-T) ? i*(i-T) ? i*(i-F) ?i*(i-i) 最右推导：E?E+T?E+T*F? E+T*i ? E+F*i ? E+i*i ? T+i*i ? F+i*i ? i+i*i E?T?T*F? T*(E) ? T*(E-T) ? T*(E-F) ? T*(E-i) ? T*(T-i) ? T*(F-i) ?T*(i-i) ? F*(i-i) ?i*(i-i) i+i*i 以及i*(i-i)的语法树如下所示：（2）i-i+i 的语法树如下图所示。从上图的语法树可知：“-”的位置位于“+”的下层，也就是前面两个i 先进行“-”运算，再与后面的i 进行“+” 运算，所以“-”的优先级高于“+”的优先级。 3 、文法G: E→ET+|T T→TF*|F F→FP↑|P P→E|i （1）试证明符号串TET+*i↑是G 的一个句型(要求画出语法树). （2）写出该句型的所有短语,直接短语和句柄. 【解答】（1）采用最右推导： E?T?F? FP↑? Fi↑? Pi↑? Ei↑ ? Ti↑? TF*i↑? TP*i↑? TE*i↑? TET+*i↑ 语法树如下图所示。从文法G 的起始符号出发，能够推导出符号串TET+*i↑，所以给定符号串是文法G的句型。 (2) 该句型的短语有： ET+,TET+*,i ,TET+*i↑ 直接短语有：ET+, i 句柄是：ET+ 4、已知文法G：S→iSeS|iS|i ，该文法是二义文法吗？为什么？【解答】该文法是二义文法。因为对于句子iiiei 存在两种不同的最左推导：第 1 种推导：S? iSeS? iiSeS? iiieS? iiiei 第2种推导：S?iS?iiSeS?iiieS?iiiei 第3 章 1、用正规式描述下列正规集：（1）C 语言的十六进制整数；（2）以ex 开始或以ex 结束的所有小写字母构成的符号串；（3）十进制的偶数。【解答】（1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε） (0x|0X)AA*，其中前面括号表示符号，可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的

编译原理第三版课后习题与答案

目录 P36-6 (2) P36-7 (2) P36-8 (2) P36-9 (3) P36-10 (3) P36-11 (3) P64–7 (4) P64–8 (5) P64–12 (5) P64–14 (7) P81–1 (8) P81–2 (9) P81–3 (12) P133–1 (12) P133–2 (12) P133–3 (14) P134–5 (15) P164–5 (19) P164–7 (19) P217–1 (19) P217–3 (20) P218–4 (20) P218–5 (21) P218–6 (22) P218–7 (22) P219–12 (22) P270–9 (24)

P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************

编译原理习题及答案(整理后)

第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。

一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a)

编译原理课后习题答案+清华大学出版社第二版

第 1 章引论第1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

编译原理复习题及答案

编译原理复习题及答案一、选择题 1．一个正规语言只能对应( B ) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是( A ) A 正规文法 B 二型文法 3．下面说法正确的是( A ) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A ) A 必要条件 B 充分必要条件 5．下面说法正确的是( B ) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是( A ) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是( A ) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行

11．(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序?B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序? C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器?C．表格处理和出错处理 ??? D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)

编译原理(清华大学第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．

短语：直接短语：句柄： 13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法：S → ABS S → Aa S →ε A → a B → b (3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语： a1 , b1 , b2, a2 , , 句柄：a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

(完整版)编译原理及实现课后习题答案

编译原理及实现课后习题解答 2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*. x0=(aaa)0=ε| x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…} A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…} 2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*

S S S * S S + a a a 2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101 2.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。 A∷=aA︱ε描述的语言: {a n|n>=0} B∷=bBc︱bc 描述的语言：{b n c n|n>=1} L(G[S])={a n b m c m|n>=0,m>=1} 2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。开始符号：E V t={+, - , * , / ,（, ）, i} V n={E , F , T}

王汝传编译原理习题答案

编译原理课后习题答案(第三版)

王汝传编译原理习题答案

(完整版)编译原理课后习题答案

编译原理复习题及答案

编译原理习题解答

编译原理课后答案

编译原理课后习题答案-清华大学-第二版

编译原理习题及答案(整理后)

编译原理课后习题答案

编译原理第三版课后习题与答案

编译原理习题及答案(整理后)

编译原理课后习题答案+清华大学出版社第二版

编译原理复习题及答案

编译原理(清华大学 第2版)课后习题答案

(完整版)编译原理及实现课后习题答案

最新编译原理小题答案

编译原理(清华大学第2版)课后习题答案