编译原理教案

第1章 编译原理概述

主要内容： 1 编译程序概述

2 编译程序的工作过程与结构 3 编译程序的开发

4 构造编译程序所应掌握的内容

任何一门高级语言都需要有相应的翻译程序将其翻译为机器语言，才能真正在计算机上执行。编译程序是这样的一种翻译程序，它对一个计算机系统来说非常重要。编写编译程序所涉及到的一些原理、技术和方法在计算机相关的各个领域中都会反复用到，具有十分普遍的意义。本章首先介绍编译原理的基本概念及与编译程序相关的一些工具，然后介绍编译的过程以及编译程序的结构、组成以及实现方法，最后对编译的相关理论和方法的应用做了简单介绍。

1程序设计语言与翻译程序

在计算机系统中，语言分三个层次：机器语言、汇编语言和高级语言。只有机器语言程序可直接在计算机上执行，高级语言和汇编语言编写的程序必须翻译为对应的机器语言程序才能执行。

计算机刚出现时，人们用机器语言(Machine Language)编写程序，如”C7 06 0000 0002”，其含义是将2放到一个存储单元中。用机器语言编写程序费时、乏味，开发难度大，周期长，很快就被汇编语言(Assembly Language)代替了。

汇编语言以助记符的形式表示指令和地址。如与上述指令等价的汇编代码为：MOV X,2，它不能直接执行，需要汇编程序（Assembler）将其翻译为机器语言程序才能执行。与汇编语言有关的程序有：反汇编程序（disassembler）是把机器语言程序逆向翻译为汇编语言程序的程序；交叉汇编程序（cross assembler）是把甲计算机上的汇编语言程序翻译为乙计算机上的机器语言程序的程序。

汇编语言仍与人类的思维相差甚远，不易阅读和理解，它严格依赖于机器，为一种机器编写的代码在应用于另一种机器时必须完全重写。高级语言的出现缩

短了人类思维和计算机语言间的差距，如上述指令用PASCAL语言写为x:=2。编写高级语言程序类似于定义数学公式或书写自然语言，与机器无关。起初人们担心这不可能，或者即使可能，目标代码也会因效率不高而没有多大用处。编译程序(Complier)的出现解除了人们的这种担忧，它能够直接将高级语言（如FORTRAN、Pascal、C或Java等）程序翻译为对应的低级语言（如汇编语言或机器语言）程序。

实际上，除了上述程序之间的翻译之外，同一种机器上的不同语言和不同种机器上的相同或不同语言程序之间都可以进行翻译错误！未找到引用源。给出了常见语言程序之间的翻译模式。把一种语言（称为源语言）书写的程序翻译成另一种语言（称为目标语言）书写的程序统称为翻译程序（Translator），后者与前者在逻辑上等价。

高级语言之间也可以相互转换，把用一种高级语言书写的程序转换为另一种高级语言的程序，统称为转换程序（converter）。

尽管人类可以借助高级语言与计算机进行交往，但是计算机硬件真正能够识别的只是0、1组成的机器指令序列。实际使用中，高级语言除了通过编译程序将其翻译为机器语言执行外，解释程序也可以把高级语言翻译为机器语言，二者的主要区别是：

编译程序先把全部源程序翻译为目标程序，然后再执行；该目标程序可以反复执行；

解释程序对源程序逐句地翻译执行，目标代码只能执行一次，若需重新执行，则必须重新解释源程序。

编译过程类似笔译，笔译后的结果可以反复阅读，而解释过程则类似于同步翻译，别人说一句，就译一句，翻译的结果没有保存。图1是两个过程的比较。

数据源程序编译程序目标程序计算机运行结果编译阶段运行阶段

（a）编译过程

数据源程序解释程序结果 （b）解释过程 图1 编译与解释过程对比

2编译程序的发展及分类

用高级语言编写程序简单方便，多数程序都可用高级语言编写。在一台计算机中对每一种高级语言，都至少配有一个编译程序。对有些高级语言甚至配置了几个不同性能的编译程序，以实现用户的不同需求。

编译程序最早出现在50年代早期，IBM的John Backus带领一个小组开发了FORTRAN语言，编写FORTRAN语言的编译器共用了18人年。与此同时Noam Chomsky开始了自然语言的研究，Chomsky的研究导致了根据语言文法 (grammar) 的难易程度以及识别它们所需的算法来对语言分类。

接着人们花费了很大的功夫来研究编译器的自动构造，出现了词法和语法分析的自动生成工具Lex与YACC。在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，其中就包括了代码生成自动化。

目前，编译器的发展与复杂的程序设计语言的发展结合在一起，如用于函数语言编译的Hindley-Milner类型检查的统一算法；编译器也已成为基于窗口的交互开发环境(IDE)的一部分；随着多处理机和并行技术、并行语言的发展，将串行程序转换成并行程序的自动并行编译技术正在深入研究之中；另外随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。

根据不同的用途和侧重，编译程序可分为很多类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序（Diagnostic Complier）。着重于提高目标代码效率的编译程序叫优化编译程序（Optimizing Complier）。运行编译程序的计算机称为宿主机，运行编译程序所产生的目标代码的计算机称目标机。如果一个编译程序产生不同于其宿主机的机器代码，称为交叉编译程序（Cross Complier）。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序（Retargetable Complier）。

编译程序的重要性在于它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员独立于机器硬件。除编译程序外，还需要其他一些程序才能生成在计算机上执行的目标程序。

预处理程序是指，当源程序以几个模块的形式存放在不同的文件中，将这些源程序汇集在一起的程序。预处理程序也能够把源程序中称为宏的缩写语句展开为原始语句加入到源程序中。源程序由编译程序编译后生成目标程序，图中的目标代码是汇编代码，需要经过汇编程序汇编转换为可装配的机器代码。再经装配连接程序连接成真正能在机器上运行的代码。装配连接程序是指，将可再装配的机器代码进行装配连接形成绝对机器代码的程序。

3 编译过程和编译程序的结构

编译过程概述

编译程序完成从源程序到目标程序的翻译工作，这是一个复杂的过程。整个工作过程需要分阶段完成，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。

根据各个阶段的复杂程度、理论基础和实现方法的不同，一般将编译程序的工作过程划分为词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成五个阶段。 词法分析

每种高级语言都规定了允许使用的字符集，如字母A～Z，a～z，数字0～9，＋、—、*、/等。高级语言的单词符号都由定义在各语言的字符集上的这些符号构成，有的单词由一个符号组成，如＋，－，*，/等，有的单词由两个或多个符号组成，如<=、>=、end等，它们都是语言的最基本的组成成分。在多数程序设计语言中，单词一般分为5类：保留字（begin、end、if、for、while等）、标识符、常数、运算符和分界符（标点符号、括号、注释符号等）。

词法分析是编译的第一个阶段，其任务是从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号串形式的中间程序。

在词法分析过程中，还要对源程序做一些简单处理，如滤掉空格、去掉注释、报告错误等。有的扫描器要求将识别出来的名字填入符号表，以备后续阶段使用。

词法分析的工作主要依据语言的构词规则，描述构词规则的有效工具是正规式和有限自动机。 语法分析

语法分析是编译过程的核心部分，其基本任务是根据语言的语法规则进行语法分析，若不存在语法错误则给出正确的语法结构并为语义分析和代码生成做准备。

完成语法分析任务的程序称为语法分析程序（parser）。如上述输入串中的单词序列id1:=int1 + id2 * id3 + id2 * id3经过语法分析后可以确定它是一个赋值语句，可以表示为图2所示的语法树。

赋值语句标识符 := 表达式表达式 + 表达式id1(X)常数表达式 + 表达式表达式 * 表达式标识符id2(B)标识符id3(C)int1(5)表达式 * 表达式标识符id2(B)标识符id3(C)

图2 语句id1:=int1 + id2 * id3 + id2 * id3的语法树

语法分析所依据的是语言的语法规则，语言的语法规则通常是由递归规则来定义，如上述例子中表达式和赋值语句可由下述递归规则来定义：

(1) 任何标识符是表达式； (2) 任何常数是表达式；

(3) 若表达式1和表达式2都是表达式，则表达式1+表达式2，表达式1*

表达式2都是表达式；

(4) 赋值语句就可以用规则：标识符 := 表达式；来定义。

图1-2的语法树就是根据赋值语句和表达式的递归定义规则生成的。这种用递归规则表示语法规则的工具称为上下文无关文法，用下推自动机实现。

推倒（derive）和归约（reduce）。推倒又分为最左推倒和最右推倒。 例如：x=a+b*50; 对该赋值语句进行：最右推倒，最左归约（根据文法要求，由文法的初始符号最终能够推出我们要证明的语句，且在最右推倒过程中，每次替换掉的都是产生式最右边的非终结符（大写符号））。若能推倒，则是正确地语句。

A?V＝E?V＝E＋T ?V＝E＋T×F? V＝E＋T×C? V＝E＋T×50

? V＝E＋F×50? V＝E＋V×50? V＝E＋b×50? V＝T＋b×50 ? V＝F＋b×50? V＝V＋b×50? V＝a＋b×50（V为最终结符）

? x＝a＋b×50

若将上式从右向左证明是一个赋值语句，最右推倒的反相推倒，这种方法就是最左归约（归约也分为最右归约和最左归约）。推倒和归约的关系互为逆过程。

例如：x=a+b*50; 对该赋值语句进行：最左推倒，最右归约

A?V＝E?x＝E?x＝E＋T?x＝T＋T?x＝F＋T?x＝V＋T

?x＝a＋T?x＝a＋T×F?x＝a＋F×F?x＝a＋V×F?x＝a＋b×F

?x＝a＋b×C

x＝a＋b×50（在最右推倒过程中，每次替换掉的都是产生式最右边的非终结符。这里只做了最右推倒。若将上面的式子，从右向左替换，即为最左归约）。

在描述程序语言的语法结构时，需要借助于上下文无关文法，而文法是描述程序语言的依据。语法分析的方法通常分为两类，即自上而下分析方法和自下而上分析方法。

所谓的自上而下分析方法，就是从文法的开始符号出发，根据文法的规则进行推导，最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。

递归下降分析法是一种自上而下的分析方法，文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程，这样向下推导直到推出句子；或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法树。

LL(1)分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。 LL(1)分析法基本思想：

自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式

自下而上分析法则是从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法的开始符号为止。

自下而上分析原理是从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.

算符优先分析法是一种简单且直观的自上而下分析方法，它适合于程序语言中各类表达式的分析，并且宜于手工实现。所谓算符优先分析，就是依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。因此，算符优先分析法不是一种规范归约，在整个归约过程中起决定性作用的是相继两个终结符的优先关系。

LR分析法是一种自下而上进行规范归约的语法分析方法，LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多，对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别，而且速度快，并能准确、及时地指出输入串

的任何语法错误及出错位置。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器。 语义分析与中间代码产生

这一阶段的主要工作有两项：首先对语法分析所识别出的各类语法单位进行静态语义审查（如标识符是否定义，类型是否匹配等）；若无语义错误，再根据识别出的语法单位的类型进行处理，若是说明语句，则将变量的类型等属性填入符号表，若是可执行语句，则进行初步的翻译，将其翻译为中间代码。

所谓中间代码，是一种含义明确，便于处理的记号系统，通常独立于具体硬件，与现有计算机的指令系统非常相似，比较容易转换成特定计算机的机器指令。常用的中间代码有：三元式、四元式、逆波兰式等。不管用哪种表示形式，其设计原则是容易生成，也容易转换成计算机的机器指令。很多编译程序采用四元式形式的中间代码，其形式为：

（运算符，运算对象1，运算对象2，结果）

语义分析和中间代码生成阶段的工作通常穿插在语法分析过程中完成，因而语义翻译程序通常由一组语义子程序组成。每当分析出一个完整的语法单位，就调用相应的语义子程序执行相应的分析和翻译任务。如当语法分析器分析完var x,y: integer;后，应把x,y的类型integer填入符号表的类型栏中；当分析赋值语句id1:=int1 + id2 * id3 + id2 * id3时，其语义处理过程是：一边读取一边检查result，B ，C，5是否定义，类型是否正确，一边就生成四元式序列，如表1。表中的T1，T2，T3和T4是编译期间引进的临时工作变量。该语句翻译的过程是：首先将表达式翻译为中间代码，再把表达式的值赋值给id1。

表1： 赋值语句id1:=int1 + id2 * id3 + id2 * id3的四元式

序号 四元式 1 2 3 4 5 (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1)

经过语义分析分析和中间代码生成阶段后，源程序被加工为整齐和标准形式的中间代码。语义分析依据的是语言的语义规则，表示工具是属性文法、P代码等。

代码优化

代码优化的任务是：产生的中间代码进行等价变换，使生成的目标代码更为高效（时间和空间）。优化的目的主要是提高运行效率，节省存储空间。优化主要有两类，一是与机器有关的优化，主要设计如何分配寄存器，如何选择指令，这类优化是在生成目标代码时进行的；另一类优化与机器无关，主要是对中间代码的优化。

根据优化所涉及的程序范围，优化又分为局部优化，循环优化，全局优化。一个程序从结构上看，作为终点的基本块是其基础。因为基本块的够最简单、因素最单纯，左翼它也是优化的基础，对基本块的优化就是局部优化。循环是程序中要反复执行的部分，优化的效益当然很大，所以循环优化是优化工作的重点。针对整个程序的优化即全局优化，它涉及到对策划能够许数据流分析的问题。

例如，对表1-1的中间代码，在优化阶段，编译程序发现两次计算id2 * id3，就可以省掉第2次的计算，而使用第一次计算的结果。同时因为第5个四元式仅仅把T4赋值给id1，也可以被简化掉。经优化后可变换为表2的四元式。仅剩下了3个四元式，完成了和表1-1同样的功能。

表2 赋值语句id1:=int1 + id2 * id3 + id2 * id3的优化后的四元式

序号 四元式 1 2 3 (*, id2, id3, T1) (+, int1, T1, T2) (+, T2, T1, id1)

代码优化的主要依据是程序的等价变换规则。优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。 目标代码生成

目标代码生成的任务是：把中间代码（或经优化的中间代码）变换成特定机器上的低级语言代码（绝对指令代码、可重定位的指令代码或汇编指令代码）。这一阶段的工作依赖于机器的硬件系统结构和机器指令的含义。工作较复杂，涉及到硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配以及寄存器的分配和调度。

代码生成是指把语法分析后或者优化后的中间代码变换成目标代码，所生成的目标代码一般有如下三种形式：

(1)能够立即执行的机器语言代码，它们通常放在固定的存储区中并可直接

执行，如PC机中后缀为.COM或.EXE的文件。

(2)待装配的机器语言模块，其地址均为相对地址，所以不能直接执行。当

需要执行时由连接装配程序把它们与其他运行程序和库函数连接起来，装配成可执行的机器语言代码，如PC机中后缀为.OBJ的文件。 (3)汇编语言程序，必须通过汇编程序的汇编才可转换成可执行的机器语言

代码如PC机中后缀为.ASM的文件

前面提到的五个阶段的划分是一种典型的划分方式，事实上，并非所有的编译程序都分成这五个阶段，有些编译程序并不生成中间代码，而是直接生成目标代码，有些编译程序不进行代码优化。 表格与表格管理

表格的作用：用来记录源程序的各种信息，以及编译过程中的各种状况。 与编译前三个阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表等。

(1)符号表：用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。

void main（）

{ }

(2)常数表和标号表

表4 常数表

表3 符号表 int m，n，k；

Name m n k Information 整型、变量地址 整型、变量地址 整型、变量地址

值 1 4 表5标号表 Name Information ．．．．． ．．．．．．． 10 四元式序号4 常数：数值型（整型和实型）、字符型、逻辑型；所有同类型的常数占有一张表格，整型占一张、实型占一张。

标号表：现在用的很少。一般在词法分析时，是不生成四元式的，只记录标号，到了生成目标代码时才在Information处填入内容。 (3)入口名表

作用：登记过程的层号，分程序符号表入口等。

由于程序是由几个过程构成的，过程都是存入内存里，每个过程从哪里

执行？必须知道过程在哪个内存单元中？因此需要登记过程的层号，分程序符号表入口等。 (4)中间代码表

表6 中间代码表

序号 （1） （2） （3） （4） （5） （6） （7） （8） （9） OP ＝ ＝ ＝ (Jump)< ＋ ＋ ＋ Jump return ARG1 i j 1 100 m n k ARG2 k 10 10 1 RESULT m n k （9） m n k （4） 在生成中间代码时才生成该表。 出错处理

任务：如果源程序有错误，编译程序应设法发现错误，并报告给用户。 此过程非常复杂，因为很难发现错误，需要编写出错的处理程序来完成。 错误类型： 可检测的错误和不可检测的错误。

——语法错误：在词法分析和语法分析阶段检测出来；（单词出错、句子不规范） ——语义错误：又分为静态语义错误和动态语义错误。静态语义错误一般在语义分析阶段检测出来，而动态语义错误是在目标程序运行的时候才能查出来；（出现语义上的不可答错误，功能无法实现。如除数为0的错误） ——逻辑错误：不可检测的错误。

而且程序的出错可能出现在任何阶段上，每一步的错误都由“出错处理”来完成。逻辑错误无法用编译程序检测出来，也就不检测此类错误。

例如：while（a||c） //而a||c在循环时判断永远为Ture， }

编译程序的结构

编译程序的五个阶段的功能可分别用五个模块来完成，分别称为词法分析器、语法分析器、语义分析与中间代码生成器、优化器和目标代码生成器。此外，

{

//出现死循环，即为逻辑错误。

．．．．．．

一个完整的编译程序还必须包括“表格管理”和“出错处理”两部分。一个编译程序在编译过程中应尽量找出源程序中的错误，向用户提供更多更准确的与错误有关的信

图3 编译程序结构框图

息，以便用户查找和纠正。一个典型的编译程序结构框图如图1.3所示。词法分析是实现编译器的基础，语法分析是实现编译器的关键。本书将按照这个顺序来讲述编译程序各个阶段涉及到的基本理论、实现方法和技术。

4 编译器的构造及编译技术的应用

1 如何构造一个编译程序

要在一台机器上为某种语言构造一个编译程序，必须从下述三方面入手： (1) 源语言：是编译程序处理的对象。对被编译的源语言要深刻理解其结构和含义，即该语言的词法、语法和语义规则，以及有关的约束和特点；

(2) 目标语言与目标机：是编译程序处理的结果和运行环境。目标语言是汇编语言或机器语言，必须对硬件系统结构，操作系统的功能，指令系统等很清楚；

(3) 编译方法与工具：是生成编译程序的关键。必须准确掌握把一种语言的程序翻译为另一种语言的程序的方法之一。同时应考虑所使用的方法与既定的源语言、目标语言是否相符合、构造是否方便，从时间、空间上考虑是否高效、实现的可能性和代价等诸多因素，并尽可能考虑使用先进、方便的生成工具。

2 编译程序的实现方式

编译程序本身也是一个程序，那怎样实现它呢？从理论上讲，基本上可以用任意语言来实现。早期人们用机器语言或汇编语言手工编写；为了充分发挥硬件资源的效率，满足各种不同的要求，许多人目前仍然采用低级语言编写；但由于

编译器本身是一个十分复杂的系统，用低级语言编写效率很低，现在越来越多的人使用高级语言来编写，这样可以节省大量的程序设计时间，且程序易读、易修改和移植；为了进一步提高开发效率和质量，可以使用一些自动生成工具来支持编译器某些部分的自动生成，如词法分析生成器LEX和语法分析生成器YACC等。

概括起来，生成编译程序的方法有：

1．直接用机器语言或汇编语言编写（编译程序核心部分常用汇编语言编写）； 2．用高级语言编写编译程序（这是普遍采用的方法）； 3．自编译；

4．用编译工具自动生成部分程序：LEX（词法分析）与YACC（用LALR分析

方法自动生成语法分析器）；

5.移植（同种语言的编译程序在不同类型的机器之间移植）。

用高级语言编写编译程序当然离不开高级语言的程序开发环境。目前常用的高级语言集成开发环境环境有Basic开发环境VB、C和C++开发环境VC++、C#开发环境VC#等。

3 编译技术的应用

为了提高软件开发效率、保证质量，在软件工程中除了遵循软件开发过程的规范或标准外，还尽量使用先进的软件开发技术和相应的软件工具。而大部分软件工具的开发，常常要用到编译技术和方法，实际上编译程序本身也是一种软件开发工具。为了提高编程效率，缩短调试时间，软件工作人员研制了不少对源程序处理的工具，这些工具的开发不同程度地用到了编译程序各个部分的技术和方法。下面是常用的软件工具：

语言的结构化编辑器 结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。这类产品有Turbo-Edit、editplus和Ultraedit等。

语言程序的调试工具 结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致、程序的执行是否实现了预期的算法和功能。对算法错误或程序不能反应算法的功能的检查就需要调试工具来完成。调试功能越强，实现就越复杂，它主要涉及源程序的语法分析和语义处理技术。

语言程序的测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。静态分析器是对源程序进行静态的分析，它对源程序进行语法分析并制定相应表格，检查变量定值与引用关系，如检查某变量未被赋值就引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误；动态测试

工具是在源程序的适当位置插入某些信息，并用测试用例记录程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。这种测试工具在国内已有开发，如FORTRAN和C语言的测试工具。

高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好的条件。然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢？为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言程序转换成另一种高级语言程序，乃至汇编语言程序如何转换成高级语言程序的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。这比实现一个完整的高级语言编译程序相比工作量要少些。目前已有成熟的转换系统。

交叉编译程序 随着嵌入式技术的发展和广泛应用，嵌入式软件开发环境所涉及的关键技术是多目标交叉编译和调试工具。这些工具希望在宿主机上为源语言交叉编译生成多个目标板上的目标程序，并能对目标机上运行的程序进行调试。

第2章 词法分析

主要内容：

1 词法分析器设计方法

2 一个简单的词法分析器示例 3 正规表达式与有限自动机简介 4 正规表达式到有限自动机的构造 5 词法分析器的自动生成

词法分析是编译的第一个阶段，其任务是从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号串形式的中间程序。

词法分析的工作主要依据语言的构词规则，描述构词规则的有效工具是正规式和有限自动机。

状态转换图

状态转换图是有限的有向图，结点代表状态，用圆圈表示；结点之间可由有

向边连接，有向边上可标记字符。

正规表达式和有限自动机

字母表?, 定义在? 上的正规式和正规集递归定义如下:

1. ?和?都是? 上的正规式, 它们所表示的正规集分别为:{?}和?; 2. 任何a? ? , a是? 上的正规式,它所表示的正规集为:{a}; 3. 假定U和V ? 上的正规式, 它们所表示的正规集分别记为L(e1) 和L(e2), 那么e1|e2, e1?e2和e1*也都是? 上的正规式, 它们所表示的

正规集分别为L(e1) ?L(e2)、 L(e1) ? L(e2)和(L(e1))* 4. 任何? 上的正规式和正规集均由1、2和3产生。 1.确定的有限自动机（DFA）

M=(Σ, Q, f,S, Z)

Σ：有穷字母表，它的每个元素称为一个输入符号 Q：有穷集，它的每个元素称为一个状态 S∈K，是唯一的初态

Z ? K是一个终态集，终态也称可接受状态或结束状态 f是转换函数，是Q×Σ→Q上的单值映射： f（q1，a）=q2

2.不确定的有限自动机（NFA）

M=(Σ, Q, f,S, Z)

f是一个多值函数，是从Q×Σ*到Q的子集的映射： f：Q×Σ→2Q

其中2Q是Q的幂集，即Q中所有子集组成的集合。 3.状态转换图与状态转换矩阵

DFA和NFA都可以用状态转换图表示。假定DFA有m个状态n个输入字符，则这个状态转换图含有m个状态，每个状态最多有n条输出边与其他状态相连接。 DFA和NFA可以用状态转换矩阵表示。 正规表达式到有限自动机的构造

（1）对于字母表Σ上的NFA M，可以构造一个Σ上的正规式R，使得L(R)=L(M)； （2）对于字母表Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 正规式R?NFA M

（1）对NFA M构造一个广义的状态图，其中只有一个初态S和终态Z，连接S

和Z的有向弧标记为正规式。

（2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表Σ上的元素或?为止。 词法分析器的自动生成： LEX的源程序

一个LEX源程序主要由三个部分组成 说明部分 －－可选 %% －－必须有

识别规则 －－必须有（LEX的核心） %% －－可选 辅助过程 －－可选

1、说明部分:变量、常量说明和正规式定义

正规式定义格式如下： D1 R1 D2 R2 ∶ ∶ Dn Rn

2、识别规则：是一串如下形式的LEX语句：

R1 {A1} R2 {A2} ∶ ∶ Rm {Am} Ri ：正规式

{Ai}：Ai为语句序列，在识别出单词Ri以后，词法分析器所应作的动作。 其基本动作是返回单词的类别编码和单词值。 3、辅助过程:用户定义的子程序

下面是识别C语言部分单词符号的LEX源程序： /*说明部分*/

digit [0-9] letter [A-Za-z]

id ({letter}|[_])({letter}|{digit}|[_])*

%%

/*识别规则，每条规则中的动作都用大括号括起来*/

“main”|”int”|”if” {Upper(yytext,yyleng);

printf(\ {id} {printf(\ “+”|”-”|”*” {printf(\\\n\%%

/*辅助过程*/

Upper(char *s,int l) { int i;

for(i=0;i< l;i++) s[i]=toupper(s[i]); return 1;} void main(void) { yylex(); }

LEX的实现

LEX的功能是根据LEX源程序构造一个词法分析程序， 该词法分析器实质上是一个有穷自动机。

LEX的工作原理是将LEX源程序中的正规式转换成DFA，进一步通过控制程序识别单词

第3章 语法分析

主要内容： 1 文法和语言 2 推导与语法树 3 自上而下分析方法 4 自下而上分析方法 5 LR分析法

主要开发了推导与语法树以及几种语法分析的方法。

推导与语法树

给定文法G[S], ??δ为该文法的句型,

若 S==>?Aδ,且A==>?, 则?是句型??δ相对于A的短语； 若 S==> ?Aδ, 且A==> ?, 则?是句型??δ相对于A的简单短语 直观理解：短语就是某句型中的子串，这个子串是由某个非终结 符通过至少一步推导得到的子串，而简单短语就是由某个非终结 符通过一步推导得到的子串。

素短语是一个短语,它至少包含有一个终结符号,并且除它自身以外不再包含其他素短语.其中最左边的素短语称为最左素短语。 例2-1求句型T+T*F+i的短语、简单短语、 句柄、素短语、最左素短语 短语：T+T*F+i, T+T*F, T,T*F,i 简单短语：T,T*F,i 句柄：T

素短语：T*F和i（因为T不包含终结符, T+T*F+i和T+T*F包含其他素短语） 最左素短语：T*F

自上而下分析法

EEET+T+TFi T*F 图2-7 句型T+T*F+i的的语法树 所谓的自上而下分析方法，就是从文法的开始符号出发，根据文法的规则进行推导，最终推导出给定的句子来。包括递归下降分析法和LL(1)分析法。

递归下降分析法是一种自上而下的分析方法，文法的每个非终结符对应一个递归过程。分析过程就是从文法开始符出发执行一组递归过程，这样向下推导直到推出句子；或者说从根结点出发，自上而下为输入串寻找一个最左匹配序列，建立一棵语法树。

LL(1)分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。 LL(1)分析法基本思想：自左向右扫描分析输入符号串从识别符号开始生成句子的最左推导

LL(1):向前看一个输入符号，便能唯一确定产生式 LL(k):向前看k个输入符号，才能唯一确定产生式 LL(1)分析法主要是构造FIRST集和FOLLOW集。 例2-2 G[E]： E→TE'

E'→+TE'| T→FT' T'→*FT'| F→(E)|i

求FIRST集。 解：FIRST(F)={(,i}

FIRST(T’)={*,ε}

FIRST(T)=FIRST(F)-{ε}={(,i} FIRST(E’)={+,ε}

FIRST(E)= FIRST(T)-{ε}={(,i} FIRST(TE’)=FIRST(T)-{ε}={(,i}

FIRST(+TE’)={+} FIRST(ε)={ε} FIRST(FT’)= FIRST(F)-{ε}={(,i} FIRST(*FT’) ={*} FIRST(（E）)={(} FIRST(i)={i} 例2-3 G[E]：

E→TE' E'→+TE'| T→FT' T'→*FT'| F→(E)|i

求FOLLOW集。

解：FOLLOW(E)={#,)} ∵E是开始符号∴#∈FOLLOW(E)

又F →(E) ∴ )∈FOLLOW(E) FOLLOW(E’)={#,)} ∵E → TE’ ∴FOLLOW(E)加入 FOLLOW(E’) FOLLOW(T)={+,),#} ∵E’ → +TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T) 又E’ε， ∴ FOLLOW(E’)加入FOLLOW(T) FOLLOW(T’)= FOLLOW(T)= {+,),#}

FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T) ={(,i} FIRST(E’)={+,ε} FIRST(E)={(,i} ∵T → FT’ ∴ FOLLOW(T)加入FOLLOW(T’) FOLLOW(F)={*,+,),#}

∵T → FT’ ∴ FOLLOW(F)=FIRST（T’）-{ε} 又T’ε ∴ FOLLOW(T)加入FOLLOW(F) 自底向上分析法

自下而上分析法则是从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法的开始符号为止。

自下而上分析原理是从输入符号串开始，通过重复查找当前句型的“可归约串”并利用有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.

算符优先分析法是一种简单且直观的自上而下分析方法，它适合于程序语言中各类表达式的分析，并且宜于手工实现。所谓算符优先分析，就是依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。因此，算符优先分析法不是一种规范归约，在整个归约过程中起决定性作用的是相继两个终结符的优先关系。

LR分析法是一种自下而上进行规范归约的语法分析方法，LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多，对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别，而且速度快，并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器。 LR分析算法描述：

将S0移进状态栈，# 移进符号栈，S为状态栈栈顶状态 a=getsym( ) //读入第一个符号给a while(ACTION[S,a]!=acc ) {

if ACTION[S,a]=Si{

PUSH i,a(分别进栈); a=getsym( ) ;//读入下一个符号给a} else if ACTION[S,a]=rj (第j条产生式为A→β) { 将状态栈和符号栈分别弹出|β| 项;push(A); 将GOTO[S’,A] 移进状态栈（S’为当前栈顶状态）;}

else error( );

第4章 语义分析和中间代码生成分析

主要内容： 1 概述 2 属性文法

3 几种常见的中间语言 4 表达式及赋值语句的翻译 5 控制语句的翻译 6 数组元素的翻译

7 过程或函数调用语句的翻译 8 说明语句的翻译

9 递归下降语法制导翻译方法简介

主要介绍了语法制导翻译方法、几种中间语言以及语句的翻译。 语法制导翻译方法

语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语法制导翻译是将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。 语法制导翻译分为两种处理方法： （1）语法制导定义（自底向上）：

对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。 （2）翻译方案（自顶向下）：

在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。 几种常见的中间语言 1．抽象语法树

抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语

法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。

与抽象语法相对应的语法树称为抽象语法树或抽象树 2．逆波兰表示法

逆波兰表示法把运算量(操作数)写在前面，把运算符写在后面，因而又称后缀表示法。例如，把a+b写成ab+，把a*(b+c)写成abc+*。 表达式E的后缀表示的递归定义如下：

(1) 如果E是变量或常数，则E的后缀表示即E自身。

(2) 如果E为E1 op E2形式，则它的后缀表示为E1'E2'op；其中op是二元运算符，而E1'、E2'分别又是E1和E2的后缀表示。若op为一元运算符，则视E1和E1'为空。

(3) 如果E为(E1)形式，则E1的后缀表示即为E的后缀表示 为了用逆波兰式表示一些控制语句，我们定义转移操作如下： (1) BL：转向某标号； (2) BT：条件为真时转移； (3) BF：条件为假时转移； (4) BR：无条件转移。 部分程序语句的逆波兰表示：

(1) 赋值语句。赋值语句“<左部>=<表达式>”的逆波兰表示为 <左部><表达式>=

(2) GOTO语句。转向语句“GOTO<语句标号>”的逆波兰表示为 <语句标号>BL

其中，“BL”为单目后缀运算符，“<语句标号>”则为BL的一个运算分量。

(3) 条件语句。BR表示无条件转移单目后缀运算符。例如，“<顺序号>BR”表示无条件转移到“<顺序号>”处，这里的顺序号是BR的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号(即第几个单词)，它不同于GOTO语句中的语句标号。BT和BF表示按条件转移的两个双目后缀运算符。例如： <布尔表达式e的逆波兰式><顺序号>BT <布尔表达式e的逆波兰式><顺序号>BF

(4) 循环语句。for循环语句为：for(i=m；i<=n；i++)S；其中，i为循环控制变量，m为初值，n为终值，S为循环体。循环语句不能直接用逆波兰表示，因而将其展开为等价的条件语句后再用逆波兰表示，即 i=m；

10：if(i<=n) { S； i=i+1； goto l0 }

3． 三地址代码

三地址代码语句的一般形式为 x=y op z

其中，x、y和z为名字、常量或编译时产生的临时变量；op为运算符，如定点运算符、浮点算符和逻辑运算符等。三地址代码的每条语句通常包含三个地址，两个用来存放运算对象， 表达式及赋值语句的翻译

例2-4 试分析赋值语句X= ?B*(C+D)的语法制导翻译过程。 [解答] 赋值语句X=?B*(C+D)的语法制导翻译过程如表所示

表2-1 赋值语句X=?B*(C+D)的语法制导翻译过程

输入串 X=?B*(C+D)

#

=?B*(C+D)#

?B*(C+D)#

B*(C+D)#

*(C+D)#

*(C+D)#

*(C+D)#

归约产生式 (6) (6) (4)

符号栈 # #i #i= #i=?

#i=?i

#i=?E #i=E

语义栈(place)

_ _X _X_

_X_ _

_X_ _B

_X_ _B

_X_T1

四元式

(uminus,B, _,T)

(C+D)# C+D)# +D)# +D)# D)# )# )# )# # # # #

(6) (6) (2) (5) (3) (1)

#i=E* #i=E*( #i=E*(i #i=E*(E #i=E*(E+ #i=E*(E+i #i=E*(E+E

#i=E*(E #i=E*(E) #i=E*E #i=E #A

_X_T1_ _X_T1_ _ _X_T1_ _C _X_T1_ _C _X_T1_ _C_ _X_T1_ _C_D _X_T1_ _C_D

_X_T1_ _T2 _X_T1_ _T2_ _X_T1_T2 _X_T3 _X

(+,C,D,T2)

(*,T1,T2,T3) (=,T3, _,X)

控制语句的翻译

在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：

(1) 顺序结构，一般用复合语句实现； (2) 选择结构，用if和case等语句实现；

(3) 循环结构，用for、while、do(即repeat)等语句实现。 三种基本控制结构的文法G[S]如下： G[S]： (1) S→CS (2) ∣TP S (3) ∣Wd S (4) ∣{L}

(5) ∣A /*A代表赋值语句*/ (6) L→LS S (7) ∣S (8) C→if(E) (9) TP→CS; else (10) Wd→W(E) (11) W→while (12) LS→L;

G[S]中各产生式对应的语义子程序如下：

(1) S→C S(1) {S.chain=merge(C.chain, S(1).chain);} (2) S→TP S(2) {S.chain=merge(TP.chain, S(2).chain);} (3) S→Wd S(1) {Backpatch(S(1) .chain, Wd.quad); emit(j,_,_,Wd.quad); S.chain=Wd.chain;} (4) S→{L} {S.chain=L.chain};} (5) S→A {S.chain=0; /*空链*/ } (6) L→LS S(1) {L.chain=S(1).chain} (7) L→S {L.chain=S.chain} (8) C→if(E) {Backpatch(E.tc, nxq); C.chain=E.fc;} (9) TP→C S(1) ; else {q=nxq; emit(j,_,_,0);

Backpatch(C.chain, nxq); TP.chain=merge(S(1).chain,q);} (10) W→while {W.quad=nxq;} (11) Wd→W(E) {Backpatch(E.tc, nxq); Wd.chain= E.fc; Wd.quad= W.quad;} (12) LS→L; {Backpatch(L.chain, nxq);} 数组元素的引用和赋值就有如下两种不同的四元式：

(1) 变址存数：若有T1[T]=X，则可以用四元式([ ]=，X，_，T1[T])表示。 (2) 变址取数：若有X=T1[T]，则可用四元式(=[ ]，T1[T]，_，X)表示。 例2-5 试给出下列语句的四元式序列： if (p1==0∧p2＞10) X[1,1]=1; else X[7,6]=0;

其中，X是10×20的数组(每维下界为1)且按行存放；一个数组元素占用两个字节，机器按字节编址。

[解] 拓展数组元素翻译的语义子程序功能，得到该语句对应的四元式序列如下： 100 (j=, P1, 0, 102)

101 (j,_, _,110) 102 (j>,P2,10,104) 103 (j, _,_,110) 104 (*,1,40,T1)

105 (*,1,2,T2) 106 (+,T1,T2,T3) 107 (?,X,42,T4) 108 ([ ]=,1, _,T4[T3]) 109 (j, _,_,115) 110 (*,7,40,T1) 111 (*,6,2,T2) 112 (+,T1,T2,T3) 113 (?,X,42,T4) 114 ([ ]=,0, _,T4[T3]) 115

第5章 代码优化

主要内容： 1 局部优化 2 循环优化 3 代码优化示例

代码优化的任务是：产生的中间代码进行等价变换，使生成的目标代码更为高效（时间和空间）。优化的目的主要是提高运行效率，节省存储空间。优化主要有两类，一是与机器有关的优化，主要设计如何分配寄存器，如何选择指令，这类优化是在生成目标代码时进行的；另一类优化与机器无关，主要是对中间代码的优化。

根据优化所涉及的程序范围，优化又分为局部优化，循环优化，全局优化。一个程序从结构上看，作为终点的基本块是其基础。因为基本块的够最简单、因素最单纯，左翼它也是优化的基础，对基本块的优化就是局部优化。循环是程序中要反复执行的部分，优化的效益当然很大，所以循环优化是优化工作的重点。针对整个程序的优化即全局优化，它涉及到对策划能够许数据流分析的问题。 局 部 优 化

局部优化是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。

循 环 优 化 循环的查栈 1．必经结点集

在程序流图中，对任意结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为m DOM n；流图中结点n的所有必经结点的集合称为结点n的必经结点集，记为D(n)。

显然，循环的入口结点是循环中所有结点的必经结点；此外，对任何结点n来说都有n DOM n。

如果把DOM看作流图结点集上定义的一个关系，则由定义容易看出它具有下述性质：

(1) 自反性：对流图中任意结点a，都有a DOM a。

(2) 传递性：对流图中任意结点a、b、c，若存在a DOM b和b DOM c, 则必有a DOM c。

(3) 反对称性：若存在a DOM b和b DOM a，则必有a=b。 2．回边

回边的定义如下：假设a→b是流图中一条有向边，如果b DOM a，则称a→b是流图中的一条回边。

查找循环的方法是：首先应用必经结点集来求出流图中的回边，然后利用回边找出流图中的循环的。 例2-6 求出流图的所有回边。

[解答] (1) 已知D(6)={1,2,4,6}，因存

在6→6且6 DOM 6，故6→6 是回边；

(2) 已知D(7)={1,2,4,7}，因存在7→4且 4 DOM 7，故7→4是回边；

(3) 已知D(4)={1,2,4}，因存在4→2且2 DOM 4，故4→2是回边

3．可归约流图

一个流图被称为可归约的，当且仅当流图中除去回边之外，其余的边构成一个无环路流图

对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。

图1 例示图 67 12345 删除归纳变量等优化。 1．代码外提

循环中的代码要随着循环反复执行，但其中某些运算的结果并不因循环而改变，对于这种不随循环变化的运算，可以将其外提到循环外。这样，程序的运行结果仍保持不变，但程序的运行效率却提高了。我们称这种优化为代码外提。 例2-7 试对图2-10给定的程序流图进行代码外提优化。

[解] 确定不变运算的原则是依次查看循环中各基本块的每个四元式，如果它的每个运算对象为常数或者定值点在循环外，则将此四元式标记为“不变运算”。查看图的程序流图，可以找出的不变运算是B3中的I=2和B4中的J=M+N。 进行代码外提时，只能将J=M+N提到循环前置结点，而B3中的I=2虽然是不变运算，但B3不是循环所有出口结点的必经结点，且循环中所有I的引用点并非只有B3的I定值能够到达，故B3中的I=2不能外提。最后，得到代码外提后的程序流图如图所示。

Y=0A=1B1if A>B goto B4B2I=2B=I+YB3B4A=A+IJ=M+NY=Y-1if Y=0 goto B2X=AB5

图2 程序流程图

if A>B goto B4B2I=2B=I+YB3A=A+IY=Y-1if Y=0 goto B2X=AB5B4J=M+NB?2Y=0A=1B1

图 3程序流程图

2．强度削弱

如果循环中有I的递归赋值I=I±C(C为循环不变量)，并且循环中T的赋值运算可化归为T=K*I±C1(K和C1为循环不变量)，那么T的赋值运算可以进行强度削弱。

进行强度削弱后，循环中可能出现一些新的无用赋值，如果它们在循环出口之后不是活跃变量则可以从循环中删除。此外，对下标变量地址计算来说，强度削弱实际就是实现下标变量地址的递归计算。 3．删除归纳变量

如果循环中对变量I只有惟一的形如I=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I±C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。一个基本归纳变量也是一归纳变量。

第6章 运行时存储空间的组织

主要内容：

1 静态存储分配 2 简单的栈式存储分配 3 嵌套过程语言的栈式实现 4 堆式动态存储分配

主要介绍了静态存储分配和动态存储分配。 静态存储分配

如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地

址，存储空间的这种分配方法叫做静态分配。

对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。 FORTRAN程序的静态分配

图FORTRAN程序的静态分配

主程序的目标代码 子程序1的目标代码 …… 子程序n的目标代码 全局变量 主程序的活动记录 子程序1的活动记录 …… 子程序n的活动记录 堆式动态存储分配

如果一种程序语言允许数据对象能够自由地分配和释放，或者不仅有过程而且有进程(process)这样的程序结构，那么由于空间的使用不一定遵循“先申请后释放”的原则，则栈式存储分配就不适用了。在这种情况下，通常使用一种称之为堆的动态存储分配方案。假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。

由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。

对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。 堆式存储管理的方法

使用可利用空间表进行动态存储分配的方法又可分为如下两种：

(1) 定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，

即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。

(2) 变长块的管理。变长块管理方法是一种常用的堆式存储管理方法，它可以根据实际需要来分配长度不同的空闲块；

系统开始时，存储空间是一完整空间，可利用空间表中只有一个大小为整个存储空间的空闲块。当系统运行一段时间后，随着分配和回收的进行，可利用空间表 中空闲块的大小和个数也随之改变。由于可利用空间表中的空闲块大小不同，因而存在着如何进行空闲块分配的问题。若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：

(1) 首次满足法。从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，则整块分配出去)，而其余部分仍作为一个空闲块留在表中。

(2) 最优满足法。系统扫描整个可利用空间表，从中找出一块不小于要求的最小空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。

(3) 最差满足法。系统将可利用空间表中最大的空闲块予以分配(当然也要求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。

第7章 目标代码生成

主要内容：

1 一个简单代码生成器

2 汇编指令到机器代码的翻译概述

主要介绍了一个简单的代码生成器。

要实现一个代码生成器，重点应该考虑两个问题：

1. 如何使生成的目标代码尽可能的短

2. 如何充分利用计算机的寄存器，减少目标代码中访问内存的次数 为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由

后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。如果没有进行数据流分析并且临时变量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。 例 考察基本块： (1) T=A?B (2) U=A?C (3) V=T+U (4) D=V+U

其中，A、B、C、D为变量，T、U、V为中间变量，试求各变量的待用信息链和活跃信息链。

[解] 我们根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表所示。表中的“F”表示“非待用”或“非活跃”，“L”表示“活跃”，(1)～(4)分别表示基本块中的四个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况(空白处表示没

有变化)。

表2 例2-8的待用信息链和活跃信息链

变量名 T A B C U V D

初值 F F F F F F F

待 用 信 息

待 用 信 息 链 (3) (3) F

(2) (2) F

F (1) (1)

初值 F L L L F F L

活 跃 信 息

活 跃 信 息 链 L L F

L L F

L L F

F L L

(4) (4) F

待用信息和活跃信息在四元式上的标记如下： (1) T(3)L=A(2)L ? BFL (2) U(3)L=AFL ? CFL (3) V(4)L=TFF+U(4)L (4) DFL=VFF+UFF

假设基本块中每个四元式的形式都是A=B op C，则代码生成算法是对每个四元式i：A=B op C执行下述步骤：

(1) 调用函数GETREG (i：A=B op C)返回存放A值结果的寄存器R。 (2) 通过地址描述数组AVALUE [B]和AVALUE [C]确定出变量B和变量C的现行值存放位置B'和C'；如果是存放在寄存器中，则把寄存器取作B'和C'。

(3) 如果B'≠R，则生成目标代码： MOV R, B' op R, C'

否则生成目标代码： op R, C'

如果B'或C'为R，则删除AVALUE [B]或AVALUE [C]中的R。 (4) 令AVALUE[A]={R}并令RVALUE[R]={A}，表示变量A的现行值只在R中且R中的值只代表A的现行值。

(5) 如果B和C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量且它们的现行值存放在寄存器Rk中，则删除RVALUE [Rk]中的B和C以及AVALUE [B]中的Rk，使寄存器Rk不再为B和C所占用。 源程序到目标代码生成示例

我们以PC机的汇编语言作为目标代码，且假定可用的寄存器为AX、BX、CX

和DX，则一C语言源程序转换为四元式代码序列，然后再转换为目标代码程序(转换中不考虑优化)的结果如下：

(1) C语言源程序(局部) while (a>b) {

if (m>=n) a=a+1; else

while (k==h) x=x+2; m=n+x*(m+y); }

(2) 四元式代码序列 100 (j>, a, b, 102) 101 (j, _, _, 117 ) 102 (j>=, m, n, 104) 103 (j, _, _, 107 ) 104 (+, a, 1, T1) 105 (=, T1, _ , a ) 106 (j, _, _, 112) 107 (j=, k, h, 109 ) 108 (j, _, _, 112) 109 (+, x , 2, T2 ) 110 (=, T2, _ , x ) 111 (j, _, _, 107 ) 112 (+, m, y, T3) 113 (*, x, T3, T4 ) 114 (+, n , T4, T5) 115 (=, T5, _ , m ) 116 (j , _, _, 100)

(3) 目标代码程序 (汇编语言程序) ; File: compile.asm

; ************************************ data segment ; 定义数据段 h DW

k DW m

DW

n DW x DW a DW

DW

y DW b

data ends ; 数据段定义结束 ; ************************************ code segment main proc far start: push ds sub bx, bx push bx

mov bx, data mov ds, bx

; 语句翻译由此开始： 100: mov AX, a cmp AX, b jg 102 101: mp 117 102: mov AX, m cmp AX, n jge 104 103: jmp 107 104: mov AX, a add AX, 1D 105: mov BX, AX mov a, BX 106: jmp 112 107: mov AX, k cmp AX, h

; 跳出基本块前保存寄存器中已改变的变量值 ; 设置DS段为当前数据段 ; 定义代码段 ; 程序的执行部分

assum cs:code, ds:data

je 109 108: jmp 112 109: mov AX, x add AX, 2D 110: mov BX, AX mov x, BX 111: jmp 107 112: mov AX, m add AX, y 113: mul x 114: mov BX, n add BX, AX 115: mov CX, BX mov m, CX 116: jmp 100 117: ret main endp

code ends ; 代码段定义结束 end start

; 跳出基本块前保存寄存器中已改变的变量值 ; 跳出基本块前保存寄存器中已改变的变量值

第8章 符号表和错误处理

主要内容：

1 符号表 2 错误处理

符号表

由于处理对象的作用和作用域可以有多种，所以符号表也有多种组织方式。按照处理对象的特点，符号表的组织方式一般可分为直接方式和间接方式。

直接方式是指在符号表中直接填入源程序中定义的标识符及相关信息

间接方式是指单独设置一个字符串数组来存放所有的标识符，并在符号表的名字栏中设置两项内容：一是指针，用来指向标识符在数组中的起始位置；二是一整数值，用来表示该标识符的长度。

另一种组织方式是按标识符的种属，如简单变量、数组、过程等分别建立不同的符号表，如简单变量名表、数组名表、过程名表等。例如，下面的函数： int f(int a,int b) { int c; if(a>b) c=1; else c=0; return c; } 常用符号表结构 1．线性符号表

符号表中最简单且最容易实现的数据结构是线性表，它是按程序中标识符出现的先后次序建立的符号表，编译程序不做任何整理次序的工作。

在扫描源程序时，根据各标识符在程序说明部分出现的先后顺序将标识符及其有关信息填入符号表中。当编译过程中需要查找符号表中的某个标识符时，只能采用线性查找方法，即从符号表的第一项开始直到表尾一项一项地顺序查找。这种查找方法的缺点是效率较低。 2．有序符号表

为了提高查表速度，可以在造表的同时把各标识符按照一定的顺序进行排列。显然，这样的符号表是有序的对于有序符号表，一般采用折半查找法进行查表，即首先从表的中项开始比较，如果未找到则将查找范围缩小一半，然后继续查找，直到找到或查找失败为止。使用这种折半查找法对一个含有N项的符号表来说，查找其中的一项最多只需做1+lbN次比较。虽然这种查找法的效率有所提高，但是对于一个边填写边引用的动态查找符号表来说，每填进一项就引起表中内容重新排序，这无疑会增加时间的开销。

对于动态查找的符号表，可以采用二叉树结构来组织有序符号表。对二叉树中的任一结点P来说，它的左子树上的任何结点都大于结点P的值，而右子树上任何结点都小于结点P的值，这样一棵二叉树实际上是二叉排序树。每当向符号表中填入一项时，总是将其作为二叉排序树的叶结点插入到合适位置。查找的过程也是这样，

首先将给定值K与二叉排序树根结点值比较，若相等则查找成功；若不等，则当

根结点值小于K时到根的左子树去继续查找，否则到根的右子树去继续查找。在随机情况下，二叉排序树的平均查找长度为1+4lbN。较之折半查找法，虽然二叉排序树的查找速度略有降低，但它大大减少了生成有序符号表的时间，是一种较好的有序符号表结构。 3．散列符号表

散列符号表是大多数编译程序采用的一种符号表。符号表采用散列技术，相对来讲具有较高的运行效率，特别适用于边填写边引用的动态查找符号表。 散列符号表又称哈希符号表，其关键在于引进了一种函数——哈希函数，并将程序中出现的标识符通过哈希函数进行映射，得到的函数值作为该标识符在符号表中的位置。

哈希函数(Hash)一般具有如下性质：

(1) 函数值只依赖于对应的标识符； (2) 函数的计算简单且高效；

(3) 函数值能比较均匀地分布在一定范围内。 错误处理

1 语法错误的校正

对源程序错误的处理通常有两类不同方法：一类是对错误进行适当的修补；另一类是跳过有错误的那个语法成分。第二类方法又称为错误的局部化法。 2 语义错误的校正 (1)．遏止错误株连信息

错误株连，是指当源程序出现一个错误时，此错误将导致发生其它错误，而后者可能并不是一个真正的错误。

为了遏止这种株连信息，一种简单的办法是在源程序中用一个“正确”的标识符去替换出错的标识符，同时把新标识符登入符号表中并尽可能填入各种属性。 (2)．遏止重复出错信息

防止诸如此类的重复出错信息比较容易。当在源程序中发现使用了一个未经说明的标识符时，就将它登入符号表中，并根据上下文填写所查出的一些属性；再建立另一张表，其中各个登记项有相应标识符的各种错误用法，在遇到一个错用的标识符时就顺序检查这张表。如果以前曾按同样方式使用过该标识符，就不再输出出错信息；否则，除输出出错信息外，还要将本次错用的情况登入该表。

编译原理实验程序的开发

编译原理是计算机类专业特别是计算机软件专业的一门重要专业课。设置

该课程的目的在于系统地向学生讲述编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术，使学生通过学习既掌握编译理论和方法方面的基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。编译原理是一门理论性和实践性都比较强的课程，使读者学习起来普遍感到内容抽象、不容易理解。在教学过程中发现有很多学生对课程不理解，为了辅助教学，帮助学生更好的学习编译原理在开发了课件后又开了几个经典的编译原理实验程序。进行上机实验的目的是使学生通过完成上机实验题目加深对课堂教学内容的理解。同时培养学生实际动手能力。

1词法分析程序的开发

实验内容：

用C语言编写程序，输入B类单词的源程序，利用词法分析将其转换为单词，

二元式形式输出。 实验目的：

深刻理解词法分析的含义，握计算机内部程序的编译过程。 实现过程：

本次实验所用的语言为标准C，以下同。本功能实现的主函数为getToken函数。通过从文件中读取字符到缓冲区中并由C语言字符的状态转换图流程判断返回一个字符（Token）。分析出来的Token主要分为关键字，专用符号，标记符号。 主体结构的说明：

在这里说明部分告诉我们使用的LETTER,DIGIT, IDENT(标识符,通常定义为字母开头的字母数字串)和STR(字符串常量,通常定义为双引号括起来的一串字符)是什么意思.这部分也可以包含一些初始化代码.例如用#include来使用标准的头文件和前向说明(forward ，references).这些代码应该再标记\和\之间;规则部分>可以包括任何你想用来分析的代码;我们这里包括了忽略所有注释中字符的功能,传送ID名称和字符串常量内容到主调函数和main函数的功能. 实现原理：

程序中先判断这个句语句中每个单元为关键字、常数、运算符、界、对 不同的单词符号给出不同编码形式的编码，用以区分之。 实验代码： #include #include int i,j,k; char c,s;

char token[10],a[30]; int letter(chars) {

if(s>=97&&s<=122) return(1); else return(0); }

int digit(chars) {

if(s>=48&&s<=57) return(1) else return(0); }

void get(); {

i++; c=a[i]; int lookup() {

if(!strcmp(token,”while”)) return(1); else if(!strcmp(token,”if”)) return(2); else if(!strcmp(token,”else”)) return(3); else if(!strcmp(token,”switch”)) return(4); else if(!strcmp(token,”case”)) return(5); else return(6); }

void main() {

printf(“input your source program:\\n”);

i=0; do {i=i+1;

scanf(“%c”,&a[i]); }

wile(a[i]!=“#”); getchar(): for(k=1;k<10;k++) token[k]=” “; i=0;j=0; get();

while(c!=”#”) {

switch(c); {

case ‘a’; case ‘b’; case ‘c’; case ‘d’; case ‘e’; case ‘f’; case ‘g’; case ‘h’;

case ‘i’; case ‘j’; case ‘k’’ case ‘l’; case ‘m’; case ‘n’; case ‘o’; case ‘p’; case ‘q’; case ‘r’; case ‘s’;

本文来源：https://www.bwwdw.com/article/h9c6.html