西电21秋编译原理与技术1题目
编译原理与技术模拟试题一一、填空题（20分，每空2分）
1.1 编译程序的工作过程可划分为词法分析、语法分析、 、中间代码生成、代码优化、 等阶段，一般在 阶段对表达式中运算对象的类型进行检查。
2 和预测分析法是自上而下的语法分析方法。
1.3常用的存储分配策略有 存储分配和动态存储分配，其中，动态存储分配策略包括 分配和 分配。
1.4 移进、归约是 分析中的典型操作。
1.5 对于数组M，如果每个元素占k个存储单元，且起始地址为a，则以行为主序存放时元素M的地址是_________________，以列为主序存放时元素M的地址是_________________。
二、单选题（10分，每空2分）
2.1词法分析器不能 。
A. 识别出数值常量 B. 过滤源程序中的注释
C. 扫描源程序并识别记号 D. 发现括号不匹配
解释：词法分析的作用为根据模式识别记号，并交给语法分析器；滤掉源程序中的无用成分，如注释、空格、回车等； 处理与具体平台有关的输入；不同的平台对某些特殊符号（如文件结束符等）可能有不同表示，因此需要在词法分析阶段分情况处理；调用符号表管理器或出错处理器，进行相关处理。
2.2 一个句型中的最左 称为该句型的句柄。
A. 短语 B. 直接短语 C. 非终结符号 D. 终结符号
解释：根据定义。
2.3 已知文法G:S→A1 A→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
解释：从表达式的求值过程考虑。逆波兰式中运算符的书写顺序就是处理顺序，中缀表达式要根据运算符的优先级和结合性进行处理。
2.5在表达式x:=y+1中， 作为左值出现(其中，“:=”表示赋值)。
A. x B. y C. 1 D. y+1
解释：形式上讲，出现在赋值号左边的对象称为左值，右边的称为右值；实质上，左值必须具有存储空间，而右值可以仅是一个值，没有存储空间。形象地讲，左值是容器，右值是内容。
三、简答题（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) 给出该文法的产生式集合。
答案：
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的结点可以仅有一个标记为ε的孩子。
分析树与语言和文法的关系：① 每一直接推导（每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；② 分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。
3.4某程序执行到某一时刻时控制栈中的内容如下所示（其中M是主程序，P、Q、R、S均是过程），给出所有在生存期的活动的调用关系(提示：若A调用B，则记为A→B)。
答案：M → P → R → Q → S → S
解释：顺序执行程序的执行在时间上是顺序的和排他的。即在程序执行的任一瞬间，有且仅有一个活动正在活动。控制栈用于保存所有在生存期的活动（一条后进先出的路径）。栈中的每个元素称为一个活动记录（activation record），为活动提供的活动场所。
显然，根据控制栈中的内容，应该是M调用了P，P随后又调用了R，R又调用了Q，Q调用了S，S又调用了S（递归调用）。
四、综合题（30分）
4.1（15分）设有正规式r=1(0|1)*1，试给出：
（a）（5分）识别该正规集的NFA；
（b）（10分）识别该正规集的DFA（要有计算过程）；
答案：
(a)NFA如下图所示
(b)s0 = {A}
ε_闭包(s0) = s0 初态
ε_闭包(smove(s0,1)) = {B} 记为s1
ε_闭包(smove(s1,0)) = {B} = s1
ε_闭包(smove(s1,1)) = {B,C} 记为s2，终态
ε_闭包(smove(s2,0)) = {B} = s1
ε_闭包(smove(s2,1)) = {B,C } = s2
DFA如下图所示
解释：用算法2.2 Thompson 算法从正规式构造出与其对应的NFA；用子集法（算法2.3）将NFA转换为DFA。其中需要用算法2.4计算状态集T的ε-闭包(T)。
4.2（15分）设有上下文无关无法G及其语法制导翻译如下（注：G中终结符id仅由单个英文字母组成，如a, b等）：
E→E1*T {E.place=newtemp; emit(*, E1.place, T.place, E.place;}
| T {E.place=T.place;}
T→T1-F {T.place=newtemp; emit(-, T1.place, F.place, T.place;}
| F {T.place=F.place;}
F→(E) {F.place=E.place;}
| id {F.place=id.name;}
(a)（4分）画出句子a-b*c的分析树；
(b)（3分）写出当a=1、b=2、c=3时的计算结果；（*表示算术乘、-表示算术减）
(c)（8分）将文法G简化为：E→E*T|T，T→T-F|F，F→id，给出其识别活前缀的DFA，该DFA的项目集中有冲突吗？若有，是哪种类型的冲突。
答案：
（a）
(b) -3
（c）拓广文法，增加产生式：S→E，识别活前缀的DFA如下图所示
存在移进－归约冲突
解释：（a）从文法推导（最左推导）出句子a-b*c的过程为：
E => E * T => T * T => T – F * T => F – F * T => a – F * T
=> a – b * T => a – b * F => a – b * c
分析树是对推导过程的直观描述。
分析树被定义为具有下述性质的一棵树：（1）根由开始符号所标记；（2） 每个叶子由一个终结符、非终结符、或ε标记；（3）每个内部结点由一个非终结符标记；（4） 若A是某内部节点的标记，且X1，X2，...，Xn该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。
（b）根据分析树，先计算a – b，得-1，然后再乘以3，结果为-3
（c）用算法3.9 计算文法基于LR(0)项目的识别活前缀的DFA。当DFA的一个项目集中同时存在：
1．A→β1.β2和B→β.：说明下一步既可以移进又可以归约，引起移进/归约冲突。
2．A→α.和B→β.：说明二者均可以指导下一步分析，引起归约/归约冲突。
解决冲突的方法是简单向前看一个终结符a：
1．对于移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可以解决。
2．对于归约/归约冲突：若FOLLOW(A) ∩FOLLOW(B)=Φ，冲突可以解决。
若冲突可以解决，则称其为SLR(1)文法和SLR(1)分析表。否则需要寻求能力更强文法，即寻求新的项目集（LR(1)项目集）。
页:
[1]