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

《编译原理》课后习题答案第一章 第 4 题 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。 （1） else 没有匹配的if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符 答案： （1） 语法分析 （2） 语义分析 （3） 语法分析 （4） 词法分析 《编译原理》课后习题答案第三章 第1 题 文法G＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc}

第2 文法G[N]N→D→G[N]的语言答案G[N]的语言是N=>ND=>NDD.... =>NDDDD...D=>D......D

题

为：

D|ND

0|1|2|3|4|5|6|7|8|9 什么？

:

。V={0,1,2,3,4,5,6,7,8,9}

是V+

或者：允许0 开头的非负整数？

第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 答案： G[S]:

S->S+D|S-D|D

D->0|1|2|3|4|5|6|7|8|9 第4 题 已知文法G[Z]： Z→aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={anbn|n>=1}

1 / 25

第5 题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0 打头； (2)不允许0 打头。 答案： (1)允许0 开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0 开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6 题 已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i 答案： <表达式> <表达式> + <项> <因子> <表达式> <表达式> + <项> <因子> i <项> <因子> i <项> <因子> i （ ) (5) <表达式> =><表达式>＋<项> =><表达式>＋<因子> =><表达式>＋（<表达式>）

2 / 25

=><=><=><=><=><=><=><=><=>i<<<<<

表达式>表达式>表达式表达式表达式表达项>因子

＋

表

表项

＋（<表达式>＋<项＋（<表达式>＋<因子>＋（<表达式>＋

>＋（<项>＋>＋（<因子>＋式>＋（i＋i

＋（i＋i>＋（i＋i（i＋i

达式

达式> + <项

> * <因子因子

项

因子

>

>iii

） ） ） ） ） ） ） ） ） > > > > i > >

(6) <表达式> =><表达式>＋<项> =><表达式>＋<项>*<因子> =><表达式>＋<项>*i =><表达式>＋<因子>*i =><表达式>＋i*i =><项>＋i*i =><因子>＋i*i =>i＋i*i 第7 题 证明下述文法G[〈表达式〉]是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/ 答案： 可为句子a+a*a 构造两个不同的最右推导: 最右推导1 〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉a 〈表达式〉* a 〈表达式〉〈运算符〉〈表达式〉* a 〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a a + a * a

最右推导2 〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉 a 〈表达式〉〈运算符〉〈表达式〉 * a 〈表达式〉〈运算符〉a * a

3 / 25

〈表达式〉+ a * a a + a * a 第8 题 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 答案： 对于串abc (1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 或者： 对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。 S a B b c S A c a b

第9 考虑下面上下文无S→

(1)表明通过此文法如何生成串aa+a*，并为S S S * S S + a a a (2)G[S]的语言是答案(1)此文法生成串aa+a*的最S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

题

关文法：

SS*|SS+|a

该串构造语法树。

什右

推

么导

如？ ： 下

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 第10 题 文法S→S(S)S|ε (1) 生成的语言是什么？ (2) 该文法是二义的吗？说明理由。 答案： （１） 嵌套的括号 （２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 第11 题 令文法G[E]为： E→T|E+T|E-T T→F|T*F|T/F

4 / 25

F→(E)|i 证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以 E+T*F 句型 此句型相对于E 的短语有:E+T*F；相对于T 的短语 有T*F 直接短语为：T*F 句柄为：T*F 第13 题 一个上下文无关文法生成句子abbaa 的推导树如下： (1)给出串abbaa 最左推导、最右推导。 (2)该文法的产生式集合P 可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 B a S A B S a S B A ε b b a 答案： (1)串abbaa 最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa

最右推导S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→可能元素有：(3)该句子a 是相对A 的短语 ε 是相b 是相对εbb 是相aa 是相对aεbbaa 是相直接短语句柄

：

ABS |Aa|ε A→a B→SBB|b

ε aa ab abbaa aaabbaa …… 的短语有： 对

B 对

S

对有是后1 规

习

：B

的S

的a ：答

案

S

的的的

短短短短短ε

语 语 语 语 语 b a 四

章 题 DFA. *101 *0

《第构（（

编造

译原下１

理列）

》正）

课题第的）

２１

式相应 1(0|1)

(1010*|1(010)*1

5 / 25