编译词汇解释

1、. 编译程序(Compiler)编译程序是一种翻译程序，它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言。 一般编译程序分成五个逻辑模块：词法分析、语法分析、语义分析和中间代码生成、中间代码优化、目标 代码生成。.解释程序(Intepretter)解释程序是一种翻译程序，它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言。它是逐个语句翻译的，边翻译边执行，不生成目标代码。. 源语言(Source language 和源程序(Source program)被编译程序翻译的程序称为源程序，书写该程序的语言称为源语言。.目标语言( Object language or

2、Target language) 和目标程序( Object program or Target program )编译程序翻译源程序而得到的结果程序称为目标程序，书写该程序的语言称为目标语言. 词法分析(Lexical analysis 或 Scanning) 和词法分析程序( Lexical analyzer 或 Scanner)词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。.语法分析(Syntax a

3、nalysis或Parsing)和语法分析程序(Parser)语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类 语法短语，如 程序”，语句“，裳达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语义分析(Syntax analysis)语义分析是编译过程的一个逻辑阶段.语义分析的任务是对结构上正确的源程序进行上下文有关性质 的审查，进行类型审查.例如一个C程序片断：int arr2,b;b = arr * 10;源程序的结本是正确的.语义分析将审查类型并报告错误：不能在表达式中使用一个数组变量，赋值语句的右端和左端的类

4、型不 匹配.中间代码生成 (Intermediate Code Generation )在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种 内部表示形式叫做中间语言或中间表示或中间代码。.中间代码优化(Intermediate Code Optimization )所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相 同，而运行速度加大或占用存储空间少，或两者都有。.目标代码生成(Object Code Generation )将优化后的中间代码转化成等价的目标代码。目标代码主要有机器语言和汇编语言。. Lex一个词法分

5、析程序的自动生成工具。它输入描述构词规则的一系列正规式，然后构建有穷自动机和这个有穷自动机的一个驱动程序，进而生成一个词法分析程序. Yacc一个语法分析程序的自动生成工具。它接受语言的文法，构造一个LALR(1)分析程序.因为它采用语法制导翻译的思想，还可以接受用 C语言描述的语义动作，从而构造一个编译程序.Yacc是Yet another compiler compiler的缩写.文法(Grammars )文法是用于描述语言的语法结构的形式规则。文法G定义为四元组(耳,6 ,产，S)。其中心 为非终结符号(或语法实体，或变量)集；/为终结符号集； P为产生式(也称规则)的集合；产生式(规则

6、)是 形如Q T 或a :=b的(a , b)有序对其中也 (% U % )|且至少含有一个非终结符，而 f丘(/ U 6)1。/，41和F是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条 规则中作为左部出现。一个文法的例子：G=(/=A, R, % =0,1 , F=A?0R , A?01,R?A1, = =A).文法分类(A hierarchy of Grammars )著名语言学家Noam Chomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制。. 0 型文法(短语结构文法)(phrase

7、structure grammars)设g=(%, p, S)，如果它的每个产生式aTS是这样一种结构aE ()1 且至少含有一个非终结符，而e(%u/)l则g是一个0型文法。0型文法产生的语言称为0型语言。.1 型文法(上下文有关文法)(context-sensitive grammars)设g=(/ M , F, S)为一文法，若?中的每一个产生式aTE均满足。，仅仅ST 除外，则文法G是1型或上下文有关的。1型文法产生的语言称为1型语言，也称作上下文有关语言。.2型文法(上下文无关文法)(context-free grammars)设g=(%, 4, P, S),若p中的每一个产生式仪满

8、足：口是一非终结符，Jw(7u丁)1则此文法称为2型的或上下文无关的。2型文法产生的语言称为 2型语言，也称作上下文无关语言。.3 型文法(正规文法) (regular grammars)：设G=( % , 4 , P , ),若P中的每一个产生式的形式都是 aB或a ,其中A和B都是非终结符，a是终结符，则 G是3型文法或正规文法。3型文法产生的语言称为 3型语言，也称作正规语言。.句型(Sententialform)设G S是一文法，如果符号串x是从识别符号推导出来的，即有S= x,则称x是文法G S的句型。.句子 S Sentences)*设G S是一文法，如果符号串x是从识别符号推导出

9、来的，即有S= x,若x仅由终结符号组成，* *即S=x, x G/了，则称x为G S的句子。.语言(Language)* *文法G所产生的语言定义为集合 x | S=x,其中S为文法识别符号，且 xG厂了 。可用L(G)或L(GS)表示该集合。.推导(Derive) +推导的概念：分别定义V*中的符号之间的关系直接推导=、长度为n (n 1)的推导=和长度为n(n 0)的推导二:(1)如2T0是文法g=(4, 4, F, S)的规则(或说是p中的一个产生式)，了和是v*中的任意符号,若有符号串 v , w满足：v=7 ct A, w= y B 8则说v (应用规则)直接产生w,或说，w是v的

10、直接推导，或说，w直接归约到v,记做vn w。(2)如果存在直接推导的序列：v wc)n wi 二 w2 二 wn= w, ( n0)则称v推导出(产生)w (推导长度为n),或称w归约到v。记作v二Wo+ *(3)若有v = w,或v=w,则记作.。. 语法树(Parse tree)语法树(推导树)的概念：给定文法G=(%,丁，P , ),对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件：每个结点都有一个标记，此标记是 V的一个符号。根的标记是So若一个结点n至少有一个它自己除外的子孙，并且有标记 A ,则A肯定在 心中。如果结点n的直接子孙，从左到右的次序是结点n

11、1，像，nk,其标记分别为 A1, A2, , Ak那么A-A1A2,，Ak一定是P中的一个产生式。.二义文法( Ambiguous grammer)如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句子，它有两个不同的最左 (最右)推导，则这个文法是二义的。.短语(phrase ) +令g是一文法，s是文法的开始符号，a/8是文法g的一个句型。如果有：Sn山15且工台 则称0是句型汽8相对与非终结符a的短语。特别，如有二0则称0是句型 阳5 相对于规则的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。.句柄(sentence h

12、andle) +令G是一文法，S是文法的开始符号， 邸6是文法g的一个句型。如果有：Sn出18且心则 称是句型相对与非终结符a的短语。特别，如有 心0则称B是句型 邸6 相对于规则 人 的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。.正规式 (regular expression) 和它所表示的正规集 (regular set)设字母表为，辅助字母表E = 4, E, I, ., *,(,)。. E和中都是上的正规式，它们所表示的正规集分别为 E和9 ；.任彳aG , a是上的一个正规式，它所表示的正规集为a；.假定4和%都是上的正规式,它们所表示的正规集分别为!_(1)

13、和L(与)，那么，(青),4 |电, 4片和外也都是正规式，它们所表示的正规集分别为L(4), lM)UL(1 ), L(4)L(B )和化(4 )1 o.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是Y上的正规集。.确定的有穷状态自动机DFA(deterministic finite automaton)我们这里是把DFA和NFA作为正规集的识别工具而介绍的。DFA定义如下：一个确定的有穷自动机(DFA)M是一个五元组：M=(K, , f, S, Z)其中. K是一个有穷集，它的每个元素称为一个状态；. E是一个有穷字母表，它的每个元素称为一个输入字符，

14、所以也称为输入符号字母表：.f是转换函数，是在 KX二K 上的映像，即，如f也,a)=/ 内 K,*/ GK)就意味着，当前状态为上输入字符为a时，将转换到下一状态 勺 我们把上J称作尢的一个后继状态；. SC K是唯一的一个初态；. ZQK,是一个终态集，终态也称可接受状态或结束状态。29,不确定的有穷状态自动机NFA(nondeterministic finite automaton )NFA定义如下；一个不确定的有穷自动机(NFA)M是一个五元组，M=(K, , f, S, Z)其中. K是一个有穷集，它的每个元素称为一个状态；. 是一个有穷字母表，它的每个元素称为一个输入字符；. f是

15、一个从KX E,到K的子集的映像. SQK,是一个非空初态集；. Z U K ,是一个终态集。DFA和NFA的等价定理：对于每个NFA M ,存在一个 DFA M?,使得L (M) = L ( M?),即M和M?是等价的。最小状态 DFA(reduced DFA or minimum DFA)我们说一个确定的有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的，这种DFA也叫做最小状态 DFA。一个DFA可以通过消除多余状态和合并等价状态而转换成一个 与之等价的最小状态 DFA oToken具有集合意义的字符序列。是词法分析的输出.Token 一般分为标识符，常数(常

16、量),关键字，运算符及界符。FIRST 集*设 G=( %, P , )是上下文无关文法FIRST( a )= a | =, a,也,0 W* 若疗= ,则规定 e FIRST( 口)。FOLLOW 集设G=4 , VT , P , S )是上下文无关文法，ACN，S是开始符号*FOLLOW(A)= a |且 aG % , a FIRST( ), .展左口* 若Sn, 且 ； ,则 #G FOLLOW(A) o*也可定义为：FOLLOW(A)=a| = - Aa- ,a fj t若有a ,则规定#e follow(A)这里我们用，#?作为输入串的结束符，或称为句子括号，如：#输入串#。SELE

17、CT 集给定上下文无关文法的产生式 2 口 AW% ,口,若氏* ,则SELECT件 口 )= FIRST(也)*如果 g ， 则 SELECT件 Q )=FIRST( Q ) U FOLLOW(A)。左递归文法( Left recursive grammar)一个文法含有下列形式的产生式时。a)A B AC / G 厂b)2B 二EK A cA,B e %, 口、 e+在a)中也可称为含有左递归的规则或称直接左递归，在 b)中为 Q A称文法中含有左递归或间接 左递归，文法中只要含有 a)或含有b)或二者皆有均认为文法是左递归的。LL (1)文法满足如下条件的上下文无关文法称为LL (1)文

18、法：对每个非终结符 A的两个不同产生式，2 Q , 2 1 ,满足SELECT (2口)A SELECT (2 0)=力其中。、/不同时能=。LL (1)文法的含义是：第一个 L表明自顶向下分析是从左向右扫描输入串，第二个 L表明分析过程 中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选择哪个产生式(规则)进行推导，类 似也可以有LL (K)文法，也就是需向前查看 K个符号才可确定选用哪个产生式。通常采用 K=1,个别情况采用K=2.递归下降法(Recursive-descent递归下降法是LL (1)文法的分析程序的一种实现方法。它对应文法中每个非终结符编写一个递归过 程，这种分

19、析程序由这一系列递归过程的相互调用来完成语法分析工作。.移进一归约分析(shift reduce analysis)自底向上分析方法，也称移进-归约分析法，它的实现思想是对输入符号串自左向右进行扫描，并将 输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对 应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复 这一过程直到归约栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。.算法优先文法(Operator Precedence Grammar)设有一不含E产生式的算法文法 G,如果对任意两个终结

20、符对a, b之间至多只有 、和二三种关系的一种成立，则称 G是一个算符优先文法(Operator Precedence Grammar),即OPG文法。.最左素短语(Most left prime phrase)设有文法G S,其句型的素短语是一个短语 ，它至少包含一个终结符，并除自身外不包含其它素 短语，句型的最左边的素短语称最左素短语。. LR分析是一种自底向上的语法分析技术，通常称为LR(K).L是说从左至右扫描输入串，R是说分析过程所形成的推导是最右推导，K是指在做分析决策时向前察看K个输入符号.LR分析可用于一大类上下文无关文法，是一种最常用的无回朔的移进归约分析。. LR(0)项目

21、 (LR(0) items )文法G的产生式的右部适当位置添加有一个圆点则称为一个LR(0)项目。. LR(0)项目集规范族( canonical collection of sets of LR(0) items)构成识别一个文法活前缀的 DFA项目集(状态)的全体称为这个文法的 LR(0)项目集规范族。.活前缀(viable prefixes) *若S号郎0中是文法G中的一个规范推导。如果符号串7是口0的前缀,则称是g的一个活前缀。也就是说y是规范句型e/h的前缀,但它的右端不超过该句型句柄的末端。这里S为对原文法G加了产生式S TS , S为原文法G的开始符号，S为拓广后文法G的开始符号

22、。.属性文法(Attribute grammar )形式上讲，一个属性文法是一个三元组，A= (G, V, F), 一个上下文无关文法G; 一个属性的 有穷集V和关于属性的断言或谓词的有穷集F。每个属性与文法的某个非终结符或终结符相联。每个断言 与文法的某产生式相联。如果对G中的某一输入串而言(句子)，A中的所有断言对该输入串的语法树结 点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序 的断言是否全部为真。.语法制导翻译(Syntax-directed translation)在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序(或

23、语义规则描述的 语义动作)进行翻译的办法称作语法制导翻译。.中间语言(中间表示) ( Intermediate language(representation)在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种 内部表示形式叫做中间语言或中间表示或中间代码。所谓中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中 间代码一级进行与机器无关的优化。.数组内情向量(array dope vector)一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做内情向量”或 信息向

24、量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的 类型，维数，各维的上、下界，以及数组的首地址。编译程序处理数组说明的主要工作是把内情向量登录 在符号表中，这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据。.符号表(symbol table)在编译程序中符号表用来存放源程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的 语义特征属性，为进行上下文语义审查和进一步的翻译使用。.静态存储分配(Static storage allocation)如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标

25、程序运行时的全 部数据空间，确定每个数据对象的存储位置，称这种分配策略为静态存储分配。.动态存储分配(Dynamic storage allocation)如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用 动态存储管理技术。因为对于这种程序在编译时无法知道它在运行时需要多大的存储空间，它所需要的数 据空间的大小需待程序运行时动态地确定。有两种动态存储分配方式：栈式(stack)和堆式(heapp.过程的活动记录 AR(Activation Record)过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的信息，一般有如下信息：.临时工作单元，

26、比如计算表达式过程中需存放中间结果用的临时值单元。.局部变量，一个过程的局部变量。.保存机器状态，容纳该过程执行前关于机器状态的信息，诸如程序计数器、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。.存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有语言需要该信 息。.控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。.实参，也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序 中，也常常使用机器寄存器传递实参。.返回地址，保存该被调过程返回后的地址。. Display 表为能存取非局部变量而纪录外包过程的活动记录地址的

27、数组。即每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表displayo这里所提到的 嵌套层次”，是指过程定义的层数，始终假定主程序的层数为0,因此主程序称为0层过程。如某过程p是在层次为i的过程q内定义的，并且q是包围 p的直接外层，那么p的过程层数为i+1。display是一个指针数组d,也可看做是一个小栈，自顶向下每个 单元依次存放着现行层，直接外层，直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址。.基本块（Basic block）所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只 能从其人口语句进入，从其出口语句退出。

28、.无循环有向图 DAG （ Directed Acyclic Graph ）如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。基本块的DAG表示可用于代码优化。.控制流程图（流图）（ Control flow graph ）一个控制流程图就是具有唯一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何结点都有一条通路的结点。我们可以把一个控制流程图表示成一个三元组G= （N, E,用。），其中，N代表图中所有结点集，E代表图中所有有向边集，力。代表首结点。控制流程图简称为流图。.循环（Loop）在程序流图中，称具有下列性质的结点序列为一个循环：.它们是强连通的。也即

29、，其中任意两个结点之间，必有一条通路，而且该通路上各结点都属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。.它们中间有且只有一个是入口结点。因此，我们定义的循环就是程序流图中具有唯一入口结点的强连通子图，从循环外要进入循 环，必须首先经过循环的入口结点。所谓人口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者它就是 程序流图的首结点。.必经结点(dominators)和必经结点集(dominators set)在程序流图中，对任意两个结点 m和n,如果从流图的首结点出发，到达 n的任一通路都要经过 m, 则称m是n的必经结点，记为m DOM

30、n。流图中结点n的所有必经结点的集合， 称为结点n的必经结点集， 记为D (n)。.回边(back edge)假设a-b是流图中的一条有向边，如果 b DOM a,则称a-b是流图中的一条回边。. T 型图(T diagram )一个编译程序涉及到三个方面的语言，即源语言、目标语言和编译程序的书写语言。为了描述方便通 常用T型图来表示一个编译程序所涉及到的这三个方面的语言。T型图的左上角表示源语言，右上角表示目标语言，底部表示书写语言 (实现语言)。.自展(bootstrap)自展的思想是先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，然后再用这个子 集作为书写语言，实现源语言的编译程序，如果把这个过程根据情况分成若干步，像滚雪球一样直到生成 预计源语言的编译程序为止，我们把这样的实现方式称为自展技术。.交叉编译(Cross compile)所谓交叉编译是指把一个源语言在一个机器(称为宿主机)上编译产生另一个机器(称为目标机)的汇编语言或机器语言。.前端(Front-end)有时，常常把编译的过程分为前端 (front end)和后端(back end),前端由那样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常这些阶段包括词法分析、语法分析、语义分析和中间代码生 成，某些优化工作也可在前端做，也包括与前端每个阶段相