编译原理与技术1

1、编译原理与技术模拟试题一一、填空题（20分，每空2分）1.1编译程序的工作过程可划分为词法分析、语法分析、中间代码生成、代码优化、等阶段，一般在阶段对表达式中运算对象的类型进行检查。答案：语义分析、目标代码生成、语义分析解释：要求掌握编译器的工作原理和特点。编译和解释方式是翻译高级程序设计语言的 两种基本方式。解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻 译成某种中间表示形式后再加以执行；而编译程序（编译器）则首先将源程序翻译成目 标语言程序，然后在计算机上运行目标程序。编译过程包含词法分析、语法分析、语义 分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理

2、。表达式 的类型信息属于语义信息，所以在语义分析阶段进行类型检查。和预测分析法是自上而下的语法分析方法。答案：递归下降法解释：语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即表 达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。根据语法树（或 分析树）的建立方式，语法分析可分为自上而下分析和自下而上分析两类，递归下降分 析和预测分析属于自上而下的语法分析方法。1.3常用的存储分配策略有 存储分配和动态存储分配，其中，动态存储分配策略包括 分配和 分配。答案：静态、栈、堆解释：编译器怎样对存储空间进行组织和采用什么样的存储分配策略，很大程度上取决 于程序设计语言

3、中所采用的机制。编译器具体实现时，根据语言机制的特性，采用静态 分配策略、栈分配策略和堆分配策略三种方式的其中若干种。静态分配策略是指编译 时安排所有数据对象的存储，即绑定是静态确定的；栈分配策略是指按栈的方式管理运 行时的存储；堆分配策略是指在运行时根据要求从堆数据区动态地分配和释放存储。1.4移进、归约是分析中的典型操作。答案：自下而上或LR解释：自下而上分析的一般思路是从句子3开始，从左到右扫描3,反复用产生式的左部 替换产生式的右部、谋求对3的匹配，最终得到文法的开始符号，或者发现一个错误。 移进-归约是实现自下而上分析的一般方法。1.5对于数组M1.6, 1.8，如果每个元素占k个存

4、储单元，且起始地址为a,则以行为 主序存放时元素M4,4的地址是，以列为主序存放时元素M4,4的地址是。答案：1.5 a+27*k，a+21k解释：计算排列在M4,4之前的元素个数即可。二、单选题(10分，每空2分)2.1词法分析器不能。A.识别出数值常量B.过滤源程序中的注释C.扫描源程序并识别记号D.发现括号不匹配答案：D解释：词法分析的作用为根据模式识别记号，并交给语法分析器；滤掉源程序中的无用 成分，如注释、空格、回车等；处理与具体平台有关的输入；不同的平台对某些特殊 符号(如文件结束符等)可能有不同表示，因此需要在词法分析阶段分情况处理；调用 符号表管理器或出错处理器，进行相关处理。

5、一个句型中的最左称为该句型的句柄。A.短语B.直接短语C,非终结符号 D.终结符号答案：B解释：根据定义。2.3已知文法GS:SA1 AA1|S0|0。与G等价的正规式是。A. 0(011)*B, 1*10*1C. 0(1110)*1D. 1(10101)*0答案：C解释：用推导和构造思路处理。2.4与逆波兰式ab+c*d+对应的中缀表达式是。A. a+b+c*dB. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d答案：B解释：从表达式的求值过程考虑。逆波兰式中运算符的书写顺序就是处理顺序，中缀表 达式要根据运算符的优先级和结合性进行处理。2.5在表达式x:=y+1

6、中，作为左值出现(其中，“：二”表示赋值)。A. xB. yC. 1D. y+1答案：A解释：形式上讲，出现在赋值号左边的对象称为左值，右边的称为右值；实质上，左值 必须具有存储空间，而右值可以仅是一个值，没有存储空间。形象地讲，左值是容器， 右值是内容。三、简答题(40分，每小题10分)3.1请分别写出传值调用、引用调用方式下，下面代码的输出结果。program main(input,output)procedure f(a,b)begina := b - a;b := a * b + 1;end;beginx := 5; y := 10;f(y,x);print(x,y);end.答案：传

7、值调用方式：5 10引用调用方式：-24 -5 解释：传值方式下，实参与形参各自有独立的存储单元，调用时将实参的值传递给形参， 对形参进行的修改与实参无关。引用调用方式下，是将实参的地址传递给形参，对形参 所作的修改最后会返回给实参。3.2请计算下面文法G(E)中各非终结符的FIRST和FOLLOW集合。请说明该文法为什 么不是LL(1)文法。G(E)： EE* T | T TT - F | F F (E) | id 答案：FIRST(F) = FIRST(T) = FIRST(E) = (,id FOLLOW(E) = #,*,) FOLLOW(T) = -, *, #,) FOLLOW(F

8、) = -, *, #,) 解释：通俗地讲，a的FIRST集合就是从a开始可以导出的序列中的开头终结符。而A 的FOLLOW集合，就是从开始符号可以导出的所有含A序列中紧跟A之后的终结符。 根据计算FIRST集合和FOLLOW集合的算法进行计算。判定G是否LL(1 )文法有两个：构造分析表，判断分析表中是否包含多重定义的条 目；根据推论3.2：文法G是LL(1)的，当且仅当G的任何两个产生式Aa|B， 满足下面条件:1.对任何终结符a，a和B不能同时推导出以a开始的串；2. a和B最 多有一个可以推导出e； 3.若B=*e，则a不能推导出以在FOLLOW (A)中的终结 符开始的任何串。3.3

9、下图所示的分析树用到了某个上下文无关文法的所有产生式。给出该文法的所有非终结符号集合N和终结符号集合T。给出该文法的产生式集合。答案：N = S, A, BT = a, b, c, dS 一 aAcB | BdA 一 AaB | cB 一 bScA | b | e解释：对CFG G的句型，分析树被定义为具有下述性质的一棵树。根由开始符号所标记；每个叶子由一个终结符、非终结符、或e标记；每个内部结点由一个非终结符标记；若A是某内部节点的标记，且X1, X2, ., Xn该节点从左到右所有孩子的标 记，则AX1X2.Xn是一个产生式。若A-e，则标记为A的结点可以仅有一个标记为8的孩子。分析树与语

10、言和文法的关系：每一直接推导（每个产生式），对应一棵仅有父子关系 的子树，即产生式左部非终结符“长出”右部的孩子； 分析树的叶子，从左到右构 成G的一个句型。若叶子仅由终结符标记，则构成一个句子。3.4某程序执行到某一时刻时控制栈中的内容如下所示（其中M是主程序，P、Q、R、S 均是过程），给出所有在生存期的活动的调用关系（提示：若A调用B，则记为A-B）。S的活动记录 S的活动记录 Q的活动记录 R的活动记录 P的活动记录 M的活动记录top控制链KI%I答案：M P R Q S S解释：顺序执行程序的执行在时间上是顺序的和排他的。即在程序执行的任一瞬间，有 且仅有一个活动正在活动。控制栈用

11、于保存所有在生存期的活动（一条后进先出的路 径）。栈中的每个元素称为一个活动记录（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 = A0_闭包(s0) = S0初态_闭包(smove(s0,1) = B记为s1_闭包(smove(s1,0) =

12、B = si_闭包(smove(s1,1) = B,C记为s2，终态_闭包(smove(s2,0) = B = si_闭包(smove(s2,1) = B,C = s2DFA如下图所示01解释：用算法2.2 Thompson算法从正规式构造出与其对应的NFA；用子集法(算法2.3) 将NFA转换为DFA。其中需要用算法2.4计算状态集T的s闭包(T)。(15分)设有上下文无关无法G及其语法制导翻译如下(注：G中终结符id仅由单个 英文字母组成，如a, b等)：EE*TE.place=newtemp; emit(*,Emplace,T.place,E.place;| TE.place=T.pla

13、ce;TTFT.place=newtemp; emit(-,Tplace,F.place,T.place;| FT.place=F.place;F(E)F.place=E.place;| idF.place=;(4分)画出句子a-b*c的分析树;(3分)写出当a=1、b=2、c=3时的计算结果；(*表示算术乘、-表示算术减)(8分)将文法G简化为:E-E*T|T, TT-F|F, F-id,给出其识别活前缀的DFA, 该DFA的项目集中有冲突吗？若有，是哪种类型的冲突。答案：(a)(b) -3拓广文法，增加产生式：S-E，识别活前缀的DFA如下图所示存在移进一归约冲突解释：(a)

14、从文法推导(最左推导)出句子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)每个叶 子由一个终结符、非终结符、或8标记；(3)每个内部结点由一个非终结符标记；(4) 若A是某内部节点的标记，且X1, X2, ., Xn该节点从左到右所有孩子的标记，则A 一X1X2.Xn是一个产生式。若A8,则标记为A的结点可以仅有一个标记为8的孩 子。根据分析树，先计算a - b,得-1，然后再乘以3,结果为-3用算法3.9计算文法基于LR(0)项目的识别活前缀的DFA。当DFA的一个项目集 中同时存在：A-B1.B2和B-B.：说明下一