编译原理期末复习资料

1、精选优质文档-倾情为你奉上一、选择题1词法分析器的输出结果是_C_。A单词的种别编码 B单词在符号表中的位置 C单词的种别编码和自身值 D单词自身值2 正规式 M 1 和 M 2 等价是指_C_。  AM1和M2的状态数相等          BM1和M2的有向边条数相等CM1和M2所识别的语言集相等 D M1和M2状态数和有向边条数相等 3 文法G：SxSx|y所识别的语言是_C_。A xyx  B (xyx)* C xnyxn(n0)     Dx*yx* 4如果文法G是

2、无二义的，则它的任何句子_A_。A最左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同   D可能存在两个不同的最左推导，但它们对应的语法树相同 5构造编译程序应掌握_D_。A源程序   B目标语言        C编译方法      D以上三项都是 6四元式之间的联系是通过_B_实现的。 A指示器         B临时变量 C符号表 &

3、#160;           D程序变量 7表达式(AB)(CD)的逆波兰表示为_B_。A. ABCD BABCD         CABCD         DABCD 8. 优化可生成_D_的目标代码。A运行时间较短            &#

4、160;   B占用存储空间较小C运行时间短但占用内存空间大 D运行时间短且占用存储空间小9下列_C_优化方法不是针对循环优化进行的。A. 强度削弱     B 删除归纳变量     C删除多余运算  D代码外提10编译程序使用_B_区别标识符的作用域。 A.说明标识符的过程或函数名B说明标识符的过程或函数的静态层次C说明标识符的过程或函数的动态层次 D. 标识符的行号1语言是AA句子的集合 B产生式的集合 C符号串的集合 D句型的集合2编译程序前三个阶段完成的工作是CA词法分析、语法分析和代码

5、优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化3一个句型中称为句柄的是该句型的最左D A非终结符号 B短语 C句子 D直接短语4下推自动机识别的语言是CA0型语言 B1型语言 C2型语言 D3型语言5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即B A 字符 B单词 C句子 D句型6对应Chomsky四种文法的四种语言之间的关系是B AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37词法分析的任务是A A识别单词 B分析句子的含义 C识别句子 D生成目标代码8

6、常用的中间代码形式不含D A三元式 B四元式 C逆波兰式 D语法树9 代码优化的目的是C A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换10代码生成阶段的主要任务是C A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言【 D 】1_型文法也称为正规文法。A 0 B 1 C 2 D 3【 D 】2_文法不是LL(1)的。 A 递归 B 右递归 C 2型 D 含有公共左因子的【 B 】3 文法EE+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为_。A1 B3 C5 D7【 A 】4四元式之间的联

7、系是通过 实现。 A临时变量 B指示器 C符号表 D程序变量【 C 】5同心集合并可能会产生的新冲突为 。 A二义 B移进/移进 C移进/归约 D归约/归约【 C 】6代码优化时所依据的是 。 A语法规则 B词法规则 C等价变换规则 D语义规则【 B 】7表达式a-(-b)*c的逆波兰表示为 。 Aa-bc* B Cab- Dabc-* （注：为单目减运算符）【 B 】8过程的DISPLAY表记录了 。 A过程的连接数据 B过程的嵌套层次 C过程的返回地址 D过程的入口地址1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个（C ），以及一组（B ）。A 字符串 B 产生

8、式 C 开始符号 D 文法2.程序的基本块是指（D ）。A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（B ）分析方法。A 自左向右 B 自顶向下 C 自底向上 D 自右向左4在通常的语法分析方法中，（ A）特别适用于表达式的分析。A 算符优先分析法 B LR分析法C 递归下降分析法 D LL（1）分析法5经过编译所得到的目标程序是（ D）。A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序6 一个文法所描述的语言是（A ）

9、；描述一个语言的文法是（ C）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一个句子，当其满足下列条件（BCD ）之一时，则称该文法是二义文法。A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导C 该句子有两个不同的最右推导 D 该句子有两棵不同的语法树E 该句子对应的语法树唯一8 下面（ BCD）语法制导翻译中，采用拉链回填技术。A. 赋值语句 B. 布尔表达式的计算 C. 条件语句 D. 循环语句1. 设有文法GI： II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（ B ）。 ab0 a0c01 aaa bc10可选项有：A B C

10、 D5 运行阶段的存储组织与管理的目的是（ C ）。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备可选项有：A. B. C. D. 1将编译程序分成若干个“遍”是为了_b_。 a.提高程序的执行效率 b.使程序的结构更加清晰 c.利用有限的机器内存并提高机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 2.构造编译程序应掌握_d_。 a.源程序 b.目标语言 c.编译方法 d.以上三项都是 3变量应当c。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 4.编译程序绝大多数时间花在_d_上。

11、a.出错处理 b.词法分析 c.目标代码生成 d.管理表格 5.词法分析器的输出结果是_c_。 a.单词的种别编码 b.单词在符号表中的位置 c.单词的种别编码和自身值 d.单词自身值 6.中间代码生成时所依据的是c。 a.语法规则 b词法规则 c语义规则 d等价变换规则 7.,后缀式ab+cd+/可用表达式_b_来表示。 a.a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d 8.程序所需的数据空间在程序运行前就可确定，称为_c_管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 9.堆式动态分配申请和释放存储空间遵守_d_原则。 a.先请

12、先放 b.先请后放 c.后请先放 d.任意 1 一个编译程序中，不仅包含词法分析，_A_，中间代码生成，代码优化，目标代码生成等五个部分。 A语法分析 B文法分析 C语言分析 D解释分析 2 词法分析器用于识别_C_。 A字符串B语句C单词 D标识符 3 语法分析器则可以发现源程序中的_D_。 A语义错误 B语法和语义错误 C错误并校正 D语法错误 4 下面关于解释程序的描述正确的是_B_。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A(1)(2) B(1) C(1)(2)

13、(3) D(2)(3) 5 解释程序处理语言时 , 大多数采用的是_B_方法。 A源程序命令被逐个直接解释执行 B先将源程序转化为中间代码 , 再解释执行 C先将源程序解释转化为目标程序 , 再执行 D 以上方法都可以 6 编译过程中 , 语法分析器的任务就是_B_。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A(2)(3) B (2)(3)(4)C (1)(2)(3) D(1)(2)(3)(4) 7 编译程序是一种_C_。 A. 汇编程序 B翻译程序C解释程序 D目标程序 8 文法 G 所描述的语言

14、是_C_的集合。 A. 文法 G 的字母表 V 中所有符号组成的符号串 B文法 G 的字母表 V 的闭包 V* 中的所有符号串 C由文法的开始符号推出的所有终极符串 D. 由文法的开始符号推出的所有符号串 9 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_B_。 A. 短语文法 B 正则文法C 上下文有关文法 D 上下文无关文法 1 文法 G 产生的_D_的全体是该文法描述的语言。 A句型 B 终结符集 C非终结符集 D句子 2 若文法 G 定义的语言是无限集，则文法必然是 _A_。 A递归的 B前后文无关的 C二义性的 D无二义性的 3 四种形式语言文法中，1型文法又称为 _C

15、_文法。 A短语结构文法 B前后文无关文法 C前后文有关文法 D正规文法 5 _B_和代码优化部分不是每个编译程序都必需的。 A语法分析 B中间代码生成 C词法分析 D目标代码生成 6_B_是两类程序语言处理程序。 A高级语言程序和低级语言程序 B解释程序和编译程序 C编译程序和操作系统 D系统程序和应用程序 7 数组的内情向量中肯定不含有数组的_A_的信息。 A. 维数 B类型 C维上下界 D各维的界差 9 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_D_。 A. 短语文法 B正则文法 C上下文有关文法 D上下文无关文法 4_A_是一种典型的解释型语言。 ABASIC BC

16、CFORTRAN D PASCAL 5与编译系统相比，解释系统_D_。 A比较简单 , 可移植性好 , 执行速度快 B比较复杂 , 可移植性好 , 执行速度快 C比较简单 , 可移植性差 , 执行速度慢 D比较简单 , 可移植性好 , 执行速度慢 6用高级语言编写的程序经编译后产生的程序叫_B_。 A源程序 B目标程序 C连接程序 D解释程序 8编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过_B_这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 A. (1)(2)(3)(4) B(1)(2)(3) C (1)(3) D (1)(4) 9把汇编语言程序翻译成

17、机器可执行的目标程序的工作是由_B_完成的。 A编译器 B汇编器 C 解释器 D预处理器 2 编译程序是对_D_。 A汇编程序的翻译 B高级语言程序的解释执行C机器语言的执行 D高级语言的翻译 3 采用自上而下分析，必须_C_。 A 消除左递归 B消除右递归 C消除回溯 D提取公共左因子 4在规范归约中，用_B_来刻画可归约串。 A直接短语 B句柄 C最左素短语 D素短语 5 若a为终结符，则A-> · a为_B_项目。 A归约 B移进 C接受 D待约 6间接三元式表示法的优点为_A_。 A采用间接码表，便于优化处理 B节省存储空间，不便于表的修改C便于优化处理，节省存储空间

18、D节省存储空间，不便于优化处理 7基本块内的优化为_B_。 A. 代码外提，删除归纳变量 B删除多余运算，删除无用赋值C强度削弱，代码外提 D循环展开，循环合并 8. 在目标代码生成阶段，符号表用_D_。 A目标代码生成 B语义检查 C语法检查 D地址分配 9若项目集Ik含有A-> · ，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A-> · ”动作的一定是_D_。 A. LALR文法 BLR(0)文法 CLR(1)文法 DSLR(1)文法 10堆式动态分配申请和释放存储空间遵守_D_原则。 A. 先请先放 B先请后放 C后请先放 D.任意

19、二、简答题1、正规表达式定义P182、上下文无关文法定义P39VT 是一个非空有限集合，其元素称为终结符。VN是一个非空有限集合，其元素称为非终结符，并有VTVN=非空S是一个非终结符，称为开始符号。P是产生式的有限集合。3、分离词法分析器的理由P44语言的词法规则简单，不必用功能更强的上下文无关文法描述它；对于词法记号，正规式给出的描述比上下文无关文法给出的更简洁且易于理解；从正规式自动构造出的词法分析器比从上下文无关文法构造出的更有效；编译器的效率会改进；编译器的可移植性加强；把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的 途径。4、LR分析器富有吸引力的原因P

20、71LR分析器能够被构造来识别所有能用上下文无关文法写出的编程语言构造。LR分析方法是已知的最一般的无回溯的移进归约方法，它能和其他移进归约方 法一样有效地实现。LR方法能分析的文法类是预测分析法或者说LL方法能分析的文法类的直超集。在自左向右扫描输入的前提下，LR分析器尽可能快地发现语法错误。5、语法制导定义的形式P107综合属性：如果b是A的属性，c1，c2，····，ck是产生式右部文法符号的属性或A的其他属性，那么b称为A的综合属性。继承属性：如果b是产生式右部某个文法符号X的属性，c1，c2，···，ck是A的属性

21、或右部文法符号的属性，那么b称为X的继承属性。S属性定义：仅仅使用综合属性的语法制导定义称为S属性定义。注释分析树：每个结点的属性值都标注出来的分析树。依赖图：分析树结点的属性之间的互相依赖可以用依赖图的有向图来描绘。6、翻译方案设计原则P117产生式右部符号的继承属性必须在先于这个符号的动作中计算。一个动作不能引用该动作右边符号的综合属性。左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。只有综合属性的情况最简单。7、活动记录结构P166临时数据；保存临时值。局部数据；保存过程的局部数据。保存的机器状态；保存刚好在过程调用前的机器状态信息，包括返回地址及调用过 程使用并且在返

22、回时必须恢复的寄存器的内容。访问链；有些语言需要通过访问链来访问非局部数据。控制链；用来指向调用者的活动记录。参数；调用过程提供的实在参数，由被调用过程使用。返回值。用于存放被调用过程返回给调用过程的值。8、活动记录设计布局原则P171调用者和被调用者之间交流的数据一般放在被调用者活动纪录的开始处，并尽可能 靠近调用者的活动纪录。固定长度的项通常放在活动纪录的中间，一般包括控制链、访问链和机器状态链。在编译时不能及时知道大小的一些项放在活动纪录的末端。 9、参数传递的方法和特点P180值调用。值调用是最简单的传递参数的方法。调用者计算实参，并把它的值（右值） 传给被调用过程。引用调用。调用者把

23、实参存储单元的地址（即实参的左值）传给被调用者，被调用 者对形参的任何访问就是对对应实参的访问。换名调用。P18110、使用独立于机器的中间形式的好处P199再目标比较容易。把针对新机器的后端加到现成的前端上，可以得到另一种机器的 编译器。独立于机器的代码优化器可用于这种中间表示。三、应用题状态转换图（有穷状态自动机）： ： ： ： ： ： ： ： ： ： ： 1、（a|b）*（aa|bb）（a|b）*画出状态转换图。IaIb 1,2,32,3,42,3,5 2,3,42,3,4,6,7,82,3,5 2,3,52,3,42,3,5,6,7,8 2,3,4,6,7,82,3,4,6,7,82,

24、3,5,7,8 2,3,5,6,7,82,3,4,7,82,3,5,6,7,8 2,3,5,7,82,3,4,7,82,3,5,6,7,8 2,3,4,7,82,3,4,6,7,82,3,5,7,8IaIb123243325446575675746 新的状态转换图如下： （1）A=1,2,3，B=4,5,6,7 Aa=2,4 ×（2）A=1,3，B=2，C=4,5,6,7 Aa=2B，Ab=3,5 ×（3）A=1，B=2，C=3,D=4,5,6,7（单元素可以不用看，必有，古先看D） Da=4,7D，Db=5,6D，Aa=2B，Ab=3C，Ba=4D，Bb=3C，Ca=2B

25、，Cb=5C，则有ab ABC BDCCBDDDD2、（a*|b*）b（ba）*的状态转换图。IaIb 1,2,3,42,43,4,5,6,8 2,42,45,6,8 3,4,5,6,8-3,4,5,6,7,8 5,6,8-7 3,4,5,6,7,86,83,4,5,6,7,8 76,8- 6,8-7IaIb1232243-54-657567-7-6新的状态转换图如下：化简：（用终结状态与非终结状态，然后输出状态一致分一类）。（1）A=1,2,6，B=3,4,5,7 Aa=2 ×（2）A=1,2，B=6，C=3,4,7，D=5 Cb=5,6 ×（只要有一个不属于任何一个集合

26、，就不行）（3）A=1,2，B=6，C=3，D=4,7，E=5 Ab=3,4 ×（4） A=1，B=2，C=6，D=3，E=4,7，F=5 Aa=2B，Ab=3D，Ba=2B，Bb=4E，Ca=7E，Db=5F，Eb=6C，Fa=7E，Fb=5Fab ABD BBECE-D-FE-CFEF知识点First集合的求法： First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合1. 直接收取：对形如U->a的产生式（其中a是终结符），把

27、a收入到First(U)中2. 反复传送：对形入U->P1P2P3Pn的产生式（其中P是非终结符），应先把First(P1)中的全部内容传送到First(U)中,如果P1中有，把First(P2)中的内容传送到First(U)中,类推直到Pi中无。Follow集合的求法： Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“$”是识别符号的后随符,先直接加入到S中。1. 直接收取：注意产生式右部的每一个形如“Ua”的组合，把a直接收入到Follow(U)中。2. 直接收取：对形如“UP”(P是非终结符)的组合，把Fir

28、st(P)中非收入到Follow(U)中。3. 反复传送：对形如U>aP的产生式（其中P是非终结符）或U->aPQ(P,Q为非终结符且Q中含)，应把Follow(U)中的全部内容传送到Follow(P)中。例 文法：SABc Aa| Bb|First集合求法:能由非终结符号推出的所有的开头符号或可能的，但要求这个开头符号是终结符号。如此题A可以推导出a和，所以FIRST（A）=a，；同理 FIRST（B）=b,;S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=a，b，cFollow集合的求法:紧跟随其后面的终结符号或。但文法的识别符号包含，在求的时候还要

29、考虑到。 具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=如求A的，产生式：SABc Aa| ，但只有SABc 有用。跟随在A后面的终结符号是FIRST（B）=b，当FIRST（B）的元素为时，跟随在A后的符号就是c，所以 Follow（A）=b，c同理Follow（B）=c对下面的文法 G ： (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的预测分析表。解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(E')