发布时间 : 星期六 文章(整理完)编译原理网上作业题参考答案20121101更新完毕开始阅读
图 语法树
（2）句子acabcbbdcc的最左推导如下： ST
aAcB
aAaBcB
acaBcB
acabcB
acabcbScA
acabcbBdcA
acabcbbdcA
acabcbbdcc
5．对于文法G[S]： S→（L）|aS|a
L→L, S|S
（1）画出句型（S,（a））的语法树。
（2）写出上述句型的所有短语、直接短语、句柄和素短语。（﹡﹡﹡） 解答：
（1）句型（S,（a））的语法树如下图所示。
图 句型（S,（a））的语法树
（2）由上图可知：
①短语：S、a、(a)、S,(a)、(S,(a))； ②直接短语：a、S； ③句柄：S；
④素短语：素短语可由图2-8-3中相邻终结符之间的优先关系求得，即；
因此素短语为a。
6. 考虑文法G[S],其产生式如下: S→(L)|a L→L，S|S
(a)试指出此文法的终结符号、非终结符号。 (b)给出句子(a,(a，a))的分析树。 (c)构造句子(a,(a，a))的一个最左推导。 (d)构造句子(a,(a，a))的一个最右推导。 (e)这个文法生成的语言是什么？（﹡﹡） 解答：(a) 终结符号为：{(,),a,,} 非终结符号为：{S,L} 开始符号为：S (b)分析树
,
（c） S (d) S
(L)
(L,S)
(S,S)
(a,S)
(a,(L)
(a,(L,S))
(a,(S,S)) (L,S)
(a,(a,S)) (L,(L))
(a,(a,a))
(L,(L,a))
(a,(a,a))
(L) (L,(L,S))
(L,(S,a))
...
(L,(a,a)) (S,(a,a))
(e) L(G[S]) = (α1,α2,,αn)或a
其中αi(1≤i≤n)是L(G[S])。即L(G[S])产生一个以a为原子的纯表，但不包括空表。 7．考虑文法G[T]： T→T*F|F F→F↑P|P P→（T）|i
证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。（﹡﹡） 解答：
首先构造T*P↑（T*F）的语法树如下图所示。
图 句型T*P↑（T*F）的语法树
由上图可知，T*P↑（T*F）是文法G[T]的一个句型。 直接短语有两个，即P和T*F；句柄为P。
8．试描述下列文法产生的语言L（G[S]）（﹡﹡）
S→10S0|aA A→bA|a
解答：L(G)={(10)iabna0i n≥0 i≥0}
9．已知语言L(G)={abnc |n≥1} 试对该语言构造相应文法。（﹡﹡） 解答：G[Z]: Z→aBC B→Bb|b
10．证明下列文法的二义性 （﹡﹡﹡） 1．G[Z] 2．G[S] Z→aZbZ|aZ|a S→AB A→bB|bC|ba B→Sb|ba|a C→Bb|b 解答：（1）
对于句子aaaba，画出二棵不同的语法树，因而是二义的。
（2）
G[S]