计算机编译原理小抄

1、编译原理名词解释1.局部优化：局限于基本块范围的优化称。2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.display表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。5.最左推导：任何一步=都是对中的最右非终结符替换。6.语法：一组规则，用它可形成和产生一组合式的程序。7.文法：描述语言的语法结构的形式规则。8.基本块：指程序中一顺序执行的语句

2、序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语：令g是一个文法，s划文法的开始符号，假定是文法g的一个句型，如果有sa且a，则称是句型相对非终结符a的短语。11.待用信息：如果在一个基本块中，四元式i对a定值，四元式j要引用a值，而从i到j之间没有a的其它定值，则称j是四元式i的变量a的待用信息。12.规范句型：由规范推导所得到的句型。13.扫描器：执行词法分析的程序。14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。1

3、5.句柄：一个句型的最左直接短语。16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。17.规范句型：由规范推导所得到的句型。18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法：是组规则，用它可形成和产生一个合式的程序。 20.语义：定义程序的意义的一组规则。21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化21词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具

4、有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。22ll(1)文法 若文法的任何两个产生式a a | b都满足下面两个条件：（1）first(a ) first(b ) = f；（2）若b * e ，那么first(a ) follow( a ) = f。我们把满足这两个条件的文法叫做ll(1)文法，其中的第一个l代表从左向右扫描输入，第二个l表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，ll(1)文法还有一些明显的性质，它不是二义的，也不含左递归。23语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给

5、定文法g=(vn，vt，p，s)，对于g的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号s。(2)每个节点的标记都是v中的一个符号。(3)若一棵子树的根节点为a，且其所有直接子孙的标记从左向右的排列次序为a1a2ar，那么aa1a2ar一定是p中的一条产生式。(4)若一标记为a的节点至少有一个除它以外的子孙，则avn。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法g的句型；若w中仅含终结符号，则w为文法g所产生的句子。24lr(0)分析器所谓lr(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归

6、约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。25语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法g定义为四元组的形式：g=(vn，vt，p，s)其中：vn 是非空有穷集合，称为非终结符号集合；vt 是非空有穷集合，称为终结符号集合；p是产生式的集合(非空)；s是开始符号(或识别符号)。这里，vnvt=，svn。v=vnvt，称为文法g的字母表，它是出现文法产生式中的一切符号的集合。文法g所描述的语言用l(g)表示，它由文法g所产

7、生的全部句子组成，即l(g)=x| s*x，其中s为文法开始符号，且 简单的说，文法描述的语言是该文法一切句子的集合。26词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。27ll(1)文法若文法的任何两个产生式a a | b都满足下面两个条件：（1）first(a ) first(b ) = f；（2）若b * e ，那么first(a ) follow( a ) = f。我们把满足这两个条件的文法叫做ll(1)文法，其中的第一个l代表从左向右扫描输入，第

8、二个l表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，ll(1)文法还有一些明显的性质，它不是二义的，也不含左递归。28语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法g=(vn，vt，p，s)，对于g的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号s。(2)每个节点的标记都是v中的一个符号。(3)若一棵子树的根节点为a，且其所有直接子孙的标记从左向右的排列次序为a1a2ar，那么aa1a2ar一定是p中的一条产生式。(4)若一标记为a的节点至少有一个除它以外的子孙，则avn。(5)若树的所有叶

9、节点上的标记从左到右排列为字符串w，则w是文法g的句型；若w中仅含终结符号，则w为文法g所产生的句子。29lr(0)分析器所谓lr(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。30语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法g定义为四元组的形式：g=(vn，vt，p，s)其中：vn 是非空有穷集合，称为非终结符号集合；vt 是非空有

10、穷集合，称为终结符号集合；p是产生式的集合(非空)；s是开始符号(或识别符号)。这里，vnvt=，svn。v=vnvt，称为文法g的字母表，它是出现文法产生式中的一切符号的集合。文法g所描述的语言用l(g)表示，它由文法g所产生的全部句子组成，即l(g)=x| s*x，其中s为文法开始符号，且 简单的说，文法描述的语言是该文法一切句子的集合。31.编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成32.解释程序：把某种语言的源程序转换成等价的另一种语言程序目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上

11、得到这句的执行结果，然后再接受下一句。33.编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。34.解释程序和编译程序的根本区别：是否生成目标代码35.句子的二义性（这里的二义性是指语法结构上的。）:文法gs的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。36文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。37.ll(1)的含义：(ll(1)文法是无二义的； ll(1)文法不含左递归)第1个l：从左到右扫描输入串

12、。第2个l：生成的是最左推导。1 ：向右看1个输入符号便可决定选择哪个产生式38某些非ll(1)文法到ll(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 39.文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。40.一个属性文法(attribute grammar)是一个三元组a=(g, v, f)g：上下文无关文法。v：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。f：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性

13、。41.综合属性:若产生式左部的单非终结符a的属性值由右部各非终结符的属性值决定,则a的属性称为综合属。42.继承属性:若产生式右部符号b的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则b的属性为继承属性。(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时： 综合属性沿属性语法树向上传递（即传递信息的方向是自下而上）；继承属性沿属性语法树向下传递（即传递信息的方向是自上而下）。 43.语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。44.语法制导翻

14、译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。45.中间代码（中间语言）：1、是复杂性介于源程序语言和机器语言的一种表示形式。2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。46.何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。47.为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。(2)便

15、于移植，便于修改，便于进行与机器无关的优化。48.中间代码的几种形式：逆波兰式（后缀式） ，三地址码（三元式、四元式、间接三元式 ）49.符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。50.符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据51.符号的主要属性及作用：1. 符号名 2. 符号的类型 （整型、实型、字符串型等）3. 符号的存储类别（公共、私

16、有）4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）52.存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。 53.静态存储分配：1、基本策略：在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）3、静态存储分配的要求：不允许递归调用，不含有可变数组。fortran程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配54.动态存储分配 ：1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态

17、存储管理技术。2、两种动态存储分配方式：栈式，堆式栈式动态存储分配策略：将整个程序的数据空间设计为一个栈。【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。55.过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；另一部分则是用以管理过程活动的记录信息(连接数据)。56.活动记录（ar）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。构成：1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；5、控制链；6、实参；7、

18、返回地址57.什么是代码优化所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。58.优化原则：等价原则：经过优化后不应改变程序运行的结果。 59.有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小。 60.合算原则：以尽可能低的代价取得较好的优化效果。61.常见的优化技术：(1) 删除多余运算(删除公共子表达式) (2) 代码外提 +删除归纳变量+ (3)强度削弱; (4)变换循环控制条件 (5)合并已知量与复写传播 (6)删除无用赋值62.基本块：程序中只有一个入口和一个出口的一段顺序执行的语句序列，称为程序

19、的一个基本块。64. 遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。65.无环路有向图(dag):如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称dag66.语法分析：按文法的产生式识别输入的符号串是否为一个句子的分析过程。67.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。68.后缀式：种把运算量写在前面，把算符写在后面的表示表达式的方法。 69.直接推导和推导直接推导：令g=(vt,vn,s,p), 若ap, 且,(vtvn)*称a直接推出,表示成a 同时也称是a的直接推导，或称 直接归约到a。推导：如果存在一个直接推导序列：0

20、12 n（n0）表示成0+n，称从0到n的长度为n的推导。0*n,或者0=n或者0+n .70.语言：设文法g（vt，vn，s,p）。如果s*,则称是一个句型。仅含终结符号的句型是一个句子。语言l(g）是由文法g产生的所有句子所组成的集合：l(g)|s*且vt*71.单词符号：由词法规则确定的，具有独立意义的最基本的结构。它一般包括：基本字，标识符，常数，运算符和界符。72. 上下文无关文法：它是这样的一种文法，它所定义的语法范畴（或语法单位）完全独立于这种范畴可能出现的环境之外，不宜描述自然语言。73. ll（k）分析法：第一个l表示从左到右扫描输入串，第二个l表示最左推导，k表示分析时每一

21、步需向前查看k个符号。74. lr（k）分析法：第一个l表示从左到右扫描输入串，第二个r表示最左推导的逆过程（既最右归约），分析时每一步需向前查看k个符号。75. 算符优先分析：所谓算符优先分析就是定义算符之间的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。76.什么是属性文法：它是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”（称为属性）。这些属性代表与文法符号相关的信息。77.有哪些存储分配策略？并叙述何时用何种存储分配策略？静态分配策略：在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。栈式动态分配策略：在运行时把存储器作为一个栈进行管理，每当

22、调用一个过程，所需存储空间就动态地分配于栈顶，一旦退出，所占空间就予以释放。堆式动态分配策略：在运行时把存储器组织成堆结构，凡申请者从堆中分给一块凡释放者退回给堆。78.编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？依据优化所涉及的程序范围，可分为局部优化，循环优化和全局优化三种类型。最常用的代码优化技术有删除公共子表达式、复写传播、删除无用代码、代码外提、强度消弱、删除归纳变量等。79.一个编译程序的代码生成要着重考虑哪些问题？代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个反面来综合考虑。80. 词法分析器的输出结果是词法分析程序

23、的功能是读入源程序，输出单词符号。单词符号是一个程序设计语言的基本语法符号。单词符号一般分为下列五种：关键字 标识符 常数 运算符 界符81. lr项目集规范族的项目类型分为如下4种：移进项目 归约项目 待约项目 接受项目 82. lr项目集规范族的项目合并同心集后可能出现什么问题？(1)同心集合并后心仍相同，超前搜索为原全集（2）合并同心集后，转换函数自动合并（3）若g是lr(1)的文法，合并同心集后，不会有移进，归约冲突，可能会有归约归约冲突（4）合并同心集后，可能推迟发现错误的时间，但错误出现位置正确，错误是归约。83.字母表：符号的非空有穷集合。84.符号：语言中最基本的不可再分的单位

24、。85.符号串：字母表中符号组成的有穷序列。86.句子：字母表上符合某种规则构成的串。87.语言：字母表上句子的集合。88.非终结符：出现在规则的左部，表示一定语法概念的词。89.终结符：语言中不可再分割的字符串，是组成句子的基本单位。90.开始符号：表示所定义的语法范畴的非终结符，又称为识别符号。91.元语言符号：用来说明文法符号之间关系的符号。92.产生式：是用来定义符号串之间关系的一组语法规则。93.推导：从开始符号开始，铜鼓使用产生式的右部取代左部，最终产生语言的一个句子的过程。94.规约：推导的逆过程。95.句型：从文法的开始符号开始，每步推导所得到的字符串。96.状态转换图：使用状

25、态转换图是设计词法分析程序的一种好途径，状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。一个状态转换图可用于识别（或接受）一定的字符串。97. 五元式：有限状态集合、有穷字母表、转换函数、唯一的初始状态、终止状态集合。98.确定的有限自动机（dfa）：一个确定有限自动机（dfa） m是一个五元式：m (s,s0 ,f) ，其中s是一个有限集，它的每个元素称为一个状态，是一个有穷字母表，它的每个元素称为一个输入字符，是一个从s至s的单值部分映射。 (s,a)=s意味着：当现行状态为、输入字符为a时，将转换到下一状态s。我们称s为s的一个后继状s0s是唯一的初态f 是一个终态

26、集（可空）。99.非确定有限自动机（nfa）：一个非确定有限自动机（nfa） m是一个五元式：m (s,s0 ,f) ，其中s是一个有限集，它的每个元素称为一个状态，是一个有穷字母表，它的每个元素称为一个输入字符，是一个从s*至s的子集的映射，即： s* 2s，s0s是唯一的初态，f是一个终态集（可空）。简答题：1.简要说明语义分析的基本功能。答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。2.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如

27、何充分利用指令系统的特点。3.简述编译程序的工作过程。编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；代码优化，以期产生更高效的代码；目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。4编译程序和高级语言有什么区别?用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译

28、），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的对话，随时可以修改高级语言的程序。basic语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表

29、示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。fortran语言就是编译型高级语言。5编译程序的工作分为那几个阶段?词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。6简述自下而上的分析方法。所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。7简述代码优化的目的和意义。代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种

30、等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。8什么是s-属性文法？什么是l-属性文法？它们之间有什么关系？解答：s-属性文法是只含有综合属性的属性文法。 l-属性文法要求对于每个产生式ax1x2xn，其每个语义规则中的每个属性或者是综合属性，或者是xj的一个继承属性，且该属性仅依赖于：(1)产生式xj的左边符号x1,x2xj-1的属性；(2)a的继承属性。 (3)s-属性文法是l-属性文法的特例。 9什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短

31、语。10划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。11运行时的display表的内容是什么？它的作用是什么？答：display表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过display表可以访问其外层过程的变量。12. 目标代码有

32、哪几种形式？生成目标代码时通常应考虑哪几个问题？目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题： (1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。13.简述规范归约的基本思想。用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。14.阐述编译程序各个组成部分主要完成的工作。(1)词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。2）语法分析：在词法分析的基础上，根据语言

33、的语法规则，把单词符号串分解成各类语法单位。（3）语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。（4）优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。（5）目标代码生成：把中间代码变换成特定机器上的低级语言代码。15.什么是编译器的前端和后端，这样划分有何意义？ 编译器粗略分为：词法分析，语法分析，类型检查，中间代码生成，代码优化，目标代码生成，目标代码优化。把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。也就是

34、不论你前端是用fortran还是c/c+,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。16.乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。0型(短语文法，图灵机)：产生式形如： a b 其中：a (vt vn)*且至少含有一个非终结符；b (vt vn)*。1型(上下文有关文法，线性界限自动机)：产生式形如： a b 其中：|a| |b|。仅 se 例外，但此时s不得出现在任何产生式的右部。2型(上下文无关文法，非确定下推自动机)：产生式形如： a b 其中

35、：a vn；b (vt vn)*。3型(正规文法，有限自动机)：产生式形如： a ab 或 a a其中： a vt e；a，bvn产生式形如： a ba 或 a a 其中： a vt e；a，bvn。17.简述编译过程中遍的概念以及遍数的多少对编译器设计的影响。遍的概念：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。遍可以和阶段相应，也可无关。遍中通常含有若干个阶段。实际上，根据语言的不同，编译器可以是一遍（onepass）所有的阶段由一遍完成，其结果是编译得很好，但（通常）代码却不太有效。pascal语言和c语言均允许单遍编译。（modula-2

36、语言的结构则要求编译器至少有两遍）。大多数带有优化的编译器都需要超过一遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第3遍用于代码生成和目标层的优化。更深层的优化则可能需要更多的遍：5遍、6遍、甚至8遍都是可能的。18.编译程序与解释程序有何区别？答：二者的工作方法不同，后者是边解释边执行，解释所得的代码并不保存；前者是先将高级语言翻译感情上标代码，将其保存到指定的空间中，待需要时再执行之，甚至可以在案一个机器上编译，而在另一台机器上执行。19.何谓素短语？答：素短语是满足下述条件的短语：（1）它至少含有一个终结符号（2）满足条件（1）的“最小”短语20.过程调用时

37、，主调程序与被调程序之间的信息传递有哪些方式？答：形式参数与实在参数结合方式传递（简称参数传递）、返回值传递、共享数据区传递。21.何谓语法制导翻译？答：语法制导翻译是对前后文无关文法的扩充，即对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序，完成相应的语义分析和翻译工作。22.何谓算符文法？答：当一个文法的所有产生式的右部均不出现两个非终结符号相邻的情况时，该就被称为算符文法。23.什么是句子？ 什么是语言 ?答：(1)设g是一个给定的文法，s是

38、文法的开始符号，如果s x(其中xvt*),则称x是文法的一个句子。 (2)设gs是给定文法，则由文法g所定义的语言l(g)可描述为： l(g)xs x,xvt* 。24.写一文法，使其语言是偶正整数的集合,要求： (1)允许0打头；(2) 不允许1打头。解：(1)gs=(s,p,d,n,0,1,2,9,p,s) p: s-pd|d p-np|n d-0|2|4|6|8 n-0|1|2|3|4|5|6|7|8|9 (2)gs=(s,p,r,d,n,q ,0,1,2,9,p,s) p: s-pd|p0|d p-nr|n r-qr|q d-2|4|6|8 n-1|2|3|4|5|6|7|8|9 q

39、-0|1|2|3|4|5|6|7|8|925.算符优先分析法和lr（1）分析法每次归约的分别是什么。算法优先分析法每次规约的都是当前句型的最左素短语，lr分析法每次规约的都是句柄26.lr分析器由哪些部分组成？它是怎样工作的？由三部分构成：（1）总控程序，也可以称为驱动程序。对所有的lr分析器总控程序都是相同的。（2）分析表或分析函数。不同的文法分析表将不同，同一个文法采用的lr分析器不同时，分析表也不同，分析表又可分为动作（action）表和状态转换（goto）表两个部分，它们都由二维数组表示。（3）分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。27.语法分析方法分为哪两类？基本

40、思想是什么？遇到的基本问题是什么？目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下的确定分析方法需要对文法有一定的限制，但是由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。而自顶向下的不确定分析方法是带回溯的分析方法，这种方法实际上是一种穷举得试探方法，因此效率低，代价高，因而极少使用。28.常用的三种循环优化技术是?代码外提，删除归纳变量，强度削弱。29.ll（1）文法的条件：1文

41、法不含左递归2）first() first() = 3）对文法中的每个非终结符a，若它存在某个候选首符集包含，则 first（a） follow（a）=。 29.简述lr分析法:1）lr（k）文法是从左到右分析，每次向貌似句柄的符号串后看k个输入符号的一种编译方法30.写出lr(0)分析表的构造步骤:确定g的lr(0)项目以lr(0)项目为状态,构造一个能识别文法g的所有活前缀的nfa利用子集法,将nfa确定化,成为以项目集合为状态的dfa根据利用上述dfa可直接构造出lr分析表。 31. 比较lr(0)、slr（1）、lr（1）、lalr（1）分析表的优缺点:这4种分析表都能识别对应文法的全

42、部句子，其共同特征就是用规范规约的方法寻找句柄进行规约。在这4种方法中，lr（0）分析表对文法的要求较高，其构造方法是其它表构造方法的基础；slr（1）分析表对文法的要求有所降低，容易实现，因而很有实用价值；lr（1）分析表对文法的要求最低，适用于一大类文法，故其分析能力最强，但其实现代价过高；lalr（1）分析表的分析能力介于slr（1）和lr（1）之间，实现代价比lr（1）低。 32.写出产生式、语义规则和语义子程序之间的关系。产生式:一个产生式描述了一个语法单位,但它只说明了该语法单位能产生的符号串,并未指明所产生的符号串有什么实际意义,即该符号串究竟要做什么。语义规则:一个产生式的语义

43、规则描述了该产生式的具体的动作意义,即该产生式产生的符号串要做什么。语义子程序:按照产生式的语义规则生成某种中间代码,实现相应的动作。33为了获得更优化的程序，可以从哪些层次上对程序进行优化？为了获得更优化的程序，可以从各个环节着手：在源代码级，可以选择适当的算法和安排适当的实现语句来提高程序的效率。在语义动作的设计上，考虑产生更高效的中间代码，并为优化阶段做准备。在中间代码级，安排专门的优化阶段，进行各种等价变换，以改进代码的效率。在目标代码级，考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等。 34.常用的优化方法局部优化: 删除公共子表达式、复写传播、删除无用代码。循环优化：代

44、码外提、强度削弱、删除归纳变量35.简述基本块的入口、基本块的划分、流图？答：入口就是其中的第一个语句1.求出四元式程序中的各个基本块中的入口地1)程序的第一个语句2)能由条件转移语句或无条件转移语句转移到的语句3)紧跟在条件转移语句后面的语句。2. 对以上求出的每一入口语句，构造其所属的基本块。它是由该人口语句（开始）到一转移语句(包括该转移语句)，或到一停语句(包括该停语句)之间的语句序列组成的。3. 删除无用代码。凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，我们可把它们从程序中删除。操作系统1解释进程的顺序性和并发性答：目前使用的计算机基本

45、上是冯诺依曼式结构，其基本特点是处理器顺序执行指令。进程在顺序的处理器上的执行是严格按顺序进行的，这就是进程的顺序性，。当一个进程独占处理器顺序执行的时，具有两个特点：（1）封闭性，进程执行的结果只取决于进程本身，不受外界影响（2）可再现性，当进程再次重复执行时，必定获得相同的结果。进程具有并发性。也就是说在一个进程的工作没有全部完成之前，另一个进程就可以开始工作。并发进程相互之间可能是无关的，也可能是有交互的。这些有交互的进程共享某些资源。2.对相关临界区的管理有哪些要求？答：为了使并发进程能正确执行，对若干进程共享某一资源的相关临界区的管理应满足以下三个要求：（1）一次最多让一个进程在临界

46、区中执行，当有进程在临界区中时。其他想进入临界区执行的进程必须等待（2）任何一个进入临界区执行的进程必须在有限的时间内退出临界区，即任何一个进程都不应该无限的逗留在自己的临界区中（3）不能强迫一个进程无限的等待进如它的临界区即有进程退出了临界区时应让下一个等待进入临界区的进程进入他的临界区执行。3什么是线程？多线程技术具有哪些优越性？答：线程是进程中可独立执行的子任务，一个进程可以有一个或者多个线程，每个线程都有一个唯一的标识符。线程与进程有许多相似之处，往往把线程又称为“轻型进程”。线程与进程的根本区别是把进程作为资源分配单位，而线程是调度和执行单位。优越性：（1）创建速度快，系统开销小，创

47、建线程不需要另行分配资源（2）通信简洁，信息传送速度快，线程间的通信在同一地址空间进行，不需要额外的通信机制（3）并行性高，线程能独立执行，能充分利用和发挥处理器与外围设备并行工作的能力。多线程机制是操作系统的发展趋势，他能提高计算机系统的性能。4简述unix系统中管道机制pipe和fifo的区别答：pipe文件是一种在两个进程间传送信息的临时文件，一旦写入pipe文件中的信息被读取后，这个pipe文件就没有必要保存了，它占用的存储空间就可被收回。命名管道fifo适用于不同的用户的进程间的通信。所谓命名管道，实际上是一个冠有文件名的管道文件。命名管道的使用方式与无名管道的使用方式不同。对命名管

48、道的使用就像对普通文件的使用一样，要通过文件操作来使用，首先必须建立文件，读写之前先打开文件，通信结束后要关闭文件。命名管道属于该文件的建立者所有。在建立有名管道文件时可设置访问权限。只有被授权的用户才可按访问权限使用有名管道文件。利用有名管道文件通信时，通信的发送者用只写方式打开，通信的接受着用只读的方式打开。对被打开的有名管道文件，进程可按打开的方式对该文件读或写。在读写的过程中管道机制要对读写操作进行同步控制，以保证信息传输的正确性。通信结束后要关闭该文件，以后需要时可再次打开。5简述信号量s的物理含义答：s0时，s表示可使用的资源数，或表示可使用的资源的进程数。s0时，表示无资源可供使

49、用或表示不允许进程在进入临界区。s0时，|s|表示等待使用资源的进程个数或表示等待进入临界区的进程个数。当s0时，使用p（s）的进程不会等待，调用v（s）后使可用资源数加1或是可用资源的进程数加1.当s0时，调用p（s）的进程必须等待，调用v（s）后将释放一个等待使用资源者或释放一个等待进入临界区者6如果一个生产者和一个消费者他们共享的缓冲区（b）容量为可以存放n件物品，如何使用pv操作来实现他们正确的同步？答：设信息量empty（表示缓冲区中可存放多少件物品）的初值为n，信号量full（表示缓冲区中存有几件物品）的初值为0.但是当缓冲区已经有n件物品时，生产者想在存入一件物品将被拒绝，每存一

50、件物品后，由于调用v（full），故empty的值表示缓冲区中可用的物品数，只要full0，消费者调用p（full）后总可去取物品。每取走一件物品后，由于调用v（empty），便增加了一个可用来存放物品的位置。用指针k和t分别表示生产者往缓冲区村物品和消费者从缓冲区物品的相对位置，他们的初值为0.那么，一个生产者和一个消费者共有容量为n的缓冲区时，可进行如下同步工作：设信号量empty,full，初值为empty=n,full=0，整型变量k,t，初值为k=t=0生产者进程：begin l1:produce a product;p（empty）;bk:=product;k:=（k+1）mod

51、n;v（full）;go to l1;end;消费者进程：begin l2:p（full）take a product from bt; t:=（t+1）mod n; v（empty）;consume;go to l2;end;7进程通信方式有两种，即直接通信和间接通信，给出各自使用的原语形式答：（1）直接通信：这种通信方式是固定在一对进程之间进行。例如，进程a把新建只发送给进程b，而进程b也只接收进程a的信件。那么，“send”和“receive”两条原语的形式如下：send （b,m）把信件m发送给进程b，receive（a,x）接收来自进程a的信件且存入x中，进程a和进程b通过“send

52、”和“receive”操作而自动建立了一种联结（2）间接通信：这种通信方式是以信箱为媒体来实现通信的，只要接收进程的设立一个信箱，那么，若干个进程都可向同一个进程发送信件。利用信箱通信时，“send”和“receive”原语中应给出信箱名，send （n,m）把信件m发送给信件n中，receive（n,x）从信件n中取出一封信存入x中8unix中，消息缓冲机制的作用是什么？答：unix中消息缓冲机制是利用缓冲区来传输消息的。有系统统一管理一组缓冲区，其中每一个缓冲区都可用来放一个消息。当一个进程要发送消息时，首先向系统申请一个缓冲区；然后再把组织好的消息存入缓冲区；接着把村有消息的缓冲区链接到

53、消息队列中。所有这些工作可通过调用消息存入缓冲区；接着把村有消息的缓冲区链接到消息队列中。所有这些工作可通过调用消息缓冲机制所提供的系统调用来完成。接受消息的进程也可通过系统调用从消息队列中取用消息，从缓冲机制取出消息后，就应释放该缓冲区。unix的消息缓冲机制设置了多个消息队列。对不同的类型的消息分别设置不同的消息队列。进程间传送的每一个消息都有一个指定的类型。消息缓冲机制根据发送进程给定的消息类型，从与该类型相关联的消息队列中读出一个消息。于是发送进程和接收进程既可以使用同一消息队列中读出一个消息。于是发送进程和接收进程既可以使用同一消息队列进行通信。9为什么并发进程执行时可能会产生与时间

54、相关的错误？如何避免？答：有交互的并发进程可能会同时使用共享资源，如果对这种情况不加控制，由于进程占用处理器的时间，执行的速度和外界的影响等。就会引起与时间有关的错误。只要使若干并发进程的相关临界区互斥执行，就可避免造成这类错误。10简述文件的组织结构 文件的组织结构是指文件的构造方式。用户和文件系统信信从不同的角度对待同一个文件。（1）文件的逻辑结构：用户按自己对信息的处理要求确定文件的逻辑结构。我们把用户组织的文件称为逻辑文件。逻辑文件有如下两种形式。流式文件：指用户对文件中的信息不再划分可独立的单位，整个文件由依次的一串停止组成；记录式文件：指用户对文件中的信息按逻辑上独立的含义现划分信

55、息单位。每个信息单位称为一个逻辑记录。简称为记录（2）文件的存储结构：文件系统根据存储设备的类型、用户采用的存储方式决定文件在存储介质上的组织方式。目前常用的存储设备有磁盘机和磁带机，他们的组织文件如下：磁带文件的组织：磁带机是一种顺序存取的设备，组织在磁带上的文件都采用顺序结构的；磁盘文件的组织：文件在磁盘上有多种组织方式。常用的有顺序结构、链接结构和索引结构11文件系统能允许用户去关闭一个不是自己打开或建立的文件吗？ 关闭文件操作只有文件的建立者或打开者才有权关闭文件。因此文件文件系统一般不能允许用户去关闭一个不是自己打开或建立的文件。12叙述下列术语;存储介质、卷、块、文件和记录。 存储

56、介质：可用来记录信息的磁带、硬磁盘组、软磁盘片、光盘、卡片等称为存储介质。目前常用的存储介质是磁带机和磁盘机。卷：把存储介质的物理单位定义为“卷.一盘磁带、一张软磁片、一个硬盘组都可以称为一个卷。块：把存储介质上连续信息所组成的一个区域称为“块”。块是存储设备与主存储器之间进行信息交换的物理单位。每次问题把一块或几块信息读入主存储器，或是把主存储器上的信息写到一块或几块中。文件：是指逻辑上具有完整意义的信息集合。记录：是指文件内信息按逻辑上独立的含义划分的信息单位，每个单位称为一个逻辑单位，简称为记录。13文件系统应由哪些部分组成？ 文件系统由以下一些部分组成：（1）文件目录：是实现按名存取的

57、一种手段。目录结构应既能方便文件的检索，又能保证文件系统的安全。（2）文件的组织：用户按信息的使用和处理方式来组织文件。文件系统要从系统效率和方便检索的角度来考虑如何保存文件。通常文件在存储介质上可以有多种组织形式。（3）文件存储空间的管理：对文件的存储空间的分配和空闲情况进行登记和管理。（4）文件操作：是文件系统提供给用户使用文件的一组接口。用户调用文件操作提出对文件的使用要求。（5）文件的安全措施：文件共享既能节省存储空间又可减少传送文件的时间，但文件需要适当的安全保护措施，既要防止有意或无意地破坏文件，又要避免随意的剽窃文件，实现文件的保护和保密。14文件是如何进行分类的？ 文件可以按各种分类方法进行分类，主要有以下几种：（1）按用途分类：可把文件分为系统文件、库文件和用户文件。（2）按保护级别分类：可以把文件分成执行文件、只读文件和读写文件等。（3）按信息流向分类：一般可以分为输入文件、输出文件和输入/输出文件。（4）按存放时限分类，可以分成临时文件