《编译原理与技术》期末考试试题
一、单选题（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(b a|a)*，
（a）（3分）列举该三个该正规式所表示正规集的元素。
（b）（12分）构造识别该正规集的NFA和最小化的DFA（要有计算过程）。
3. （13分）对于文法：
S→aABe
A→b | Abc
B→d
拓广文法并构造识别该文法活前缀的DFA，是否有冲突？若有，请说明。