| 现在广泛使用的各种程序语言都需要翻译，才能在计算机上运行，编译和解释是两种基本的编程语言翻译方式，对应的程序分别称为编译程序（编译器）和解释程序（解释器）。
|
|
|
|
|
| 编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（形式为汇编语言程序或机器语言程序）。编译程序的工作过程可以分为6个阶段，如下图所示。实际的编译器中可能会将其中的某些阶段结合在一起进行处理。下面简要介绍各阶段实现的主要功能。
|
|
|
|
|
|
|
|
|
| 词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。源程序可以被看成是一个多行的字符串。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（标点符号、左右括号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词种类和单词自身的值。
|
|
|
| 词法分析过程依据的是语言的词法规则，即描述“单词”结构的规则。例如，对于某PASCAL源程序中的一条声明语句和赋值语句：
|
|
|
|
|
| 词法分析阶段将构成这条语句的字符串分割成如下的单词序列。
|
|
|
|
|
|
|
|
|
| （10）标识符X（11）赋值号:=（12）标识符Y
|
|
|
|
|
|
|
| 对于标识符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进行语法分析后形成的语法树如下图所示。
|
|
|
|
|
|
|
|
|
| 语义分析阶段主要分析程序中各种语法结构的语义信息，包括检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能被翻译成正确的目标代码。
|
|
|
| 语义分析的一个主要工作是进行类型分析和检查。程序设计语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。
|
|
|
| 在确认源程序的语法和语义之后，就可对其进行翻译，同时改变源程序的内部表示。对于声明语句，需要记录所遇到的符号的信息，因此应进行符号表的填查工作。在下图（a）所示的符号表中，每行存放一个符号的信息。第一行存放标识符X的信息，其类型为real，为它分配的逻辑地址是0；第二行存放Y的信息，其类型为real，为它分配的逻辑地址是4。对于可执行语句，则检查结构合理的语句是否有意义。对语句id1：=id2+id3*60进行语义分析后的语法树如下图（b）所示，其中增加了一个语义处理结点inttoreal，用于将一个整型数转换为浮点数。
|
|
|
|
|
|
|
|
|
| 中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。中间代码的设计原则主要有两点：一是容易生成，二是容易被翻译成目标代码。最常用的一种中间代码是与汇编语言的指令非常相似的三地址码，其实现方式常采用四元式。四元式的形式为：
|
|
|
|
|
| 例如，对语句X：=Y+Z*60，可生成以下四元式序列：
|
|
|
|
|
|
|
|
|
|
|
| 其中，t1、t2、t3是编译过程中形成的临时变量，用于存放中间运算结果。
|
|
|
|
|
|
|
| 由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在计算时间上和存储空间上有很大的浪费。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。由于中间代码是不依赖于具体机器的，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。例如，在生成语句X：=Y+Z*60的四元式后，60是编译时已知的常数，把它转换为60.0的工作可以在编译时完成，没有必要生成一个四元式，同时t3仅仅用来将其值传递给id1，也可以化简掉，因此上述的中间代码可优化成下面的等价代码：
|
|
|
|
|
|
|
| 这只是优化工作中的一个简单示例，真正的优化工作还要涉及公共子表达式的提取、循环优化等更多的内容和技术。
|
|
|
|
|
| 目标代码生成是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。例如，使用两个寄存器R1和R2，可对上述的四元式生成下面的目标代码：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
|
|
|
|
|
| 用户编写的源程序不可避免地会有一些错误，这些错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标越界等错误。静态错误是指编译时所发现的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误称为语法错误；而语义分析时发现的运算符与运算对象类型不匹配等错误属于静态语义错误。
|
|
|
| 在编译时发现程序中的错误后，编译程序应采用适当的策略修复它们，使得分析过程能够继续下去，以便在一次编译过程中尽可能多地找出程序中的错误。
|
|
|
| 对于编译过程的各个阶段，在逻辑上可以把它们划分为前端和后端两部分。前端包括从词法分析到中间代码生成各阶段的工作，后端包括中间代码优化和目标代码的生成及优化等阶段。以中间代码为分水岭，把编译器分成了与机器有关的部分和与机器无关的部分。如此一来，对于同一种程序设计语言的编译器，开发出一个前端之后，就可以针对不同的机器开发相应的后端，前后端有机结合后就形成了该语言的一个编译器。当语言有改动时，只会涉及前端部分的维护。对于不同的程序设计语言，分别设计出相应的前端，然后将各个语言的前端与同一个后端相结合，就可得到各个语言在某种机器上的编译器。
|
|
|
|
|
| 词法分析过程的本质是对构成源程序的字符串进行分析，是一种对象为字符串的运算。语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
|
|
|
|
|
| （1）字母表∑：元素的非空有穷集合。例如，∑={a，b}。
|
|
|
| （2）字符：字母表∑中的一个元素。例如，∑上的a或b。
|
|
|
| （3）字符串：字母表∑中字符组成的有穷序列。例如，a、ab、aaa都是∑上的字符串。
|
|
|
| （4）字符串的长度：字符串中的字符个数。例如，|aba|=3。
|
|
|
| （5）空串ε：由0个字符组成的序列。例如，|ε|=0。
|
|
|
| （6）连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表∑上的任意字符串S，S·ε=ε·S=S。
|
|
|
|
|
| （8）∑*：指包括空串ε在内的∑上所有字符串的集合。例如，设∑={a，b}，∑*={ε，a，b，aa，bb，ab，ba，aaa，…｝。
|
|
|
| （9）字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αn。α0=ε，αn=ααn-1=αn-1α（n>0）。
|
|
|
| （10）字符串集合的运算：设A、B代表字母表∑上的两个字符串集合。
|
|
|
|
|
|
|
| .幂：An=A·An-1=An-1·A（n>0），并规定A0={ε}。
|
|
|
|
|
| .闭包*：A*=A0∪A+。显然，∑*=∑0∪∑1∪∑2∪…
|
|
|
|
|
| 词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
|
|
|
| 对于字母表∑，其上的正规式（正则表达式）及其表示的正规集可以递归定义如下。
|
|
|
| （1）ε是一个正规式，它表示集合L（ε）={ε}。
|
|
|
| （2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为L（a）={a}。
|
|
|
| （3）若正规式r和s分别表示正规集L（r）和L（s），则：
|
|
|
|
|
|
|
|
|
|
|
| 仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
|
|
|
| 运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。
|
|
|
| 设∑={a，b}，在下表中列出了∑上的一些正规式和相应的正规集。
|
|
|
|
|
|
|
| 若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。
|
|
|
|
|
| 有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为两类：确定的有限自动机和不确定的有限自动机。
|
|
|
| （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是弧上的标记。
|
|
|
| 例如，DFAM1=（{s0，s1，s2，s3}，{a，b}，f，s0，{s3}），其中f为：
|
|
|
| f（s0，a）=s1，f（s0，b）=s2，f（s1，a）=s3，f（s1，b）=s2，f（s2，a）=s1，f（s2，b）=s3，f（s3，a）=s3
|
|
|
| 与DFAM1对应的状态转换图如下图（a）所示，其中，状态s3表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示，矩阵元素M[A，a]的行下标表示状态，列下标表示输入字符，M[A，a]的值是当前状态为A、输入字符为a时，应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图（b）所示。在转换矩阵中，一般以第一行的行下标对应的状态作为初态，而终态则需要特别指出。
|
|
|
|
|
|
|
| 对于∑中的任何字符串ω，若存在一条从初态结点到某一终止状态结点的路径，且这条路径上所有弧的标记符连接成的字符串等于ω，则称ω可由DFAM识别（接受或读出）。若一个DFAM的初态结点同时又是终态结点，则空字ε可由该DFA识别（或接受）。DFAM所能识别的语言L（M）={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。
|
|
|
| 例如，对于字符串"ababaa"，在上图（a）所示的状态转换图中，识别"ababaa"的路径是s0→s1→s2→s1→s2→s1→s3。由于从初态结点s0出发，存在到达终态结点s3的路径，因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“，从初态结点s0出发，经过路径s0→s1→s2→s1→s2，当串结束时还没有到达终态结点s3；而对于串"baab"，经过路径s0→s2→s1→s3，虽然能到达终态结点s3，但串尚未结束又不存在与下一字符"b"相匹配的状态转换。
|
|
|
| （2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下。
|
|
|
| ①f是S×∑→2s上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。
|
|
|
|
|
| 例如，已知有NFAN=（{s0，s1，s2，s3}，{a，b}，f，s0，{s3}），其中f为：
|
|
|
| f（s0，a）=s0，f（s0，a）=s1，f（s0，b）=s0，f（s1，b）=s2，f（s2，b）=s3
|
|
|
| 与NFAM2对应的状态转换图和状态转换矩阵如下图所示。
|
|
|
|
|
|
|
| 显然，DFA是NFA的特例。实际上，对于每个NFAM，都存在一个DFAN，且L（M）=L（N）。
|
|
|
| 词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号，然后构造相应有限自动机的状态转换图，最后依据状态转换图编写词法分析器（程序）。
|
|
|
|
|
| 程序设计语言的语法常采用上下文无关文法描述。文法不仅规定了单词如何组成句子，而且刻画了句子的组成结构。形式文法是一个规则（或称产生式）系统，它规定了单词在句子中的位置和顺序，也描述了句子的层次结构。
|
|
|
| 下面以一个简单算术表达式的文法为例进行说明，其中，E代表算术表达式。
|
|
|
|
|
|
|
|
|
| D→0|1|2|3|4|5|6|7|3|4|5|6（4）
|
|
|
|
|
| “→”读作“定义为”，上述产生式规定简单算术表达式的运算符号为“加（+）”“乘（*）”，运算符号写在运算对象的中间，运算对象是非负整数，“乘”运算的优先级高于“加”运算，表达式或运算对象可加括号。
|
|
|
| 有了以上文法，对于算术表达式2+3*4，其结构可从上面的文法推导得出，如下图（a）所示（分析树），简化的语法树如下图（b）所示。
|
|
|
|
|
|
|
| 有关语法分析以及编译过程后续阶段的工作较为复杂，兹不赘述。
|
|
|
|
|
| 解释程序是另一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的内部形式。因此，解释程序不产生源程序的目标程序，这是它和编译程序的主要区别。下图显示了以解释方式实现高级语言的三种方式。
|
|
|
|
|
|
|
| 源程序被直接解释执行的处理方式如上图中的标记A所示。这种解释程序对源程序进行逐个字符的检查，然后执行程序语句规定的动作。
|
|
|
|
|
|
|
| 解释程序就开始搜索源程序中标号L后面紧跟冒号“：”的出现位置。这类解释程序通过反复扫描源程序来实现程序的运行，效率很低。
|
|
|
| 解释程序也可以先将源程序转换成某种中间代码形式，然后对中间代码进行解释来实现用户程序的运行，这种翻译方式如上图中的标记B和C所示。通常，在中间代码和高级语言的语句间存在一一对应的关系。解释方式B和C的不同之处在于中间代码的级别，在方式C下，解释程序采用的中间代码更接近于机器语言。在这种实现方案中，高级语言和低级中间代码间存在着“1：n”的对应关系。PASCAL-P解释系统是这类解释程序的一个实例，它在词法分析、语法分析和语义分析的基础上，先将源程序翻译成P-代码，再由一个非常简单的解释程序来解释执行这种P-代码。这类系统具有比较好的可移植性。
|
|
|
| 下面简要描述解释程序的基本结构。这类系统通常可以分成两部分：第一部分是分析部分，包括与编译过程相同的词法分析、语法分析和语义分析程序，经语义分析后把源程序翻译成中间代码，中间代码常采用逆波兰表示形式。第二部分是解释部分，用来对第一部分产生的中间代码进行解释执行。下面简要介绍第二部分的工作原理。
|
|
|
| 设用数组MEM模拟计算机的内存，源程序的中间代码和解释部分的各个子程序都存放在数组MEM中。全局变量PC是一个程序计数器，它记录了当前正在执行的中间代码的位置。这种解释部分的常见结构可以由下面两部分组成。
|
|
|
|
|
| （2）执行位于opcode-table[MEM[PC]]的子程序（解释子程序执行后返回到前面）。用一个简单例子来说明其工作原理。设两个实型变量A和B进行相加的中间代码是：
|
|
|
|
|
| 其中，中间代码Ipush和Iaddreal实际上都是opcode-table表的索引值（即位移），而该表的单元中存放着对应的解释子程序的起始地址，A和B都是MEM中的索引值。解释部分开始执行时，PC的值为start-1。
|
|
|
|
|
|
|
|
|
| 其中，stackreal()表示把相应值压入栈中，而popreal()表示取得栈顶元素值并弹出栈顶元素。上面的解释部分基于栈实现了将两个数值相加并将结果存入栈中的处理。
|
|
|
| 对于高级语言的编译和解释翻译方式，可从以下几个方面进行比较。
|
|
|
|
|
| 一般情况下，在解释方式下运行程序时，解释程序可能需要反复扫描源程序。例如，每一次引用变量都要进行类型检查，甚至需要重新进行存储分配，从而降低了程序的运行速度。在空间上，以解释方式运行程序需要更多的内存，因为系统不但需要为用户程序分配运行空间，而且要为解释程序及其支撑系统分配空间。
|
|
|
| 在编译方式下，编译程序要生成源程序的目标代码并进行优化，该过程比解释方式需要更多的时间。虽然与仔细写出的机器程序相比，一般由编译程序创建的目标程序运行的时间更长，需要占用的存储空间更多，但源程序只需要被编译程序翻译一次，就可以多次运行。因此总体来讲，编译方式比解释方式可能取得更高的效率。
|
|
|
| （2）灵活性。由于解释程序需要反复检查源程序，这也使得解释方式能够比编译方式更灵活。当解释器直接运行源程序时，“在运行中”修改程序就成为可能，例如增加语句或者修改错误等。另外，当解释器直接在源程序上工作时，它可以对错误进行更精确地定位。
|
|
|
| （3）可移植性。源程序是由解释器控制来运行的，可以提前将解释器安装在不同的机器上，从而使得在新环境下无需修改源程序使之运行。而编译方式下则需要针对新机器重新生成源程序的目标代码才能运行。
|
|
|
| 由于编译方式和解释方式各有特点，因此现在的一些编译系统既提供编译的方式，也提供解释的方式，甚至将两种方式结合在一起。例如，在Java虚拟机上发展的一种compiling-just-in-time技术，就是当一段代码第一次运行时进行编译，其后运行时就不再进行编译了。
|
|
|
