北方工业大学
序号 《编译原理》课程期末复习题（答案）
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??