编译原理基本概念

1．编译程序编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。2．词法分析（Lexicalanalysis或Scanning）和词法分析程序（Lexicalanalyzer或Scanner）词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。3．语法分析（Syntaxanalysis或Parsing）和语法分析程序（Parser）语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.4．语义分析（Syntaxanalysis）及中间代码生成语义分析是编译过程的一个逻辑阶段.语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查,进行类型审查.例如一个C程序片断:intarr[2],b;b=arr*10;源程序的结构是正确的.语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.语义分析时，根据语句的含义，可对它进行翻译，用另一种语言形式（比源语言更接近于目标语言的一种中间代码或直接用目标语言）来描述这种语义。5．代码优化代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效的，即省时间和空间的代码。6．目标代码生成目标代码的生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。7．遍8．前端（Front－end）和后端（Backend）有时，常常把编译的过程分为前端(frontend)和后端(backend)，前端由那样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常这些阶段包括词法分析、语法分析、语义分析和中间代码生成，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理工作。后端工作指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。编译程序和解释程序9．Lex一个词法分析程序的自动生成工具。它输入描述构词规则的一系列正规式,然后构建有穷自动机和这个有穷自动机的一个驱动程序,进而生成一个词法分析程序.10．Yacc一个语法分析程序的自动生成工具。它接受语言的文法,构造一个LALR(1)分析程序.因为它采用语法制导翻译的思想,还可以接受用C语言描述的语义动作,从而构造一个编译程序.Yacc是Yetanothercompilercompiler的缩写.11．源语言（Sourcelanguage）和源程序（Sourceprogram）被编译程序翻译的程序称为源程序,书写该程序的语言称为源语言.12．目标语言（ObjectlanguageorTargetlanguage）和目标程序（ObjectprogramorTargetprogram）编译程序翻译源程序而得到的结果程序称为目标程序,书写该程序的语言称为目标语言.13．中间语言（中间表示）（Intermediatelanguage(representation)）在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统复杂性介于源程序语言和机器语言之间，容易将它翻译成目标代码。另外，还可以在中间代码一级进行与机器无关的优化。常见的中间代码形式有：逆波兰式、三元式、四元式、树形表示和三地址代码。14．文法（Grammars）文法是用于描述语言的语法结构的形式规则。文法G定义为四元组(VN，VT，P，S)。其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；产生式(规则)是形如α→β或a::=b的(a,b)有序对,其中α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*。VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。一个文法的例子:G=(VN={A，R},P={0,1}，P={A→0R，A→01,R→A1},S=A)15．文法分类（AhierarchyofGrammars）著名语言学家NoamChomsky定义了四类文法和四种形式语言类，文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制，分别是：0型文法(短语结构文法)(phrasestructuregrammars)：设G=(VN，VT，P，S)，如果它的每个产生式α→β是这样一种结构α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。1型文法（上下文有关文法）(context-sensitivegrammars)：设G=(VN，VT，P，S)为一文法|α|，若P中的每一个产生式α→β均满足|β|≥|α|，仅仅S→ε除外，则文法G是1型或上下文有关的。2型文法（上下文无关文法）(context-freegrammars)：设G=(VN，VT，P，S)，若P中的每一个产生式α→β满足：α是一非终结符，β∈(VN∪VT)*则此文法称为2型的或上下文无关的。3型文法（正规文法）(regulargrammars)：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。0型文法产生的语言称为0型语言。1型文法产生的语言称为1型语言，也称作上下文有关语言。2型文法产生的语言称为2型语言，也称作上下文无关语言。3型文法产生的语言称为3型语言，也称作正规语言。16．句型（Sententialform），句子（Sentence）和语言（Language）设G［S］是一文法，如果符号串x是从识别符号推导出来的，即有Sx，则称x是文法G［S］的句型。若x仅由终结符号组成，即Sx，x∈VT*，则称x为G［S］的句子。文法G所产生的语言定义为集合｛x｜Sx，其中S为文法识别符号，且x∈VT*｝。可用L(G)或L(G[S])表示该集合。17．推导（Derive）和语法树（Parsetree）推导的概念：分别定义V*中的符号之间的关系直接推导、长度为n（n≥1）的推导和长度为n（n≥0）的推导：（1）如α→β是文法G=(VN，VT，P，S)的规则（或说是P中的一个产生式），γ和δ是V*中的任意符号，若有符号串v，w满足：v＝γαδ，w＝γβδ则说v（应用规则α→β）直接产生w，或说，w是v的直接推导，或说，w直接归约到v，记做vw。（2）如果存在直接推导的序列：vw0w1w2…wnw，（n0）则称v推导出（产生）w（推导长度为n），或称w归约到v。记作vw。（3）若有vw，或v＝w，则记作。语法树（推导树）的概念：给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：①每个结点都有一个标记，此标记是V的一个符号。②根的标记是S。③若一个结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中。④如果结点n的直接子孙，从左到右的次序是结点n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式。18．二义文法（Ambiguousgrammer）如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义的。19．短语，句柄(phrase,sentencehandle)令G是一文法，S是文法的开始符号，αβδ是文法G的一个句型。如果有：且则称β是句型αβδ相对与非终结符A的短语。特别，如有则称β是句型αβδ相对于规则A→β的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。20．正规式（regularexpression）和它所表示的正规集（regularset）设字母表为Σ,辅助字母表Σ’=｛Φ,ε，｜，.，*,(,)｝。1.ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和Φ；2.任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；3.假定е1和е2都是Σ上的正规式，它们所表示的正规集分别为L(е1)和L(е2)，那么，(е1)，е1｜е2，е1·е2和е2*也都是正规式，它们所表示的正规集分别为L(е1)，L(е1)∪L(е2)，L(е1)L(е2)和(L(е1))*。4.仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。21．确定的有穷状态自动机DFA(deterministicfiniteautomaton)和不确定的有穷状态自动机NFA(nondeterministicfiniteautomaton)我们这里是把DFA和NFA作为正规集的识别工具而介绍的。DFA定义如下：一个确定的有穷自动机(DFA)M是一个五元组：M=(K,Σ，f，S，Z)其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入字符,所以也称Σ为输入符号字母表;3.f是转换函数，是在K×Σ→K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称作ki的一个后继状态;4.S∈K是唯一的一个初态；5.ZK，是一个终态集，终态也称可接受状态或结束状态。NFA定义如下;一个不确定的有穷自动机(NFA)M是一个五元组，M=(K,Σ，f，S，Z)其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入字符；3.f是一个从K×Σ*到K的子集的映像.4.SK，是一个非空初态集;5.ZK，是一个终态集。DFA和NFA的等价定理：对于每个NFAM，存在一个DFAM’，使得L（M）＝L（M’），即M和M’是等价的。22．最小状态DFA(reducedDFAorminimumDFA)我们说一个确定的有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的，这种DFA也叫做最小状态DFA。一个DFA可以通过消除多余状态和合并等价状态而转换成一个与之等价的最小状态DFA。24．FIRST集设G=(VN，VT，P，S)是上下文无关文法FIRST(α)=｛a｜，a∈VT，α,β∈V*｝若，则规定∈FIRST(α)。25．FOLLOW集设G=(VN，VT，P，S)是上下文无关文法，A∈VN，Ｓ是开始符号FOLLOW(A)=｛a｜且a∈VT，a∈FIRST(β)，μ∈VT*，β∈V+｝若，且，则#∈FOLLOW(A)。也可定义为：FOLLOW(A)={a|…Aa…,a∈VT}若有…A，则规定#∈FOLLOW(A)这里我们用‘＃’作为输入串的结束符，或称为句子括号，如：＃输入串＃。26．SELECT集给定上下文无关文法的产生式A→αA∈VN，α∈V*，若，则SELECT(A→α)=FIRST(α)如果，则SELECT(A→α)=FIRST(α)∪FOLLOW(A)。27．左递归文法（Leftrecursivegrammar）一个文法含有下列形式的产生式时。a)A→AβA∈VN，β∈V*b)A→BβB→ＡαA,B∈VN，α、β∈V*在a)中也可称为含有左递归的规则或称直接左递归，在b)中为AＡ…称文法中含有左递归或间接左递归，文法中只要含有a)或含有b)或二者皆有均认为文法是左递归的。28．LL（1）文法满足如下条件的上下文无关文法称为LL（1）文法：对每个非终结