编译原理自测(一、二、三)及答案复习过程

1、编译原理自测一一、是非题（下列各题，你认为正确的，请在题干的括号内打“vf错的打“X。每题1分 ,共 5 分 ）1、算符优先关系表不一定存在对应的优先函数。 正确2、数组元素的地址计算与数组的存储方式有关。 .正确3、 仅考虑一个基本块，不能确定一个赋值是否真是无用的。正确4、每个文法都能改写为 LL（1） 文法。 不正确5、对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 不正确二、填空题1 、 从功能上说， 程序语言的语句大体可分为 （执行性） 语句和 （说明性） 语句两大类。2、 扫描器的任务是从（源程序）中识别出一个个（单词符号）。3、所谓最右推导是指：（任何一步af都

2、是对a中最右非终结符进行替换的）。4、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。5、一个上下文无关文法所含四个组成部分是 （一组终结符号，一组非终结符号、一 个开始符号、一组产生式 ）。6、所谓语法制导翻译方法是 （为每个产生式配上一个翻译子程序，并在语法分析的 同时执行这些子程序 ）。7、符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、？）等 等。8、一个过程相应的 DISPLAY 表的内容为（现行活动记录） 。9、 常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。10、产生式是用于定义 （语法范畴 ）的一种书写规则。三、名词解释1遍指编译程序

3、对源程序或中间代码程序从头到尾扫描一次。2. 无环路有向图（DAG）如果有向图中任一通路都不是环路， 则称庐有向图为 无环路有向图，简称 DAG。3. 语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。4短语令G是一个文法。S划文法的开始符号，假定 a f S是文法G的一 个句型，如果有Sa AS且AB则称f是句型a f相对非终结符A的短语。5.后缀式一种把运算量写在前面，把算符写在后面的表示表达式的方法。编译原理自测二、是非题（下列各题，你认为正确的，请在题干的括号内打“V”错的打“X”每题1分,共5分）1、一个 LL（1） 文法一定是无二义的。 .正确2、 逆波兰法表示的表达

4、式亦称前缀式。.不正确3、 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。.正确4、 正规文法产生的语言都可以用上下文无关文法来描述。.正确5、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态 。不正确二、填空题1、语法分析是依据语言的 （语法）规则进行的，中间代码产生是依据语言的 （语 义）规则进行的 。2、程序语言的单词符号一般可以分为（ 基本字、标识符、常量、算符、界符 ） 等等。3、语法分析器的输入是 （单词符号串），其输出是 （语法单位）4、所谓自上而下分析法是指（ 从开始符号出发，向下推导，推出句子 ）。5、如果一个文法存在某个句子对应两棵不同的语法树

5、， 则称这个文法是 （二义 的）。6对于文法G仅含终结符号的句型称为（句子）。7、逆波兰式 ab+c+d*e- 所表达式为 （）。8、一个名字的属性包括 （类型）和（作用域）。9、对于数据空间的存贮分配，FORTRA采用（静态存储分配）策略，PASCAL 采用 （动态存储分配）策略。10、所谓优化是指（ 对程序进行各种等价变换，使得从变换后的程序出发，能生 成更有效的目标代码 ）。三、 名词解释1词法分析器指执行词法分析的程序。2语法一组规则，用它可以形成和产生一个合式的程序3最右推导指对于一个推导序列中的每一步直接推导，被替换的总是当前 符号串中的最右非终结符号。4语法制导翻译在语法分析过程

6、中，根据每个产生式所对应的语义子程序 进行翻译的办法叫做语法制导翻译。学习-好资料5 基本块一一指程序中一个顺序执行的语句序列，其中只有一个入口，一个出 口，入口即第一个语句。出口即最后一个语句。编译原理自测三一选择题（每空2分，共20分）1文法 G产生的 的全体是该文法描述的语言。DA.句型广B.终结符集C.非终结符集灯 D.句子2、 若文法 G定义的语言是无限集，则文法必然是：A蒋 A.递归的厂B.前后文无关的厂 C.二义性的 D.无二义性的3、 Chomsky定义的四种形式语言文法中，0型文法又称为 A文法；1型文法又称为 C文法；2型语言可由 G识别。“ A.短语结构文法B.前后文无关

7、文法厂C前后文有关文法"D.正规文法厂E.图灵机厂F有限自动机厂G.下推自动机A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机厂F有限自动机厂G.下推自动机“ A.短语结构文法"B.前后文无关文法" C.前后文有关文法" D.正规文法CE.图灵机厂F有限自动机"G.下推自动机4、 一个文法所描述的语言是A ;描述一个语言的文法是B。rrA.唯一的 B.不唯一的C.可能唯一，可能不唯一A.唯一的* B.不唯一的C.可能唯一，可能不唯一5、数组的内情向量中肯定不含有数组的A的信息A.维数厂B.类型厂C.维上下界"

8、 D.各维的界差6、在下述的编译方法中，自底向上的方法有F，自顶向下的分析方法有A。简单优先分析算符优先分析递归下降分析预测分析技术LR（ K）分析 SLR（ k）分析 LL（ k）分析 LALR（ K）分析A.厂B.厂 C. D.学习-好资料E."F.A.厂B.厂C.厂D.E.厂F.简答题1 . LL ( 1 )分析法对文法有哪些要求?对于G中的每个产生式 A -Y 1 | 丫 2 | 丫 m ,其各候选式均应满足：(1)不同的候选式不能推出以同一终结符号打头的符号串，即FIRST( 丫i ) n FIRST( 丫 j )=©( 1 < i , j < m ；

9、 i j )(2)若有丫 j £ ,则其余候选式丫 i所能推出的符号串不能以 FOLLOW(A)中的终结符号开始，即有FIRST( 丫 i ) n FOLLOW(A)邛(i < 1 ,2,，m ; i 工 j)2 .常见的存储分配策略有几种？它们都适合于什么性质的语言?有三种分配存储空间的方式：(1 )静态分配若在编译阶段就能确定源程序中各个数据实体的存 储空间大小，则可以采用较简单的静态存储管理。 适合静态管理的语言应具备条 件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。(2 )栈式分配适用于允许递归调用的程序设计语言 ；(3 )堆式分配对于允许程序在运行时为变量动态申请和释放存储 空间的语言，采用堆式分配是最有效的解决方案。3 .常见循环优化都有哪些项目？不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化4 .什么是活动记录？它主要由哪些内容构成?一个过程的一次执行所需信息的管理，是通过称为 活动记录 的连续存储块来实 现的。活动记录的主要内容有：（ 1 ） 临时变量域 存放目标程序临时变量的值；（ 2 ）局部数据域 存放过程本次执行时的局部数据、简单变量及数组内情向量等；（ 3 ）