|
|
| 编译程序的作用是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言形式）。编译程序的工作过程一般可以分为6个阶段，如下图所示，实际的编译器中可能会将其中的某些阶段结合在一起进行处理。下面简要介绍各阶段实现的主要功能。
|
|
|
|
|
|
|
|
|
| 源程序可以简单地被看成是一个多行的字符串。词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（如标点符号、左右括号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词类别和单词自身的值。
|
|
|
| 词法分析过程依据的是语言的词法规则，即描述“单词”结构的规则。例如，对于某Pascal源程序中的一条声明语句和赋值语句：
|
|
|
|
|
| 词法分析阶段将构成这条语句的字符串分割成如下17个单词序列：
|
|
|
|
|
| 对于标识符X、Y、Z，其单词类别都是id（用户标识符），字符串"X""Y""Z"都是单词的值；而对于单词60，整常数是该单词的类别，60是该单词的值。这里用id1、id2和id3分别代表X、Y和Z，强调标识符的内部标识由于组成该标识符的字符串不同而有所区别。经过词法分析后，声明语句VAR X，Y，Z：real；表示为VAR id1，id2，id3：real，赋值语句X:=Y+Z*60；表示为id1:=id2+id3*60；。
|
|
|
|
|
| 语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”“程序”等。语法规则就是各类语法单位的构成规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树；否则就指出语法错误，并给出相应的诊断信息。对id1:=id2+id3*60进行语法分析后形成的语法树如下图所示。
|
|
|
|
|
|
|
| 词法分析和语法分析本质上都是对源程序的结构进行分析。
|
|
|
|
|
| 语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能翻译成正确的目标代码。
|
|
|
| 语义分析的一个主要工作是进行类型分析和检查。程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。
|
|
|
| 在确认源程序的语法和语义之后，就可对其进行翻译并给出源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，所以应进行符号表的填查工作。在下图所示的符号表中，每一行存放一个符号的信息。第一行存放标识符X的信息，其类型为real，为它分配的地址是0；第二行存放Y的信息，其类型是real，为它分配的地址是4。因此，在该语言中，为一个real型数据分配的存储空间是4个存储单元。对于可执行语句，则检查结构合理的表达式是否有意义。对id1:=id2+id3*60进行语义分析后的语法树如下图所示，其中增加了一个语义处理节点inttoreal，该运算用于将一个整型数转换为浮点数。
|
|
|
|
|
|
|
|
|
| 中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码，其实现方式常采用四元式。四元式的形式为：
|
|
|
|
|
| 例如，对语句X:=Y+Z*60，可生成以下四元式序列：
|
|
|
|
|
| 其中，t1、t2、t3是编译程序生成的临时变量，用于存放临时的运算结果。
|
|
|
|
|
|
|
| 优化是一个编译器的重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间方面的效率较差。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。由于中间代码不依赖于具体机器，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。例如，在生成X:=Y+Z*60的四元式后，60是编译时已知的常数，把它转换为60.0的工作可以在编译时完成，没有必要生成一个四元式，同时t3仅仅用来将其值传递给idl，也可以化简掉，因此上述的中间代码可转优化成下面的等价代码：
|
|
|
|
|
| 这只是优化工作中的一个简单示例，真正的优化工作要复杂得多。
|
|
|
|
|
| 目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。例如，使用两个寄存器R1和R2，可对上述的四元式生成下面的目标代码：
|
|
|
|
|
|
|
|
|
| 符号表的作用是记录源程序中各符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
|
|
|
|
|
| 源程序中不可避免地会有一些错误，这些错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标错误等。静态错误是指编译阶段发现的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误称为语法错误，而语义分析时发现的运算符与运算对象类型不合法等错误属于静态语义错误。
|
|
|
| 在编译时发现程序中的错误后，编译程序应采用适当的策略修复它们，使得分析过程能够继续下去，以便在一次编译过程中尽可能多地找出程序中的错误。
|
|
|
| 对于编译器的各个阶段，在逻辑上可以把它们划分为前端和后端两部分。前端包括从词法分析到中间代码生成各阶段的工作，后端包括中间代码优化和目标代码的生成及优化等阶段。这样，以中间代码为分水岭，把编译器分成了与机器有关的部分和与机器无关的部分。如此一来，对于各种程序语言可以开发各自的编译器前端，针对指令系统和体系结构都不同的各种处理器开发相应的后端，最后将每种程序语言的前端与各种处理器的后端有机结合，就形成了每种语言在各种处理器上的编译器。这样，当语言有改动时，只需要修改其编译器的前端部分，如果处理器有改变，仅替换该语言的编译器后端即可。
|
|
|
|
|
| 语言L是有限字母表Σ上有限长度字符串的集合，这个集合中的每个字符串都是按照一定的规则生成的。下面从产生语言的角度出发，给出文法和语言的形式定义。所谓产生语言，是指制定出有限个规则，借助它们就能产生此语言的全部句子。
|
|
|
|
|
| .字母表Σ和字符：字母表是字符的非空有穷集合，字符是字母表Σ中的一个元素。例如Σ=｛a，b｝，a或b是字符。
|
|
|
| .字符串：Σ中的字符组成的有穷序列。例如a，ab，aba，aaaa都是Σ的字符串。
|
|
|
| .字符串的长度：指字符串中的字符个数。如｜aba｜=3。
|
|
|
|
|
| .连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表Σ的任意字符串S，S·ε=ε·S=S。
|
|
|
| .Σ*：是指包括空串ε在内的Σ上所有字符串的集合。例如，设Σ=｛a，b｝，Σ*=｛ε，a，b，aa，bb，ab，ba，aaa，…｝。
|
|
|
| .字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αn。α0=ε，αn=ααn-1=αn-1α（n>0）。
|
|
|
| .字符串集合的运算：设A，B代表字母表Σ上的两个字符串集合。
|
|
|
 或（合并）：A∪B=｛α｜α∈A或α∈B｝。
|
|
|
 积（连接）：AB=｛αβ｜α∈A且β∈B｝。
|
|
|
 幂：An=A·An-1=An-1：A（n>0），并规A0=｛ε｝。
|
|
|
 正则闭包＋：A+=A1∪A2∪A3∪…∪An∪…。
|
|
|
 闭包*：A*+A0∪A+。显然，Σ*=Σ0∪Σ1∪Σ2∪…∪Σn∪…。
|
|
|
|
|
| 描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为G=（VN，VT，P，S）。其中VT是一个非空有限集，其每个元素称为一个终结符；VN是一个非空有限集，其每个元素称为非终结符。VN∩VT=Φ，即VN和VT不含公共元素。令V=VN∪VT，称V为文法G的词汇表，V中的符号称为文法符号，包括终结符和非终结符。S∈VN，称为开始符号，它至少要在一条产生式中作为左部出现。P是产生式的有限集合，每个产生式形如“α→β”。其中，α称为产生式的左部，α∈V+且α中至少含有一个非终结符；β称为产生式的右部，且β∈V*。若干个产生式α→β1，α→β2，…，α→βn的左部相同时，可简写为α→β1｜β2｜…｜βn，称βi（1≤i≤n）为α的一个候选式。
|
|
|
| （1）文法的分类。乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法G=（VN，VT，P，S）的每个产生式α→β，均有α∈（VN∪VT）*，α至少含有一个非终结符，且β∈（VN∪VT）*，则称G为0型文法。对0型文法的每条产生式分别施加以下限制，则可得以下文法：
|
|
|
| .1型文法：G的任何产生式α→β（S→ε除外）均满足｜α｜≤｜β｜（｜x｜表示x中文法符号的个数）。
|
|
|
| .2型文法：G的任何产生式形如A→β，其中A∈VN，β∈（VN∪VT）*。
|
|
|
| .3型文法：G的任何产生式形如A→a或A→aB（或者A→Ba），其中A，B∈VN，a∈VT。
|
|
|
| 0型文法也称为短语文法，其能力相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法，它意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串。例如，若αAβ→αγβ是1型文法的产生式，α和β不全为空，则非终结符A只有在左边是α，右边是β的上下文中才能替换成γ。2型文法就是上下文无关文法，其非终结符的替换无需考虑上下文。3型文法等价于正规式，因此也被称为正规文法或线性文法。
|
|
|
| 若文法G1与文法G2产生的语言相同，即L（G1）=L（G2），则称这两个文法是等价的。
|
|
|
| （2）句子和语言。设有文法G=（VN，VT，P，S）。
|
|
|
.推导与直接推导：推导就是从文法的开始符号S出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列（展开产生式用 表示），直到产生一个终结符的序列时为止。若有产生式α→β∈P，且γ，δ∈V*，则 称为文法G中的一个直接推导，并称γαδ可直接推导出γβδ。显然，对P中的每一个产生式α→β都有 。若在文法中存在一个直接推导序列，即 ，则称α0可推导出αn，αn是α0的一个推导，并记为 。用记号 表示α0=αn或者。
|
|
|
.直接归约和归约：归约是推导的逆过程。若文法G中有一个直接推导 ，则称β可直接归约成α，或α是β的一个直接归约。若文法G中有一个推导 ，则称δ可归约成γ，或γ是δ的一个归约。
|
|
|
.句型和句子：若文法G的开始符号为S，那么，从开始符号S能推导出的符号串称为文法的一个句型，即α是文法G的一个句型，当且仅当有如下推导 ，α∈V*。若X是文法G的一个句型，且 ，则称X是文法G的一个句子，即仅含终结符的句型是一个句子。
|
|
|
| .语言：从文法G的开始符号出发，能推导出的句子的全体称为文法G产生的语言，记为L（G）。
|
|
|
|
|
| 语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
|
|
|
|
|
| 对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：
|
|
|
| （1）ε是一个正规式，它表示集合L（ε）=｛ε｝。
|
|
|
| （2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为｛a｝。
|
|
|
| （3）若正规式r和s分别表示正规集L（r）和L（s），则：
|
|
|
|
|
|
|
|
|
|
|
| 仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式，其中运算符“｜”“.”“*”分别称为“或”“连接”“闭包”。在正规式的书写中，连接运算符“.”可省略。运算符的优先级从高到低顺序排列为“*”“.”“｜”。
|
|
|
| 设∑=｛a，b｝，下表列出了∑上的一些正规式和相应的正规集。
|
|
|
|
|
|
|
| 若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a｜b）*=（a*b*）*。设U、V和W均为正规式，正规式的代数性质如下表所示。
|
|
|
|
|
|
|
|
|
| 有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
|
|
|
| （1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是一个五元组（S，Σ，f，s0，Z），其中：
|
|
|
|
|
| .Σ是一个有穷字母表，其每个元素称为一个输入字符。
|
|
|
| .f是S×Σ→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
|
|
|
|
|
.Z是非空的终止状态集合， 。
|
|
|
| 一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
|
|
|
| （2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下：
|
|
|
| ①f是S×Σ→2S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
|
|
|
|
|
|
|
| 任何一个NFA都可以转换为DFA，下面先定义转换过程中需要的计算。
|
|
|
|
|
| 若I是NFAN的状态集合的一个子集，定义ε_CLOSURE（I）如下：
|
|
|
| .状态集I的ε_CLOSURE（I）是一个状态集。
|
|
|
| .状态集I的所有状态属于ε_CLOSURE（I）。
|
|
|
| .若s∈I，那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE（I）。
|
|
|
|
|
| 由以上的定义可知，I的ε_闭包就是从状态集I的状态出发，经ε所能到达的状态的全体。
|
|
|
|
|
| 假定I是NFAN的状态集的一个子集，a是Σ中的一个字符，定义：
|
|
|
|
|
| 其中，J是所有那些可从I中的某一状态节点出发经过一条a弧而到达的状态节点的全体。
|
|
|
|
|
| 设NFAN=（S，Σ，f，s0，Z），与之等价的DFAM=（S'，Σ，f'，q0，Z'），用子集法将非确定的有限自动机确定化的算法步骤如下：
|
|
|
| ①求出DFAM的初态q0，即令q0=ε_CLOSURE（｛s0｝），此时S'仅含初态q0，并且没有标记。
|
|
|
| ②对于S'中尚未标记的状态qi=｛si1，si2，…，sim｝，sij∈S（j=1，…，m）进行以下处理：
|
|
|
|
|
| .对于每个a∈∑，令T=f（｛si1，si2，…，sim｝，a），qj=ε_CLOSURE（T）。
|
|
|
| .若qj尚不在S'中，则将qj作为一个未加标记的新状态添加到S'，并把状态转换函数f'（qi，a）=qj添加到DFAM中。
|
|
|
| ③重复进行步骤②，直到S'中不再出现未标记的状态时为止。
|
|
|
|
|
|
|
|
|
| 对上图所示的自动机进行化简所得的DFA如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
| 对于Σ上的NFAM，可以构造一个Σ上的正规式R，使得L（R）=L（M）。
|
|
|
| 拓广状态转换图的概念，令每条弧可用一个正规式作标记。为Σ上的NFAM构造相应的正规式R，分为如下两步：
|
|
|
| 第一步：在M的状态转换图中加两个节点，一个x节点，一个y节点。从x节点到NFAM的初始状态节点引一条弧并用ε标记，从NFAM的所有终态节点到y节点引一条弧并用ε标记。形成一个与M等价的M'，M'只有一个初态x和一个终态y。
|
|
|
| 第二步：按下面的方法逐步消去M'中除x和y的所有节点。在消除节点的过程中，用正规式来标记弧，最后节点x和y之间弧上的标记就是所求的正规式。消除节点的规则如下图所示。
|
|
|
|
|
|
|
|
|
| 同样地，对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L（M）=L（R）。
|
|
|
|
|
|
|
|
|
| ②通过对正规式R进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。
|
|
|
|
|
|
|
| 最后所得的图即为一个NFAM，x为初态节点，y为终态节点。显然，L（M）=L（R）。
|
|
|
|
|
| 构造词法分析器的一般步骤为：用正规式描述语言中的单词构成规则；为每个正规式构造一个NFA，它识别正规式所表示的正规集；将构造出的NFA转换成等价的DFA；对DFA进行最小化处理，使其最简；最后用手工编码或表驱动的方式从最简DFA构造词法分析器。
|
|
|
|
|
| 语法分析的任务是根据语言的语法规则，分析单词串是否构成短语和句子，即是否为合法的表达式、语句和程序等基本语言结构，同时检查和处理程序中的语法错误。程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。语法分析方法有多种，根据产生语法树的方向，可分为自底向上（或自下而上）和自顶向下（或自上而下）两类。
|
|
|
|
|
| 上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法G［S］=（VN，VT，P，S），其产生式的形式都是A→β，其中A∈VN，β∈（VN∪VT）*。
|
|
|
| 若不加特别说明，下面用大写英文字母A、B、C等表示非终结符，小写英文字母a、b、c等表示终结符号，u、v、w等表示终结符号串，小写希腊字母α、β、γ、δ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以简写为其产生式集合的描述形式。
|
|
|
（1）规范推导（最右推导）。如果在推导的任何一步 其中α、β是句型），都是对α中最右边的非终结符进行替换，则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
|
|
|
（2）短语、直接短语和句柄。设αδβ是文法G的一个句型，即 ，且满足 和 ，则称δ是句型αδβ相对于非终结符A的短语。特别地，如果有 ，则称δ是句型αδβ相对于产生式A→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。
|
|
|
|
|
| 自顶向下分析法的基本思想是：对于给定的输入串ω，从文法的开始符号S出发进行最左推导，直到得到一个合法的句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右地为输入串ω建立语法树。整个分析过程是一个试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。若输入串是给定文法的句子，则必能成功，反之必然出错。
|
|
|
| 文法中存在下述产生式时，自顶向下分析过程中会出现下面的问题：
|
|
|
| （1）若文法中存在形如A→αβ｜αδ的产生式，即A产生式中有多于一个候选项的前缀相同（称为公共左因子，简称左因子），则可能导致分析过程中的回溯处理。
|
|
|
| （2）若文法中存在形如A→Aα的产生式，由于采取了最左推导，可能会造成分析过程陷入死循环的情况，产生式的这种形式被称为左递归。
|
|
|
| 因此，需要对文法进行改造，消除其中的左递归，以避免分析陷入死循环；提取左因子，以避免回溯。
|
|
|
| （3）递归下降分析法。递归下降分析法直接以子程序调用的方法模拟产生式产生语言的过程，其基本思想是：为每一个非终结符构造一个子程序，每个子程序的过程体按该产生式候选项分情况展开，遇到终结符即进行匹配，而遇到非终结符则调用相应的子程序。该分析法从调用文法开始符号的子程序开始，直到所有非终结符都展开为终结符并得到匹配为止。若分析过程可以达到这一步，则表明分析成功，否则表明输入串中有语法错误。递归下降分析法的优点是简单且易于构造，缺点是程序与文法直接相关，对文法的任何改变都需要在程序中进行相应的修改。
|
|
|
| （4）预测分析法。预测分析法是另一种自顶向下的语法分析方法，其基本模型如下图所示。
|
|
|
|
|
|
|
| 预测分析法的核心是预测分析表，可以用一个二维数组M表示，其元素M［A，a］（A∈VN，a∈VT∪#）存放关于A的产生式，表明当遇到输入符号为a且用A进行推导时，所应采用的产生式；若M［A，a］为error，则表明推导时遇到了不该出现的符号，应进行出错处理。
|
|
|
| 例如，根据文法G［E］=｛E→TE'，E'→+TE'｜ε，T→FT'，T'→*FT'｜ε，F→（E）｜id｜｝的构造的预测分析表如下表所示。
|
|
|
|
|
|
|
| 预测分析法的工作过程是：初始时，将“#”和文法的开始符号依次压入栈中；在分析过程中，根据输入串中的当前输入符号a和当前的栈顶符号X进行处理。
|
|
|
| 若X=a='#'，则分析成功；若X='#'且a≠'#'，则出错。
|
|
|
| 若X∈VT且X=a，则X退栈，并读入下一个符号a；若X∈VT且X≠a，则出错。
|
|
|
| 若X∈VN且M［X，a］='A→α'，则X退栈，α中的符号从右到左依次进栈（ε无须进栈）；若M［X，a］='error'，则调用出错程序进行处理。
|
|
|
|
|
| 常用的自底向上分析方法也称移进-归约分析法，工作模型是下推自动机，如下图所示。其基本思想是对输入序列ω自左向右进行扫描，并将输入符号逐个移进一个栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串（即句柄）时，就用某个产生式的左部非终结符来替代，这称为一步归约。重复这一过程，直至栈中只剩下文法的开始符号且输入串也被扫描完时为止，确认输入串ω是文法的句子，表明分析成功；否则，进行出错处理。
|
|
|
|
|
|
|
| LR分析法是一种规范归约分析法。规范归约是规范推导（最右推导）的逆过程，下面举例说明规范归约的过程。
|
|
|
| LR分析法根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k≥0）符号，就可唯一确定分析器的动作是移进还是归约，以及用哪条产生式进行归约，因而也就能唯一地确定句柄。当k=1时，已能满足当前绝大多数高级语言编译程序的需求。常用的LR分析器有LR（0）、SLR（1）、LALR（1）和LR（1）。
|
|
|
|
|
| （1）驱动器。或称驱动程序。对所有LR分析器，驱动程序都是相同的。
|
|
|
| （2）分析表。不同的文法具有不同的分析表。同一文法采用不同的LR分析器时，分析表也不同。分析表又可分为动作表（ACTION）和状态转换表（GOTO）两个部分，它们都可用二维数组表示。
|
|
|
|
|
| 分析器的动作由栈顶状态和当前输入符号决定（LR（0）分析器不需向前查看输入符号），LR分析器的模型如下图所示。
|
|
|
|
|
|
|
| 其中SP为栈顶指针，Si为状态，Xi为文法符号。ACTION［Si，a］=Sj规定了栈顶状态为Si且遇到输入符号a时应执行的动作。状态转换表GOTO［Si，X］=Sj表示当状态栈顶为Si且文法符号栈顶为X时应转向状态Sj。
|
|
|
| LR分析器的工作过程以格局的变化来反映。格局的形式为（栈，剩余输入，动作）。分析是从某个初始格局开始的，经过一系列的格局变化，最终达到接受格局，表明分析成功；或者达到出错格局，表明发现一个语法错误。因此，开始格局的剩余输入应该是全部的输入序列，而接受格局中的剩余输入应该为空，任何其他格局或者出错格局中的剩余输入应该是全部输入序列的一个后缀。
|
|
|
|
|
| （1）移进（shift）。当ACTION［Si，a］=Sj时，把a移进文法符号栈并转向状态Sj。
|
|
|
| （2）归约（reduce）。当在文法符号栈顶形成句柄β时，把β归约为相应产生式A→β的非终结符A。若β的长度为r（即｜β｜=r），则弹出文法符号栈顶的r个符号，然后将A压入文法符号栈中。
|
|
|
| （3）接受（accept）。当文法符号栈中只剩下文法的开始符号S，并且输入符号串已经结束时（当前输入符是“#”），分析成功。
|
|
|
| （4）报错（error）。当输入串中出现不该有的文法符号时，就报错。
|
|
|
| LR分析器的核心部分是分析表的构造，这里不再详述。
|
|
|
|
|
| 程序语言的语义分为静态语义和动态语义。描述程序语义的形式化方法主要有属性文法、公理语义、操作语义和指称语义等，其中属性文法是对上下文无关文法的扩充。目前应用最广的静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予文法的产生式。在语法分析的推导或归约的步骤中，通过执行语义规则实现对属性的计算，以实现对语义的处理。
|
|
|
|
|
| 从原理上讲，对源程序进行语义分析之后就可以直接生成目标代码，但由于源程序与目标代码的逻辑结构往往差别很大，特别是考虑到具体机器指令系统的特点，要使翻译一次到位很困难，而且用语法制导方式机械生成的目标代码往往是烦琐和低效的，因此有必要设计一种中间代码，将源程序首先翻译成中间代码表示形式，以利于进行与机器无关的优化处理。由于中间代码实际上也起着编译器前端和后端的分水岭作用，所以使用中间代码也有助于提高编译程序的可移植性。常用的中间代码有后缀式、四元式和树等形式。
|
|
|
| （1）后缀式（逆波兰式）。逆波兰式是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用栈实现求值。对于表达式x:=（a+b）*（c+d），其后缀式为xab+cd+*:=。
|
|
|
| （2）树形表示。例如，表达式x:=（a+b）*（c+d）的树形表示如下图所示。
|
|
|
|
|
|
|
| （3）四元式表示。四元式是一种普遍采用的中间代码形式，其组成成分为运算符OP、第一运算对象ARG1、第二运算对象ARG2和运算结果RESULT。其中，运算对象和运算结果有时指用户自定义的变量，有时指编译程序引入的临时变量，RESULT总是一个新引进的临时变量，用来存放运算结果。例如，表达式x:=（a+b）*（c+d）的四元式表示为：
|
|
|
| ①（+，a，b，t1）②（+，c，d，t2）③（*，t1，t2，t3）④（：=，t3，_，x）
|
|
|
|
|
| 常见的程序语言结构主要有算术表达式、布尔表达式、赋值语句和控制语句（if、while）等。不同结构需要不同的处理方法，但翻译程序的构造原理是相似的。
|
|
|
| 对于各种语法结构的语法制导翻译，一般是在相应的语法规则中加入适当的语义处理，从而在对程序语句进行语法分析过程中的恰当时机同时完成语义处理，实现语义分析。
|
|
|
|
|
|
|
|
|
|
|
| 过程（函数）说明和过程（函数）调用是程序中一种常见的语法结构，绝大多数语言都含有这方面的内容。过程说明和调用语句的翻译，有赖于形参与实参结合的方式以及数据空间的分配方式。
|
|
|
| 由于各种语言的不同特点，在目标程序运行时，对存储空间的分配和组织有不同的要求，在编译阶段应产生相应的目标来满足不同的要求。需要分配存储空间的对象有基本数据类型（如整型、实型和布尔型等）、结构化数据类型（如数组和记录等）和连接数据（如返回地址、参数等）。分配的依据是名字的作用域和生存期的定义规则。分配的策略有静态存储分配和动态存储分配两大类。
|
|
|
| 如果在编译时就能确定目标程序运行时所需的全部数据空间的大小，则在编译时就安排好目标程序运行时的全部数据空间，并确定每个数据对象的存储位置（逻辑地址）。这种分配策略称为静态存储分配。Fortran语言的早期版本可以完全采用静态存储分配策略。
|
|
|
| 如果一个程序语言允许递归过程和动态可变数据结构，那么就需采用动态存储分配技术。动态存储分配策略的实现有栈分配方式和堆分配方式两种。在栈式动态存储分配中，将程序的数据空间设计为一个栈，每当调用一个过程时，它所需的数据空间就分配在栈顶；每当过程执行结束时，就释放这部分空间。若空间的使用未必服从“先申请后释放”的原则，那么栈式的动态存储分配方式就不适用了，这种情况下通常使用堆分配技术。
|
|
|
|
|
| 优化就是对程序进行等价变换，使得从变换后的程序能生成更有效的目标代码。所谓等价，是指不改变程序的运行结果；所谓有效，是指目标代码运行时间较短，占用的存储空间较少。优化可在编译的各个阶段进行。最主要的优化是在目标代码生成以前对中间代码进行的，这类优化不依赖于具体的计算机。
|
|
|
| 目标代码的生成由代码生成器实现。代码生成器以经过语义分析或优化后的中间代码为输入，以特定的机器语言或汇编代码为输出。代码生成所需考虑的主要问题如下所述：
|
|
|
| （1）中间代码形式。中间代码有多种形式，其中树与后缀表示形式适用于解释器，而编译器多采用与机器指令格式较接近的四元式形式。
|
|
|
| （2）目标代码形式。目标代码可以分为两大类：汇编语言形式和机器指令形式。机器指令形式的目标代码又可以根据需求的不同分为绝对机器指令代码和可再定位机器代码。绝对机器代码的优点是可以立即执行，一般应用于一类称为load-and-go形式的编译模式，即编译后立即执行，不形成保存在外存上的目标代码文件。可再定位机器代码的优点是目标代码可以被任意链接并装入内存的任意位置，是编译器采用较多的代码形式。汇编语言作为一种中间输出形式，便于进行分析和测试。
|
|
|
| （3）寄存器的分配。由于访问寄存器的速度远快于访问内存单元的速度，所以总是希望尽可能多地使用寄存器存储数据，而寄存器的个数是有限的，因此，如何分配及使用寄存器，是目标代码生成时需要着重考虑的。
|
|
|
| （4）计算次序的选择。代码执行的效率会随计算次序的不同有较大的差别。在生成正确目标代码的前提下，适当地安排计算次序并优化代码序列，也是生成目标代码时要考虑的重要因素之一。
|
|
|
