一、单选题（每小题 2 分，共 10 分）
1、编译过程中，生成中间代码所依据的是 C 。
A ．语法规则 B ．词法规则 C ．语义规则 D ．等价变换规则
2、在自下而上语法分析中， LL(1)中的第二个 L 表示 B 。
A ．最右归约 B ．最左推导 C ．最左归约 D ．最右推导
3 、在自下而上语法分析中，句柄是指右句型中的 D 。
A ．非终结符 B ．短语 C ．直接短语 D ．最左直接短语
4、有限状态自动机（NFA、DFA）可以识别的语言为 D 。
A ．上下文有关语言 B ．上下文无关语言
C ．短语文法定义的语言 D ．正规文法定义的语言
5 、在布尔表达式短路计算的翻译方案中，当按照产生式E→E1 and E2 进行归约时， 可以确定 B 。
A ．E1 的真出口 B ．E1 的假出口 C ．E2 的真出口 D ．E2 的假出口
二、填空（每空 2 分，共 20 分）
1 、动态存储分配包括 分配和 分配两种。
2 、正规式 (a|b)*abb 表示的正规集为 。
3 、 上 下 文 无 关 文 法 G 的 四 元 组（N,T,P,S） 中 ， S 表 示 ，P 表 示 。
4 、在文法 E→E + T | T T→F * T | F F→id 中，运算 + 的优先级比 * ，
运算 + 是 结合的，运算 * 是 结合的。
5 、函数调用执行时， 引用调用是将实参的 传给形参，值调用是将实参 的 传给形参。
三、简答题（每小题 10 分，共 30 分）
1 、请列举三种常用的中间代码，并说明编译过程中采用中间代码有什么好处。
2、请计算下面文法 G[E]中各非终结符的 FIRST 和 FOLLOW 集合， 同时说明该文法为 什么不是 LL(1)文法。
E→E * T | T T→T - F | F F→ (E) | id
3、请给出下述语句的三地址码序列并指出此语句的出口。
while (x<100) do
begin x:=x+1;
if a>0 then a:=a-1;
end;
四、计算题（每小题 20 分，共 40 分）
1、某 NFA 的状态转换图如下表所示（0 是初态，3 是终态）
a
（1）（6 分）写出该 NFA 可识别的 3 个长度各不相同的串；
（2）（9分）写出将该 NFA 确定化为 DFA D 的过程，并给出 D 的状态转换图； （3）（5 分）计算 D 的最小 DFA D ’，并给出 D ’的状态转换图。
2、设有上下文无关无法G[V]和语法制导翻译如下：
V → id
| id(E)
E → E + V
| V
{var_no:=var_no+1;}
{arr_no:=arr_no+1;}
{exp_no:=exp_no+1;}
{exp_no:=exp_no+1;}
（1）（6 分）给出句子 id(id+id(id))的分析树；
（2）（6 分）若语义变量 var_no、arr_no 和 exp_no 的初值均为 1，对句子 id(id+id(id)) 分析完成后它们各自的值；
（3）（8 分）给出识别该文法活前缀的 DFA。