《编译原理与技术》期末考试试题 编译原理期末考试试题及答案

《编译原理与技术》期末考试试题

一、单选题（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分）列举该三个该正规式所表示正规集的元素。

（b）（12分）构造识别该正规集的NFA和最小化的DFA（要有计算过程）。

3. （13分）对于文法：

S→aABe

A→b | Abc

B→d

拓广文法并构造识别该文法活前缀的DFA，是否有冲突？若有，请说明。