1、大作业试题公布时间：2024 年 5 月 9 日；
2、考试必须独立完成，如发现抄袭、雷同均按零分计；
3、答案须用《西安电子科技大学网络与继续教育学院 2024 春期末考试答题纸》（个 人专属答题纸）手写完成，要求字迹工整、卷面干净、整齐；
4、在线上传时间：2024 年 5 月 9 日至 2024 年 5 月 20 日在线上传大作业答卷；
5、拍照要求完整、清晰，一张图片对应一张个人专属答题纸（A4 纸），正确上传。
一、单项选择题（每小题 2 分， 共 20 分）
1、编译程序是对 。
A ．汇编语言的翻译 B ．高级语言的解释执行
C ．机器语言的执行 D ．高级语言的翻译
2 、不含子串 100 的所有 0 、1 符号串的正规式是 。
A ．0* (1|10)* B ．1* |0* 1 C ．0(01|10)* 1 D ．1(10|01)*0
3、词法分析器不能 。
A ．识别出数值常量 B ．过滤源程序中的注释
C ．扫描源程序并识别记号 D ．发现括号不匹配
4 、源程序是句子的集合， 可以较好地反映句子的结构。
A ．数组 B ．树 C ．完全图 D ．堆栈
5、识别上下文无关语言的自动机是 。
A ．下推自动机 B ．NFA C ．DFA D ．图灵机
6 、与逆波兰式 ab+c*对应的中缀表达式是 。
A ．a+b*c B ．(a+b)*c C ．a*b+c D ．a*(b+c)
7 、一个文法产生的语言是指 。
A ．从开始符号出发推导的所有符号串的集合 B ．所有终结符和非终结符形成的集合
C ．所有短语构成的集合 D ．该文法产生的句子的集合
8 、一个句型中的最左 称为该句型的句柄。
A ．短语 B ．直接短语 C ．非终结符号 D ．终结符号
9、生成中间代码所依据的是 。
A ．语法规则 B ．词法规则 C ．语义规则 D ．等价变换规则 10、用来描述控制进入和离开活动方式的树结构被称为 。
A ．语法树 B ．分析树 C ．活动树 D ．嵌套关系树
二、填空题（每空 2 分， 共 10 分）
1、在以阶段划分的编译中， 阶段的主要工作是得到语言句子结构并以树 的形式表示； 阶段的主要工作是对中间代码进行优化等价变换，以提高代 码的执行效率。
2、预测分析器改变格局的动作有接受、报错、 和 。 3、动态存储分配策略包括栈分配和 分配。
三、简答题（每小题 10 分， 共 40 分）
1、简述从正规式构造词法分析器的一般方法和过程。
2、请列举三种常用的中间代码？采用中间代码有什么好处？
3、简述拉链与回填技术的基本思想。
4 、给出语句 while (x<0) do if (x<y) then x:= y+z 的中间代码序列。
四、综合题（每小题 15 分， 共 30 分）
1 、给定正规式 R = (0|1)*1(0|1)
（1）（5 分） 用 Thompson 算法构造识别 L(R)的 NFA N；
（2）（7 分）用“子集法”把 N 确定化（写出完整过程），得到识别 L(R)的 DFA D； （3）（3 分） 如果 D 不是最简 DFA ，请找出最简 DFA。
2、设有上下文无关无法 G 及其语法制导翻译如下（注：G 中终结符 id 仅由单个英文字 母组成， 如 a, b 等）：
E→E1*T | T
T→T1-F | F
{E.place=newtemp; emit(*, E1.place, T.place, E.place;}
{E.place=T.place;}
{T.place=newtemp; emit(-, T1.place, F.place, T.place;}
{T.place=F.place;}
F→(E) {F.place=E.place;}
| id {F.place=id.name;}
（1）（4 分） 画出句子 a-b*c 的分析树；
（2）（3 分） 写出当 a=1 、b=2 、c=3 时的计算结果；（ *表示算术乘、 -表示算术减）
（3）（8 分）将文法 G 简化为：E→E*T|T ，T→T-F|F ，F→id ，给出其识别活前缀的 DFA ，该 DFA 的项目集中有冲突吗？若有，是哪种类型的冲突。