loading2006～2007学年第1学期期末考试试卷
《编译原理》答案
一、单项选择题（共10分，每小题1分。） A卷答案： 题号 答案 分值 B卷答案 题号 答案 分值 1 D 2 2 D 1 3 A 1 4 B 1 A 1 5 C 1 C 1 F 1 6 A 1 1 B 1 2 A 1 3 D 1 4 D 2 F 1 5 A 1 A 1 6 C 1 C 1 二、简答题
1. 简要叙述语法分析的基本功能是什么？对于同一个文法，LALR(1)和SLR(1)的分析表状
态个数相同，为什么前者的分析能力要比后者强？（简述要点即可）（10分）
答：语法分析的基本功能是：
a) 语法分析处于词法分析和语义分析之间，它的输入是词法分析的输出，它的输出是
语义分析的输入。（1分）
b) 词法分析对输入的字符串进行分析，判断是否一个合法的输入。其中合法是指输入
的字符串是否符合程序设计语言的语法规定（或者文法的规定）。（3分） c) 对于不符合语法的字符串要设计错误处理机制。其分析方法包括自顶向下和自底向
上分析两种。（1分）
LALR(1)比SLR(1)分析能力强的原因：
在构造分析表时，SLR(1)中的规约项填写的是全体FOLLOW(A)集合中的符号，这样就增加了移动-规约冲突的可能性。（2分）
而对于LALR(1)，虽然分析表状态和SLR(1)同样多，但是它采用了向前搜索符技术，使得规约项填写的只是FOLLOW(A)集合的子集，而且大部分时间下是真子集，这就使得产生移动-规约冲突的可能性减少，因此更加精确，所以分析能力更强。（3分）
2. 在对运行时的内存空间进行存储组织时，过程一次执行所需的信息用一块连续的存储区
来管理，这就是活动记录。在活动记录中，有两个域分别保存了“可选的访问链”和“可选的控制链”。请简要描述这两个域的区别，以及它们保存的数据在存储管理中都起到了什么作用。（10分）
答：区别：
“可选的访问链”总是指向定义该过程的过程的活动记录。因为它总是指向定义者，所以这个指针主要用来对非局部数据的访问。（2.5分）
“可选的控制链”总是指向调用该过程的过程的活动记录。因为指针的指向顺序总是由上一个活动记录指向下一个活动记录，所以这个指针主要用于过程调用时参数的传递和数据返回。（2.5分）
数据的作用
“可选的访问链”中的数据用于计算非局部数据的位置。即利用其中存储的数据计算出访问链的指针域，再加上非局部数据在其所在活动记录中的偏移地址，就可以得到要访问的
非局部数据的绝对地址。（2.5分）
“可选的控制链”中的保存的是调用者活动记录的地址。通过记录调用者活动记录的位置，可以实现变量的作用域以及程序控制的返回。（2.5分）
3. C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受
的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。（10分）
答：例子主要是由指针构成的数据结构（栈、队列等）的悬空引用、计算表达式时数据类型的溢出（比如两个整数相乘结果大于整数能表示的范围）。例子大部分都是由于C语言支持指针而造成的。
答出上述任一情况即可得分。
三、推导计算题 1． 设文法G(S):
S → S+aF | aF | +aF F → *aF | *a
(1) 消除左递归和回溯；
(2) 构造相应的FIRST和FOLLOW集合； (3) 构造预测分析表 （10分） 答：
（1）消除左递归（2分）和回溯（2分）： S→aFS' | +aFS' S'→+aFS' | ε F→*aF' F'→F | ε
（2）构造FIRST集合（1分）构造FOLLOW集合（2分） FIRST(S)={a,+} FOLLOW(S)={$} FIRST(S')={+,ε} FOLLOW(S')={$} FIRST(F)={*} FOLLOW(F)={+,$}
FIRST(F')={*,ε) FOLLOW(F')={+,$} （3）构造预测分析表（3分）
- S' F F' a - - - + S'→+aFS' - F'→ε * - - F→*aF' F'→F $ - S'→ε - F'→ε S S→aFS' S→+aFS'
2. 浮点数的定义如下：它只含有一个小数点，小数点前后至少有一位数字。指数用E表示，后面跟一个符号（+或-）或者无此符号，再后面跟一个或一个以上的数字串。（例如，1.175494351 E – 38和3.402823466 E 38都是浮点数）(10分)
(1) 构造出产生该浮点数的正规文法 (2) 用正规式表示上述浮点数
(3) 构造接受该浮点数的有限自动机（NFA和DFA都可以）
3. 令综合属性val给出下列文法中S产生的二进制数的值。例如，输入101.101时，S.val=5.625。（计算过程如下1*22+0*21+1*20+1*2-1+0*2-2+1*2-3）
S→ L1 . L2 | L L→ L1B | B B→ 0 | 1
请给出该文法的语法制导定义。（10分）