一、单选题（10分，每空2分）
1. 对于正规式(a|b)*abb，属于其所表示正规集的是 。 A. aaabbb B. abab C. bbbaaa D. ababb 2. 识别上下文无关语言的自动机是 。
A. 下推自动机 B. NFA C. DFA D. 图灵机 3. 一个句型中的最左 称为该句型的句柄。
A. 短语 B. 直接短语 C. 非终结符号 D. 终结符号 4. 给定文法A→bA|ab， 是该文法的句子。
A. babb B.abab C. baab D. bbab 5. 用来描述控制进入和离开活动方式的树结构被称为 。
A. 语法树 B. 分析树 C. 活动树 D. 嵌套关系树 二、填空（20分，每空2分）
1. 编译程序翻译源程序的过程可划分为词法分析、______________、语义分析、中间代码生成、代码优化、________________等阶段，还涉及符号表管理和 。 2. 把汇编语言翻译成机器语言的过程称为 。
3. 编译器分析源程序时遇到的错误可分为语法错误和语义错误两类。表达式中括号不匹配是 错误，零作为除数是 错误。。 4. LL（1）分析中，第一个L表示自左至右扫描输入序列，第二个L表示 ， 1表示________________。
5. 语法分析方法分为自上而下和自下而上两类，递归下降分析属于 ，移进-归约方法属于 。 三、简答题（30分，每小题10分）
1. 简述从正规式构造词法分析器的一般方法和过程。
2. 对于文法G: S→0S1 | 1S0 | 10，请给出句子11010100的最左推导，并画出分析树。 3. 请分别写出采用传值调用和引用调用方式下，下面代码的输出结果。
program main(input,output)
procedure f(a,b) begin
a := a + 1; b := a * 2 + 1;
end;
begin
x := 10; y := 20;
f(y, x);
print(x,y); end.
四、计算题（40分） 1.（12分）设有文法G：
S→tAdB A→aC B→b C→cC |ε
计算该文法所有非终结符的FIRST、FOLLOW集合；
*
2.（15分）设有正规式r=b(ba|a)，
（a）（3分）列举该三个该正规式所表示正规集的元素。
第 1 页 （共 2 页）
（b）（12分）构造识别该正规集的NFA和最小化的DFA（要有计算过程）。 3. （13分）对于文法：
S→aABe A→b | Abc B→d
拓广文法并构造识别该文法活前缀的DFA，是否有冲突？若有，请说明。
第 2 页 （共 2 页）
因篇幅问题不能全部显示，请点此查看更多更全内容