西安电子科技大学网络与继续教育学院
2023 学年上学期
《编译原理与技术》期末考试试题
(综合大作业)
一、单选题(每小题 2 分， 共 10 分)
1、编译过程中，生成中间代码所依据的是__________。
A．语法规则 B．词法规则 C．语义规则 D．等价变换规则
2 、在自下而上语法分析中， LL(1)中的第二个 L 表示________。
A．最右归约 B．最左推导 C．最左归约 D．最右推导
3 、在自下而上语法分析中，句柄是指右句型中的________。
A．非终结符 B．短语 C．直接短语 D．最左直接短语
4、有限状态自动机(NFA、DFA)可以识别的语言为________。
A．上下文有关语言 B．上下文无关语言
C．短语文法定义的语言 D．正规文法定义的语言
5 、在布尔表达式短路计算的翻译方案中，当按照产生式E→E1 and E2 进行归约时， 可以确定 。
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 {var_no:=var_no+1;}
| id(E) {arr_no:=arr_no+1;}
E → E + V {exp_no:=exp_no+1;}
| V {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。