内容发布更新时间 : 2024/6/17 1:46:21星期一 下面是文章的全部内容请认真阅读。

北方工业大学

序号 《编译原理》课程期末复习题（答案）

2012年春季学期

开课学院：信息工程学院

考试方式：闭卷

A卷

考试时间：120 分钟

班级 姓名 学号 题 号 得 分 阅卷人 装

一 二 三 四 五 六 七 八 九 十 总 分 一.简要回答下列各问题（共40分，每个小题5分）

(1) 阐述高级语言的编译过程，编译过程与解释过程的区别。

答：（编译过程）

第一阶段：词法分析； 第二阶段：语法分析；

第三阶段：语义分析与中间代码产生； 第四阶段：优化；

第五阶段：目标代码生成。 （区别）

解释过程是解释一条命令后立即执行，一般不产生中间代码，也不进行优化；

而编译过程是要进行词法、语法、语义分析后，生成中间代码并进行优化，最终产生目标代码后再执行。

订

(2) 如何用语言L1的编译器实现语言L2的编译器？

? A上实现L1在A上的L2编译源程序；

? 在A上编译这个源编译程序，得到在A可以运行的L2的编译程序。

线

? A上实现L2在B上的编译源程序；

? 在A上编译这个源编译程序，得到在A可以运行的B上L2的编译程序； ? 用得到的编译程序再一次编译L2的B 上编译源程序即可；

北方工业大学试卷 第1页 共16页

(3)以简单算术表达式的语法规为例，说明一个计算机高级语言的语法规则。

答：一个高级语言的语法规则由上下文无关文法描述。例如，一个简单的算术表达式文法：

E→T| E+T

T→F| T*F （1-1） F→i | (E) 终结符号：i 非终结符号：E

开始符号：算术表达式 产生式：(1-1)

(4) 画出词法分析器的逻辑结构图，并解释输入缓冲区和扫描缓冲区功能。

答：

输入缓冲区：接收源程序，语言元素登记到 符号表；等待预处理。

扫描缓冲区：接收预处理后的程序代码，等 待扫描器的分析。

输入 列表 输入缓冲区 预处理 扫描缓冲区 扫描器 单词符号 图1.3 词法分析器 (5) 分别画出C语言中“标示符”和“整数”语法规则的状态转换图，举例说明标示符的分析过程。

答：

0

数字或字

母 字母 其它

* 2 0 字

数数字

其它

1 图(a)标示符识别

1 2 (b)整数识别

举例：变量A12的分析过程为：从0状态开始，接收到A后进入1状态；当接收到1和2后状态机仍然在1状态；当接收到空格符合（＃）后，进入2状态后结束。

北方工业大学试卷 第2页 共16页

(6) 已知一个文法的语言L(G)={ambn|m,n?1}。试求：

? 该语言对应的文法；

? 给出产生该语言的状态转换图。

答：

文法G：VN={S,A},VT={a,b},?={S→AB, A→aA|a, B→Bb|b}, S=S。

am-1

bn-1

a b * 0 1 2

(7) 试分别给出上、下文无关文法和上、下文有关文法的例子，并加以说明。

答：

例如，文法G：VN={S},VT={a,b},?={S→aSb|ab}, S=S。G是上下文无关语言，因为S →aSb|ab与a、b无关，则是上下文无关文法。

例如，文法G：VN={S,P},VT={a,b},?={S→aPb, aPb→a?b }, S=S。G是上下文有关语言，因为S →aPb, aPb→a?b与a、b有关，则是上下文有关文法。

(8)在自上而下的语法分析中，为什么要消除左递归？请给出一个含有左递归的文法。

答：

? 由于在自上而下的语法分析中，采用最左推导的策略分析输入串是否为合法的句子，所以

左递归文法会产生无限的循环表达式，无法实现输入串的分析；

? 由于回溯需要大量的系统资源，保持调用的现场，所以增加语法分析的代价。 举例：E?E+T|E-T|T

T?T*F|F F?(E)|i

(9)设变量类型说明文法如下：

L?id L

L?,id L| :T T?float|int

试构造一个翻译模式，把每个标示符的类型存入符号表。

答：

L?M id L

addtype(id,type. L.in) L(1).in:=L.in

Addtype(id.type, L.in) T.type:=int, T.type:=float; L.in:=T.type

北方工业大学试卷 第3页 共16页

L?，id L| :T

T?integer|real M??