编译原理第二版答案张素琴

s?(a)|a a?a+s|s

1）构造各非终结符的firstvt集合和lastvt集合。 2）构造优先关系表。

15、设文法g（s）： s?(a)|a a?a+s|s

1）构造各非终结符的firstvt集合和lastvt集合。 2）构造优先关系表。

16、设文法g（s）： s?(a)|a a?a+s|s

1）构造各非终结符的firstvt集合和lastvt集合。 2）构造优先关系表。

【篇三：编译原理课后习题答案(清华大学_张素琴)复习

例题】

、lr（1）、lalr（1）等。但要求至少要按照作业题的范围复习。) 一 选择题

1．编译的各阶段工作都涉及 。

[a]词法分析 [b]表格管理 [c]语法分析 [d]语义分析 2． 型文法也称为正规文法。 [a] 0 [b] 1[c] 2 [d] 3 3． 文法不是ll(1)的。

[a]递归[b]右递归[c]2型[d]含有公共左因子的

4．文法e→e+e|e*e|i的句子i*i+i*i有 棵不同的语法树。 [a] 1 [b] 3[c] 5 [d] 7

5．文法 s→aas|abc 定义的语言是 。 [a]{a2kbc|k0}

[c]{a2k-1bc|k0} [b]{akbc|k0} [d]{akakbc|k0} 6．若b为非终结符，则 a→?.b? 为 。

[a]移进项目 [b]归约项目 [c]接受项目 [d]待约项目 7．同心集合并可能会产生新的 冲突。

[a]二义 [b]移进/移进 [c]移进/归约 [d]归约/归约 8．代码优化时所依据的是 。 [a]语法规则 [b]词法规则

[c]等价变换规则[d]语义规则

9．表达式a-(-b)*c的逆波兰表示（@为单目减）为 。 [a]a-b@c* [b]ab@c*- [c]ab@- [d]ab@c-*

10．过程的display表是用于存取过程的 。

[a]非局部变量 [b]嵌套层次 [c]返回地址 [d]入口地址 二 填空题

1．词法分析阶段的任务式从左到右扫描 字符流 ，从而逐个识别 一个个的单词 。

2．对于文法g[e]：e→t|e+t t→f|t*f f→p^f|pp→(e)|i，句型t+t*f+i的句柄是 。

3．最右推导的逆过程称为 规范归约 ，也称为 最 左归约 。

4．符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表是的依据。

三 判断题（认为正确的填“t”，错的填“f”）

【】1．同心集的合并有可能产生“归约/归约”冲突。

【】2．一个文法所有句子的集合构成该文法定义的语言。 【】3．非终结符可以有综合属性，但不能有继承属性。 【】4．逆波兰表示法表示表达式时无需使用括号。 【】5．一个有穷自动机有且只有一个终态。

【】6．若过程p第k次被调用，则p的display表中就有 k+1个元素。 四 解答题

1．给定文法g和句型(t+f)*i+t, g: e→e+t | tt→t*f | ff→(e) | i （1）画出句型的语法树；

（2）写出句型的全部短语、简单短语和句柄。 解：（略）

2．设有文法g：s→s+s|s*s|i|(s)。

（1）对于输入串i+i*i 给出一个最左推导；

（2）该文法是否是二义性文法？请证明你的结论。 解：（1）i+i*i的最左推导：

s = s+s = i+s = i+s*s = i+i*s = i+i*i

（2）该文法是二义性的。因为对于句子i+i*i可以画出两棵 语法树（语法树略）。

3．给出语言{ambmcn|m≥1,n≥0}的上下文无关文法（2型）。 解： g: s→ab|a a→aab|ab b→cb|c

4．给出语言{akbmcn|k,m,n≥1}的正规文法（3型）。 解： g: a→aa|ab b→bb|bc c→cc|c

5．将文法g改写成等价的正规文法（3型）。 g: s→dab a→aa|a b→bb|b

解： g: s→da a→aa|ab b→bb|b

6．构造一文法产生任意长的a，b串，使得 |a|≤|b|≤2|a|

其中，“|a|”和“|b|”分别表示串中的字符a和b的个数。 解：b的个数在a的个数和其2倍之间，串的结构形如asbs和 bsas，其中b为1或2个b。故得文法 b→b|bb

7．设有字母表{a，b}上的正规式r=(ab|a)*。 （1）构造r的相应有限自动机； 解：

（2）构造r的相应确定有限自动机；

（3）构造r的相应最小确定有限自动机；

解：对（2）得到的dfa化简，合并状态0和2 为状态2： +

（4）构造与r等价的正规文法

解：令状态1和2分别对应非终结符b和a 可化简为：

8．写出如图所示的自动机描述的语言的正规式 解：abb*|abb*aa*b|aaa*b

9．写出在{a,b}上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简dfa）。

解：依题意，“不以a开头”，则必以b开头，又要“以aa 结尾”，

故正规式为：b(a|b)*aa

（构造与之等价的最简dfa，此略） 10．写一个

ll(1)文法g，使其语言是

l(g)={ ambnc2n | m=0,n0 } 并证明文法是ll(1)。

解：文法g（s）：s ? as | e e ? be’

e’? ecc | cc

故文法为ll(1)的

11．将文法g改写成等价的ll(1)文法，并构造预测分析表。 t→+at|+a

（编写递归下降子程序）

解：消除左递归后的文法g’: s→ats’|*ats’ t→+at|+a

提取左公因子得文法g’’:s→ats’|*ats’ t→+at’

select(s→ats’)={a} select(s→*ats’)={*} select(s’→*ats’)={*} select(t→+at’)={+}

select(t’→t)=first(t) ={+} 所以该文法是ll(1)文法。

12．对文法g[s]: s → asb | p p → bpc | bqc q → qa | a

（递归下降子程序，略）