《编译原理总复习【习题汇总】》由会员分享，可在线阅读，更多相关《编译原理总复习【习题汇总】（76页珍藏版）》请在金锄头文库上搜索。
1、总 复 习(一 ）选择题（10小题，共20分，每题2分） 1.编译程序必须完成的工作有 。 词法分析 语法分析语义分析 中间代码生成中间代码优化目标代码生成 A. B. C. D. 2.下列关于编译和解释的说法，正确的是 。解释方式和编译方式的区别在于解释程序对源程序并没有进行真正翻 译。 编译方式与解释方式的根本区别在于是否生成目标代码。 解释程序和编译程序都是语言处理程序。 与编译系统相比，解释系统比较简单，可移植性好，执行速度慢。 编译程序是将高级语言程序翻译成汇编语言程序或机器语言程序 解释程序是将汇编语言程序翻译成机器语言程序 A.B. C. D.CD3. 这样一些语言，它们能被确定
2、有限自动机识别，但不能用正则表达式表示。 A存在 B.不存在 C.无法判定是否存在 4.已知文法GS： S SaS | SbS | ScS | dSe | f,下列句型中， 是规范句型。 AfafbS B.faSbS C.SaSbf. D.faSBCSaSSSbSffSaSSSbSfSaSSS b SSaSSff5.下列文法中不是二义性文法的是 。 AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)B.句型：( ) ( )(SSS)S(SS)SA(SSS)S(SS)S5.下列文法中不是二义
3、性文法的是 。 AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)C.句型：ababSSbSaSbSaSSbSaSaSbA5.下列文法中不是二义性文法的是 。 AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)D.句型：a+a*S + SS S * a aS *SS + SaaA6.后缀表达式ab+c*de*+ 的中缀形式是 。 Aa*(b+c)+d*eB(a+b)*c+d*e Ca+
4、b*c*d+eDa+b*c+d*eB后缀式(逆波兰式 )n例：pos(A*B+C*D)=AB*CD*+n逆波兰式的特点:逆波兰式中的变量的次序与中缀式中的 变量的次序完全一致。逆波兰式中无括号。逆波兰式中的运算符已按计算顺序排列 。7.合并无冲突的LR（1）状态机得到的LALR（ 1）状态机中一定不会出现 冲突。 A. 移入/移入冲突B. 移入/归约冲突 C. 归约/归约冲突B例如，假定Si、Sj是某一LR(1)状态机的两个状态，其中，u1、u2、v1、v2、t1、t2分别为归约展望符集 , aVT。 在Si中有: u1v1=、u1a=、v1a=; 在Sj中有: u2v2=、u2a=、v2a=
5、。 显然Si和Sj是同心状态，合并后得到新状态Sij :A B Cau1 v1 t1SiA B Cau2 v2 t2SjA B Cau1 u2 v1 v2 t1 t2Si因： (u1 u2 ) a= (v1 v2 ) a= 所以不可能产生移 入归约冲突。因： (u1 u2 ) (v1 v2 ) = ？ 所以可能产生归约归 约冲突。8.编译程序使用 区别标识符的作用域。 A.声明标识符的过程或函数名 B. 声明标识符的过程或函数的静态层数 C.声明标识符的过程或函数的动态层数 D.标识符的行号B9.适合采用静态存储分配策略的程序设计语言的限制有 。 数据实体所需空间在编译时能确定 过程调用不允许
6、递归 不能动态建立数据实体 运行时每个数据对象只能有一个实例 数组的上下界是常量 A. B. C. D. 10.目标代码生成器的输出可以是 。 绝对机器代码可重定位机器代码汇编代码 虚拟机代码抽象语法树三地址代码 AB. C. D. AD二、简答题（5小题，共30分，每个6分） 1.对于文法GS： S aAbB A c | Ac B d | dB 请画出句型aAcbdd的语法树，并求出该句 型的所有短语、简单短语和句柄。定义1：由某一结点及其所有分支组成的部 分树称为原树的一棵子树。 定义2：只有单层分支的子树称为简单子树 。 定义3：最左简单子树的叶称为句柄。 定理：1.每个句型都有一棵语法
7、树，每个语法 树的叶组成该句型。2.每棵子树的叶组成短语，每棵简单子 树的叶组成简单短语。3.最左简单子树的叶组成句柄。语法树的应用_一个有用的定理2.2.42.2.4语法树语法树背景知识背景知识GS： S aAbB A c | Ac B d | dB 句型aAcbddSaAbBAcdBdaAcbddAc ddd短语：简单短语： Ac d句柄： Ac二、 2.写出类型Grade07的内部表示，其中每个int、char类型 数据各占1个内存单元。 typedef struct char name20;int num;student; typedef student Grade07400;Elem
8、TypeSizeKindSubSizeArrayTyLow Up其中各个域的含义如下：ZSize表示数组类型所占空间的大小，是数组所有成分数据占用空间的和，需要通过计算得到，Size = (Up-Low+1)*sizeof(ElemType), 其中sizeof是一个辅助函数，用于计算每种类型的size；ZKind = arrayTy, 表示是数组类型；ZLow表示数组下标的下界，在C语言中Low = 0；ZUp表示数组下标的上界；ZElemType 表示数组成分类型的内部表示指针。 数组类型：FieldListKindSize结构体与共用体类型其中各个域的含义义如下：Size表示该类该类 型
9、数据所占空间间的大小，结结构体是所有域占用空间间的和，共用体类类型则则是所有域中占用空间间的最大者的值值。Kind = structTy, 表示是结结构体或共用体类类型；FieldList 是域名表的表头头指针针。其中各个域的含义如下： Name表示标识符的名字； Type = TypePtr，TypePtr是域名标识符类型的内部表 示指针； Off表示域名标识符相对于记录类型分配的内存块起始 地址的偏移量，对于联合类型而言，所有的域名标识符 的起始偏移都是相同的，所以可以省略；OffTypeName域名标识符的内部表示如下： 结构体与共用体类型-域名表charPtr 20 ArrayTy01
10、9typedef struct char name20; int num;student; typedef student Grade07400;structTy0name20intPtrnumArrayTy0399840021二、 3. 请给出下面文法GA的LL(1)分析表。 A aABe 1 | Bc 2 B dB 3 | 4三个重要的集合 vFirst集 First() = a VT | * a. (if * then else ) vFollow集Follow(A) = a VT | S+ .Aa. (if S*.A then # else )vPredict集(Select集)Pre
11、dict(A) First() 当 First()=First()- Follow(A) 当 First() 背景知识背景知识对每一文法符号X计算First(X)集(1)v 若X VT ：First(X)=Xv若X VN : 对关于X的每一个产生式进行如下处理:uStep1.形如: X , 则: First(X)uStep2.形如:X a , a VT则 : a First(X)背景知识背景知识uStep3.对每一个形如下的产生式: XY1Y2Yi-1YiYn若：Y1,Y2, ,Yi VN且Y1,Y2, ,Yi-1* 则: First(Y1)- , First(Y2)- , , First(Y
12、i-1)- , First(Yi)都包含在First(X)中。若： Yi VN且Yi * (i=1,2,n), 则: First(Y1) , First(Y2), , First(Yn) 都包含在 First(X)中。重复Step3 ，直至对所有AVN，First(A)收敛为止。对每一文法符号X计算First(X)集(2)背景知识背景知识计算First()集若符号串=X1X2Xn，v当X1,X2, , Xi-1*，Xi 不能 * ， 则:First()=1i-1(First(Xj)-) First(Xi)v若所有Xi 都能*， 则:First()= 1n First(Xj)背景知识背景知识1:
13、 对所有AVN 且 A非开始符 : 令Follow(A):= ；对开始符 S : 令Follow(S)= # ； 2: 若有产生式AxBy：如果 First(y) 则： Follow(B)= Follow(B) (First(y) Follow(A)否则：Follow(B) = Follow(B) First(y) 3: 重复2和3，直至对所有AVN，Follow(A)收敛为止。计算Follow(A) (AVN )背景知识背景知识计算Predict集lPredict(A) First() ，当First()不含= First()- Follow(A) ，当First()含背景知识背景知识LL(
14、1)分析表的构造vLL(1)分析表的定义：T：VN VT P Error T(A,t)=A 若tPredict( A )T(A,t)=Error 否则其中P表示所有产生式的集合。背景知识背景知识vLL(1)分析表的构造方法：对文法的每一个产生式求其predict集 ；对文法的每一个产生式A进行如下 处理：Predict( A )=（ a1,a2,.,an);则令： T(A,ai)=A ,i=1,2,3,n LL(1)分析表的其它元素为error。背景知识背景知识文法GA的LL(1)分析表。 A aABe 1 | Bc 2 B dB 3 | 4文法符号First集Follow集 A B #,d, e,c（1）求每个产生式的Predict集： Predict（ A aABe
