《编译词汇解释》由会员分享，可在线阅读，更多相关《编译词汇解释（12页珍藏版）》请在金锄头文库上搜索。
1、1.编译程序编译程序(Compiler) 编译程序是一种翻译程序，它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言。一般编译程序分成五个逻辑模块：词法分析、语法分析、语义分析和中间代码生成、中间代码优化、目标代码生成。2.解释程序（解释程序（Intepretter）解释程序是一种翻译程序，它将不能被计算机识别的某种高级语言翻译成计算机能够识别的低级语言。它是逐个语句翻译的，边翻译边执行，不生成目标代码。3 源语言（源语言（Source language）和源程序（）和源程序（Source program） 被编译程序翻译的程序称为源程序,书写该程序的语言称为源语言。4 目标语言
2、（目标语言（Object language or Target language）和目标程序（）和目标程序（Object program or Target program） 编译程序翻译源程序而得到的结果程序称为目标程序, 书写该程序的语言称为目标语言.5 词法分析（词法分析（Lexical analysis 或或 Scanning）和词法分析程序（）和词法分析程序（Lexical analyzer 或或 Scanner） 词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词
3、法分析程序实现这个任务。词法分析程序可以使用 lex 等工具自动生成。 6语法分析（语法分析（Syntax analysis 或或 Parsing）和语法分析程序（）和语法分析程序（Parser） 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述. 7语义分析（语义分析（Syntax analysis） 语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个 C 程序片
4、断:int arr2,b;b = arr * 10; 源程序的结构是正确的. 语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配. 8 中间代码生成中间代码生成（Intermediate Code Generation）在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。9中间代码优化（中间代码优化（Intermediate Code Optimization）所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占
5、用存储空间少，或两者都有。10目标代码生成（目标代码生成（Object Code Generation ）将优化后的中间代码转化成等价的目标代码。目标代码主要有机器语言和汇编语言。11. Lex 一个词法分析程序的自动生成工具。它输入描述构词规则的一系列正规式,然后构建有穷自动机和这个有穷自动机的一个驱动程序,进而生成一个词法分析程序.12. Yacc 一个语法分析程序的自动生成工具。它接受语言的文法,构造一个 LALR(1)分析程序.因为它采用语法制导翻译的思想,还可以接受用 C 语言描述的语义动作,从而构造一个编译程序. Yacc 是 Yet another compiler compil
6、er 的缩写.13文法（文法（Grammars） 文法是用于描述语言的语法结构的形式规则。文法 G 定义为四元组(，)。其中为非终结符号(或语法实体，或变量)集；为终结符号集；为产生式(也称规则)的集合；产生式(规则)是形如或 a :=b 的(a , b)有序对,其中() 且至少含有一个非终结符，而()。，和是非空有穷集。称作识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。 一个文法的例子: G=(=A，R,=0,1 ，=A0R，A01,RA1,=A) 14文法分类（文法分类（A hierarchy of Grammars） 著名语言学家 Noam Chomsky 定义了
7、四类文法和四种形式语言类，文法的四种类型分别是 0 型、1 型、2 型和 3 型。几类文法的差别在于对产生式施加不同的限制。 15 0 型文法型文法(短语结构文法短语结构文法)(phrase structure grammars) 设 G=(，)，如果它的每个产生式是这样一种结构： () 且至少含有一个非终结符，而() ，则 G 是一个 0 型文法。0 型文法产生的语言称为 0 型语言。16 1 型文法（上下文有关文法）型文法（上下文有关文法）(context-sensitive grammars) 设 G=(，)为一文法，若中的每一个产生式均满足|，仅仅除外，则文法 G 是 1 型或上下文有
8、关的。1 型文法产生的语言称为 1 型语言，也称作上下文有关语言。17 2 型文法（上下文无关文法）型文法（上下文无关文法）(context-free grammars) 设 G=(，)，若 P 中的每一个产生式满足：是一非终结符，() 则此文法称为 2 型的或上下文无关的。2 型文法产生的语言称为 2 型语言，也称作上下文无关语言。18 3 型文法（正规文法）型文法（正规文法）(regular grammars)： 设 G=(，)，若中的每一个产生式的形式都是 AaB 或 Aa，其中 A 和 B 都是非终结符，a 是终结符，则 G 是 3 型文法或正规文法。 3 型文法产生的语言称为 3 型
9、语言，也称作正规语言。19句型（句型（Sententialform）设 GS是一文法，如果符号串 x 是从识别符号推导出来的，即有 S x，则称 x 是文法GS的句型。20句子（句子（Sentence）设 GS是一文法，如果符号串 x 是从识别符号推导出来的，即有 S x，若 x 仅由终结符号组成，即 Sx，x，则称 x 为 GS的句子。21语言（语言（Language）文法 G 所产生的语言定义为集合xSx，其中 S 为文法识别符号，且 x。可用 L(G) 或L(GS)表示该集合。 22. 推导（推导（Derive）推导的概念：分别定义 V*中的符号之间的关系直接推导直接推导、长度为长度为
10、n（n1）的推导）的推导和长度为长度为n（n0）的推导）的推导： （1）如是文法 G=(，)的规则（或说是 P 中的一个产生式），和是 V*中的任意符号，若有符号串 v，w 满足： v，w 则说 v（应用规则）直接产生 w，或说，w 是 v 的直接推导，直接推导，或说，w 直接归约归约到 v，记做vw。 （2）如果存在直接推导的序列： vw0 w1 w2 wnw，（n0） 则称 v 推导出（产生）w（推导长度为 n），或称 w 归约到 v。记作 vw。 （3）若有 vw，或 vw，则记作。 23. 语法树（语法树（Parse tree）语法树（推导树）的概念：给定文法 G=(，)，对于 G 的
11、任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列 4 个条件： 每个结点都有一个标记，此标记是 V 的一个符号。 根的标记是 S。 若一个结点 n 至少有一个它自己除外的子孙，并且有标记 A，则 A 肯定在中。 如果结点 n 的直接子孙，从左到右的次序是结点 n1，n2， ，nk，其标记分别为A1，A2，Ak，那么 AA1A2，Ak一定是 P 中的一个产生式。 24二义文法（二义文法（Ambiguous grammer）如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义的。 25短语短
12、语 (phrase )令 G 是一文法，S 是文法的开始符号，是文法 G 的一个句型。如果有：且则称是句型相对与非终结符 A 的短语。特别，如有则称是句型相对于规则的直接短语 (也称简单短语)。一个句型的最左直接短语称为该句型的句柄。 26句柄句柄 ( sentence handle)令 G 是一文法，S 是文法的开始符号，是文法 G 的一个句型。如果有：且则称是句型相对与非终结符 A 的短语。特别，如有则称是句型相对于规则的直接短语 (也称简单短语)。一个句型的最左直接短语称为该句型的句柄。27正规式（正规式（regular expression）和它所表示的正规集（）和它所表示的正规集（r
13、egular set）设字母表为,辅助字母表=,，.，*,(,)。1. 和都是上的正规式，它们所表示的正规集分别为和； 2.任何 a，a 是上的一个正规式，它所表示的正规集为a； 3.假定和都是上的正规式，它们所表示的正规集分别为 L()和 L()，那么，()，和也都是正规式，它们所表示的正规集分别为 L()，L()L()，L()L()和(L() 。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。 28确定的有穷状态自动机确定的有穷状态自动机 DFA(deterministic finite automaton)我们这里是把 DFA 和 NF
14、A 作为正规集的识别工具而介绍的。DFA 定义如下：一个确定的有穷自动机(DFA)M 是一个五元组：M=(K, ，f，S，Z)其中 (1). K 是一个有穷集，它的每个元素称为一个状态；(2). 是一个有穷字母表，它的每个元素称为一个输入字符,所以也称为输入符号字母表:(3). f 是转换函数，是在 KK 上的映像，即，如 f(,a)=(K, K)就意味着，当前状态为，输入字符为 a 时，将转换到下一状态，我们把称作的一个后继状态;(4). SK 是唯一的一个初态；(5). ZK，是一个终态集，终态也称可接受状态或结束状态。29不确定的有穷状态自动机不确定的有穷状态自动机 NFA(nondet
15、erministic finite automaton）NFA 定义如下;一个不确定的有穷自动机(NFA)M 是一个五元组，M=(K, ，f，S，Z)其中 (1). K 是一个有穷集，它的每个元素称为一个状态；(2). 是一个有穷字母表，它的每个元素称为一个输入字符； (3). f 是一个从 K到 K 的子集的映像.(4). SK，是一个非空初态集;(5). ZK，是一个终态集。 DFA 和 NFA 的等价定理：对于每个 NFA M，存在一个 DFA M，使得 L（M）L（M），即 M 和M是等价的。 30最小状态最小状态 DFA(reduced DFA or minimum DFA) 我们说
16、一个确定的有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的，这种 DFA 也叫做最小状态 DFA。一个 DFA 可以通过消除多余状态和合并等价状态而转换成一个与之等价的最小状态 DFA。 31Token 具有集合意义的字符序列。是词法分析的输出. Token 一般分为标识符,常数(常量),关键字,运算符及界符。32FIRST 集集设 G=(，)是上下文无关文法 FIRST()=a，a，, 若，则规定FIRST()。 33FOLLOW 集集设 G=(，)是上下文无关文法，A，是开始符号FOLLOW(A)=a且 a，aFIRST()， 若，且，则#FOLLOW(A)。也可定义为：FOLL
