计算机编译原理小抄

《计算机编译原理小抄》由会员分享，可在线阅读，更多相关《计算机编译原理小抄（20页珍藏版）》请在装配图网上搜索。

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-

36、2语言的构造则规定编译器至少有两遍）。大多数带有优化的编译器都需要超过一遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第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

39、Q-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通过“sen

52、d”和“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文献是如何进行分类的？ 文献可以

58、按多种分类措施进行分类，重要有如下几种：（1）按用途分类：可把文献分为系统文献、库文献和顾客文献。（2）按保护级别分类：可以把文献提成执行文献、只读文献和读写文献等。（3）按信息流向分类：一般可以分为输入文献、输出文献和输入/输出文献。（4）按寄存时限分类，可以提成临时文献、永久文献和档案文献。（5）按设备类型分类，可以把文献提成磁盘文献、磁带文献、卡片文献和打印文献等。（6）按文献组织构造分类，可分为逻辑文献、流式文献和记录式文献、物理文献、顺序文献、链接文献和索引文献。15如果顾客规定读一种尚未打开的文献时文献系统如何解决？如果顾客规定读一种尚未打开的文献时，文献系统会报告顾客需要一方面打

59、开文献的信息。有的系统为了以便顾客，提供了一种隐式使用文献的措施，容许顾客不调用“打开文献”、“建立文献”和“关闭文献”操作，而直接调用“读文献”或“写文献”操作。当顾客规定使用一种未被打开或建立的文献时，文献系统先做“打开文献”或“建立文献”的工作，然后再执行“读文献”吉“写文献”的操作。16简述“打开文献”操作的系统解决过程。 当顾客使用一种已经寄存在存储介质上的文献的时候，必须先调开“打开”操作，向系统提出使用一种文献的规定。顾客调用“打开”操作时，也必须向系统提供参数：顾客名、文献名、存取方式、存储设备类型、口令等。文献系统在接到顾客的“打开”规定后，要为顾客做好使用前的准备工作。这些

60、工作重要是：（1）让顾客在指定的存储设备上装存储介质；（2）把存储介质上的文献目录读入主存储器；（3）按文献名检索文献目录，找出该文献的目录项；（4）核对顾客口令，仅当输入口令与目录项中口令一致时才容许打开；（5）核对存储方式与否与建立该文献时规定的存储方式一致；（6）找出文献寄存在存储介质上的起始位置，把她们作为目前位置；（7）对索引文献应把该文献的索引表读入重要存储器，以便后续的读操作能迅速地进行；（8）做上该文献已打开的标志。17如何避免由于系统故障而导致的文献被破坏？ 对于因硬件故障或软件失误而引起的文献被破坏，应常常采用对立副本定期转储的措施来解决。（1）建立副本。副本既可建立在同类

61、型的不同存储介质上，也可建立在不同类型的存储介质上。当系统浮现故障时，应根据系统故障的具体状况来选用副本。操作系统还可以在同一存储介质上对系统文献建立多种副本，万一某个副本上的文献受了侵害，可以其他副本上的文献更换，增强系统文献的安全性。建立副本的措施简朴易行，但系统开销增大，当文献更新时必须要改动所有的副本。因此这种措施合用于容量较小且重要的文献。（2）定期转储。在文献存储过程中，定期地把文献转储到某个存储介质上。当文献发生故障时就用转储的文献来复原。这样可把有故障的文献恢复到某一时刻的状态，仅丢失了自上次转储来新修改或新增长的信息，只要从修复点重新执行就可得到弥补。UNIX系统就采用定期转

62、储来保护文献，提高文献的安全性。18UNIX文献系统有什么特点？ UNIX的文献系统提成基本文献系统和可装卸的子文献系统两部分。 不管基本文献系统还是可装卸子文献系统均有自己独立的目录构造。但上基本文献系统是整个UNIX系统的基本，被称为根文献系统。系统一旦启动运营后，基本文献系统不能脱卸，而子文献系统就可以随便更换。这种构造使得文献系统易于扩大和更改。19UNIX中的系统调用link和unlink起什么作用？系统调用link和unlink的典型应用是容许开发的几种小构成员共享一种文献。每个成员用link使件连接到自己的目录中、任何一种人都可以用自己的途径去访问该文献，且对文献所作出的修改对于

63、其别人都是可见的。这对多人合伙开发来说是以便的，不需要每人去复制一份文献，也不需要去复制更新过的文献，而是直接对同一种文献进行操作。当任何一种成员不需要再访问该文献时，可以用unink删除自己目录中该文献的目录项，不影响其别人对该文献进行操作。如果连接该文献的最后一种目录项被删除，则该文献也被删除。20为什么具有设备独立性的计算机系统，在分派时适应性好、灵活性好？系统只要从指定的设备类中找出一台“好的且未被分派的”设备来进行分派。万一分派给顾客的设备在使用中出了故障，系统可以从同类设备中另找一台“好的且未分派的”设备来替代。21启动磁盘执行一次输入/输出操作耗费的时间由哪几部分构成？ 启动磁盘执行一次又一次输入/输出操作时，先把移动臂移动到指定的柱面，再等待指定的扇区旋转到磁头位置下，然后让指定的磁头进行读/写。完毕信息传送。因此执行一次输入/输出操作所耗费的时间有：寻找时间-磁头在移动臂带动下移到指定的柱面所耗费的时。完毕信息传送的时间。其中传送时间是硬件设计时就已固定了的，而寻找时间和延迟时间是与信息在磁盘上的位置有关。22实现虚拟设备的重要条件是什么? 实现虚拟设备必须要有一定的硬件和软件条件为基本。对于硬件来说，必须配备大容量的磁盘。要有中断装置的通道，具有中央解决器与通道并行工