《编译原理》课后习题答案第三章
S→aA A→aA|B B→bB|b (3) A→aA|B B→bB|C C→cC|ε 第 17 题
习题７和习题 11 中的文法等价吗？ 答案： 等价。 第 18 题
解释下列术语和概念：（１） 字母表 （２） 串、字和句子
（３） 语言、语法和语义 答案：
（１） 字母表：是一个非空有穷集合。
（２）
串：符号的有穷序列。字：字母表中的元素。句子：如果 Z x , x +
∈V *T 则称 x 是文法 G 的一个句子。（３）语言：它是由句子组成的集合，
是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。
语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。
盛威网（www.snwei.com）专业的计算机学习网站
8
《编译原理》课后习题答案第三章
附加题
问题 1：
给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 答案：
R = (01 | 10) ( 01 | 10 )* 问题 2：
已知文法 G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案:
G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同. 问题 3：
给出语言描述，构造文法.
构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合. 答案一： G[E] E→E+T|T T→T* F|F F→(E)|a 答案二：
G[E] E→E+E|E* E|(E)|a 问题 4：
盛威网（www.snwei.com）专业的计算机学习网站
9
《编译原理》课后习题答案第三章
已知文法 G[S]: S→dAB A→aA|a B→ε|bB
相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 答案：
正规式是 daa*b*；
相应的正规文法为(由自动机化简来)：
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 问题 5：
已知文法 G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
试给出下述表达式的推导及语法树 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i)
答案：
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) E
E
E E + T E + T E + T T T * F T T F F i
i
F F F ( E ) i
i i
i
E + T
T F T
F i
盛威网（www.snwei.com）专业的计算机学习网站 (4)
i
10
《编译原理》课后习题答案第三章 F
F
i (1) 问题 6：
已知文法 G[E]: E→ET+|T T→TF* | F
F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：
该句型对应的语法树如下： 该句型相对于 E 的短语有 FF^^* 相对于 T 的短语有 FF^^*,F 相对于 F 的短语有 F^;F^^ 简单短语有 F;F^ 句柄为 F.
问题 7：
适当变换文法，找到下列文法所定义语言的一个无二义的文法： S → SaS ? SbS ? ScS ? d 答案：
该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。
i (2)
(3)
盛威网（www.snwei.com）专业的计算机学习网站
11
《编译原理》课后习题答案第三章
设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为： S → SaS ? A
A → AbA ? C C → CcC ? d
规定结合性为左结合，进一步将文法变换为： S → SaA? A
A → AbC ?C C → CcF ? F F → d
该文法为非二义的。
问题 8：构造产生如下语言的上下文无关文
法：
（1） {anb2ncm | n，m ≥ 0} （2） {anbmc2m | n，m ≥ 0} （3） { ambn ? m ≥ n }
（4） { a m b n c p d q ? m+n = p+q } （5） { uawb ? u,w ∈{a, b}* ∧ | u | = | w | } 答案：
（1） 根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。
对于该语言，存在一个由以下产生式定义的上下文无关文法 G[S]：
S → AB
A → ε ? aAbb B → ε ? cB
（2） 同样，要产生形如anbmc2m的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：
S → AB A → ε ? aA B → ε ? bBcc
盛威网（www.snwei.com）专业的计算机学习网站
12
编译原理课后习题答案+清华大学出版社第二版
