编译原理 第1章 编译系统概述

第1章编译系统概述1.1 程序设计语言的发展1.2 基本术语解释1.3 编译过程概述1.4 出错处理1.5 编译程序的前端和后端1.6 编译程序的实现方式1.1 程序设计语言的发展汇编语言(AssembleLanguage)机器语言(MachineLanguage)程序设计语言(ProgrammingLanguage)例计算表达式3*16+2的值，实现该计算的机器语言程序、汇编语言程序和程序设计语言（C语言）程序如下所示。目标计算机的系统结构和汇编语言的使用方法详见本书第7章。22038210260261011000f000LoadR0,3MulR0,10LoadR1,2AddR0,R1WriteR0Haltvoidmain(void){cout<<3*16+2;}注：10表示16㈠机器语言机器指令集合称为机器语言。机器指令即二进制数，通常由若干字节构成。①优点计算机可直接识别执行可充分利用硬件特性②缺点可读性差指令系统随机种而异由于机器指令直接或间接含有绝对地址，增加或减少一条指令，可能会引起多条指令的修改。编程者需协调内存的使用所以，机器语言形式的程序编制和维护困难，限制了计算机的推广和应用。㈡汇编语言用记忆符取代二进制位，存储地址和汇编语句的序号可用符号名表示。①优点用符号取代二进制数，提高了程序的可理解性。性能较好的汇编语言，可用符号名来表示存储地址和汇编语句序号，这样避免了在汇编语句中绝对地址的出现。可充分利用硬件特性所以，汇编语言在一定程度上降低了程序编制和维护的难度。②缺点汇编语句和机器指令基本上是一对一的，所以汇编语言的编程效率并没有质的提高。和机器语言一样，汇编语言依附于目标计算机。需汇编程序，将汇编语言译成机器语言。㈢程序设计语言程序设计语言又称高级语言。程序设计语言接近于英语，相当于工程语言。目前计算机系统一般含有多个程序设计语言的翻译程序（例VC、VB等），甚至对同一个程序设计语言配备了多个不同性能的翻译程序，供用户选择使用。①优点独立于具体计算机，面向过程（函数）或对象。程序设计语言接近于英语，可理解性好。数据类型丰富，各种功能的语句齐备，一条语句至少相当于几十条汇编语句。所以，程序设计语言极大地提高了编程效率，大幅度地降低了编程难度。②缺点需翻译程序，将高级语言译成机器语言或汇编语言。对硬件操作困难，高级语言通常提供汇编语言接口。1.2基本术语解释㈠源语言和源程序(SourceLanguageandSourceProgram)

用程序设计语言书写的程序，称为源程序，该程序设计语言称为源语言。源程序通常用编缉程序输入，用字符(ASCII码)表示，以文本文件形式存储。㈡文本文件(TextFile)

文本文件的内容由94个图形字符‘!’-‘~’(33-126)和4个控制字符换行(10)、回车(13)、空格(32)、TAB(9)构成，文本文件又称为ASCII码文件，扩展名通常为TXT，文件尾用控制字符EOF(26)指示。当换行和回车二个控制字符从文本文件读入内存，在C语言中是用一个字符（换行）表示。㈢目标语言和目标程序(TargetLanguageandTargetProgram)目标语言可以是机器语言(二进制数)，也可以是汇编语言(字符)，或者是其它中间语言(字符)，但最终结果必定是机器语言。机器语言程序用二进制文件存储，汇编语言或中间语言程序用文本文件存储。目标程序是经翻译程序加工后用目标语言表示的程序。㈣二进制文件(BinaryFile)二进制文件由机器指令即二进制数构成，因二进制数可能是26，故文件尾用文件长度(文件的字节数)指示，扩展名通常为EXE。㈤翻译程序(Translator)将源程序译成逻辑上等价的目标程序的程序。翻译程序有二种工作方式：编译和解释。解释程序Interpreter

源程序结果输入数据解释、执行解释方式主要特点是：用户程序是消极的。用户程序运行时，控制点在解释程序，即用户程序的执行离不开解释程序。①解释方式(Interpret)以源程序作为输入，输入一句解释执行一句，不产生完整的目标程序，相应的翻译程序称为解释程序(Interpreter)

。工作方式如下图所示：②编译方式(Compile)将源程序全部译为目标程序，该目标程序可在操作系统环境下直接执行，相应的翻译程序称为编译程序(Compiler)

，工作方式如下图所示：编译程序Compile连接程序Link装入运行Run编辑程序EditASCII码二进制(整体未定位)

二进制(整体定位)

源程序结果输入数据编辑程序的工作结果是ASCII码形式的源程序。编译程序以ASCII码形式的源程序为输入，它的工作结果是二进制形式的目标程序，但并未包括用户程序中所使用的系统函数的目标代码。从整体上来看，程序是不完整的，程序中的部分地址尚未确定（例系统函数的调用）。将二进制形式的用户程序和系统函数目标代码连接成一个程序，对未确定的地址进行定位。由操作系统将用户程序装入内存后运行。程序在运行过程中读入数据，经处理加工后输出计算结果。编译方式主要特点是：用户程序是积极的。用户程序执行时，控制点在用户程序自身。除操作系统外，程序运行无需其它支撑软件。③二种翻译方式比较解释方式和编译方式的主要区别是：目标代码的执行方式不同，基本原理和方法没有本质上的区别。1）解释方式的优点提供一种直接的交互调试功能，容易获得较好的动态调试效果。使用变量可不预先定义。变量性质可动态修改。2）解释方式的缺点在执行时需动态地对程序进行分析翻译，开销大，其执行速度相当于编译方式的1/10至1/100。解释方式占用内存大显然解释程序的优点就是编译程序的缺点，反之亦然，对于编译程序的优缺点不再重复叙述。④对任何一种高级语言，既可采用编译方式，也可采用解释方式，包括汇编语言在内（MASM方式和DEBUG方式）。1.3 编译过程概述典型的编译程序工作过程是：输入源程序，对它进行加工处理，最后输出目标程序（机器语言或汇编语言形式）。整个过程相当复杂，从数据加工的角度来看，可将其分成4个逻辑阶段，它们是：词法分析语法分析语义分析（中间代码产生）目标代码生成词法分析语法分析语义分析(中间代码产生)目标代码生成源程序目标程序编译程序基本上是按照这个流程来设计的。图示如下： 以算术表达式3+abc*128为例，来说明编译程序工作过程。㈠词法分析(LexicalAnalysis)执行词法分析任务的程序称为词法分析器。任务：字符串形式单词编码形式单词内部码（二元式）依据：语言的构词规则①二元式(Pair)(单词种别,单词值)单词种别：用整数码表示（为直观起见用字符表示），语法分析时用。单词值：在本书中用字符串表示，语义分析时用。当一个单词种别中可能有多个单词时，单词的值才有意义。为了便于输入处理，无意义的单词值用"NUL"表示。②二元式编码单词单词种别单词值++NUL--NUL**NUL//NUL((NUL))NUL………标识符i字符串形式符号名

整常数x字符串形式整常数实常数y字符串形式实常数………经词分析，算术表达式3+abc*128的单词内部码（二元式）为：('x',"3")('+',"NUL")('i',"abc")('*',"NUL")('x',"128")㈡语法分析(Parsing)执行语法分析任务的程序称为语法分析器。任务：检查源程序的语法结构是否正确依据：语言的语法规则在语法分析时，算术表达式3+abc*128的语法结构应表示为x+i*x，语法分析器最终应识别出这是一个算术表达式。识别过程相当于建立一棵语法树 <算术表达式> <算术表达式> + <项> <项> <项> * <因子> <因子> <因子> x(整常数) x(整常数) i(标识符)㈢语义分析(SemanticAnalysis)执行语义分析任务的程序称为语义分析器或中间代码产生器。任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。依据：语言的语义内涵语义分析（中间代码产生）主要工作为：语义正确性检查语义翻译①语义正确性检查 例2：begin

real

A;integerB;B=A+B;end

语法正确，不同的语言有不同的语义解释。标准Fortran语言认为是错误的，其不允许不同类型的量进行混合运算。C语言认为是正确的，允许混合运算，但需转换成相同类型的量，然后再进行运算。Pascal语言认为是错误的，虽允许混合运算，但不允许将实型量赋值于整型量。②语义翻译1)说明语句的翻译 将标识符及其属性填入符号表。2)执行语句的翻译 根据不同语句的语义，生成逻辑上等价的中间代码。中间代码结构简单、意义明确的记号系统，非常接近机器指令，又独立于具体机器。常用的中间代码有三元式和四元式。表达式3+abc*128可译成如下四元式：

(*,&abc,&128,&T1) (+,&3,&T1,&T2)其中，

&abc表示标识符abc在符号表中入口（即地址）；

T1和T2是在翻译过程中由编译程序引入的临时变量，&T1和&T2分别表示T1和T2在符号表中入口；而&128表示常数128在常数表中的地址。符号表(SymbolTable)

符号表用于记录源程序中出现的标识符(Identifier)，一个标识符往往具有一系列的语义值，它包括标识符的名称、标识符的种属、标识符的类型、标识符值的存放地址等等。每个标识符在符号表中有一项记录，用于记录标识符的各种语义值，而在四元式中填写的是标识符在符号表中的记录地址，通常称为符号表入口。内存地址符号名种属类型…………未分配abc简单变量整型未分配T1简单变量整型未分配T2简单变量整型…………符号表的结构示意如下：常数表(ConstantTable)

常数表用于记录在源程序中出现的常数。假定，每个整常数在常数表中占2个字节，每个实常数在常数表中占4个字节。常数的二进制值00000000-00000011（3）00000000-01000000（128）……常数表的结构示意如下：㈣目标代码生成(CodeGeneration)执行目标代码生成的程序称为目标代码生成器。任务：中间代码目标代码（机器指令或汇编语言）依据：目标机器的系统结构假设模型机器的指令格式为：

opRi,M （Ri）op（M）→Ri

opRi,Rj （Ri）op（Rj）→Ri

opRi,C （Ri）opC→Ri其中Ri表示寄存器，M表示内存地址（可用符号表示），C表示常数。表达式3+abc*128最终形成的汇编语言程序示意如下： LoadR0,abc MulR0,128 StoreR0,T1 LoadR0,3 AddR0,T1 StoreR0,T2编译程序在工作过程中可发现源程序中各种错误，错误类型及错误处理对策简述如下：㈠错误类型词法错误（可在词法分析阶段发现）语法错误（可在语法分析阶段发现）语义错误（可在语义分析阶段发现）1.4 出错处理(ErrorHandle)㈡出错处理一旦发现错误，暂停编译程序工作，指出错误的地点和类型。在发现错误后，不中断编译程序工作。采取某些措施（例错误局部化、错误校正等），使得源程序的编译工作可继续下去，尽可能发现源程序中比较多的错误。1.5 编译程序的前端和后端

由于在编译程序的内部引入了中间代码，这样可将编译程序分为二个相互独立部分。㈠编译程序前端(TheFrontEnd)组成：词法分析器、语法分