1.翻译程序：将某一种语言（源语言）程序转换为与其逻辑上等价的另一种语言（目标语言）程序。

编译程序：源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。

汇编程序：源语言为汇编语言，目标语言为机器语言的翻译程序。

解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。

2.解释器与编译器的主要区别在于：运行目标程序时的控制权在解释器而不在目标程序。

3.编译程序的工作过程可划分五个阶段：①词法分析：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）②语法分析：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等③语义分析和中间代码生成：语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。

完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。

④代码优化：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。

⑤目标代码生成：目标代码生成阶段的任务就是是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

4.前端(Front-End)——与目标机无关的部分后端(Back-End )——与目标机有关的部分5.编译系统：编译程序与运行系统合称编译系统6.遍：对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标程序。

7.文法是一个四元组：G[S]=(VN, VT, P, S)VN：非终结符集合；VT ：终结符集合；P ：产生式集合（α→β或α∷=β）；S ：开始符号(或称根符号，识别符号)。

若S ->α,α∈V*，则称α为文法G的句型若S ->α,α,α∈VT*，则称α为文法G的句子语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集，即L(G) VT* 8.0型文法又叫短语文法，它所确定的语言称为0型语言。

1型文法,上下文敏感文法或上下文有关文法。

2型文法,上下文无关文法3型文法线性文法、正则文法或正规文法规范(最右)推导即任何一步α->β都是对α中的最右非终结符进行替换的，规范(最左)归约文法可唯一地确定一个语言子树与短语：在句型所对应的语法树中，若某些符号按从左到右的顺序组成某棵子树的末端结点，那么由这些末端结点所组成的符号串是相对于子树根结点的短语。

原则上语法树有多少棵子树，就有多少个短语。

9.词法分析的主要工作:从源程序的第一个字符开始，从左到右扫描源程序,一次读一个字符，根据词法规则将有关字符组合成单词，并识别各类单词，当确定单词类别后，将单词输出。

10.正规文法所描述的是字汇表V(VN∪VT)上的一些特殊子集，称为正规集。

也称正则表达式11.一个确定有限自动机（DFA）M是一个五元组：M=(S，Σ，f，S0，F)，S是一个非空有限集，它的每个元素称为一个状态Σ是一个有限的输入字母表，它的每个元素称为一个输入字符f是转换函数，它是从S ×Σ到S的单值部分映射S0∈S，是唯一的初始状态F 属于S，是终止状态集合。

状态转换图是有限自动机的一种表示形式12.一个非确定的有限自动机(NFA) M是一个五元组：M=(S ，Σ，f，S0，F)S是一个非空有限集，它的每个元素称为一个状态Σ是一个有限的输入字母表，它的每个元素称为一个输入字符f是转换函数，它是从S ×Σ*到2S的子集的映象S0 属于S是一个非空的初始状态集，初态可以是多个F 属于S，是终止状态集合13.语法分析是整个编译过程的核心部分，它完成的任务是：按照文法从源程序单词串(符号串)中识别各类语法成分，判断所给出的单词串是否是给定文法的正确句子，并为语义分析和代码生成做准备。

14.按照语法分析树的建立方法可以将语法分析方法分为：自上而下分析法、自下而上分析法。

15.确定的自上而下分析：算法思想：对于任一输入符号串，从文法的识别符号出发，根据当前的输入符号，唯一确定一个产生式，用产生式右部的符号串替代相应的非终结符往下推导，或构造一棵语法树。

若能推导出输入串或构造语法树成功则输入串是句子，否则不是。

16.LL(1)文法满足确定的自上而下的分析方法。

条件：①文法不含左递归。

②对文法中每一个非终结符A的各个产生式的候选首符集两两不相交。

若 A α1 | α2 |…| αn则FIRST(αi) ∩FIRST(αj)=Φ（i≠j）③对文法中每一个非终结符A，若存在某个候选首符集包含 ，则FIRST(A)∩FOLLOW(A)=Φ17.直接左递归的消除：P→Pα| ß转换结果P →ßP’P’→αP’| ε间接左递归：A→Bc | dB→aA | Ab转换结果：A→aAc | Abc| dA→aAcA’| dA’A’→bcA’| ε18.首符号集：①. 若x∈VT，则FIRST(x)={x};②.若x∈VN，且有产生式x →a…，则把a加到FIRST(x)中；若x →ε也是一条产生式，则把ε也加到FIRST(x)中③-1.若X →Y…是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε元素都加到FIRST(x)③-2. 若X →Y1Y2Y3…YK是一个产生式,Y1Y2Y3…Y i-1都是非终结符，而且对于任何j,1≤j≤i-1, FIRST(Yj)都含有ε，则把FIRST(Yj)中的所有非ε元素都加到FIRST(x)中。

特别地，若所有的FIRST(Yj)均含有ε,则把ε加到FIRST(X)中。

素短语：某文法的句型它至少包含有一个终结符号，并且除它之外，不再包含任何更小的素短语。

活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号19.后继符号集①.对于文法的开始符号S,置# 于FOLLOW(S)中②.FOLLOW(U)={a | S->…Ua…,a VT}③.若A→α B ß是一个产生式，则把FIRST(ß)中的非ε加到FOLLOW(B)中④.若A→α B 是一个产生式，或A→α B ß是一个产生式而且ß ε，则把FOLLOW(A)加到FOLLOW(B)中。

20.预测分析程序是一种自顶向下分析程序，预测分析要求文法是LL(1)文法，它由分析栈、分析表和分析程序三部分组成，其中分析表的构成与文法有关。

21.自下而上分析方法是从输入符号串开始，查找当前句柄，并用产生式将它归约成相应的非终结符号，最后归约为开始符号的一种分析方法22.有一个文法G，如果G中没有形如:U …VW…的产生式，即它的任意产生式的右部都不含两个相继（并列）的非终结符，则称G为算符文法。

或称为OG文法。

设有一个不含空产生式的算符文法，如果在任意两个终结符号之间，至多只有一种优先关系成立，则称这样的算符文法为算符优先文法即OPG文法23.E->E+T得LASTVT(E)> +,+<FIRSTVT(T)24.LR分析法是一种有效的自底向上的语法分析技术，25.它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法LR方法的基本思想是：在规范归约过程中，一方面记住以移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对于未来进行“展望”。

当一串貌似句柄的符号串呈现分析栈的顶端时，根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序据分析表确定分析动作。

26.语法制导翻译:对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应地语义动作或语义子程序。

语法制导翻译的实质:根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）语句或子程序，对所要完成的功能进行描述，在语法分析过程中，当分析器使用该产生式进行语法分析时（不论是推导还是归约），除完成语法分析动作之外，还将调用为其配备的语义子程序，进行相应地语义处理，完成语义翻译工作。

27..中间代码也叫中间语言:是源程序的一种内部表示，不依赖目标机的结构，易于机械生成 目标代码的中间表示。

常见的几种形式：① 后缀式② 图表示法（抽象语法树、DAG 图）③ 三地址代码（三元式、四元式、间接三元式）28.符号表的三种构造法和处理法：线性查找、二叉树、杂凑技术。

线性查找：平均查找次数：n/2二叉树：平均查找次数：1+log2（n ）29.杂凑技术：假定有一个足够大的区域，这个区域用来填写一张含N 项的符号表。

构造一个地址函数 H ，对任何名字，H 函数的取值在0至N-1之间。

即不论对此项查表或填表，都能从H 函 数中获得它在表中的位置。

30.一个可执行程序所使用的存储空间被分为四个个区：代码区、数据区、栈区、堆区31.过程的每一次运行(或执行)被称为一次活动32.过程的活动生存期是指从该过程体第一步操作到最后一步操作之间的操作序。

两个过程 的活动生存期或嵌套或不重叠。

33.静态链：它指向直接外层过程的活动记录的起始位置，用于访问各外层的变量（非局部 变量）。

34.带有Display 的活动记录：老 SP 返回地址 参数个数 形式单元 简单变量 内情向量临时工作单元 TOP SP 静态链 内情向量临时工作单元 OP35.划分基本块的算法：①. 求出程序中可做基本块入口的语句，它们是：Ⅰ. 程序的第一条语句；Ⅱ. 能由条件转移语句或无条件转移语句转移到的语句；Ⅲ. 紧跟在条件转移语句后面的语句。

②. 对以上入口语句，构造其所属的基本块：此入口语句到下一条入口语句前，或下一条跳 转语句前，或一条停语句前的语句序列组成一个基本块。

③.删除未被纳入任何基本块的语句对基本块内的语句可以进行如下优化变换：合并已知量,交换语句位置,代数变换存储分配策略：静态存储分配：编译时对所有数据对象分配固定的存储单元（地址空间），运行时始终不变。

栈式动态存储分配：每个过程建立活动记录，运行时每当调用一个过程，Display老 SP 返回地址 参数个数 形式单元 简单变量 内情向量 临时工作单元TOPSP 全局Display就将活动记录动态的分配于栈顶，过程活动结束，则活动记录退出栈顶。

堆式动态存储分配：将存储空间组织成堆结构，以便用户可以随时申请或释放存储空间。