发布时间 : 星期四 文章编译原理期末复习题(含答案2011-5)更新完毕开始阅读ff1ad9a5f524ccbff1218403
（8） （*，f，e，T6） （9） （-，T5，T6，T7） （10） （：=，T7， ，b） （11） （BR， ， ，（1）） （12） 8、将语句
if A V B>0 then while C>0 do C:=C+D 翻译成四元式。 答：
100 (jnz， A， -， 104) 101 (j， -， -， 102) 102 (j>， B， 0， 104) 103 (j， -， -， 109) 104 (j>， C， 0， 106) 105 (j， -， -， 109) 106 (+， C， D， T1) 107 (:=， T1， -， C) 108 (j， -， -， 104)
109
9、对下列文法G: S'->#S# S->D(R) R->R;P|P P->S|i D->i
（1）计算文法G中每个非终结符的FIRSTVT集； （2）计算文法G中每个非终结符的LASTVT集； 答：（1）各非终结符的FIRSTVT集合为：
FIRSTVT（S’）={ #} FIRSTVT（P）={（，FIRSTVT（S）={（，i） FIRSTVT（D）={i } FIRSTVT（R）={；，（，i ） （2）各非终结符的LASTVT集合为：
LASTVT（S’）={#} LASTVT（P）={ }，i} LASTVT（S）={} } LASTVT（D）={ i}
LASTVT（R）={；，），i} 10、对下列文法G:
）i S'->#S# S->fStS S->i=E E->E+T|T T->P↑T|P P->(E)|i
（1）计算文法G中每个非终结符的FIRSTVT集； （2）计算文法G中每个非终结符的LASTVT集；
答：（1）各非终结符的FIRSTVT集合为：
FIRSTVT（S’）={ #} FIRSTVT（T）={ ↑，（，i） FIRSTVT（S）={f，i} FIRSTVT（E）={+，↑，（，i ） FIRSTVT（P）={（，i ）
（2）各非终结符的LASTVT集合为：
LASTVT（S’）={#} LASTVT（T）={ ↑，}，i} LASTVT（S）={ t，=，+，↑，)，i} LASTVT（E）={ +，↑，}，i} LASTVT（P）={ }，i}
11、文法G1：P->PaP|PbP|cP|Pe|f
证明文法G1是二义文法。
答：因为文法存在句型：fbfbf ，此句型有两棵不同的语法树，所以文法是二义的。
或存在2种最右推导：
A、 P=>PbP=>PbPbP=>PbPbf=>Pbfbf=>fbfbf B、 P=>PbP=>Pbf=>PbPbf=>Pbfbf=>fbfbf 12、有文法G[N]：
N->SE|E S->SD|D
E->0|2|4|6|8|10 D->0|1|2|3|4|5|6|7|8|9
证明该文法是二义的；此文法描述的语言是什么？并试写出另一文法，使L（G‘）=L（G），且G‘是无二义的。
答：对于该文法，存在句型110，有两棵不同的语法树或两种不同的最右推导，因此文法具有二义性。
A、 N=>SE=>S10=>D10=>110
B、 N=>SE=>S0=>SD0=>S10=>D10=>110
该文法描述的语言是偶数集合。 等价的无二义文法是： G‘[N]： N->SE|E S->SD|D E->0|2|4|6|8
D->0|1|2|3|4|5|6|7|8|9
13、写出不能被5整除的偶整数的文法。 答：G[Z]:
Z->(+|-)AB
A->0|1|2|3|4|5|6|7|8|9|AA B->1|2|3|4|5|6|7|8|9 14、对于文法G=（VN，VT，S，P）：
VN={ S，A，B，}；VT={a，b}，开始符号为S
P： S->aB|bA A->aS|bAA|a B->bS|aBB|b 给出串aaabbabbba的
（1） 最左推导；（2）最右推导；（3）推导树。 答：最左推导：
S=>aB=>aaBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB=>aaabbabbS=>aaabbabbbA=>aaabbabbba 最右推导：
S=>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>aaabbabbba
15、什么是句柄？
答：一个句型德最左直接短语称为句柄。 16、什么是最左素短语？
17、 上下文无关文法
答：若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；
四、问答题：
1、给出将赋值语句翻译成四元式的语法制导定义，允许右部表达式含有加法、乘法、取负、括号运算。生成赋值语句x:=b*(c+d)+a的四元式。
2、出条件赋值语句 i:=if b then e1 else e2 的语义子程序。其中b是布尔表达式，e1和e2 是算术表达式，I代表与e1和e2类型相同的左部变量。按写出的语义子程序生成条件赋值语句 z:=if a>c then x+y else x-y+0.5 的四元式序列。
3、试写出PASCAL循环语句 for I:=1 to n do s的语义子程序，假定该语句的文法为：
F1:=for i:=1 to n S:= F1 do S1
4、给出做为条件控制的布尔表达式翻译为四元式的语法制导定义，允许布尔表达式中有与、或、非及括弧运算。（如在翻译过程中使用了自定义的函数，可以不写函数过程，但请注明函数的功能和出入口的参数）。
5、按语法制导的定义将下面的后缀表达式翻译成中缀表达式。注意：不允许出现冗余括号。
E->E1E2+ E->E1E2* E->id
6、某程序设计语言说明部分的语法制导定义如下所示：
D->TL T->int|real L->L1,id|id
给出其语法制导定义及自底向上的翻译方案，并比较两者的不同。 7、设有文法G[S]：
S->E
(1)