《编译原理》课后习题答案第三章 第 16 题 给出生成下述语言的三型文法：
(1){an|n >=0 } (2) { anbm|n,m>=1 } (3){anbmck|n,m,k>=0 } 答案：
(1) S→aS|ε (2) 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
《编译原理》课后习题答案第三章 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。
盛威网（www.snwei.com）专业的计算机学习网站
9
《编译原理》课后习题答案第三章 附加题
问题 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：
已知文法 G[S]: S→dAB A→aA|a B→ε|bB
盛威网（www.snwei.com）专业的计算机学习网站
10
《编译原理》课后习题答案第三章
相应的正规式是什么？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 + T E + T E + T T T * F T T F F i
i
F F F ( E ) i
+ E
i i
i
E T
E
T F T F i F
F
(4)
i
盛威网（www.snwei.com）专业的计算机学习网站
11
《编译原理》课后习题答案第三章
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 答案：
该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。
设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为： S → SaS ? A
A → AbA ? C i (2)
(3)
盛威网（www.snwei.com）专业的计算机学习网站
12
相关推荐：
loading