编译程序：将源程序翻译成等价的目标程序（汇编语言或机器语言）。
解释程序：按源程序中语句动态顺序，边解释，边执行。
汇编程序：将汇编语言编写的程序翻译成机器指令序列。
编译程序的特点:翻译过程是一种功能上等价的翻译,输出结果是（机器语言或汇编语言）低级语言。
遍:指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。
简述编译程序的基本过程的任务。
编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。
词法分析：输入源程序，进行词法分析，输出单词符号。
语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。
中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。
优化：对中间代码进行优化处理。
目标代码生成：把中间代码翻译成目标语言程序。
编译程序与解释程序的区别？
编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。
有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？
编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有
这一部分工作，仍然能够得到目标代码。
编译程序的分类
    目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。
LL(1)分析法的必要条件
文法不包含左递归; 对于文法中的每一个非终结符A的各个产生式的侯选首字符集两两不相交。 即：对于产生式A
若  ,  则FIRST()∩FIRST()= Ф
若＝ε,则FIRST(A)∩FOLLOW(A)=φ
构造FIRST集合的算法
对每一文法符号X(VN U VT)*
(1)若XVT ，则FIRST(X)={X}。
(2)若XVN ，且有产生式Xa，aVT，则aFIRST(X)。
(3)若XVN ，X，则FIRST(X)
(4)若XVN，Y1，Y2，，Yi VN，且有产生式XY1,,Yn。
若对于1≤i≤k≤n，都有Yi, 则FIRST(Yk+1)-{}属于FIRST(X)
构造FOLLOW集算法
对文法开始符号S，将“#”置于FOLLOW(S)中。 (∵有句型#S#)
若有A→B，则把FIRST(β)-{ε}加至FOLLOW(B)
若有A→B或A→B，而；则把FOLLOW(A)加至FOLLOW(B)中。
构造预测分析表（LL(1)分析表）方法
若a∈FIRST(α)，则把A→α放入M[A,a]中;
若ε∈FIRST(α)，则对每个终结符b∈ FOLLOW(A),将A→ε放入M[A,b]中；
短语：设文法G的开始符号为S，S，且Aβ,则称β是句型相对于非终结符A的一个短语。
直接短语：在短语定义的基础上，若有SA，且A源程序能直接执行吗,则称是句型相对于产生式A→的直接短语
句柄：句型的最左直接短语称为该句型的句柄。
构造LR(0)分析表的算法
①若项目A.X 属于Ik，且GO(Ik,X)=Ij：若XVT，则置ACTION[k,X]为“把(j,X)移进栈”，简记为Sj; 若XVN，则置GOTO[k,X]=j，j为状态号；
②若项目A.属于Ik，则对任何终结符a或结束符＃，置ACTION[k,a]为“用产生式A→进行归约”,简记为ri，i为产生式序号；
③若项目S’→S.属于Ik，则置ACTION[k,＃]=acc，为接受；
SLR(1)分析表的构造
只需将LR(0)分析表算法的②改为:
若归约项目A.属于Ik，则对任何输入符号a∈FOLLOW(A)，置ACTION[k,a]=rj，j为产生式序号。
符号表的作用:是编译程序保存（记录）源程序中各种名字的属性和特征信息的各种表格(数据结构);
一般在处理说明性语句时填符号表，在使用变量等时查符号表。
符号表中的信息在编译各阶段都要使用。 在语义分析中，用符号表中的内容进行语义检查（如：名字的使用与说明是否一致）； 在目标代码生成阶段对符号名进行地址分配时,符号表是地址分配的依据。
动态存储分配
很多高级语言都支持嵌套分程序、嵌套或递归过程结构及动态数组，这些需要运行时存储空间管理机制。 栈式存储分配方法是适合于这类语言的一种存储管理方法。 栈式存储分配方法是把整个程序的存储空间都安排在一个栈内。
栈式存储分配基本思路
进入主程序时，将主程序定义的各类全程量所需存储空间分配于栈顶； 每当调用一个子程序（过程/函数）时，就将其所需的存储空间分配于栈的当前栈顶;每当从子程序运行结束时，就从栈中释放其所占空间； 整个程序执行完后，释放它所占用的全部空间。
栈式存储分配适合的语言：
允许层次嵌套结构， 允许过程递归调用， 许含可变数组 。
由于过程定义是嵌套的，任一个过程都可以引用其外层过程中定义的变量,因此，子过程必须要知道其全部外层过程的最新活动记录的地址。 由于允许递归调用和包含可变数组，因此过程的活动记录位置往往是变化的，因此应跟踪每个外层过程的最新活动记录的位置。
常用的跟踪方法
静态链：指向其直接外层过程的最新活动记录的基地址。 Display表：每当进入一个子过程时，在建立它的活动记录区的同时建立一张嵌套的层次显示表——display，用来存放各外层最新活动记录的基地址。
活动记录结构
活动记录：当前执行的过程的数据区内容。含过程嵌套结构、允许递归调用、含可变数组的程序设计语言的活动记录结构
优化概念
等价原则：对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
有效原则：优化的目的在于既要设法缩小存储空间，又要尽量提高运行速度，而且更偏重于提高运行速度。
合算原则：应尽可能以较低的代价取得较好的优化效果。
优化方法
1.基本块内优化
合并已知量 删除多余运算 删除无用赋值
2.循环优化
代码外提 强度消弱
3.合并已知量优化方法
4．删除多余运算
5. DAG图
是一种带结点、带标记或附加信息的有向图
叶结点（没有后继的结点）用一个标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。
内部结点（有后继的结点）用一个运算符作为标记，表示该结点代表应用该结点运算符对其后继结点所代表的值进行运算的结果。
各结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。
1.设有如下所示代码段，试写出在过程S中调用过程Q后的栈式存储空间分配情况。（右边所示为动态存储分配采用的活动记录结构，假设存储空间分配从地址0开始）
Program P;
Var a,b: integer;   
  Procedure Q(x: int ) 
  Var y: integer; 
  begin
    ……
  end 
  procedure S;   
  var c,y: integer;
  begin
c:=1;
call Q(c);
  end
begin
  call S( ); 
end
top
解答：
16
简单变量：y
15
形式单元：x
14
参数个数：1
13
静态链：0
sp
12
返回地址
11
老sp：5
10
简单变量：y
9
简单变量：c
8
参数个数：0
7
静态链：0
6
返回地址
5
老sp：0
4
简单变量：b
3
简单变量：a
2
静态链：0
1
返回地址
0
0

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。