各章练习题(编译原理).pdf

第三章复习重点：1.文法与语言的对应关系
语言L(G)=L(G’)文法G文法G’

{bn|n>0}B→bB|bB→Bb|b
{bn|n≥0}P→bP|εP→Pb|ε
S→DB
S→aB
{abn|n>0}D→a→
B→bB|bBBb|b
T→PDT→Pa
{bna|n≥0}D→a
P→bP|εP→Pb|ε

U→EU|EU→Uab|ab
{(ab)n|n>0}E→ab

V→ABV→aV|aB
{ambn|m>0,n>0}A→aA|aB→bB|b
B→bB|b
→
WABW→aW|B
{ambn|m≥0,n>0}A→aA|ε
B→bB|bB→bB|b

{anbn|n>0}X→aXb|ab
X→DXH|DH
D→Acd
{(akcd)nbn|k,n>0}A→aA|a
H→b
Y→KYH|a

{a2n+1bn|n>=0}Y→aaYb|aK→aa
H→b

思路要点：注意结构拆分
技巧：如何将表示语言的通用字符串形式作适当的“切割”？

例：已知语言：L1={axb2xcy|x,y>=0}，给出此语言的文法，并证明此语言是上
下文无关语言。
提示：该题实际上要求为相应语言设计上下文无关文法。
一个文法设计好后，严格来说应当证明此文法是否对应于该语言。
解：G[S]：S→ABA→|aAbbB→|cB

推导过程：
SAB+axAb2xB/*使用A→aAbbx次*/
axb2xB/*使用A→一次*/
axb2xcxB/*使用B→cBx次*/
axb2xcx/*使用B→一次*/

举一反三：已知语言L2={axb2ycy|x,y>=0}，给出此语言的文法，并证明此
语言是上下文无关语言。
解：G[S]：S→ABA→|aAB→|bBcc
练习：14：写出下列语言对应的文法
(1).{anbnambm|n,m≥0}
2.{1n0m0m0n|n,m≥0}
3.{1n0m0m0n|n≥0,m>0}
4.{anbmck|n,m,k≥0}
G1:S—>AAG2:S—>AB
A—>aAb|εA—>aAb|ε
B—>aBb|ε
G:S—>1S0
S—>A
A—>0A1
A—>ε
G:S1S0|AS1S0|0A1
A0A1|01A0A1|ε
2.给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、
直接短语、句柄。
1.令文法G［E］为：
Z→bMb
M→a|(L
L→Ma）
①符号串b(Ma)b是否为该文法的一个句型，并证明。
②若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。
1）（5分）证明：S=>bMb=>b(Lb=>b(Ma)b
所以，符号串b(Ma)b是该文法的一个句型。
（2）（5分）短语:Ma)，(Ma)，b(Ma)b
直接短语:Ma)句柄:Ma)
练习：
（10分）已知文法G[T]：T→T*F|F；F→F↑P|P；P→(T)|i
（1）用最右推导法证明β：T*P↑(T*F)是G[T]的一个句型；
（2）画出β的语法树；
（3）写出β的全部短语、直接短语和句柄。
(1)T=>T*F=>T*F↑P=>T*F↑(T)=>T*F↑(T*F)
=>T*P↑(T*F)证毕。
(2)如图
T

T*F

F↑P

P(T)

T*F

第3题语法树

（3）短语：T*P↑(T*F)；P↑(T*F)；(T*F)；T*F；P
直接短语：T*F；P
句柄：P
3.证明一个文法是二义性文法。
证明下述文法G［S］是二义的。（5分）
S->iSeS|iS|i
解：
SS

iSeSiS

iSiSeS

可见，句型iises有两种不同的语法树，所以G[S]是二义的。
练习：证明下述文法G：
SaSbS|aS|d
是二义性文法。
解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个
文法是二义性文法。
句子aadbd有两棵语法树。如下图：
S
S

aS
aSbS

aSbS
aSd
dd
(1)d(2)
由此可知，SaSbS|aS|d定义的文法是二义性文法。

第四章:重点：1.NFADFA的确定化及DFA的最小化。
2.试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化
将下图所示的NFA确定化，再最小化。(2010年出过)

3
aa


X12Y


4
b
a
用子集法确定化如下表:
编号II
Iab
AA{X,1,2,4}B{1,2,3,4}C{1,2,4,Y}
BB{1,2,3,4}B{1,2,3,4}C{1,2,4,Y}
CC{1,2,4,Y}B{1,2,3,4}C{1,2,4,Y}
由于对于非终态的状态A和B来说，它们输入a、b的下一个状态都是一样的，故状态A
和B可以合并，将合并后的状态重命名为A，而终态则重命名为B，则