编译原理教案

本文格式为Word版，下载可任意编辑——编译原理教案第1章编译原理概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（a）编译过程

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

2编译程序的发展及分类

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

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

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

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

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

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

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

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，结果）

语义分析和中间代码生成阶段的工作寻常穿插在语法分析过程中完成，因而语义翻译程序寻常由一组语义子程序组成。每当分析出一个完整的语法单位，就调用相应的语义子程序执行相应的分析和翻译任务。如当语法分析器分析完varx,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的四元式

序号四元式12345(*,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的优化后的四元式

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

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

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

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

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

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

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

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

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

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

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

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

voidmain（）

{}

(2)常数表和标号表

表4常数表

表3符号表intm，n，k；

NamemnkInformation整型、变量地址整型、变量地址整型、变量地址

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

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

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

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

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

表6中间代码表

序号（1）（2）（3）（4）（5）（6）（7）（8）（9）OP＝＝＝(Jump)

%%

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

“main〞|〞int〞|〞if〞{Upper(yytext,yyleng);printf(\{id}{printf(\“+〞|〞-〞|〞*〞{printf(\\\n\%%

/*辅助过程*/

Upper(char*s,intl){inti;

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

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

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

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

E'→T→FT'T'→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-3G[E]：

E→TE'E'→T→FT'T'→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)又

ε，∴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’）-{ε}又自底向上分析法

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

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

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

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

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

ifACTION[S,a]=Si{

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

elseerror();

ε∴FOLLOW(T)参与FOLLOW(F)

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

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

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

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

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

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

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

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

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

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

{j=j+1;optr[j]=s;get();}

elseif(f[optr[j]==g(s)){

if(optr[j]==’(‘get();}

elseprintf(“error!!!\\n〞);}

elseprintf(“error!!!\\n〞);

}}

调试运行：pleaseinputyourexpression;6*(7+1)#enter(+,1,7,8)(*,8,6,48)

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

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

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

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

(2)假使E为E1opE2形式，则它的后缀表示为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表示按条件转移的两个双目后缀运算符。例如：BTBF

(4)循环语句。for循环语句为：for(i=m；i,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代码优化例如

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

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

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

case‘t’;case‘u’;case‘v’;case‘w’;case‘x’;case‘y’;case‘z’;

while(letter(c)||digit(c)){

token[j]=c;j++;get();}i--;k=lookup();

if(k==6)printf(“(%d,%s)\\n〞,k,token);elseprintf(“(%d,-)\\n〞,k);break;