编译原理与技术模拟试题一
一、填空题（20分，每空2分）
1.1编译程序的工作过程可划分为词法分析、语法分析、、中间代码生
成、代码优化、等阶段，一般在阶段对表达式中运算对象的类型进行检查。
答案：语义分析、目标代码生成、语义分析
解释：要求掌握编译器的工作原理和特点。编译和解释方式是翻译高级程序设计语言的两种基本方式。解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再加以执行；而编译程序（编译器）则首先将源程序翻译成目标语言程序，然后在计算机上运行目标程序。编译过程包含词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理。表达式的类型信息属于语义信息，所以在语义分析阶段进行类型检查。
1.2 和预测分析法是自上而下的语法分析方法。
答案：递归下降法
解释：语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。根据语法树（或分析树）的建立方式，语法分析可分为自上而下分析和自下而上分析两类，递归下降分析和预测分析属于自上而下的语法分析方法。
1.3常用的存储分配策略有存储分配和动态存储分配，其中，动态存储分配
策略包括分配和分配。
答案：静态、栈、堆
解释：编译器怎样对存储空间进行组织和采用什么样的存储分配策略，很大程度上取决于程序设计语言中所采用的机制。编译器具体实现时，根据语言机制的特性，采用静态分配策略、栈分配策略和堆分配策略三种方式的其中若干种。静态分配策略是指编译时安排所有数据对象的存储，即绑定是静态确定的；栈分配策略是指按栈的方式管理运行时的存储；堆分配策略是指在运行时根据要求从堆数据区动态地分配和释放存储。
1.4移进、归约是分析中的典型操作。
答案：自下而上或LR解
释：自下而上分析的一般思路是从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误。移进-归约是实现自下而上分析的一般方法。
1.5对于数组M[1..6, 1..8]，如果每个元素占k个存储单元，且起始地址为a，则以行为主序存放时元素M[4,4]的地址是_________________，以列为主序存放时元素M[4,4]的地址是_________________。
答案：1.5 a+27*k，a+21k
解释：计算排列在M[4,4]之前的元素个数即可。
二、单选题（10分，每空2分）
2.1词法分析器不能。
A. 识别出数值常量
B. 过滤源程序中的注释
C. 扫描源程序并识别记号
D. 发现括号不匹配
答案：D
解释：词法分析的作用为根据模式识别记号，并交给语法分析器；滤掉源程序中的无用成分，如注释、空格、回车等；处理与具体平台有关的输入；不同的平台对某些特殊符号（如文件结束符等）可能有不同表示，因此需要在词法分析阶段分情况处理；调用符号表管理器或出错处理器，进行相关处理。
2.2一个句型中的最左称为该句型的句柄。
A. 短语
B. 直接短语
C. 非终结符号
D. 终结符号
答案：B
解释：根据定义。
2.3已知文法G[S]:S→A1A→A1|S0|0。与G等价的正规式是。
A. 0(0|1)*
B. 1*|0*1
C. 0(1|10)*1
D. 1(10|01)*0
答案：C
解释：用推导和构造思路处理。
2.4与逆波兰式ab+c*d+对应的中缀表达式是。
A. a+b+c*d
B. (a+b)* c+d
C. (a+b)* (c+d)
D. a+b*c+d
答案：B
解释：从表达式的求值过程考虑。逆波兰式中运算符的书写顺序就是处理顺序，中缀表达式要根据运算符的优先级和结合性进行处理。
2.5在表达式x:=y+1中，作为左值出现(其中，“:=”表示赋值)。
A. x
B. y
C. 1
D. y+1
答案：A
解释：形式上讲，出现在赋值号左边的对象称为左值，右边的称为右值；实质上，左值必须具有存储空间，而右值可以仅是一个值，没有存储空间。形象地讲，左值是容器，右值是内容。
三、简答题（40分，每小题10分）
3.1 请分别写出传值调用、引用调用方式下，下面代码的输出结果。
program main(input,output)
procedure f(a,b)
begin
a :=
b - a;
b := a * b + 1;
end;
begin
x := 5; y := 10;
f(y,x);
print(x,y);
end.
答案：传值调用方式：5 10
引用调用方式：-24 -5
解释：传值方式下，实参与形参各自有独立的存储单元，调用时将实参的值传递给形参，对形参进行的修改与实参无关。引用调用方式下，是将实参的地址传递给形参，对形参所作的修改最后会返回给实参。
3.2 请计算下面文法G(E)中各非终结符的FIRST和FOLLOW集合。请说明该文法为什么不是LL(1)文法。
G(E)：E→E* T | T T→T - F | F F→(E) | id
答案：
FIRST(F) = FIRST(T) = FIRST(E) = { (,id }
FOLLOW(E) = {#,*,)} FOLLOW(T) = {-, *, #,) } FOLLOW(F) = {-, *, #,) } 解释：通俗地讲，α的FIRST集合就是从α开始可以导出的序列中的开头终结符。而A 的FOLLOW集合，就是从开始符号可以导出的所有含A序列中紧跟A之后的终结符。根据计算FIRST集合和FOLLOW集合的算法进行计算。
判定G是否LL(1)文法有两个：①构造分析表，判断分析表中是否包含多重定义的条目；②根据推论3.2：文法G是LL(1)的，当且仅当G的任何两个产生式A→α|β，满足下面条件:1. 对任何终结符a，α和β不能同时推导出以a开始的串；2. α和β最多有一个可以推导出ε；3. 若β=*>ε，则α不能推导出以在FOLLOW（A）中的终结符开始的任何串。
3.3下图所示的分析树用到了某个上下文无关文法的所有产生式。
(a) 给出该文法的所有非终结符号集合N和终结符号集合T。
(b) 给出该文法的产生式集合。
S
a A c B
A a
B b S c A
c b B
d c
ε
答案：
N = {S, A, B}
T = {a, b, c, d}
S → aAcB | Bd A → AaB | c B → bScA | b | ε
解释：对CFG G的句型，分析树被定义为具有下述性质的一棵树。
（1）根由开始符号所标记；
（2）每个叶子由一个终结符、非终结符、或ε标记；
（3）每个内部结点由一个非终结符标记；
（4）若A是某内部节点的标记，且X1，X2，...，Xn该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记
