计算机编译原理_知识点复习考点归纳总结
三一
文库
（https://www.wendangku.net/doc/b519139002.html, ）*电大考试*
编译原理名词解释
1.局部优化：局限于基本块范围的优化称。
2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。
3.DISPLAY 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display 表就是用于登记每个外层过程的最新活动记录起始地址。 5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。
6.语法：一组规则，用它可形成和产生一组合式的程序。
7.文法：描述语言的语法结构的形式规则。
8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。
9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。 10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。
11.待用信息：如果在一个基本块中，四元式i 对A 定值，四元式j 要引用A 值，而从i 到j 之间没有A 的其它定值，则称j 是四元式i 的变量A 的待用信息。 12.规范句型：由规范推导所得到的句型。
13.扫描器：执行词法分析的程序。 14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。 15.句柄：一个句型的最左直接短语。 16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。 17.规范句型：由规范推导所得到的句型。
18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。
19.语法：是组规则，用它可形成和产生一个合式的程序。
20.语义：定义程序的意义的一组规则。 21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。
三种级别：局部优化、循环优化、全局优化
21．词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 22．LL(1)文法
若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足
这两个条件的文法叫做LL(1)文法，其中
的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 23．语法树
句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈
V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 24．LR(0)分析器
所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 25．语言和文法
文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈
V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符
号，且+
∈T V
x }简单的说，文法描述的语言是该文法一切句子的集合。 26．词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 27．LL(1)文法
若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 28．语法树
句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈
V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 29．LR(0)分析器
所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 30．语言和文法
文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈
V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符
号，且+
∈T V
x }简单的说，文法描述的语言是该文法一切句子的集合。 31.编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成
32.解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 33.编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。
34.解释程序和编译程序的根本区别：是否生成目标代码
35.句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。
36文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。
37.LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)第1个L ：从左到右扫描输入串。第2个L ：生成的是最左推导。1 ：向右看1个输入符号便可决定选择哪个产生式 38．某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 39.文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。
40.一个属性文法(attribute grammar)是一个三元组A=(G, V, F)
G ：上下文无关文法。V ：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F ：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。
41.综合属性:若产生式左部的单非终结符A 的属性值由右部各非终结符的属性值决定,则A 的属性称为综合属。
42.继承属性:若产生式右部符号B 的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B 的属性为继承属性。(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时： 综合属性沿属性语法树向上传递（即传递信息的方向是自下而上）；继承属性沿属性语法树向下传递（即传递信息的方向是自上而下）。
43.语法制导翻译：是指在语法分析过程
中，完成附加在所使用的产生式上的语义规则描述的动作。
44.语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。
45.中间代码（中间语言）：1、是复杂性介于源程序语言和机器语言的一种表示形式。2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。
46.何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。
47.为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。(2)便于移植，便于修改，便于进行与机器无关的优化。
48.中间代码的几种形式：逆波兰式（后缀式） ，三地址码（三元式、四元式、间接三元式 ）
49.符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word ）。
50.符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据
51.符号的主要属性及作用：1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区）
52.存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。
53.静态存储分配：1、基本策略：在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）3、静态存储分配的要求：不允许递归调用，不含有可变数组。FORTRAN 程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配
54.动态存储分配 ：1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。2、两种动态存储分配方式：栈式，堆式栈式动态存储分配策略：将整个程序的数据空间设计为一个栈。【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。
55.过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；另一部分则是用以管理过程活动的记录信息(连接数据)。 56.活动记录（AR ）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。构成：1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；5、控制链；6、实参；7、返回地址 57.什么是代码优化
所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。
58.优化原则：等价原则：经过优化后不应改变程序运行的结果。
59.有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
60.合算原则：以尽可能低的代价取得较好的优化效果。
61.常见的优化技术：(1) 删除多余运算(删除公共子表达式) (2) 代码外提
+删除归纳变量+ (3)强度削弱; (4)变换循环控制条件(5)合并已知量与复写传播(6)删除无用赋值
62.基本块：程序中只有一个入口和一个出口的一段顺序执行的语句序列，称为程序的一个基本块。
64. 遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。
65.无环路有向图(DAG):如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG
66.语法分析：按文法的产生式识别输入的符号串是否为一个句子的分析过程。
67.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。
68.后缀式：种把运算量写在前面，把算符写在后面的表示表达式的方法。
69.直接推导和推导
直接推导：令G=(VT,VN,S,P), 若A→γ∈P, 且α,β∈(VT∪VN)*称αAβ直接推
出αγβ,表示成αAβ⇒αγβ同时
也称αγβ是αAβ的直接推导，或称αγβ直接归约到αAβ。推导：如果存在一个直接推导序列：α0⇒α1⇒α
2⇒…⇒αn（n＞0）表示成α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表示分析时每一步需向前查看k
个符号。
74. LR（k）分析法：第一个L表示从左到右扫描输入串，第二个R表示最左推导的逆过程（既最右归约），分析时每一步需向前查看k个符号。
75. 算符优先分析：所谓算符优先分析就是定义算符之间的某种优先关系，借助于这种优先关系寻找“可归约串”和进行归约。
76.什么是属性文法：它是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”（称为属性）。这些属性代表与文法符号相关的信息。
77.有哪些存储分配策略？并叙述何时
用何种存储分配策略？
静态分配策略：在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。栈式动态分配策略：在运行时把存储器作为一个栈进行管理，每当调用一个过程，所需存储空间就动态地分配于栈顶，一旦退出，所占空间就予以释放。堆式动态分配策略：在运行时把存储器组织成堆结构，凡申请者从堆中分给一块凡释放者退回给堆。
78.编译过程中可进行的优化如何分
类？最常用的代码优化技术有哪些？
依据优化所涉及的程序范围，可分为局部优化，循环优化和全局优化三种类型。最常用的代码优化技术有删除公共子表达式、复写传播、删除无用代码、代码外提、强度消弱、删除归纳变量等。79.一个编译程序的代码生成要着重考
虑哪些问题？
代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个反面来综
合考虑。
80. 词法分析器的输出结果是
词法分析程序的功能是读入源程序，输
出单词符号。单词符号是一个程序设计
语言的基本语法符号。单词符号一般分
为下列五种：关键字标识符常数
运算符界符
81. LR项目集规范族的项目类型分为如
下4种：移进项目归约项目待约项
目接受项目
82. LR项目集规范族的项目合并同心集
后可能出现什么问题？
(1)同心集合并后心仍相同，超前搜索为
原全集（2）合并同心集后，转换函数自
动合并（3）若G是LR(1)的文法，合并
同心集后，不会有移进，归约冲突，可
能会有归约归约冲突（4）合并同心集后，
可能推迟发现错误的时间，但错误出现
位置正确，错误是归约。
83.字母表：符号的非空有穷集合。
84.符号：语言中最基本的不可再分的单
位。
85.符号串：字母表中符号组成的有穷序
列。
86.句子：字母表上符合某种规则构成的
串。
87.语言：字母表上句子的集合。
88.非终结符：出现在规则的左部，表示
一定语法概念的词。
89.终结符：语言中不可再分割的字符
串，是组成句子的基本单位。
90.开始符号：表示所定义的语法范畴的
非终结符，又称为识别符号。
91.元语言符号：用来说明文法符号之间
关系的符号。
92.产生式：是用来定义符号串之间关系
的一组语法规则。
93.推导：从开始符号开始，铜鼓使用产
生式的右部取代左部，最终产生语言的
一个句子的过程。
94.规约：推导的逆过程。
95.句型：从文法的开始符号开始，每步
推导所得到的字符串。
96.状态转换图：使用状态转换图是设计
词法分析程序的一种好途径，状态转换
图是一张有限方向图。在状态转换图中，
结点代表状态，用圆圈表示。一个状态
转换图可用于识别（或接受）一定的字
符串。
97. 五元式：有限状态集合、有穷字母
表、转换函数、唯一的初始状态、终止
状态集合。
98.确定的有限自动机（DFA）：一个确定
有限自动机（DFA）M是一个五元式：
M ＝(S,∑,δ,s0 ,F) ，其中S是一个有
限集，它的每个元素称为一个状态，∑
是一个有穷字母表，它的每个元素称为
一个输入字符，δ是一个从S×∑至S
的单值部分映射。δ(s,a)=s´意味着：当
现行状态为、输入字符为a时，将转换
到下一状态s´。我们称s´为s的一个后
继状s0∈S是唯一的初态F 是一个终态
集（可空）。
99.非确定有限自动机（NFA）：一个非确
定有限自动机（NFA）M是一个五元式：
M ＝(S,∑,δ,S0 ,F) ，其中S是一个有
限集，它的每个元素称为一个状态，∑
是一个有穷字母表，它的每个元素称为
一个输入字符，δ是一个从S×∑*至S
的子集的映射，即δ：S×∑* →2s，
S0∈S是唯一的初态，F是一个终态集（可
空）。
简答题：
1.简要说明语义分析的基本功能。
答：语义分析的基本功能包括: 确定类
型、类型检查、语义处理和某些静态语
义检查。
2.目标代码通常采用三种形式：机器语
言，汇编语言，待装配机器语言模块。
应着重考虑的问题：(1)如何使生成的目
标代码较短；(2)如何充分利用寄存器，
以减少访问内存次数；(3)如何充分利用
指令系统的特点。
3.简述编译程序的工作过程。
编译程序的工作过程，是指从输入源程
序开始到输出目标程序为止的整个过
程，是非常复杂的，就其过程而言，一
般可以划分为五个工作阶段：①词法分
析，对构成源程序的字符串进行扫描和
分解，识别出一个个的单词；②语法分
析，根据语言的语法规则，把单词符号
串分解成各类语法单位；③语义分析与
中间代码产生，即对各类语法单位，分
析其汉一并进行初步翻译；④代码优化，
以期产生更高效的代码；⑤目标代码生
成，把中间代码变换成特定机器上的低
级语言指令形式。
4．编译程序和高级语言有什么区别?
用汇编语言或高级语言编写的程序，必
须先送入计算机，经过转换成用机器语
言表示的目标程序（这个过程即编译），
才能由计算机执行。执行转换过程的程
序叫编译程序。汇编程序是指没有编译
过的汇编语言源文件。编译程序转换过
的叫目标程序，也就是机器语言。编译
程序的工作情况有三种：汇编型、解释
型和编译型。汇编型编译程序用来将汇
编语言编写的程序，按照一一对应的关
系，转换成用机器语言表示的程序。解
释型编译程序将高级语言程序的一个语
句，先解释成为一组机器语言的指令，
然后立即执行，执行完了，取下一组语
句解释和执行，如此继续到完成一个程
序止。用解释型编译程序，执行速度很
慢，但可以进行人和计算机的"对话"，
随时可以修改高级语言的程序。BASIC
语言就是解释型高级语言。编译型编译
程序将
级语言编写的程序，一次就会部翻译成
机器语言表示的程序，而且过程进行很
快，
在过程中，不能进行人机对话修改。
FORTRAN语言就是编译型高级语言。
5．编译程序的工作分为那几个阶段?
词法分析、语法分析和语义分析是对源
程序进行的分析(称为编译程序的前端)，
而中间代码生成、代码优化和代码生成
三个阶段合称为对源程序进行综合(称
为编译程序的后端)，它们从源程序的中
间表示建立起和源程序等价的目标程
序。
6．简述自下而上的分析方法。
所谓自下而上分析法就是从输入串开
始，逐步进行“归约”，直至归约到文法
的开始符号；或者说从语法树的末端开
始，步步向上“归约”，直到根节点。
7．简述代码优化的目的和意义。
代码优化是尽量生成“好”的代码的编译
阶段。也就是要对程序代码进行一种等
价变换，在保证变换前后代码执行结果
相同的前提下，尽量使目标程序运行时
所需要的时间短，同时所占用的存储空
间少。
8．什么是S-属性文法？什么是L-属性文
法？它们之间有什么关系？
解答：S-属性文法是只含有综合属性的
属性文法。L-属性文法要求对
于每个产生式A X1X2…Xn，其每个语义
规则中的每个属性或者是综合属性，或
者是Xj的一个继承属性，且该属性仅依
赖于：(1)产生式Xj的左边符号
X1,X2…Xj-1的属性；(2)A的继承属性。
(3)S-属性文法是L-属性文法的特例。
9．什么是句柄？什么是素短语？
一个句型的最左直接短语称为该句型的
句柄。素短语是这样的一个短语，它至
少包含一个终结符并且不包含更小的素
短语。
10．划分程序的基本块时，确定基本块
的入口语句的条件是什么？
解答：（1）程序第一个语句，或（2）能
由条件转移语句或无条件转移语句转移
到的语句，或（3）紧跟在条件转移语句
后面的语句。
11．运行时的DISPLAY表的内容是什
么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当
进入一个过程后，在建立它的活动记录
区的同时建立一张嵌套层次显示表
diaplay.假定现在进入的过程层次为i，则
它的diaplay表含有i+1个单元，自顶向
下每个单元依次存放着现行层、直接外
层、…、直至最外层(主程序，0层)等每
层过程的最新活动记录的起始地址。通
过DISPLAY表可以访问其外层过程的变
量。
12. 目标代码有哪几种形式？生成目标
代码时通常应考虑哪几个问题？
目标代码通常采用三种形式：机器语言，
汇编语言，待装配机器语言模块。应着
重考虑的问题：(1)如何使生成的目标代
码较短；(2)如何充分利用寄存器，以减
少访问内存次数；(3)如何充分利用指令
系统的特点。
13.简述规范归约的基本思想。
用一个寄存符号的先进后出栈，把输入
符号一个一个地移进到栈里，当栈顶形
成某个产生式的候选式时，即把栈顶的
这一部分替换成(归约为)该产生式的左
部符号。
14.阐述编译程序各个组成部分主要完
成的工作。
(1)词法分析的任务:输入源程序，对构成
源程序的字符串进行扫描和分解，识别
出一个个的单词。2）语法分析：在词法
分析的基础上，根据语言的语法规则，
把单词符号串分解成各类语法单位。（3）
语义分析与中间代码产生：对语法分析
所识别出的各类语法范畴，分析其含义，
并进行初步翻译。（4）优化：在于对前
段产生的中间代码进行加工变换，以期
在最后阶段能产生出更为高效的目标代
码。（5）目标代码生成：把中间代码变
换成特定机器上的低级语言代码。
15.什么是编译器的前端和后端，这样划
分有何意义？
编译器粗略分为：词法分析，语法分析，
类型检查，中间代码生成，代码优化，
目标代码生成，目标代码优化。把中间
代码生成及之前阶段划分问编译器的前
端，那么后端与前端是独立的。后端只
需要一种中间代码表示，可以是三地址
代码或四元式等，而这些都与前端生成
的方式无关。也就是不论你前端是用
fortran还是c/c++,只要生成了中间代码
表示就可以了，后端是不管你是用哪种
语言生成的。
16.乔姆斯基把文法分为哪几种类型？
对这几种类型文法作简要说明。
把文法分成四种类型：0，1，2，3型。
与上下文无关文法一样，它们都由四部
分组成，但对产生式的限制有所不同。0
型(短语文法，图灵机)：产生式形如：α
→β其中：∈α (VT ⋃ VN)*且至少含有一
个非终结符；∈β (VT ⋃ VN)*。1型(上下
文有关文法，线性界限自动机)：产生式
形如：α→β其中：|α| ≤ |β|。仅
Sε→例外，但此时S不得出现在任何产
生式的右部。2型(上下文无关文法，非
确定下推自动机)：产生式形如： A →
β其中：A∈ VN；∈β (VT ⋃ VN)*。3型(正
规文法，有限自动机)：产生式形如：A
→ aB 或A → a其中：a∈ VT ⋃ {ε}；A，
B∈VN产生式形如：A → Ba 或A → a
其中：a∈ VT ⋃ {ε}；A，B∈VN。
17.简述编译过程中遍的概念以及遍数
的多少对编译器设计的影响。
遍的概念：对源程序或源程序的中间结
果从头到尾扫描一次，并作有关的加工
处理，生成新的中间结果或目标程序。
遍可以和阶段相应，也可无关。遍中通
常含有若干个阶段。实际上，根据语言
的不同，编译器可以是一遍（onepass）
——所有的阶段由一遍完成，其结果是
编译得很好，但（通常）代码却不太有
效。Pascal语言和C语言均允许单遍编
译。（Modula-2语言的结构则要求编译
器至少有两遍）。大多数带有优化的编译
器都需要超过一遍：典型的安排是将一
遍用于扫描和分析，将另一遍用于语义
分析和源代码层优化，第3遍用于代码生成和目标层的优化。更深层的优化则可能需要更多的遍： 5遍、6遍、甚至8遍都是可能的。
18.编译程序与解释程序有何区别？
答：二者的工作方法不同，后者是边解释边执行，解释所得的代码并不保存；前者是先将高级语言翻译感情上标代码，将其保存到指定的空间中，待需要时再执行之，甚至可以在案一个机器上编译，而在另一台机器上执行。
19.何谓素短语？
答：素短语是满足下述条件的短语：（1）它至少含有一个终结符号（2）满足条件（1）的“最小”短语
20.过程调用时，主调程序与被调程序之间的信息传递有哪些方式？
答：形式参数与实在参数结合方式传递（简称参数传递）、返回值传递、共享数据区传递。
21.何谓语法制导翻译？
答：语法制导翻译是对前后文无关文法的扩充，即对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序，完成相应的语义分析和翻译工作。
22.何谓算符文法？
答：当一个文法的所有产生式的右部均不出现两个非终结符号相邻的情况时，该就被称为算符文法。
23.什么是句子？什么是语言?
答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),
则称x是文法的一个句子。(2)设G[S]
是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。
24.写一文法，使其语言是偶正整数的集合,要求：(1)允许0打头；(2) 不允许1打头。
解：(1)G[S]=({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)G[S]=({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->0|1|2|3|4|5|6|7|8|9
25.算符优先分析法和LR（1）分析法每次归约的分别是什么。
算法优先分析法每次规约的都是当前句型的最左素短语，LR分析法每次规约的都是句柄
26.LR分析器由哪些部分组成？它是怎样工作的？
由三部分构成：（1）总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。（2）分析表或分析函数。不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作（ACTION）表和状态转换（GOTO）表两个部分，它们都由二维数组表示。（3）分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。
27.语法分析方法分为哪两类？基本思
想是什么？遇到的基本问题是什么？
目前语法分析常用的方法有自顶向下分析和自底向上分析两大类。自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下的确定分析方法需要对文法有一定的限制，但是由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因而仍是目前常用
的方法之一。而自顶向下的不确定分析
方法是带回溯的分析方法，这种方法实
际上是一种穷举得试探方法，因此效率
低，代价高，因而极少使用。
28.常用的三种循环优化技术是?
代码外提，删除归纳变量，强度削弱。
29.LL（1）文法的条件：1文法不含左递
归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种分析表都
能识别对应文法的全部句子，其共同特
征就是用规范规约的方法寻找句柄进行
规约。在这4种方法中，LR（0）分析表
对文法的要求较高，其构造方法是其它
表构造方法的基础；SLR（1）分析表对
文法的要求有所降低，容易实现，因而
很有实用价值；LR（1）分析表对文法的
要求最低，适用于一大类文法，故其分
析能力最强，但其实现代价过高；LALR
（1）分析表的分析能力介于SLR（1）
和LR（1）之间，实现代价比LR（1）低。
32.写出产生式、语义规则和语义子程序
之间的关系。
①产生式:一个产生式描述了一个语法
单位,但它只说明了该语法单位能产生
的符号串,并未指明所产生的符号串有
什么实际意义,即该符号串究竟要做什
么。②语义规则:一个产生式的语义规则
描述了该产生式的具体的动作意义,即
该产生式产生的符号串要做什么。③语
义子程序:按照产生式的语义规则生成
某种中间代码,实现相应的动作。
33．为了获得更优化的程序，可以从哪
些层次上对程序进行优化？
为了获得更优化的程序，可以从各个环
节着手：在源代码级，可以选择适当的
算法和安排适当的实现语句来提高程序
的效率。在语义动作的设计上，考虑产
生更高效的中间代码，并为优化阶段做
准备。在中间代码级，安排专门的优化
阶段，进行各种等价变换，以改进代码
的效率。在目标代码级，考虑如何有效
地利用寄存器，如何选择指令，以及进
行窥孔优化等。
34.常用的优化方法
局部优化: 删除公共子表达式、复写传
播、删除无用代码。循环优化：代码外
提、强度削弱、删除归纳变量
35.简述基本块的入口、基本块的划分、
流图？
答：入口就是其中的第一个语句1.求出
四元式程序中的各个基本块中的入口地
1)程序的第一个语句2)能由条件转移语
句或无条件转移语句转移到的语句3)紧
跟在条件转移语句后面的语句。2. 对以
上求出的每一入口语句，构造其所属的
基本块。它是由该人口语句（开始）到
一转移语句(包括该转移语句)，或到一停
语句(包括该停语句)之间的语句序列组
成的。3. 删除无用代码。凡未被纳入某
一基本块中的语句，都是程序中控制流
程无法到达的语句，从而也是不会被执
行到的语句，我们可把它们从程序中删
除。
操作系统
1解释进程的顺序性和并发性
答：目前使用的计算机基本上是冯·诺
依曼式结构，其基本特点是处理器顺序
执行指令。进程在顺序的处理器上的执
行是严格按顺序进行的，这就是进程的
顺序性，。当一个进程独占处理器顺序执
行的时，具有两个特点：（1）封闭性，
进程执行的结果只取决于进程本身，不
受外界影响（2）可再现性，当进程再次
重复执行时，必定获得相同的结果。进
程具有并发性。也就是说在一个进程的
工作没有全部完成之前，另一个进程就
可以开始工作。并发进程相互之间可能
是无关的，也可能是有交互的。这些有
交互的进程共享某些资源。
2.对相关临界区的管理有哪些要求？
答：为了使并发进程能正确执行，对若
干进程共享某一资源的相关临界区的管
理应满足以下三个要求：（1）一次最多
让一个进程在临界区中执行，当有进程
在临界区中时。其他想进入临界区执行
的进程必须等待（2）任何一个进入临界
区执行的进程必须在有限的时间内退出
临界区，即任何一个进程都不应该无限
的逗留在自己的临界区中（3）不能强迫
一个进程无限的等待进如它的临界区即
有进程退出了临界区时应让下一个等待
进入临界区的进程进入他的临界区执
行。
3什么是线程？多线程技术具有哪些优
越性？
答：线程是进程中可独立执行的子任务，
一个进程可以有一个或者多个线程，每
个线程都有一个唯一的标识符。线程与
进程有许多相似之处，往往把线程又称
为“轻型进程”。线程与进程的根本区别
是把进程作为资源分配单位，而线程是
调度和执行单位。优越性：（1）创建速
度快，系统开销小，创建线程不需要另
行分配资源（2）通信简洁，信息传送速
度快，线程间的通信在同一地址空间进
行，不需要额外的通信机制（3）并行性
高，线程能独立执行，能充分利用和发
挥处理器与外围设备并行工作的能力。
多线程机制是操作系统的发展趋势，他
能提高计算机系统的性能。
4简述UNIX系统中管道机制pipe和FIFO
的区别
答：pipe文件是一种在两个进程间传送
信息的临时文件，一旦写入pipe文件中
的信息被读取后，这个pipe文件就没有
必要保存了，它占用的存储空间就可被
收回。命名管道FIFO适用于不同的用户
的进程间的通信。所谓命名管道，实际
上是一个冠有文件名的管道文件。命名
管道的使用方式与无名管道的使用方式
不同。对命名管道的使用就像对普通文
件的使用一样，要通过文件操作来使用，
首先必须建立文件，读写之前先打开文
件，通信结束后要关闭文件。命名管道
属于该文件的建立者所有。在建立有名
管道文件时可设置访问权限。只有被授
权的用户才可按访问权限使用有名管道
文件。利用有名管道文件通信时，通信
的发送者用只写方式打开，通信的接受
着用只读的方式打开。对被打开的有名
管道文件，进程可按打开的方式对该文
件读或写。在读写的过程中管道机制要
对读写操作进行同步控制，以保证信息
传输的正确性。通信结束后要关闭该文
件，以后需要时可再次打开。
5简述信号量S的物理含义
答：S＞0时，S表示可使用的资源数，
或表示可使用的资源的进程数。S＝0时，
表示无资源可供使用或表示不允许进程
在进入临界区。S＜0时，|S|表示等待使
用资源的进程个数或表示等待进入临界
区的进程个数。当S＞0时，使用P（S）
的进程不会等待，调用V（S）后使可用
资源数加1或是可用资源的进程数加1.
当S≤0时，调用P（S）的进程必须等
待，调用V（S）后将释放一个等待使用
资源者或释放一个等待进入临界区者
6如果一个生产者和一个消费者他们共
享的缓冲区（B）容量为可以存放N件
物品，如何使用PV操作来实现他们正
确的同步？
答：设信息量empty（表示缓冲区中可
存放多少件物品）的初值为n，信号量
full（表示缓冲区中存有几件物品）的初
值为0.但是当缓冲区已经有n件物品时，
生产者想在存入一件物品将被拒绝，每
存一件物品后，由于调用V（full），故
empty的值表示缓冲区中可用的物品
数，只要full＞0，消费者调用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）;B[k]:=product;k:=（k+1）mod
n;V（full）;go to L1;end;消费者进程：begin
L2:P（full）take a product from B[t]; 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”和
“receive”操作而自动建立了一种联结
（2）间接通信：这种通信方式是以信箱
为媒体来实现通信的，只要接收进程的
设立一个信箱，那么，若干个进程都可
向同一个进程发送信件。利用信箱通信
时，“send”和“receive”原语中应给出
信箱名，send （N,M）把信件M发送给
信件N中，receive（N,X）从信件N中取
出一封信存入X中
8UNIX中，消息缓冲机制的作用是什
么？
答：UNIX中消息缓冲机制是利用缓冲区
来传输消息的。有系统统一管理一组缓
冲区，其中每一个缓冲区都可用来放一
个消息。当一个进程要发送消息时，首
先向系统申请一个缓冲区；然后再把组
织好的消息存入缓冲区；接着把村有消
息的缓冲区链接到消息队列中。所有这
些工作可通过调用消息存入缓冲区；接
着把村有消息的缓冲区链接到消息队列
中。所有这些工作可通过调用消息缓冲
机制所提供的系统调用来完成。接受消
息的进程也可通过系统调用从消息队列
中取用消息，从缓冲机制取出消息后，
就应释放该缓冲区。UNIX的消息缓冲机
制设置了多个消息队列。对不同的类型
的消息分别设置不同的消息队列。进程
间传送的每一个消息都有一个指定的类
型。消息缓冲机制根据发送进程给定的
消息类型，从与该类型相关联的消息队
列中读出一个消息。于是发送进程和接
收进程既可以使用同一消息队列中读出
一个消息。于是发送进程和接收进程既
可以使用同一消息队列进行通信。
9为什么并发进程执行时可能会产生与
时间相关的错误？如何避免？
答：有交互的并发进程可能会同时使用
共享资源，如果对这种情况不加控制，
由于进程占用处理器的时间，执行的速
度和外界的影响等。就会引起与时间有
关的错误。只要使若干并发进程的相关
临界区互斥执行，就可避免造成这类错
误。
10简述文件的组织结构
文件的组织结构是指文件的构造方
式。用户和文件系统信信从不同的角度
对待同一个文件。（1）文件的逻辑结构：用户按自己对信息的处理要求确定文件的逻辑结构。我们把用户组织的文件称为逻辑文件。逻辑文件有如下两种形式。
①流式文件：指用户对文件中的信息不再划分可独立的单位，整个文件由依次的一串停止组成；②记录式文件：指用户对文件中的信息按逻辑上独立的含义现划分信息单位。每个信息单位称为一个逻辑记录。简称为记录（2）文件的存储结构：文件系统根据存储设备的类型、用户采用的存储方式决定文件在存储介质上的组织方式。目前常用的存储设备有磁盘机和磁带机，他们的组织文件如下：①磁带文件的组织：磁带机是一种顺序存取的设备，组织在磁带上的文件都采用顺序结构的；②磁盘文件的组织：文件在磁盘上有多种组织方式。常用的有顺序结构、链接结构和索引结构
11文件系统能允许用户去关闭一个不
是自己打开或建立的文件吗？
关闭文件操作只有文件的建立者或打开者才有权关闭文件。因此文件文件系统一般不能允许用户去关闭一个不是自己打开或建立的文件。
12叙述下列术语;存储介质、卷、块、文件和记录。
存储介质：可用来记录信息的磁带、硬磁盘组、软磁盘片、光盘、卡片等称为存储介质。目前常用的存储介质是磁带机和磁盘机。卷：把存储介质的物理单位定义为“卷’.一盘磁带、一张软磁片、一个硬盘组都可以称为一个卷。块：把存储介质上连续信息所组成的一个区域称为“块”。块是存储设备与主存储器之间进行信息交换的物理单位。每次问题把一块或几块信息读入主存储器，或是把主存储器上的信息写到一块或几块中。文件：是指逻辑上具有完整意义的信息集合。记录：是指文件内信息按逻辑上独立的含义划分的信息单位，每个单位称为一个逻辑单位，简称为记录。13文件系统应由哪些部分组成？
文件系统由以下一些部分组成：（1）文件目录：是实现按名存取的一种手段。目录结构应既能方便文件的检索，又能保证文件系统的安全。（2）文件的组织：用户按信息的使用和处理方式来组织文件。文件系统要从系统效率和方便检索的角度来考虑如何保存文件。通常文件在存储介质上可以有多种组织形式。（3）文件存储空间的管理：对文件的存储空间的分配和空闲情况进行登记和管理。（4）文件操作：是文件系统提供给用户使用文件的一组接口。用户调用文件操作提出对文件的使用要求。（5）文件的安全措施：文件共享既能节省存储空间又可减少传送文件的时间，但文件需要适当的安全保护措施，既要防止有意或无意地破坏文件，又要避免随意的剽窃文件，实现文件的保护和保密。
14文件是如何进行分类的？
文件可以按各种分类方法进行分类，主要有以下几种：（1）按用途分类：可把文件分为系统文件、库文件和用户文件。（2）按保护级别分类：可以把文件分成执行文件、只读文件和读写文件等。（3）按信息流向分类：一般可以分为输入文件、输出文件和输入/输出文件。（4）按存放时限分类，可以分成临时文件、永久文件和档案文件。（5）按设备类型分类，可以把文件分成磁盘文件、磁带文件、卡片文件和打印文件等。（6）按文件组织结构分类，可分为逻辑文件、流式文件和记录式文件、物理文件、顺序文件、链接文件和索引文件。
15如果用户要求读一个尚未打开的文
件时文件系统怎样处理？
如果用户要求读一个尚未打开的文件时，文件系统会报告用户需要首先打开文件的信息。有的系统为了方便用户，提供了一种隐式使用文件的方法，允许用户不调用“打开文件”、“建立文件”和“关闭文件”操作，而直接调用“读文件”或“写文件”操作。当用户要求
使用一个未被打开或建立的文件时，文
件系统先做“打开文件”或“建立文件”
的工作，然后再执行“读文件”吉“写
文件”的操作。
16简述“打开文件”操作的系统处理过
程。
当用户使用一个已经存放在存储介质
上的文件的时候，必须先调开“打开”
操作，向系统提出使用一个文件的要求。
用户调用“打开”操作时，也必须向系
统提供参数：用户名、文件名、存取方
式、存储设备类型、口令等。文件系统
在接到用户的“打开”要求后，要为用
户做好使用前的准备工作。这些工作主
要是：（1）让用户在指定的存储设备上
装存储介质；（2）把存储介质上的文件
目录读入主存储器；（3）按文件名检索
文件目录，找出该文件的目录项；（4）
核对用户口令，仅当输入口令与目录项
中口令一致时才允许打开；（5）核对存
储方式是否与建立该文件时规定的存储
方式一致；（6）找出文件存放在存储介
质上的起始位置，把他们作为当前位置；
（7）对索引文件应把该文件的索引表读
入主要存储器，以便后续的读操作能快
速地进行；（8）做上该文件已打开的标
志。
17怎样防止由于系统故障而造成的文
件被破坏？
对于因硬件故障或软件失误而引起的
文件被破坏，应经常采用对立副本定时
转储的办法来解决。（1）建立副本。副
本既可建立在同类型的不同存储介质
上，也可建立在不同类型的存储介质上。
当系统出现故障时，应根据系统故障的
具体情况来选取副本。操作系统还可以
在同一存储介质上对系统文件建立多个
副本，万一某个副本上的文件受了侵害，
可以其它副本上的文件更换，增强系统
文件的安全性。建立副本的方法简单易
行，但系统开销增大，当文件更新时必
须要改动所有的副本。因此这种方法适
用于容量较小且重要的文件。（2）定时
转储。在文件存储过程中，定时地把文
件转储到某个存储介质上。当文件发生
故障时就用转储的文件来复原。这样可
把有故障的文件恢复到某一时刻的状
态，仅丢失了自上次转储来新修改或新
增加的信息，只要从修复点重新执行就
可得到弥补。UNIX系统就采用定时转储
来保护文件，提高文件的安全性。
18UNIX文件系统有什么特点？
UNIX的文件系统分成基本文件系统
和可装卸的子文件系统两部分。不论基
本文件系统还是可装卸子文件系统都有
自己独立的目录结构。但上基本文件系
统是整个UNIX系统的基础，被称为根文
件系统。系统一旦启动运行后，基本文
件系统不能脱卸，而子文件系统就可以
随便更换。这种结构使得文件系统易于
扩充和更改。
19UNIX中的系统调用link和unlink起什
么作用？
系统调用link和unlink的典型应用是允
许开发的几个小组成员共享一个文件。
每个成员用link使件连接到自己的目录
中、任何一个人都可以用自己的路径去
访问该文件，且对文件所作出的修改对
于其它人都是可见的。这对多人合作开
发来说是方便的，不需要每人去复制一
份文件，也不需要去复制更新过的文件，
而是直接对同一个文件进行操作。当任
何一个成员不需要再访问该文件时，可
以用unink删除自己目录中该文件的目
录项，不影响其它人对该文件进行操作。
如果连接该文件的最后一个目录项被删
除，则该文件也被删除。
20为什么具有设备独立性的计算机系
统，在分配时适应性好、灵活性好？
系统只要从指定的设备类中找出一台
“好的且未被分配的”设备来进行分配。
万一分配给用户的设备在使用中出了故
障，系统可以从同类设备中另找一台“好
的且未分配的”设备来替换。
21启动磁盘执行一次输入/输出操作花
费的时间由哪几部分组成？
启动磁盘执行一次又一次输入/输出
操作时，先把移动臂移动到指定的柱面，
再等待指定的扇区旋转到磁头位置下，
然后让指定的磁头进行读/写。完成信息
传送。因此执行一次输入/输出操作所花
费的时间有：寻找时间---磁头在移动臂
带动下移到指定的柱面所花费的时。完
成信息传送的时间。其中传送时间是硬
件设计时就已固定了的，而寻找时间和
延迟时间是与信息在磁盘上的位置有
关。
22实现虚拟设备的主要条件是什么?
实现虚拟设备必须要有一定的硬件和
软件条件为基础。对于硬件来说，必须
配置大容量的磁盘。要有中断装置的通
道，具有中央处理器与通道并行工作的
能力。对于操作系统来说，应采用多道
程序设计技术。
23比较多种磁盘移臂算法
调度算法调度方式性能特点
先来先服
务
按访问者
提出访问
请求的先
后顺序进
行调度
寻找时间
长、输入/
输出操作
总时间长
最短寻找
时间优先
首先调度
寻找时间
最短的访
问请求者
系统效率
高
电梯调度优先调度
距离当前
移动臂最
近的访问
者
简单、实
用、高效
单向扫描总是从0柱
面开始扫
描，优先满
足其移动
方向上的
最近访问
者请求
系统效率
较高，适用
于大量存
取请求
24中央处理器与通道之间是怎样配合
工作的/
I/O中断是中央处理器和通道协调工
作的一种手段。通道借助I/O中断请求
中央处理器进行干预，中央处理器根据
产生的I/O中断处理事件了解输入/输
出操作的执行情况。（1）当通道状态中
有通道结束，控制器结束和设备结束时，
表达已完成了通道程序所规定的所有操
作，通道就形成输入/输出操作正常结束
的中断事件。此时，操作系统将使有关
进程从等待状态变成就绪状态。（2）当
通道发现有设备故障时就形成操作异常
结束的I/O中断事件。如果是设备故障，
系统将组织通道程序复执，或产生有关
信息由维护人员排除故障；如果是设备
特殊，系统将根据情况来分别处理，
25解释通道命令通道程序、通道地址字
和通道状态字。
通道命令：通道命令规定设备的操作，
每一种通道命令规定了设备的一种操
作，通道命令一般由命令码、数据主存
地址、传送字节个数及标志码等部分组
成。通道程序：操作系统可以由若干条
通道命令规定通道执行一次输入/输出
操作应做的工作。这若干条通道命令就
组成了一个通道程序。通道地址字：即
Channel ddress Word，缩写为CAW。在
具有通道的计算机系统中，用来存放通
道程序首地址的主存固定单元称为通道
地址字。通道状态字：即Channel Status
Word，缩写为CSW。当通道程序执行结
束时，被记录的执行情况卢要存放到一
个固定的主存单元中。这个单元称为通
道状态字。
26SPOOLING系统由哪些部分组成？各
部分的功能是什么？
SPOOLING系统即斯普林系统，主要由
以下三部分组成：（1）预输入程序：负
责把一批组织在一起的作业流中的每一
个作业的初始信息传递到“输入井”保
存以备作业执行时使用。（2）井管理程
序“包括井管理读程序和井管理写程序
两个功能。井管理读程序负责从输入机
上读取文件信息供用户使用；井管理写
程序负责把作业执行产生的结果保存到
输出井中。（3）缓输出程序：负责查看
输出井中是否有待输出的结果信息。若
有，则启动打印机把作业的结果文件打
印输出。
27SPOOLING系统为什么能提高独占设
备的利用率？
SPOOLING系统借助天硬件的中断装置和
通道技术，使得中央处理器与各种外围
设备以及外围设备之间均可并行工作。
操作系统采用多道程序设计技术，合理
分配处理器，实现联机的外围设备同时
操作。作业执行时，从磁盘上读写信息
代替从输入机和打印机的读写操作，不
仅使多个作业可以同时执行，而且加快
了作业的执行速度，提高了单位时间内
处理作业的能力。在作业执行的同时还
可以利用输入机继续预输入作业信息和
利用打印机输出结果。于是整个系统可
以是：第一批作业的执行结果正在输出，
第二批作业正在处理，第三批作业信息
正在预输入到磁盘的输入井中。这种联
机同时操作极大的提高了独占设备的利
用率，也使计算机的各种资源被充分利
用。
28比较电梯调度算法和最短寻找时间
优先调度算法的异同点。
电梯调度算法和最短寻找时间优先算
法都是要尽量减少移动臂移动时所花的
时间，不同的是：最短寻找时间优先调
度算法不考虑臂的移动方向，总是优先
选择离当前位置最近的那个柱面的访问
者，这种选择可能导致移动臂来回改变
移动方向；电梯调度算法是沼着臂的移
动方向去选择，仅当沼臂移动方向无等
待访问者时才改变臂的移动方向。由于
移动臂改变方向是机械运动，所以速度
相对较慢。相比之下，电梯调度算法是
一种简单实用且高效的调度算法。但在
实现时，除了要记住读写磁头的当前位
置外，还必须记住移动臂的移动方向。
29设备通常分为哪两类？
独占设备：在一段时间内只能一个进
程占有并使用它，不允许多个进程同时
使用，如打印机、磁带机等设备，对这
类备通常采用静态分配方式。（2）共享
设备：允许多个进程共享使用，这种可
让若干个作业同时使用的设备称为可共
享设备，如对磁盘的使用。
30什么是设备的绝对号和相对号？
计算机系统对每一台设备都要进行登
记，且为每一台设备确定一个编号，以
便区分和识别，这个确定的编号称为设
备的绝对号。由用户对自己需要使用的
若干台同类设备给出的编号称为设备的
相对号。
31什么是缓冲技术？采用缓冲技术的
优点是什么？
在操作系统中，把利用缓冲区来缓解
处理与外围设备之间工作速度不匹配的
矛盾而采用的技术称为缓冲技术。采用
缓冲技术即能协调逻辑记录大小与物理
块大小不一致的问题，又能缓解处理器
与外围设备之间速度不匹配的矛盾。所
以在现代计算机系统中，常常在主存储
器中辟出一些专用区域作为缓冲区，支
持输入/输出设备。
32简述虚拟设备的实现原理、
把地批作业的全部信息通过输入设备
预先传送到磁盘上等待处理。在多道程
序设计系统中，可从磁盘上选择若干个
作业同时装入主存储器，并让它们同时
执行。由于作业的信息已全在磁盘上，
故作业执行时不需要再启动输入机读信
息，而可以从共享的磁盘上读取各自的
信息。把作业产生的结果也存放在磁盘
编译原理知识点汇集
第1章： 1、名词：解释器/解释程序 interpreter；编译器/编译程序 compiler；翻译器/翻译程序translator。三者的区别与联系。虚拟机（如JAVA虚拟机JVM、Tiny语言虚拟机）是哪种程序？ （1）解释器（也称为解析程序）则是只在执行程序时,才一条一条的解释成机器语言给计算机来执行,所以运行速度是不如编译后的程序运行的快的. （2）编译器（也称为编译程序）是把源程序的每一条语句都编译成机器语言,并保存成二进制文件,这样运行时计算机可以直接以机器语言来运行此程序,速度很快; （3）翻译器（也称为翻译程序）是一种系统程序，它将计算机编程语言编写的程序翻译成另外一种计算机语言的一般来说等价的程序，主要包括编译程序和解释程序，汇编程序也被认为是翻译程序。程序的最初形式称为源程序或者源代码，翻译后的形式被称为目标程序或者目标代码。大多数翻译程序是将高级语言编写的程序翻译为机器语言形式的可执行程序。但是也有些翻译程序将源程序翻译成其他高级语言或者字节码等中间形式。 （4）解释器翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立的目标程序。 解释器是另外种形式的语言处理器，它相当于不生成上面的目标程序，直接将输入“放到”源程序中，然后经过解释器，就得到了输出。通常情况下，编译过程比解释过程更快，但解释器能够有更好的错误诊断，因为解释器是逐句进行解释的。编.0译器和解释器可以结合起来进行处理，Java语言处理器就是其中的代表，其过程是源程序经过翻译器处理后得到中间程序，也被称作字节码（bytecode），然后和输入共同加入到虚拟机（virtual machine）的前端，得到输出，其前一部分用到编译器，后一部分用到解释器，这样做的好处是一个机器解释的代码可以应用在另外的机器上，甚至可以延伸到网络上。 2、编译过程图示 P5 图1-1 第3章： 1、Chomsky语言文法分类，程序语言的语法是哪一类，词法是哪一类，其产生式有什么特点。（教材3.6.3，但归纳得不好，参看课件） 下面4种文法构成的语言类成为乔姆斯基层次（Chomskyhierarchy）
编译原理考试重点整理
第一章 1.编译程序：能够把某一种语言程序转换成另一种语言程序，而后者与前者在逻辑上是等 价的一种程序。通常是从高级语言转换成为低级语言。 2.解释程序：它以该语言写的源程序作为输入，但是不产生目标代码，而是边解释边执行 源程序本身。 3.诊断编译程序：专门用于帮助程序开发和调试的编译程序。 4.优化编译程序：着重于提高目标代码效率的编译程序。 5.宿主机：运行编译程序的计算机。 6.目标机：运行编译程序所产生目标代码的计算机。 7.交叉编译程序：一个程序产生不同于宿主机的机器代码的程序。 8.可变目标编译程序：如果不需要重新编译程序中与机器无关的部分就能改变目标机，则 该编译程序就叫做可变目标编译程序。 PS：世界上第一个编译程序——FORTRAN编译程序——20世纪50年代 9.编译过程 ●第一阶段：词法分析——词法分析器 1）任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），标示符，常熟，算符和界符。 2）单词符号是语言的基本组成成分，是人们理解和编程的基本要素。 3）描述词法规则的有效工具是：正规式和有限自动机 ●第二阶段：语法分析——（词法）分析器 1）任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位，如“短语”、“子句”、“句子”、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。 2）语法分析所依据的是语言的语法规则。通常是上下文无关文法描述、 3）词法分析是一种线性分析，而语法分析是一种层次结构分析。 ●第三阶段：语义分析和中间代码产生——语义分析器 1）任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 2）对每种语法范畴进行静态语义检查—>进行中间代码的翻译。 3）语义分析所依据的是语言的语义规则，通常使用属性文法描述语义规则。 4）中间代码：一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。 5）中间代码的四元式表示形式。此外还有三元式、间接三元式、逆波兰记号和树。 ●第四阶段：优化——优化器 1）任务：在于前段产生的中间代码进行加工交换，，以期在最后阶段能产生更为高效（省时间和空间）的目标代码。 2）优化的主要方面有：公共字表达式、优化循环、删除无用代码等等。 3）优化所依据的原则：程序的等价变化原则。 ●第五阶段：目标代码生成——目标代码生成器 1）任务：吧中间代码（或经优化处理后）变换成特定机器上的低级语言代码。 2）形式：绝对指令代码或可重定位的指令代码或汇编指令代码。 10.编译程序的结构
编译原理全复习(完整版)
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？ 答 编译程序总框架 （1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。 （2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 （3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 （4）优化器，对中间代码进行优化处理。 （5）目标代码生成器，把中间代码翻译成目标程序。 （6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。 （7）出错管理，把错误信息报告给用户。 编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。 （2）。语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。 （3）语义分析与中间代码产生。任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 （4）优化。任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。 （5）目标代码生成。任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。 2》．重要概念： a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。 b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等 c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。 d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
编译原理复习汇总
复习汇总 一、第一章概述 1.文法与自动机的等价 1)0型文法—图灵机 2)1型文法—线性有界非确定图灵机 3)2型文法—非确定下推自动机 4)3型文法—有限状态自动机 2.编译技术的应用 1)语法制导的结构化编辑器 2)程序格式化工具 3)软件测试工具 4)程序理解工具 5)高级语言的翻译工具 6)等等 3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解） 1)面向机器的语言：机器指令，汇编语言 2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述 语言（正规式,产生式）等等。 4.各语言的分类（结合第二章第9小点理解） 1)过程式语言，面向对象语言：通用程序设计语言。 2)函数语言：面向特点领域的，递归特性。例如LISP语言 3)说明性，非算法式语言：LEX/YACC,SQL。 4)脚本式语言：Shell语言 5.语言之间的转换（李静PPT41） 1)高级语言之间的转换一般称为预处理或转换。 2)高级语言翻译成汇编语言或机器语言称之为编译。 3)把汇编语言翻译成机器语言称之为汇编。 4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之
为交叉汇编。 5)把机器语言翻译成汇编语言称之为反汇编。 6)把汇编语言翻译成高级语言称之为反编译。 6.编译器和解释器 1)编译器 ●源程序的翻译和翻译后的程序的运行是两个不同的阶段。 ◆编译阶段：用户输入源程序，经过编译器的处理，生成目标 程序。 ◆目标程序的运行阶段：根据要求输入数据，得出结果。 2)解释器（凡是可以采用编译器的地方均可以采用解释器） ●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执 行它。这种方式称为解释。 7.解释器的优点（对比与编译器） 1)具有较好的动态特性。 2)具有较好的移植特性。 8.解释器的缺点（对比于编译器） 1)相比于编译器需花费大量的时间。 2)占用更多的内存空间。 9.编译器的工作阶段（结合第二章6小点红色部分理解） 1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器-> 代码优化器->目标代码生成器->目标代码 2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。10.编译器各阶段的工作过程（结合第二章6小点红色部分理解） 1)源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语 法树，然后根据语法树来进行适当的语义处理，语义分析产生符号 表和中间代码。 2)符号表的格式：标识符，类型，分配的地址。 3)中间代码的格式：操作符，左操作数，右操作数，结果。 4)中间代码的优化：传值的代码可以省略。
编译原理考试知识点复习
第一章： 编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成， 代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执 行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑 上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 第三章： Chomsky 对文法中的规则施加不同限制，将文法和语言分为四大类： ） 0型文法（PSG ） 0型语言或短语结构语言 文法 Ｇ的每个产生式α→β中：若α∈Ｖ*ＶN Ｖ*, β∈(ＶN ∪ＶT)* ， 则 Ｇ是0型文法，即短语结构文法。 1型文法（CSG ） 1型语言或上下文有关语言 在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外， 则Ｇ是１型文法,即：上下文有关文法 另一种定义： 文法G 的每一个产生式具有下列形式：αA δ→αβδ，其中α、δ∈V*，A ∈VN ，β∈V+； ( 2型文法（CFG ） 2型语言或上下文无关语言 文法Ｇ的每个产生式A →α，若A ∈ＶN ,α∈(ＶN ∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。 3型文法（RG ） 3型语言或正则(正规)语言 若Ａ、Ｂ∈ＶN ，ａ∈ＶT 或 ， ' 右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ 左线性文法：若产生式为 Ａ→Ｂａ或Ａ→ａ 都是３型文法（即：正规文法） 最左（最右）推导 在推导的任何一步α β，其中α、β是句型，都是对α中的最左（右）非终结符 进行替换 规范推导：即最右推导。 规范句型：由规范推导所得的句型。 } 句子的二义性（这里的二义性是指语法结构上的。） 文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 短语 若S * αA δ且 A +β，则称β是句型αβδ相对于非终结符A 的短语。 简单短语（直接短语） 2型文法 1型文法 0型文法 3型文
计算机编译原理_知识点复习考点归纳总结
三一 文库 （https://www.wendangku.net/doc/b519139002.html, ）*电大考试* 编译原理名词解释 1.局部优化：局限于基本块范围的优化称。 2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。 3.DISPLAY 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display 表就是用于登记每个外层过程的最新活动记录起始地址。 5.最左推导：任何一步α=>β都是对α中的最右非终结符替换。 6.语法：一组规则，用它可形成和产生一组合式的程序。 7.文法：描述语言的语法结构的形式规则。 8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。 9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。 10.短语：令G 是一个文法，S 划文法的开始符号，假定αβδ是文法G 的一个句型，如果有S αAδ且A β，则称β是句型αβδ相对非终结符A 的短语。 11.待用信息：如果在一个基本块中，四元式i 对A 定值，四元式j 要引用A 值，而从i 到j 之间没有A 的其它定值，则称j 是四元式i 的变量A 的待用信息。 12.规范句型：由规范推导所得到的句型。 13.扫描器：执行词法分析的程序。 14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。 15.句柄：一个句型的最左直接短语。 16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。 17.规范句型：由规范推导所得到的句型。 18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。 19.语法：是组规则，用它可形成和产生一个合式的程序。 20.语义：定义程序的意义的一组规则。 21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化 21．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 22．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足 这两个条件的文法叫做LL(1)文法，其中 的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 23．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈ V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 24．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 25．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 26．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。 27．LL(1)文法 若文法的任何两个产生式A → α | β都满足下面两个条件：（1）FIRST(α ) ⋂ FIRST(β ) = φ；（2）若β ⇒* ε ，那么FIRST(α ) ⋂ FOLLOW( A ) = φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。 28．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈ V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。 29．LR(0)分析器 所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。 30．语言和文法 文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =∅，S ∈ V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即L(G)={x| S ⇒*x ，其中S 为文法开始符 号，且+ ∈T V x }简单的说，文法描述的语言是该文法一切句子的集合。 31.编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 32.解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 33.编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 34.解释程序和编译程序的根本区别：是否生成目标代码 35.句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 36文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 37.LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归)第1个L ：从左到右扫描输入串。第2个L ：生成的是最左推导。1 ：向右看1个输入符号便可决定选择哪个产生式 38．某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 39.文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 40.一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G ：上下文无关文法。V ：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。F ：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 41.综合属性:若产生式左部的单非终结符A 的属性值由右部各非终结符的属性值决定,则A 的属性称为综合属。 42.继承属性:若产生式右部符号B 的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B 的属性为继承属性。(1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。(2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。在计算时： 综合属性沿属性语法树向上传递（即传递信息的方向是自下而上）；继承属性沿属性语法树向下传递（即传递信息的方向是自上而下）。 43.语法制导翻译：是指在语法分析过程 中，完成附加在所使用的产生式上的语义规则描述的动作。 44.语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 45.中间代码（中间语言）：1、是复杂性介于源程序语言和机器语言的一种表示形式。2、一般，快速编译程序直接生成目标代码。3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 46.何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 47.为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。(2)便于移植，便于修改，便于进行与机器无关的优化。 48.中间代码的几种形式：逆波兰式（后缀式） ，三地址码（三元式、四元式、间接三元式 ） 49.符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word ）。 50.符号表的功能：（1）收集符号属性 (2) 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据 51.符号的主要属性及作用：1. 符号名 2. 符号的类型 （整型、实型、字符串型等））3. 符号的存储类别（公共、私有）4. 符号的作用域及可视性 （全局、局部） 5. 符号变量的存储分配信息 （静态存储区、动态存储区） 52.存储分配方案策略：静态存储分配；动态存储分配：栈式、 堆式。 53.静态存储分配：1、基本策略：在编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。2、适用的分配对象：子程序的目标代码段；全局数据目标（全局变量）3、静态存储分配的要求：不允许递归调用，不含有可变数组。FORTRAN 程序是段结构，不允许递归，数据名大小、性质固定。 是典型的静态分配 54.动态存储分配 ：1、如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术。2、两种动态存储分配方式：栈式，堆式栈式动态存储分配策略：将整个程序的数据空间设计为一个栈。【例】在具有递归结构的语言程序中，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。 55.过程所需的数据空间包括两部分：一部分是生存期在本过程这次活动中的数据对象。如局部变量、参数单元、临时变量等；另一部分则是用以管理过程活动的记录信息(连接数据)。 56.活动记录（AR ）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区 (块)叫做一个活动记录。构成：1、临时工作单元；2、局部变量；3、机器状态信息；4、存取链；5、控制链；6、实参；7、返回地址 57.什么是代码优化 所谓优化，就是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少。 58.优化原则：等价原则：经过优化后不应改变程序运行的结果。
计算机编译原理基础知识概述
计算机编译原理基础知识概述计算机编译原理是计算机科学的重要分支，它研究的是将高级编程 语言转化为机器语言的方法和技术。编译器是计算机软件中的核心组件，它负责将程序员编写的高级语言代码转换为计算机能够执行的二 进制指令。本文将对计算机编译原理的基础知识进行概述。 一、编译原理的定义及作用 计算机编译原理是研究如何将高级编程语言转化为机器语言的学科，它的主要目标是设计和实现高效可靠的编译器。编译器是一种将源代 码翻译成目标代码的软件工具，它可以将程序员编写的高级语言程序 转换为机器语言指令，以便计算机能够执行。 编译原理的作用主要有以下几个方面： 1. 提高程序执行效率：编译器可以进行优化，使得程序的执行更加 高效，节省计算资源，提升计算机系统的性能。 2. 简化程序编写：使用高级编程语言可以使程序编写更加方便快捷，减少程序员的工作量。 3. 跨平台开发：通过编译器将高级语言代码转换为机器语言，可以 使程序在不同的计算机平台上运行。 二、编译原理的基本过程 编译器通常包含以下几个基本过程：
1. 词法分析：将源代码分解为一个一个的单词或符号，形成词法单 元序列。这个过程中会去掉程序中的注释和多余的空格，将代码转换 为一个标记流。 2. 语法分析：根据语法规则对词法单元序列进行语法分析，构建抽 象语法树。这一过程对代码的结构进行分析，确定是否符合语法规范。 3. 语义分析：对抽象语法树进行语义分析，确定变量声明、类型检 查等信息，并进行错误检查和修复。 4. 中间代码生成：将抽象语法树转化为中间代码表示，通常是一种 独立于机器的中间表示形式。 5. 代码优化：对中间代码进行优化，提高程序的执行效率，减少代 码的长度和执行时间。 6. 目标代码生成：将优化后的中间代码转化为目标机器代码，生成 可执行文件。 7. 符号表管理：维护和管理程序中的变量、函数等符号信息，用于 在编译过程中进行引用和检查。 三、编译器的基本结构 编译器通常包含以下几个组成部分： 1. 前端：负责词法分析、语法分析、语义分析等处理程序的结构和 语义。前端生成中间代码。
编译原理知识点汇总
编译原理的复习提纲 1. 编译原理=形式语言+编译技术 2. 汇编程序：把汇编语言程序翻译成等价的机器语言程序 3. 编译程序：把高级语言程序翻译成等价的低级语言程序 4. 解释执行方式：解释程序，逐个语句地模拟执行 翻译执行方式：翻译程序，把程序设计语言程序翻译成等价的目标程序 5. 计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、 语义分析及中间代码生成、代码优化、目标代码生 成 词法分析的任务：扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数 等） 语法分析是：在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程 序识别出的符号，根据给定的语法规则，识别出各个语法结构。语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分 析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导 技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码
编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6. 编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独 立性。 7. 汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1•符号，字母表，符号串，符号串的长度计算P18,子符号串的含义，符号串的简单运算XY，Xn， 2. 符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ } 3. 重写规则，简称规则。非xx(V n），xx（V t ）的概念。 4•文法的概念。P23识别符号.P23文法的第一个重写规则的左部符号为识别号。
编译原理复习整理(重点含答案)
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化）
4、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧ （1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。 (1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)} FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#} (2)考虑下列产生式: '→+'→'→'→E E T T F F P E a b ||*|()|^||εεε FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3) + * ( ) a b ^ # E E TE →' E TE →' E TE →' E TE →' E' '→+E E '→E ε '→E ε T T F T →' T F T →' T F T →' T F T →' T' '→T ε '→T T '→T ε '→T T '→T T '→T T '→T ε F F P F →' F P F →' F P F →' F P F →' F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F ε P P E →() P a → P b → P →^ 5、考虑文法: S →AS|b A →SA|a （1）列出这个文法的所有LR(0) 项目。
编译原理期末总结复习
编译原理期末总结复习 （经典版） 编制人：__________________ 审核人：__________________ 审批人：__________________ 编制单位：__________________ 编制时间：____年____月____日 序言 下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢! 并且，本店铺为大家提供各种类型的经典范文，如公文写作、报告体会、演讲致辞、党团资料、合同协议、条据文书、诗词歌赋、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注! Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you! In addition, this shop provides you with various types of classic sample essays, such as official document writing, report experience, speeches, party and group materials, contracts and agreements, articles and documents, poems and songs, teaching materials, essay collections, other sample essays, etc. Learn about the different formats and writing styles of sample essays, so stay tuned!
编译原理知识点总结
编译原理知识点总结 在计算机科学领域中，编译原理是一个重要的研究方向。它涵盖了从源代码到可执行代码的整个过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等多个环节。本文将简要总结编译原理的一些关键知识点。 1. 词法分析： 词法分析是编译过程的第一步，它负责将源代码分割成一个个单词或记号。在词法分析中，需要定义合法的单词或记号的规则，这些规则通常使用正则表达式或有限自动机来表示。词法分析器还可以去除空格、注释等无关元素，并将分割后的单词传递给下一步的语法分析。 2. 语法分析： 语法分析是编译过程的第二步，它负责根据语法规则检查源代码的结构是否符合语法规范。常用的语法表示方法有文法、语言、语法分析树等。语法分析器可以通过递归下降、LL(1)分析、LR分析等方法来实现。语法分析的主要目标是生成抽象语法树，为后续的语义分析做准备。 3. 语义分析： 语义分析是编译过程的第三步，它负责检查源代码的语义是否合法，并对其进行解释或翻译。语义分析的主要任务包括类型检查、作用域分析、绑定检查等。在语义分析过程中，常用的方法有符号表、语义规则等。语义分析器可以检测到潜在的语义错误，并生成中间代码或直接对源代码进行转换。 4. 中间代码生成： 中间代码生成是编译过程的第四步，它负责将源代码转换成高级语言或低级语言的中间表示形式。中间代码是介于源代码和目标代码之间的一种抽象表示，可以
方便地进行代码优化和目标代码生成。常见的中间代码表示方法有三地址码、四元式、虚拟机指令等。 5. 代码优化： 代码优化是编译过程的一个重要环节，它可以在不改变程序功能的前提下，提高程序执行效率和资源利用率。代码优化的目标通常包括减少代码体积、提高程序运行速度、减少存储器的使用等。常见的代码优化技术有常量折叠、复写传播、循环优化等。 6. 目标代码生成： 目标代码生成是编译过程的最后一步，它负责将中间代码转换成可执行的目标代码。目标代码可以是机器语言、汇编语言或其他类似的形式。目标代码生成器需要根据目标机器的特性和限制，进行寄存器分配、指令选择、代码布局等优化，以实现最佳的代码生成效果。 综上所述，编译原理涉及的知识点非常广泛且复杂，从词法分析到目标代码生成，每个环节都有其特定的任务和技术。了解并掌握编译原理的相关知识，对于编程和软件开发的理解和能力提升具有重要意义。因此，无论是从事编译器设计与实现的研究工作，还是在软件开发过程中需要进行编译优化的工作，都需要对编译原理有深入的了解和研究。
编译原理知识点详解
编译原理知识点详解 编译原理是计算机科学中的一门基础课程，它研究的是将高级语言程序翻译成机器语言的技术和方法。在编译原理中有很多重要的知识点，下面我将详细介绍其中的几个。 第一个知识点是词法分析。词法分析是编译器的第一个阶段，它的任务是将输入的字符序列分解成一个个的词法单元，并将这些词法单元分类。例如，在C语言中，词法单元可以是关键字、标识符、常量、运算符等。词法分析器通常使用有限自动机来实现，它能够高效地识别不同的词法单元。 第二个知识点是语法分析。语法分析是编译器的第二个阶段，它的任务是根据词法分析得到的词法单元序列构建语法树。语法树表示了程序的语法结构，它可以帮助编译器理解程序的语义。常用的语法分析算法有LL算法和LR算法，它们能够根据语法规则逐步推导出语法树。 第三个知识点是语义分析。语义分析是编译器的第三个阶段，它的任务是对语法树进行静态语义分析。静态语义分析可以检查程序中的语义错误，例如类型不匹配、变量未声明等。语义分析器通常会构建符号表来保存程序中的变量和函数信息，并通过遍历语法树来进行类型检查和语义分析。 第四个知识点是中间代码生成。中间代码生成是编译器的第四个阶
段，它的任务是将语法树转换成一种中间表示形式。中间表示形式可以是三地址码、虚拟机指令等。中间代码生成器通常会进行优化，例如常量折叠、公共子表达式消除等，以提高程序的执行效率。 第五个知识点是目标代码生成。目标代码生成是编译器的最后一个阶段，它的任务是将中间代码转换成目标机器代码。目标机器代码可以是汇编语言代码或机器指令。目标代码生成器通常会进行寄存器分配、指令选择等优化，以提高生成的目标代码的质量和执行效率。 除了以上几个知识点，编译原理还涉及到错误处理、优化技术等内容。编译原理是一门非常重要的课程，它对于理解计算机系统和开发高效程序都有着重要意义。通过学习编译原理，我们可以更好地理解编程语言的工作原理，并且能够开发出高效、可靠的编译器和解释器。
考研编译原理知识点串讲
考研编译原理知识点串讲 编译原理是计算机科学中一个重要的领域，研究如何将人类编写的高级语言程序转化为计算机能够执行的机器语言程序。考研编译原理作为计算机科学与技术专业的必修课程，涵盖了众多的知识点。本文将为大家进行编译原理知识点的串讲，旨在帮助考研学子复习整理重要知识点，准备考试。 1. 编译原理概述 编译原理是计算机科学中的一门学科，研究如何将高级语言程序转化为计算机能够执行的机器语言程序。编译原理主要包括词法分析、语法分析、语义分析、中间代码生成和优化、目标代码生成等几个基本阶段。这些阶段都是编译器的核心组成部分，对于理解编译原理具有重要意义。 2. 词法分析 词法分析是编译原理的第一个阶段，主要负责将源代码分解成一个个的词法单元。词法单元是程序中的最小语义单位，比如关键字、标识符、常量、运算符等。词法分析使用有限自动机或正则表达式等方法，将源代码分解并根据词法规则进行识别。 3. 语法分析 语法分析是编译原理的第二个阶段，主要负责根据语法规则分析词法单元序列，并构建相应的语法树。语法树是一个抽象的数据结构，
用于描述程序的语法结构。语法分析使用上下文无关文法和语法分析 算法（如LL(1)文法、LR分析等）来进行分析。 4. 语义分析 语义分析是编译原理的第三个阶段，主要负责对语法树进行语义检 查和语义动作的执行。语义检查主要包括类型检查、作用域检查等， 确保源代码的语义正确。语义动作的执行则是根据语义规则对语法树 进行相应的操作，如生成中间代码或修改符号表等。 5. 中间代码生成与优化 中间代码生成与优化是编译原理的第四个阶段，主要负责将源代码 转化为中间代码，并对中间代码进行优化。中间代码是一种介于源代 码和目标代码之间的中间表示形式，通常是一种抽象的、与机器无关 的表示形式。优化技术可以对中间代码进行各种优化，如公共子表达 式消除、循环展开等，以提高目标代码的执行效率。 6. 目标代码生成 目标代码生成是编译原理的最后一个阶段，主要负责将中间代码转 化为目标机器语言程序。目标机器语言是特定机器所能执行的指令集，与具体的硬件平台相关。目标代码生成根据目标机器的指令集和约束 生成目标代码，并进行寄存器分配、指令调度等优化手段，以提高目 标代码的效率。 通过对编译原理的知识点串讲，可以更好地理解和掌握整个编译过程。词法分析、语法分析、语义分析、中间代码生成与优化、目标代
计算机基础知识点编译原理代码生成
计算机基础知识点编译原理代码生成编译原理是计算机科学中非常重要的一门学科，它研究的是如何将 高级语言编写的程序转化为机器可以执行的指令序列。在编译过程中，代码生成是其中一个关键的步骤。本文将介绍编译原理中的代码生成 基础知识点。 一、代码生成概述 代码生成是编译过程中的最后一个阶段，它的任务是将中间表示形 式（如抽象语法树或中间代码）转化为目标机器代码，使得程序可以 在计算机上运行。代码生成的目标是产生高效且正确的机器指令序列，以最大程度地利用计算机的硬件资源。 代码生成的过程可以分为以下几个步骤： 1. 寄存器分配：将变量和临时值分配到计算机的寄存器中，以便在 指令中进行操作。 2. 指令选择：根据中间表示的特点和目标机器的指令集，选择适当 的机器指令来实现所需的操作。 3. 指令调度：对指令进行重新排序，以减少指令相关性和提高执行 效率。 4. 内存分配：将变量和临时值存储到内存中，以便在需要时可以进 行访问。
5. 代码优化：对生成的机器指令进行优化，以减少执行时的开销和 资源占用。 二、寄存器分配 在代码生成的过程中，寄存器分配是一个非常重要的环节。寄存器 是计算机中的一种高速存储设备，可以用于存储和执行指令操作。在 生成的机器代码中，寄存器通常用于存储临时值和计算结果。 寄存器分配的目标是将变量和临时值存储到寄存器中，并进行相应 的寄存器的分配和释放。常见的寄存器分配算法有线性扫描分配算法、图着色分配算法等。寄存器分配算法的选择通常取决于目标机器的寄 存器数量和寄存器之间的互斥关系。 三、指令选择 指令选择是代码生成的关键一环，它的任务是根据中间表示和目标 机器的指令集，选择合适的机器指令来实现所需的操作。指令选择的 准则通常是从操作数和操作符的角度考虑，以及考虑目标代码的执行 效率和可读性。 指令选择的过程中，需要考虑目标机器的指令格式、寻址方式、寄 存器约束等因素。对于一些特殊的操作，如函数调用、跳转指令等， 还需要考虑目标代码的控制流程和程序执行的正确性。 四、指令调度