若P→…aR…，则?b∈FIRSTVT(R)，a
(3)?>?关系
求出每个非终结符P的LASTVT(P)
若P→…Rb…，则?a∈LASTVT(B)，a>b
对于文法G[S]，构造它的算符优先关系表如下：
a + ( ) a > > + < > < > ( < < < = ) > >
8. 设文法G（S）： S→T | S∨T T→U |T∧U U→i |-U
(1) 计算FIRSTVT 和LASTVT； (2) 构造优先关系表。
解答
(1)对于文法G[S]，构造它的每个非终结符的FIRSTVT和LASTVT集合。 FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -}
FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - }
LASTVT(T)={∧, i, -}
LASTVT(U)={i, -}
(2) 构造优先关系表。
i ∨ ∧ - S .> .> ∨ <. .> <. <. ∧ <. .> .> <. - <. .> .> <.
11
9. 下面映射if语句的文法G[S]是算符优先文法吗？如果是，则构造算符优先关系表。如果不是，则说明理由。 G[S]
S?iBtS S?iBtSeS S?a B?b 解答
对于文法G[S]，它是一个二义性文法。因为存在句子ibtibtaea有两个不同的最左推导 S? iBtS? ibtS? ibtiBtSeS? ibtibtSeS? ibtibtaeS? ibtibtaea
S? iBtSeS? ibtSeS? ibt iBtSeS? ibtibtSeS? ibtibtaeS? ibtibtaea
由于算符优先文法一定不是二义性文法，所以文法G[S]不是算符优先文法。
10. 设有如下的基本块 T1:=A+B T2:=5 M:=T2*4 T3:=C-D T4:=M+T3 L:=T1*T3 T4:=A+B N:=T4
(1) 画出该基本块的DAG图；
(2) 假设只有L，M 和N 在基本块之后还要引用，写出优化后的四元式序列。 解答
在构造基本块的DAG图时，必须注意两个方面：一是对于已知的常量要进行计算；二是对同一变量进行多次定值时，最后一次定值是基本块中该变量的最终变量。由于基本块有语句T2：=5，可知T2是已知量。所以，语句M：=T2 * 4 可计算出M 的值来，即，M也转为常量（M = 20）。一方面，变量T4进行了两次操作，基本块执行完时，最后一次给T4的定才是T4的最终结果。活跃信息是针对变量而言的。如果一个变量在基本块之后不再被引用，则称该变量是非活跃的（或称为非活跃变量），反之称之为活跃的（或称为活跃变量）。变量的活跃信息对代码优化和代码生成都有非常重要的指导意义。
当DAG图构造出来后，根据题目所给的条件从DAG图中计算出活跃变量的结果即可。本是中只要计算出变量L、M和N的结果就行了。
基本块对应的DAG图如下：
12
n3 L * n3 n3 T1,T4,N T4 n3 T3 + + _ n1 n2 n4 T2 n5 M n6 n7 A B 5 20 C D
按照构造其结点的顺序，重新写成四元式序列G?
T1=A+B T4=T1 N=T4 T2=5 M=20 T3=C-D L=T1*T3
由于只有L，M 和N 在基本块之后还要引用，T1、T2、T3和T4都不会引用，于是重新写出优化后的四元式序列为：
N:=A+B M:=20 T3:=C-D L:=N*T3
11. 把语句
while a>0 ∧b>0 do if x>y then b:=b-1 else a:=a-1; 翻译为四元式序列。 解答
13
对于这类题目，关键是准确掌握语句的语动作。
while-do 语句的语义动作while M1EE.truelistE.falselistdoS1.nextlistM2S1(j, _, _, M.quad)S.nextlistif-then-else 语句的语义动作if E.falselistE.truelistEthenS1.nextlistM1S1N.nextlistNelseM2S2S2.nextlistS.nextlist作为条件控制的布尔式的翻译：
把 A or B 解释成 if A then true else B 把 A and B 解释成 if A then B else false 把 not A 解释成 if A then false else true 布尔表达式赋予两种“出口” ：一是“真”出口；一是“假”出。 假设四元式序列从100开始编号。 14
表达式a>0 翻译为： 100 (j>，a，0，_) 101 (j，_，_，_)
继续翻译表达式a>0 ∧b>0，由于是与运算，100号语句应转跳到102号语句，102号语句为“真”出口，101号语句和103号语句为“假”出，四元式序列为：
100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，_) 103 (j，_，_，_)
继续翻译语句while a>0 ∧b>0 do if x>y …
while语句中的逻辑表达式的“真”出口应转跳到其循环体的第一个四元式标号，即104号语句。
100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，104) 103 (j，_，_，_) 104 (j>，x，y_) 105 (j，_，_，_)
if语句中的逻辑表达式的“真”出口为104号语句，应转跳到then 中的第一个四元式标号，“假”出口为105号语句，应转跳到else 中的第一个四元式标号。then 中语句翻译完，应转跳出去。
100 (j>，a，0，102) 101 (j，_，_，_) 102 (j>，b，0，104) 103 (j，_，_，_) 104 (j>，x，y_) 105 (j，_，_，_) 106 (-，b，1，T1) 107 (:=，T1，_，b) 108 (j，_，_，_) 109(-，a，1，T2) 110 (:=，T2，_，a)
while语句中循环体翻译完，应转跳到while语句的第一个四元式标号，即100号语句。while语句中的逻辑表达式的“假”出口应转跳到while语句后的第一个四元式标号。
100 (j>，a，0，102) 101 (j，_，_，112) 102 (j>，b，0，104) 103 (j，_，_，112) 104 (j>，x，y_) 105 (j，_，_，_) 106 (-，b，1，T1) 107 (:=，T1，_，b) 108 (j，_，_，100)
15
109(-，a，1，T2) 110 (:=，T2，_，a) 111 (j，_，_，100)
12. 已知文法G[S]及相应翻译方案 S→aAb {print “1”}
S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？
解答
对于这类题目，首先画出句子acab对应的语法树。每当用一个产生式归约时，则执行相应的语义动作。句子acab对应的语法树为：
S a A b A S c a
第一个归约的产生式是A→c，它相应的语义动作为print “4”。所以，产生输出4。 第二个归约的产生式是S→a，它相应的语义动作为print “2”， 产生输出2。 第三个归约的产生式是A→AS，它相应的语义动作为print “3”，产生输出3。 最后归约的产生式是S→aAb，它相应的语义动作为print “1”， 产生输出1。 因此，输入acab, 输出是4231。
16