《编译原理》教案

《编 译 原 理》教案

授课题目（教学章、节或主题）： 第一章 引论 教学目的、要求（分掌握、熟悉、了解三个层次）： 简单介绍学习此课程的目的和要求 初步了解编译技术的基本原理和方法 熟悉Compiler的基本概念 掌握Compiler的结构和功能 教学重点和难点：编译程序的基本结构和功能 授课类型（请打√）：理论课? 讨论课□ 实验课□ 练习课□ 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： 编译程序的基本结构如何？各部分功能？ 教学内容

0 课程学习的要求及任务，学习方法介绍，成绩考核标准。

第一章 引论

1.1 什么叫编译程序？

通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序(称为源语

言程序)转换成另一种语言程序(称为目标语言程序)，而后者与前者在逻辑上是等价的。如果 源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这样的?高级语言?，而目标语言是诸如汇编语言或机器语言之类的?低级语言?，这样的一个翻译程序就称为编译程序。

高级语言程序除了像上面所说的先编译后执行外，有时也可?解释?执行。一个

源语言的解释程序是这样的程序，它以该语言写的源程序作为输入，但不产生目标程序，而是 边解释边执行源程序本身。本书将不对解释程序作专门的讨论。实际上，许多编译程序的构造与实现技术同样适用于解释程序。

根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和

调试 的编译程序称为诊断编译程序(Diagnostic Compiler)，着重于提高目标代码效率的编译程序叫优化编译程序(Optimizing Compiler)。现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过?开关?进行选择。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。 如果一个编译程序产生不同于其宿主机的机器代码， 则称它为交叉编译程序

(CrOSS Compiler)。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序(Retargetable Compiler)。

1

课时安排 2 授课时间 第1周 第1、2节

1.2 编译过程概述

编译程序过程: 从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成.

1.3 编译程序的结构

编译程序的结构可以按照从输入源程序开始到输出目标程序为止的整个编译过

程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成。 1.3.1 编译程序总框

编译程序的结构可以按照这五个阶段的任务分模块进行设计。下图给出了编译程

序的总框。

1.3.2 表格与表格管理

编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编

译各阶段的进展状况。在编译程序使用的表格中，最合理的是符号表。 编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。合理地设计和使用表格是编译程序构造的一个重要问题。在编译程序使用的表格中，最重要的是符号表。它用来登记源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等；如果是变量名，它的类型是什么、所占内存是多大、地址是什么等等。通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填人到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。

当扫描器识别出一个名字(标识符)后，它把该名字填人到符号表中。但这时不能

完全确定名字的属性，它的各种属性要在后续的各阶段才能填人。例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确定。

由此可见，编译各阶段都涉及到构造、查找或更新有关的表格。 1.3.3 出错处理

2

遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，

生产新的中间结果或目标程序。一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。这部分工作是由专门的一组程序(叫做出错处理程序)完成的。一个好的编译程序应能最大限度地发现源程序中的各种错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。如果不仅能够发现错误，而且还能自动校正错、误，那当然就更好了。但是，自动校正错误的代价是非常高的。

编译过程的每一阶段都可能检测出错误，其中，绝大多数错误可以在编译的前三

阶段检测出来。源程序中的错误通常分为语法错误和语义错误两大类。语法错误是指源程序中不符合语法(或词法)规则的错误，它们可在词法分析或语法分析时检测出来。例如，词法分析阶段能够检测出?非法字符?之类的错误；语法分析阶段能够检测出诸如?括号不匹配?、?缺少；?之类的错误。语义错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。语义错误通常包括：说明错误、作用域错误、类型不一致等等。 1.3.4 遍

遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，

生产新的中间结果或目标程序。通常，每遍的工作由从外存上获得的前一遍的中间结果开始(对于第一遍而言，从外存上获得源程序)，完成它所含的有关工作之后，再把结果记录于外存。既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。例如，词法分析这一阶段可以单独作为一遍，但更多的时候是把它与语法分析合并为一遍；为了便于处理，语法分析和语义分析与中间代码产生又常常合为一遍。在优化要求很高时，往往还可把优化阶段分为若干遍来实现。

当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如，我们可以把词法

分析、语法分析及语义分析与中间代码产生这三阶段安排成一遍。这时，语法分析器处于核心位臵，当它在识别语法结构而需要下一单词符号时，它就调用词法分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语义分析并产生相应的中间代码。

一个编译程序究竟应分成几遍，如何划分，是与源语言、设计要求、硬件设备等

诸因素有关的，因此难于统一划定。遍数多一点有个好处，即整个编译程序的逻辑结构可能清晰一点。但遍数多势必增加输入／输出所消耗的时间。因此，在主存可能的前提下，一般还是遍数尽可能少一点为好。应当注意的是，并不是每种语言都可以用单遍编译程序实现。 1.3.5 编译前端与后端

概念上，我们有时把编译程序划分为编译前端和编译后端。前端主要由与源语言

有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。

可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程

序。如果后端的设计是经过精心考虑的，那么后端的改写将用不了太大工作量，

3

这样就可实现编译程序的目标机改变。也可以设想将几种源语言编译成相同的中间语言，然后为不同的前端配上相同的后端，这样就可为同一台机器生成不同语言的编译程序。然而，由于不同语言存在某些微妙的区别，因此在这方面所取得的成果还非常有限。

为了实现编译程序可改变目标机，通常需要有一种定义良好的中间语言支持。例

如．在著名的Ada程序设计环境APSE中，使用的是一种称为Diana的树形结构的中间语言一个Ada源程序通过前编译转换为Diana中间代码，由编译后端把Diana中间代码转换为目标代码。编译前端与不同的编译后端以Diana为界面，实现编译程序的目标机改变。

又如，在Java语言环境中，为了使编译后的程序从一个平台移到另一个平台，

Java定义一种虚拟机代码--Bytecode。只要实际使用的操作平台上实现了的Java解释器，这个操作平台就可以执行各种Java程序。这就是所谓Java语言操作平台无关性。

1.4 编译程序与程序设计环境

开发通常还需要一些其它的工具；如编辑程序、连接程序，调试工具等等。编译

程序与这些程序设计工具一起构成所谓的程序设计环境。

在高级语言发展的早期，这些程序设计工具往往是独立的，缺乏整体性，而且也

缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，现在人们越来越倾向于构造集成化的程序设计环境。一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全生命周期。有代表性的集成化程序设计环境有Ada语言程序设计环境APSE、LISP语言程序设计环境INTERLISP等。广大读者所熟悉的Pascal、TurboC、VisualC++等语言环境也都可认为是集成化的程序设计环境。 1.5 编译程序的生成

以前人们构造编译程序大多是用机器语言或汇编语言做工具的。为了发挥各种不

同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然采用这种工具来构造编译程序。但是，越来越多的人倾向于使用高级语言作为工具来构造编译程序。因为，这样可以节省大量的程序设计时间，而且所构造出来的编译程序也易于阅读、修改和移植。

人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于

自动产生扫描器，有些可用于自动产生语法分析器，有些甚至可用来自动产生整个的编译程序。如：编译程序-编译程序、编译程序产生器、翻译程序书写系统等，它们是按照对源语言和目标语言（或机器）的形式描述（作为输入数据）而自动产生编译程序的。本课程将把自动产生器作为一个重要课题来讨论。 近些年来，有些人主张采用?自编译方式?产生编译程序。意思是，先对语言的核心部分构造一个小小的编译程序（可用手编实现），再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就象滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。这种通过一系列自展途径而形成编译程序的过程叫作自编译过程。

现在，有些编译程序是通过?移植?得到的。即把某一机器上的编译程序移植到

另一机器上。着需要寻求某种适当的?中间语言?。但是，由于建立通用中间语言实际上办不到，因此，移植也只能在几种语言和几种机器之间进行。

4

授课题目（教学章、节或主题）： 第二章 词法分析 课时安排 12 第1周 第3-6节 授课时间 第2周 第1-6节 第3周 第1、2节

教学目的、要求（分掌握、熟悉、了解三个层次）： 了解词法分析器的构造方法 熟悉词法分析的任务和过程 掌握正规式和有限自动机的基本概念 教学重点和难点：词法分析器的设计、正规表达式和有限自动机、正规表达式和有限自动机的等价性、正规文法和有限自动机间的转换 授课类型（请打√）：理论课? 讨论课□ 实验课? 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P63：3，6，7，8，12，14

教学内容

第二章 词法分析

2.1 对于词法分析器的要求

首先讨论词法分析器输出的单词符号的一般形式，然后研究词法分析器应如何和

语法分析器相衔接。

2.1.1 词法分析器的功能和输出形式

词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基

本语法符号，程序语言的单词符号一般可分为下列五种： 1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等； 2 标识符 用来表示各种名字，如变量名、数组名和过程名等等； 3 常 数 各种类型的常数，如125，0.718、TRUE等等； 4 运算符 如+、-、*、/等等；

5 界 符 如逗号、括号、分号等等。

标识符一般统归为一种。常数则宜按类型（整、实、复或布尔）分种。基本字可

将其全体视为一种，也可以一字一种。运算符可采用一符一种的分法，但也可以把具有一定共性的算符（如所有关系符）视为一种。界符一般用一符一种的分法。 如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代

表它自身了。若一个种别含有许多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给出自身的值。 2.1.2 词法分析器作为一个独立子程序

可以使整个编译程序的结构更简洁、清晰和条例化。

5

2.2 词法分析器的设计

我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。

2.2.1 输入、预处理

词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，

这个缓冲区称为输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。

预处理的工作包括：剔除无用的空白、跳格、回车和换行符等编辑性字符；预

处理工作还可以包括源程序和出错信息的列表打印。 2.2.2 单词符号的识别：超前搜索

词法分析器的结构如下图所示：当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，扫描器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。

源程序串 预处理 子程序 输入缓冲区 列表 扫描缓冲区 扫描器 单词符号 图3.1 词法分析器

下面我们来介绍一下单词符号识别的一个简单方法——超前搜索。

基本字的识别 有些语言的基本字的输入表示有特殊标志，如加双引号（如

?BEGIN?），在这种情况下，基本字的识别是很直接的，不存在什么困难。 象FORTRAN这样的语言，基本字不加特殊保护，基本字和用户自定义的标识符或标号之间没有特殊的界符作间隔，这就使得基本字的识别甚为麻烦。这里就需要用到超前搜索。 2.2.3 状态转换图

使用状态转换图是设计词法分析程序(扫描器)的一种好途径。转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结(即箭弧始节)状态下可能出现的输入字符或字符类。如下图3.2（a）所示。

在状态1下，若输入字符X，则读进X，并转换到状态2。若输入字符Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。

6

图3.2（a）状态转换图示例

2.2.4 状态转换图的实现

一个状态转换图可用于识别（或接受）一定的字符。大多数程序语言的单词符号

都可以用转换图予以识别。转换图非常易于用程序实现，最简单的办法是让每个状态结点对应一小段程序。下面我们将引进一组全局变量和过程，把它们作为实现转换图的基本成分。这些变量和过程是：

1. CHAR 字符变量，存放最新读进的源程序字符。 2. TOKEN 字符数组，存放构成单词符号的字符串。

3. GETCHAR 子程序过程，把下一个输入字符读到CHAR中，把搜索指示器前移一字节位臵。

4. GETBC 子程序过程，检查CHAR中的字符是否为空白.若是，则GETCHAR直到CHAR中进入一个非空白符。

5. CONCAT 子程序过程，把CHAR中的字符连接TOKEN之后。例如，TOKEN原来的值为‘AB'，而CHAR中存放着'C'，经调用CONCAT后，TOKEN的值就变为'ABC'。

6. LETTER和DIGIT布尔函数过程，它们分别CHAR中的字符是否为字母和数字，从尔给出真值TRUE或假值FALSE。

7. RESERVE 整型函数过程，对TOKEN中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值(假定0不是保留字的编码)。 8. RETRACT 子程序过程，把搜索指示器回调一个字节位臵，把CHAR中的字符臵为空白。

2.3 正规表达式与有限自动机 2.3.1 正规式与正规集

设Σ是一个有穷字母表，它的每个元素称为一个字符。Σ上的一个字（也叫字符

串）是指由Σ中的字符所构成的一个有穷序列。不包含任何字符的序列称为空字，记为ε。用Σ* 表示Σ上的所有字的全体 ，空字ε也包括在其中。 例如，若Σ={a，b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa}下面是正规式和正规集的递归定义： 1.和Φ 都是 上的正规式，它们所表示 的正规集分别为{ε} 和 Φ； 2.任何α∈Σ，是Σ上的一个正规式，它所表示的正规集为{α}; 3.假定U和V都是 上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U V）、（U|V）和（U）*也都是正规式，它们所表示的正规集分别为L（U）?L（V）、L（U）.L（V）（连接积）和 （L（U））*（闭包）。

仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。算符的优先顺序为：先\，次\，最后\。

7

例如，令Σ ={a，b} ，下面是 Σ上的正规式和相应的正规集： ba*： Σ上所有以b为首后跟任意多个a的字 a(a| b)* ： Σ上所有以a为首的字

(a| b)* (aa| bb)(a|b)*： Σ上所有含有两个相继的a或两个相继的b的字

又例如，令Σ={A，B，0，1} ，则

(A|B)(A|B|0|1)* ： Σ上的\标识符\的全体 (0|1)(0|1)* ： Σ上的\数\的全体

若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。 令U、V和W 均为正规式，显而易见，下列关系普遍成立 1. V=V|U （交换律）

2. U|(V|W)=(u|v)|w（结合律） 3. U|(V|W)=(U|V)|W（结合律）

4. U|(VW)=UV|UW（分配律） (V|W)U=VU|WU 5.εU=Uε =U

2.3.2 确定有限自动机（DFA）

设一个确定的有限自动机（DFA）M是一个五元式M=(S, Σ ,f,S0, Z)其中

1. S是一个有限集，它的每个元素称为一个状态；

2. 是一个有穷字母表Σ，它的每个元素称为一个输入字符；

3. f是一个从S×Σ至S的（单值）部分映照。f（s，a）=s'意味着：当现行状态为s，输入字符a时，将转换到下一状态s'。我们把s'称为s的一个后继状态； 4. S0?S，是唯一的一个初态； 5. Z?S，是一个终态集（可空）。

一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元

素表示f（s，a）的值，这个矩阵称为状态转换矩阵。 例如，有DFA M=({0,1,2,3 ,{a,b ,f,0,{3 }其中f为： f(0,a)=1 f(0,b)=2 f(1,a)=3 f(4,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3

则对应的状态转换矩阵如下表3.2所示：

表3.2 状态转换矩阵 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3

一个DFA也可以表示成一张（确定的）状态转换图。

对于Σ*中的任何字?，若存在一条从初态结到某一条终态结的道路，且这条路上所有弧的标记符连接成的字等于?，则称?可为DFA M 所识别（读出或接受）。若 M的初态结同时又是终态结， 则空字ε可为M所识别（或接受）。

上例所定义的DFA M相应的状态转换图如下所示：它能识别Σ上所有含有相继

8

两个a或相继两个b的字。

图3.5 状态转换图

2.3.3 非确定有限自动机(NFA)

设一个确定的有限自动机（DFA）M是一个五元式M=(S,Σ,f,S0, Z)其中 1. S是一个有限集，它的每个元素称为一个状态；

2.Σ是一个有穷字母表，它的每个元素称为一个输入字符； 3. f是一个从S×Σ*到S的子集的映照，即 f：S×Σ*? 2S 4. S0?S，是非空初态集；

5. Z ?S，是一个终态集（可空）。

2.3.4 正规文法与有限自动机的等价性

对于正规文法G和有限自动机M，如果L（G）＝L（M），则称G和M是等价

的。关于正规文法和有限自动机的等价性，有以下结论： （1） 对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机

（FA）M，使得L（M）＝L（G）。

（2） 对每一个FA M，都存在一个右线性正规文法GR或左线性正规文法GL，

使得L（M）＝L（GR）＝L（GL）

2.3.5 正规式与有限自动机的等价性 我们可以证明：

（1） 对任何FA M，都存在一个正规式r，使得L（r）＝L（M）。 （2） 对任何的正规式r，都存在一个FA M，使得L（M）＝L（r）。

上述结论加上前面章节所证明的结论，说明正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。 2.3.6 确定有限自动机的化简 等价状态；最少化。 2.4 词法分析器的自动产生

教学目的：使用状态转换图构造词法分析程序；上机实践LEX的实现。 2.4.1 语言LEX的一般描述

一个LEX源程序主要包括两部分。一部分是正规定义式，另一个是识别规则。 产

生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。一个产生式的 形式是 A?a 其中，箭头(有时也用：：＝)左边的A是一个非终结符，称为产生式的左部符号；箭头右边的a是由终结符号或非终结符号组成的符号串，称为产生式的右部。我们有时也说，产生式A?a是关于A的一条产生规则。产生式是

9

用来定义语法范畴的。

例如，令i 代表已定义的范畴?变量?，那么，产生式 算术表达式?i 意味着把?算术表达式?这个范畴定义为?变量?。在有的书上，???也用?：：＝?表示：这种表示方法也称巴科斯范式。 2.4.2 超前搜索

在某些语言中，要识别一个单词符号必须超前看若干字符。 2.4.3 LEX的实现

LEX的编译程序旨在将一个LEX源程序改造为一个词法分析器L，这个词法分

析器L将像有限自动机那样工作。

相关介绍：人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器(如LEX)，有些可用于自动产生语法分析器(如YACC)，有些甚至可用来自动产生整个的编译程序。这些构造编译程序的工具称为编译程序——编译程序、编译程序产生器或翻译程序书写系统，它们是按对源程序和目标语言(或机器)的形式描述(作为输入数据)而自动产生编译程序的。

10

授课题目（教学章、节或主题）： 第三章 语法分析-上下文无关文法、形式语言和文法 教学目的、要求（分掌握、熟悉、了解三个层次）： 课时安排 授课时间 6 第3周 第3-6节 第4周 第1、2节

理解和定义上下文无关文法，为学习和构造编译程序打下良好基础。 理解语言和文法的定义 掌握文法的等价变换及语法描述方法 了解文法的分类 教学重点和难点：文法的直观概念、文法和语言的形式定义、文法的类型、语法树和二义性、文法中的实用限制、句型的分析 授课类型（请打√）：理论课? 讨论课□ 实验课□ 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P36：6，8，11 教学内容 3.1.1 上下文无关文法

箭头‘-->’读为?定义为?，直竖‘|’读为?或?，它们是元语言符号。在后面

的讨论中，根据不同情况，我们将用大写字母A、B、C…或汉语词组(如，算术表达式)代表非终结符号，特别是用小写字母a、b、c…代表终结符，用α、β、γ等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。 例如，下面是一个上下文无关文法：

E-->i|EAE A-->+|*

其中，E、A是非终结符，E是开始符号，而i、+和*是终结符。

一个上下文无关文法如何定义一个语言呢?其中心思想是，从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如，我们考虑下面的文法G:

E-->E十E | E*E | (E) |i

其中，唯一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发，进行一系列的推导，推出种种不同的算术表达式来。例如，根据规则E一>(E)我们可以说：从‘E’可直接(一步地)推出‘(E)’。与前面一样，我们用‘?’表示?直接推出?，这样，这句话就可表示为:E?(E)。若对‘(E)’中的E使用规则E-->E+E，就有

(E)?(E+E)。即，从‘(E)’可直接推出‘(E+E)’。把上述这两步合并起来，就有

E?(E)?(E+E)。再对‘(E+E)’中的E相继两次使用规则E-->i之后，我们就有(E) ?(E+E)?(i+E)?(i+i)。

11

我们称这样的一串替换序列是从E推出(i+i)的一个推导。这个推导提供了一个证明，证明(i+i)是文法(2.1)所定义的一个算术表达式。注意，推导每前进一步总是引用一条规则(产生式),而符号‘?’指仅推导一步的意思。

我们可以用一种图示化的方法来表示这种推导，如下图2.1，说明He gave me a book是一个语法正确的句子。这种图形表示称为语法分析树。

定义 ?he gave me a book‖这个英文句子的规则可以说就是一个上下文无关文法。其中，He，me，book，gave，a等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里称为开始符号；<间接宾语>--><冠词><名词>这种书写形式称为产生式。

归纳起来，一个上下文无关文法C包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。 <句子>

<主语> <形容词>

<名词>

<动词>

<谓语>

<宾语>

<

名

<形容词>

he

a boo

图2.1语法树

非终结符号(也称语法变量)用来代表语法范畴。例如，?算术表达式?、?布尔表达式?、?赋值句?、?分程序?、?过程?等，它们都是现今程序语言常见的语法范畴。我们也可以说，一个非终结符代表一个一定的语法概念。因此，一个非终结符是一个类(或集合)记号，而不是一个个体记号。例如，?算术表达式?这个非终结符乃代表一定算术式组成的类。因而，也可以说，每个非终结符号表示一定符号串的集合(由终结符号和非终结符号组成的符号串)。

开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为?句子?。但在程序语言中，我们最终感兴趣的是?程序?这个语法范畴，而其它的语法范畴都只不过是构造?程序?的一块块砖石。

3.1.2 语法分析树与二义性

gave

me

12

前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，

或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，枝叶在下。语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。例如，对于文法(2.1)，关于(i*i+i)的推导(2.2)的语法树如图2.2所示。

E(根) （ E ） E + E E * E i i i 图2.2 语法树

这就是说，一棵语法树表示了一个句型种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表。

如果我们坚持使用最左(最右)推导，那么，一棵语法树就完全等价于一个最左(最右)推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致性。但是，一个句型是否只对应唯一的一棵语法树呢?也就是，它是否只有唯一的一个最左(最右)推导呢?不尽然。 3.1.3 形式语言鸟瞰

前面乔姆斯基把文法分成四种类型，即0型，1型，2型，和3型。0型强于1

型，1型强于2型，2型强于3型。这几类文法的差别在于对产生式施加不同的限制。

0型文法：也称短语文法，其能力相当于图灵机。任何0型语言都是递归可枚举

的，反之，递归可枚举集必定是一个0型语言。

1型文法：也称上下文有关文法，对非终结符进行替换时务必联系上下文，并且

一般不允许替换成空串。

2型文法：也称上下文无关文法

3型文法：也称右线性文法，这类文法等价于正规式，所以也称正规文法。只有

下面两种形式的产生式：A→Ba 或A→a。 3.2.1文法等价的概念：

若L(G1)=L(G2),则称文法G1和G2是等价的

例如：下列两个文法是等价的

G1[A]: A 0R A 01 R A1 G2[A]：S 0S1 S 01 因为L(G1)=L(G2)={0n1n|n ≥1}

13

定义：对文法进行变换，使变换后的文法满足某种要求并于原文法等价，这种变换成

为文法的等价变换。 3.2.2、增广文法 定义：设文法G[S]={VN,VT,P,S}，构造文法G‘[S‘]=(VN∪{S‘},VT,P‘,S‘),其中，P‘={A

α|A α ∈P}∪{S‘ S},显然L(G)= L(G‘)，称G‘为文法G的增广文法。 例：[Z]:Z →abZA|a A→b

经等价变换后可得到增广文法G[A?]: Z‘ →Z

Z →abZA|a A→b

3.2.3、提取左因子 定义：若文法中有产生式P→δβ1|δβ2|…|δβn,则称该文发含有左因子δ。其中

P ∈VN ，β1，β2… βn ∈ (VN∪ VT)*。 例：文法[S]: S →iEtS|iEtSeS|a E →b 提取左因子该文法变为： G[S]: S →iEtSS‘|a S‘ →eS|ε E →b 3.2.4、消除左递归

定义：若文法中存在推导：P ?+ Pα,则称该文法含有左递归。若存在产生式P ? P

α,则称该文法含有直接左递归。若存在产生式P ? P1α，P1 ?P2β, ……,Pn-1 ?Pnγ，Pn ? Pδ,则称该文法含有间接左递归。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。 直接左递归的消除方法：

假设非终结符P存在产生式P ?Pα|β 删除左递归产生式P ?Pα

引入新的非终结符P‘消除文法中的左递归，得： P ?βP‘ P‘ ?αP‘|ε

间接左递归的消除方法：

将间接左递归转化为直接左递归； 消除直接左递归；

化简文法，删除含有从起始符号无法到达的非终结符的产生式 最后，作为描述程序语言的上下文无关文法，我们对它有几点限制。

（1）文法中不含任何下面形式的产生式： P→P因为这种产生式除了产生二义性

外没有任何用处。

（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导 S?*?P?.

另一方面意味着，必须存在终结符串??VT*,使得P?+?；也就是，对于P不存在

永不终结的回路。

我们以后所讨论的文法均假定满足上述两条件。

14

授课题目（教学章、节或主题）： 第三章 语法分析——自上而下分析 课时安排 12 第4周 第3-6节 授课时间 第6周 第1-6节 第7周 第1-2节

教学目的、要求（分掌握、熟悉、了解三个层次）： 了解确定的自顶向下分析思想 熟悉某些非LL（1）文法到LL（1）文法的等价变换 掌握LL（1）文法的判别、确定的自顶向下分析方法 教学重点和难点：语法分析器的功能、确定的自顶向下分析思想、LL（1）文法的判别、某些非LL（1）文法到LL（1）文法的等价变换、不确定的自顶向下分析思想、确定的自顶向下分析方法 授课类型（请打√）：理论课? 讨论课□ 实验课? 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P81：1，2，4 教学内容

第三章 语法分析——自上而下分析

3.1 语法分析器的功能

语法分析器：是这样的一个程序，它将按文法的产生式，识别输入符号串是否为

一个句子。输入串是指由单词符号（文法的终结符）组成的有限序列。

语法分析的方法：可大致分为两类，一类是自下而上分析法，另一类是自上而下分析法。所谓自下而上分析法就是从输入串开始，逐步进行?归约?，直至归约到文法的开始符号。自上而下分析过程恰好与此相反，它从文法的开始符号出发，反复使用各种产生式，寻找?匹配?于输入串的推导。 3.2 自上而下分析面临的问题

本节主要是通过例子使我们认识到，作自上而下分析所遇到的主要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒重来，为解决这些问题我们要消除左递归和消除回溯。 3.3 LL(1)分析法

自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。 3.3.1 左递归的消除

假定关于非终结符P的规则为 :P--> P|αβ

15

其中，每个 都不以P开头，那么我们可以把P的规则改写成如下的非直接左递归形式：

p --βp'

p'-- αp'|ε(ε 为空字)

这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。 3.3.2 消除回溯、提左因子

我们首先来看一下在不得回溯的情况下对于文法有什么要求。前面已经说过，欲实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，对G 的所有的非终结符号的每个候选?定义它的终结首符集FIRST(?)为：

FIRST(?)={a|??*a…,a?VT}

特别是，若??*ε，则规定ε?FIRST(?)。换句话说FIRST(?)是?的所有可能推导的开头终结符或可能的ε。如果非终结符A的所有候选首符集两两不相交，即A

的

任

何

两

个

不

同

的

候

选

?i

和

?j

FIRST(?i)?FIRST(?j) = ?那么，当要求A匹配输入串时，A 就能根据它所面临的第一个输入符号a，准确地指派某个候选前去执行任务。这个候选就是那个终结首符集含a的?。

如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是提取公共左因子。例如，假定关于A 的规则是

A???1|??2|…|??n|?1|?2|… |?m （其中每个?不以?开头）那么，可以把这些规则改写成：A??A‘|?1|?2|… |?m

A‘?|?1|?2|…|?n

3.3.3 LL(1)分析条件

假定S是文法G的开始符号，对于任何非终结符A我们定义：

FOLLOW(A) = { a | S?*…Aa…,a?VT}

特别是，若S?*…A， 则规定#?FOLLOW(A). 也就是说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或者?#‘。判断某给定文法是否为LL(1)文法其条件为：

（1）文法不含左递归。

（2）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。

即，若 A?a1 | a2 |…| an 则： FIRST(?i)?FIRST(?j) = ?（i?j ）

(3) 对文法中每一个终结符A，若它存在某个候选首符集包含ε，则

FIRST(A) ?FLLOW(A)= ?一个文法若满足以上条件，则称该文法G为LL(1)文法

16

3.4 递归下降分析程序构造

在不含左递归和每个非终结符的所有候选终结首符集都两两不相交的条件下，可

能（仅是可能）构造一个不带回溯的自上而下分析程序.

文法如下：

E--> TE‘ E‘--> +TE‘/ε T--> FT‘ T‘--> *FT‘/ε F--> （E）/i

当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分

析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。 3.5 预测分析程序

用高级语言的递归过程描述递归下降分析器只有当具有实现这种过程的编译系

统刚才有实际意义。实现LL(1)分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。我们现在要介绍的预测分析程序就是属于这种类型的LL(1)分析器

3.5.1 预测分析程序工作过程

预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号

a行事的。

3.5.2 预测分析表的构造

为了构造预测分析表M，我们需要先构造与文法G有关的集合FIRST和FOLLOW. 消除左递归和提取左因子将有助于获得无多重定义的分析表M。 可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)

的。

3.6 LL(1)分析中的错误处理

我们以预测分析为例。在预测分析过程中，出现了下列两种情况，则说明遇到了语法错误。

(1)栈顶的终结符与当前的输入符号不匹配。

(2)非终结符A处于栈顶，面临的输入符号为a，但分析表M中的MIA，a]为空。发现错误后，要尽快地从错误中恢复过来，使分析能继续进行下去。基本的做法就是跳过输入串中的一些符号直至遇到?同步符号?为止。这种做法的效果有赖于同步符号集的选择。我们可以从以下几个方面考虑同步符号集的选择。 (1)把FOLLOW(A)中的所有符号放人非终结符A的同步符号集。如果我们跳读一些输入符号直到出现FOLLOW(A)中的符号，把A从栈中弹出，这样就可能使分析继续下去。

(2)对于非终结符A来说，只用FOLLOW(A)作为它的同步符号集是不够的。例如，如果分号作为语句的结束符(C语言中就是这样的)，那么作为语句开头的关键字就可能不在产生表达式的非终结符的FOLIDW集中。这样，在一个赋值语句后少一个分号就可能导致作为下一语句开头的关键字被跳过。

(3)如果把FIRST(A)中的符号加入非终结符A的同步符号集，那么，当FIRST(A)中的一个符号在输人中出现时，可以根据A恢复语法分析。

(4)如果一个非终结符产生空串，那么，推导6的产生式可以作为缺省的情况，这样做可以推迟某些错误检查，但不能导致放弃一个错误。这种方法减少在错误

17

恢复期间必须考虑的非终结符数。

(5)如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶的这个终结符号，并发出一条信息，说明已经插入这个终结符，继续进行语法分析。结果，这种方法使一个单词符号的同步符号集包含所有其它单词符号。

18

授课题目（教学章、节或主题）： 第三章 语法分析——自下而上分析 课时安排 16 第7周 第3-4节 第8周 第1-4节 授课时间 第9周 第1-4节 第10周 第1-4节 第11周 第1-2节 教学目的、要求（分掌握、熟悉、了解三个层次）： 熟悉自下而上分析思想 了解算符优先分析法 掌握LR分析法 教学重点和难点：自下而上分析思想、算符优先分析法、LR分析法 授课类型（请打√）：理论课? 讨论课□ 实验课? 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P133：1，2，3，5

教学内容

第三章 语法分析程序--自下而上分析

所谓自下而上分析法就是从输入串开始，逐步进行―归约‖，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上―归约‖，直到根结。5.1 自下而上分析基本问题

我们首先讨论自下而上分析法的基本思想和基本概念 3.1.1 归约

?移进---归约?：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换（归约为）该产生式的左部符号。我们可用句柄来刻画移进—归约过程的?可归约串?。

3.1.2 规范归约简述

规范规约是关于α的一个最右推导的逆过程。因此，规范规约也称最左规约。最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的，那么规范推导的逆过程必是规范规约。

句柄：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句

型，如果有S?*αAδ且A?＋β则称β是句型αβδ相对于非终结符A的短语。特别是，如果有A?β则称β是句型αβδ相对于规则A??的直接短语。一个句型的最左直接短语称为该句型的句柄。 3.1.3 符号栈的使用与语法树的表示

19

在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的，那么，规范推导(最右推导)的逆过程必是规范归约(最左归约)。请注意句柄的?最左?特征，这一点对于移进—归约来说是重要的。因为，句柄的?最左性?和符号栈的栈顶两者是相关的。对于规范句型来说，句柄的后面不会出现非终结符I号(即，句柄的后面只能出现终结符)。基于这一点，我们可用句柄来刻画移进—归约过程的?可归约串?。因此，规范归约的实质是，在移进过程中，当发现栈顶呈现句柄时就用相应产生式的左部符号进行替换。 3.2 算符优先分析法

现在，我们来讨论一种简单直观、广为使用的自下而上分析法，叫做算符优先分析法。这种方法特别有利于表达式分析，宜于手工实现。算符优先分析过程是自下而上的归约过程，但这种归约未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓算符优先分析就是定义算符之间(确切地说，终结符之间)的某种优先关系，借助于这种优先关系寻找?可归约串?和进行归约。 我们用下面方法表示任何两个可能相继出现的终结符a和b(它们之间可能插有一个非终结符)的优先关系。这种关系有三种： a??b a的优先性低于b a＝?b a的优先性等于b a?>b a的优先性高于b

注意，这三个关系不同于数学中的‘?’，‘＝’和‘>’。例如，a??b并不一定意味着b?>a。

3.2.1 算符优先分析文法及其优先表构造

一个文法，如果它的任何产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：

…QR… 则我们称该文法为算符文法。

在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；?…‘代表有终结符和非终结符组成的任意序列，包括空字。

假定G是一个不含?--产生式的算符文法。对于任何一对终结符a、b，我们说： （1） a=?b 当且仅当文法G中含有形如P?…ab…或P?…aQb…的产生式; (2) ab当且仅当G中含有形如P?…Rb…的产生式， R而R?+…a或R ?+…aQ; 如果一个文法G中的任何终结符对（a, b ）至多只满足下述三关系之一： a=·b, a<·b, a·>b 则称G是一个算符优先文法。 应掌握算符优先表的构造方法。

通过检查G的每个产生式的每个候选式，可以找出满足a=·b的终结符对。为了找出所有满足关系<·和·>的终结符对，我们需要对G的每个非终结符P 构造两个集合FIRSTVT(P)和LASTVT(P):

FIRSTVT(P)={a | P?+a…或P?+Qa…,a?VT而Q?VN } LASTVT(P)={a | P?+…a或P?+…aQ, a?VT而Q?VN }

20

有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系<·和·>的所有终结符对。例如：假定有个产生式的一个候选式为 …aP… 那末，对任何b?FISTVT(P),我们有a<·b。 类似地，假定有产生式的一个候选式为

…Pb…那末，对任何a?LASTVT(P),我们有a·>b.我们首先讨论构造集合FIRSTVT(P)的算法。按定义，我们可用下面两条规则来构造集合FIRSTVT(P): (1)若有产生式P?a…或P?Qa…,则a?FIRSTVT(P)

(2)若a?FIRSTVT(Q)，且有产生式P?Q…，则a?FIRSTVT(P) 同样我们可以构造LASTVT(P)的算法。

在我们有了每个非终结符P 的FISTVT(P)和LASTVT(P)之后我们就能够造文法G的优先表。其算法如下：

FOR 每一条产生式P?X1X2…Xn FOR i:=1 TO n-1 DO BEGIN

IF Xi 和 Xi+1 均为终结符THEN 臵 Xi=·Xi+1IF I<=n-2且Xi和Xi+2都为终结符，而Xi+1为非终结符，则臵Xi=·Xi+2 IF Xi为终结符而Xi+1为非终结符 THEN FOR FISTVT(Xi+1)中的每个a DO 臵 Xi<· a

IF Xi为非终结符而Xi+1为终结符THEN FOR LASTVT(Xi)中的每个a DO 臵 a ·> Xi+1 END 至此我们完成了从文法G构造优先表的算法。 3.2.2 算符优先分析算法

在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。注意，在上述算法中，我们并没有指出应把所找到的最左素短语归约到哪一个非终结符号‘N’。N是指那样一个产生式的左部符号，此产生式的右部和S[j＋1]…S[k]构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。在算符优先归约过程中，我们无法用那些右部仅含一个非终符的产生式(称为单非产生式，如P?Q)进行归约。 3.2.3 优先函数

如果优先函数存在，那么，从优先表构造优先函数的一个简单方法是：

(1)对于每个终结符a(包括#)令其对应两个符号fa和ga，画一张以所有符号f(a)和g(a)为结点的方向图，如果a·>=·b，那么，就从fa画一箭弧至gb；如果a<·=·b，就画一条从gb到fa的箭弧。

(2)对每个结点都赋予一个数，此数等于从该结点出发所能到达结点(包括出发结点自身在内)的个数。赋给fa的数作为f(a)，赋给gb的数作为g(b)。

(3)检查所构造出来的函数f和g，看它们同原来的关系表是否有矛盾。如果没有矛盾，则f和g就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。 现在必须证明：若a=·b，则f(a)＝g(b)；若a<·b，则f(a)b，则f(a)> g(b).

在实际实现算符优先分析算法时，一般不用上述这样的优先表，而是用两个优先函

21

数f和g相对应，函数f称为人栈优先函数，g称为比较优先函数。使用优先函数有两方面的优点：便于作较运算，并且节省存储空间，因为优先关系表占用的存储量比较大。其缺点是，原先不存在优先关系的两个终结符，由于与自然数相对应，变成可比较的了。因而，可能会掩盖输入串的某些错误。但是，我们可以通过检查栈顶符号和输入符号的具体内容来发现那些原先不可比较的情形。 3.2.4 算符优先分析中的出错处理

使用算符优先分析法时，可在两种情况下，发现语法错误：

(1)若在栈顶终结符号与下一输人符号之间不存在任何优先关系；

(2)若找到某一?句柄?(此处?句柄?指素短语)，但不存在任一产生式，其右部为此?句柄?。

针对上述情况，处理错误的子程序也可分成几类。

5.3 LR分析法

LR分析器的核心部分是一张分析表。这张分析表包括两部分，一是?动作?(ACTION)表，另一是?状态转换?(G0TO)表。它们都是二维数组。ACTONIs，a]规定了当状态s面临输入符号a时应采取什么动作。GOTO[s，X]规定了状态s面对文法符号X(终结符或非终结符)时下一状态是什么。显然，[s，X]定义了一个以文法符号为字母表的DFA。每一项ACTON[s，a]所规定的动作不外是下述四种可能之一。

(1)移进 把(s，a)的下一状态s‘=GOTO[s，a]和输入符号a推进栈，下一输人符号变成现行输入符号。

(2)归约 指用某一产生式A??进行归约。假若?的长度为r，归约的动作是A，去除栈顶的r个项，使状态Sm－r变成栈顶状态，然后把(Sm－r，A)的下一状态s’＝GOTO[Sm－r，A]和文法符号A推进栈。归约动作不改变现行输入符号。执行归约动作意味着?(=Xm－r＋1…Xm)已呈现于栈顶而且是一个相对于A的句柄。 (3)接受 宣布分析成功，停止分析器的工作。

(4)报错 发现源程序含有错误，调用出错处理程序。

LR分析器的总控程序本身的工作是非常简单的。它的任何一步只需按栈顶状态s和现行输人符号a执行ACTION[s，a]所规定的动作。不管什么分析表，总控程序都是一样地工作。

一个LR分析器的工作过程可看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程。栈的每一项内容包括状态s和文法符号X两部分。(so，#)为分析开始前预先放在栈里的初始状态和句子括号。栈顶状态为Sm，符号串X1X2…Xm是至今已移进归约出的部分。

输入带

输出带总控程序分析表

下 推 栈

图5.4 LR分析器模型

LR分析器模型如图5.4所示。

22

3.3.1 LR分析器

一个LR分析器实质上是一个带先进后出存储器（栈）的确定有限状态自动机。我们将把?历史?和?展望?材料综合地抽象成某些?状态?

3.3.2 LR（0）项目集族和 LR（0）分析表的构造

字的前缀是指字的任意首部。所谓活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在右边添一些终结符之后，就可以使它成为一个规范句型。 文法G的每一个产生式右部添加一个圆点就称为G的一个LR(0)项目。 构成识别一个文法活前缀的DFA的项目集（状态）的全体称为这个文法的LR(0)项目集规范族 为了使\接受\状态易于识别，我们总是把文法G 进行拓广。假定文法是一个以S 为开始符号的文法，我们构造一个G' 它包含了整个G ，但它引进了一个不出现在G 中的非终结符S' ，并加进了一个新产生式S'-->S，而这个S' 是G' 的开始符号。那么，我们称G' 是G 的拓广文法。这样，便会产生一个仅含项目S'-->S?的状态，这就是唯一的\接受\态。

假定一个文法G 的拓广文法G' 的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含规约项目；（2）或者含有多个规约项目，则称G是一个LR(0)文法。

由于假定LR(0) 文法规范族的每一个项目集不含冲突项目，因此，按上述方法构造的分析表的每一个入口都是唯一的（即不含多重定义）。我们称如此构造的分析表是一张LR(0) 表。使用LR(0) 表的分析器叫做一个LR(0)分析器。

3.3.3 SLR分析表的构造 SLR是LR(0)的一种改进，它在归约时除了考虑历史情况之外还考虑了一点现实。上面所说的LR(0)文法是一类非常简单的文法。这种文法的活前缀识别自动机的每一个状态（项目集）都不含冲突性的项目。如果LR(0)项目集中某个项目存在有冲突的项目集，可以根据读头下符号的不同来消除冲突。 一般而言，对于任何形如I={X?δ?bβ , A?α?, B?α?}LR(0)项目集，若Follow(A) ∩Follow(B)= ?且b ? Follow(A), b ? Follow(B),则可以根据当前读头下符号a来消除冲突。即在构造LR分析表的算法中做一些改变：1）若当前输入符a=b，做移进；

2）若当前输入符a ? Follow(A)，按A?α产生式归约； 3）若当前输入符a ? Follow(B)，按B?α产生式归约； 4）其他，报错。

3.3.4 规范LR分析表的构造

在构造SLR分析表的方法中，若项目集Ik中含有A?α?，那么在状态k时，只要面临 输入符号a ? Follow(A)，就确定采用A?α产生式进行归约。但是，在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀βα未必允许把α归约为A。因为可能没有一个规范句型含有前缀βAa。因此此时用A?α产生式进行归约未必有效。

?对策：给每个LR(0)项目添加展望信息，即：添加句柄之后可能跟的终结符，因为这些终结符确实是规范句型中跟在句柄之后的。这就是LR(1)的方法。 3.3.5 LALR分析表的构造

23

现在来讨论构造分析表的LALR方法。这本质上是一种折衷方法。LALR分析表比规范分析表要小得多，能力也差一点，但它却能对付一些SLR所不能对付的情形。对于同一个文法，LALR分析表和SLR分析表永远具有相同数目的状态。对于ALGOL一类语言来说，一般要用几百个状态，但若用规范LR分析表，同一类语言，却要用几千个状态。因此，用SLR或LALR要经济得多。

3.3.6 二义文法的应用

任何二义文法决不是一个LR文法，因而也不是SLR或LALR文法。这是一条定理。但是，某些二义文法是非常有用的。本节将讨论如何使用LR分析法的基本思想，凭借一些其它的条件，来分析二义文法所定义的语言。 例如，若用下面的文法来描述含有+、?的算术表达式：

E?E+E | E?E |(E)| i (5．11)

采用附加条件之后，发生冲突的表元素就只留下了一种操作；在上面的规则中，我们是认为―*‖的优先级大于―+‖，若现在规则发生变化，认为―+‖ 的优先级大于―*‖，那么对它的实现根本不需修改文法，只要处理冲突时改变一下就行。用这种方法改变算符的优先级是非常方便的。 3.3.7 LR分析中的出错处理

在LR分析过程中，当我们处在这样一种状态下，即输入符号既不能移入栈顶，栈内元素又不能归约时，就意味着发现语法错误。发现错误后，便进入相应的出错处理子程序。

3.4 语法分析器的自动生成工具YACC

YACC是一个编译程序的编译程序，借助它可以构造编译程序。YACC输入用户提供的语言的语法描述规格说明，基于LALR语法分析的原理，自动构造一个该语言的语法分析器，同时，它还能根据规格说明中给出的语义子程序建立规定的翻译。

24

授课题目（教学章、节或主题）： 第四章 语法制导翻译和中间代码产生 课时安排 8 第11周 第3、4节 授课时间 第12周 第1-4节 第13周 第1、2节 教学目的、要求（分掌握、熟悉、了解三个层次）： 理解属性文法的定义，语法制导翻译方法 熟悉中间代码的形式 掌握中间代码形式变换 掌握简单赋值语句的翻译、布尔表达式的翻译、控制语句的翻译 教学重点和难点：属性文法的定义，属性的计算、中间代码的形式、简单赋值语句的翻译、 布尔表达式的翻译、控制语句的翻译 授课类型（请打√）：理论课? 讨论课□ 实验课? 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P217：1，4，7，9

教学内容

第四章 语法制导翻译和中间代码产生

4.1 属性文法和语法制导翻译

属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的―值‖（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列 、符号表内容等等。属性和变量一样，可以进行计算和传递。

属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于―自下

而上‖传递信息，而继承属性用于―自上而下‖传递信息。 属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。 在一个属性文法中，对应于每个产生式A??都有一套与之相关联的语义

规则，每条语义规则的形式为： b:=f(c1,c2,…,ck) 这里f是一个函数，而且或者

（1）b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性； 或者

（2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,…，ck是A或 产生式右边任何文法符号的属性

在这两种情况下，我们都说属性b依赖于属性c1,c2，…,ck. 4.1.1综合属性：

25

在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S—属性文法。

例4.1 3×5＋4n 其值为根的第一个子结点E.val的值 4.1.2继承属性： 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。 4.1.3依赖图

如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的属性规则必须在确定c的语义规则之后使用。在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。 在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成 b:= f(c1,c2, …ck) 的形式。依赖图中为每一个属性设臵一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。 这里要掌握依赖图的画法。 例如，属性

A.a:=f( X.x, Y.y )

对应于产生式 A?XY的语义规则,这条语义规则确定了依赖于属性X.x和Y.y的综合属性A.a。 如果在语法树中应用这个产生式，那么在依赖图中会有三个结点A.a,X.x,和Y.y。由于A.a依赖X.x，所以有一条有向边从X.x到A.a.由于A.a也依赖于Y.y，所以还有一条有向边从Y.y连到A.a. 如果与产生式A?XY对应的语义规则还有： X.i:=g(A.a,Y.y) 那么，图中还应有两条有向边，一条从A.a连到X.i，另一条从Y.y连到X.i,因为X.i依赖于A.a和Y.y.

4.1.4 S—属性文法的自下而上计算

这一节我们考虑这样一类属性文法：S—属性文法，它只含有综合属性。相应属性文法的翻译器很容易建立。

下面我们讨论分析栈中的综合属性。

26

在自底向上的分析法中。我们使用一个栈来存放已经分析过的子树的信息。现在我们可以在分析栈中使用一个附域来存放综合属性值。图4.9表示的是一个带有一个属性值空间的分析栈的例子。

State val … … X X.x Y Y.y Z Z.z … … 图4.9

4.1.5 L—属性文法和自顶向下翻译

一个属性文法称为L—属性文法：如果对于每个产生式A?X1X2…Xn其每个语义规则中的每个属性或者是综合属性，或者是Xj(1<=j<=n)的一个继承属性且这个继承属性仅依赖于：

（1）产生式Xj的左边符号X1,X2,…Xj-1的属性 （2）A的继承属性。

L—属性文法允许通过一次遍历就计算出所有属性值。

4.2 中间语言

我们将介绍其他几种常见的中间语言形式：后缀式（逆波兰式） 三地址代码（四元式，三元式，间接三元式），DAG图表示。 4.2.1 后缀式

后缀式表示法是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法，因此又称逆波兰表示法。

表达式E的后缀形式可以如下定义：

(1)如果E是一个变量或常量，则E的后缀式是E自身。

(2)如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后

缀式为E1‘E2‘op，这里E1‘和E2‘分别为El和E2的后缀式。

这种表示法用不着使用括号。根据运算量和算符出现的先后位臵，以及每个算符的目数，就完全决定了一个表达式的分解。 例如 abc+* 所代表的表达式是 a*(b+c)。

只要我们知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它正确进行唯一分解。把一般表达式翻译为后缀式是很容易的。

27

4.2.2 图表示法

这里的图表示法包括DAG（无循环有向图）与抽象语法树。 4.2.3 三地址代码

三地址代码可以看成是抽象语法树或DAG的一种线性表示。之所以称为三地址代码是因为每条语句通常包含三个地址，两个用来表示操作数，一个用来存放结果。对于后面给出的三地址代码中，用户定义的名字在实际实现时将由指向符号表中的相应名字入口的指针所代替。

三地址语句类似于汇编语言代码。语句可以带有符号标号，而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。 4.3 说明语句

当我们考查一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，我们都将在符号表中建立相应的表项，并填入有关的信息如类型、在存储器中的相对地址等。相对地址是指对静态数据区基址或活动记录中局部数据区基址的一个偏移量。有关活动记录我们将在第九章详细介绍。

当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的。例如，假定在一个以字节编址的目标机上，整数必须存放在4的倍数的地址单元，那么，计算地址时就应以4的倍数增加。 4.3.1 过程中的说明语句

在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一个数据区中。从而我们需要一个全程变量如offset来跟踪下一个可用的相对地址的位臵。在关于说明语句的翻译模式中，非终结符号P产生一系列形如id：T的说明语句。在处理第一条说明语句之前，先臵offset为0，以后每次遇到一个新的名字，便将该名字填入符号表中并臵相对地址为当前offset之值，然后使offset加上该名字所表示的数据对象的域宽。

过程enter(name，type，offset)用来把名字name填入到符号表中，并给出此名字的类型type及在过程数据区中的相对地址offset。非终结符号T有两个综合属性T．type和 T．width，分别表示名字的类型和名字的域宽(即该类型名字所占用的存储单元个数)。假定整数类型域宽为4；实数域宽为8；一个数组的域宽可以通过把数组元素数目与一个元素的域宽相乘获得；每个指针类型的域宽假定为以4增加。 4.3.2 保留作用域信息

过程readarray，exchange和quicksord的符号表有指针指向其外围过程的符号表。另一过程partition是在quicksort中被说明，因此它的符号表有指针指向quicksort的符号表。在下面的语义规则中用到如下操作： (1)mktable(previous)创建一张新符号表，并返回指向新表的一个指针。参数previous 指向一张先前创建的符号表，譬如刚好包含嵌入过程的外围过程符号表。指针previous 之值放在新符号表表头，表头中还可存放一些其它信息如过程嵌套深度等。我们也可以按过程被说明的顺序对过程编号，并把这一编号填入表头。

(2)enter(table，name，type，offset)在指针table指示的符号表中为名字建立一个新项，并把类型type、相对地址offset填入到该项中。

(3)addwidth(table，width)在指针table指示的符号表表头中记录下该表

28

中所有名字占用的总宽度。

(4)enterproc(table，name，newtable)在指针table指示的符号表中为名字为name的过程建立一个新项。参数newtable指向过程name的符号表。 4.3.3 记录中的域名

当遇到保留字record时，与标记非终结符号I相应的语义动作为记录中的各域名创建一张新的记录符号表。把指向该表的指针压入栈tblptr中，并把相对地址0压入栈offset中。产生式D?id：T的语义动作是将域名id的有关信息填入此记录的符号表中。当记录的所有域名都被检查过之后，在offset的栈顶将存放着记录之内的所有数据对象的总域宽。文法中end之后的语义动作是将offset的栈顶的总域宽作为综合属性T．width的值。类型T．type通过对指向本记录符号表的指针施用类型构造符record而得到。在下一节该指针将用来从T.type恢复记录中各域的域名、类型及域宽等。有关类型构造符和类型表达式概念将在4．7节介绍。

4.4赋值语句的翻译

在本节中赋值语句中的表达式的类型可以是整型、实型、数组和记录。作为翻译赋值语句为三地址代码的一个部分，我们将讨论如何在符号表中查找名字及如何存取数组和记录的元素。

4.4.1简单算术表达式及赋值语句

课本P179给出了把简单算术表达式及赋值语句翻译为三地址代码的翻译模式。该翻译模式中说明了如何查找符号表的入口。属性id.name表示id所代表的名字本身。过程lookup(id.name)检查是否在符号表中存在此名字的入口。如果有，则返回一个指向该表项的指针，否则，返回nil表示没找到。在相关的语义动作中，调用过程emit将生成的三地址语句发送到输出文件中，我们可以重新解释lookup操作，若采用最近嵌套作用域规则查找非局部名字，如Pascal语言中的那样，此时前面的翻译模式仍是可用的。 4.4.2 数组元素的引用

现在讨论包括数组元素的表达式和赋值语句的翻译问题。

若数组A的元素存放在一片连续单元里，则可以较容易的访问数组的每个元素。假定数组的每个元素的宽度为w，则一维数组A[i] 这个元素的起始地址为： base + (i – low)*w （4.4）

其中low为数组下标的下界， 并且base是分配给数组的相对地址，即base为A的第一个元素A[low]的相对地址。

4.4式可以整理为： i*w + (base – low*w) 其中：i*w 是随数组下标变量而变化的部分

（base – low*w）是在数组中不变化的常数记为C对于多维数组中二维的情况尤其应注意：

若二维数组A按行存放，则可用如下公式计算A[i1,i2]的相对地址： base + (( i1 – low1)*n2 + i1 – low2) *w

其中，low1、low2分别为i1、i2的下界；n2是i2可取值得个数。即若high2

29

为i2的上界，则n2=high2 – low2 +1.

假定i1,i2是编译时唯一尚未知道的值，我们可以重写上述表达式为： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）

后一项子表达式( base – （(low1 *n2) + low2) *w ）的值是可以在编译时确定的,为常数。前一子项随i1, i2 而改变是一个变数。 特别是当low=1， 时有：V=(i1*n2+i2)*w C= base –(n2+1)*w

应该牢记。要生成数组的引用代码，其主要问题是把常数C和变数V 的计算与数组引用的文法联系起来。如果在图7.10的文法中 id 出现的地方也允许下面产生式中的L出现，则可把数组元素引用加入到赋值语句中。 L→id [ Elist ]| id Elist→Elist, E | E 为语句处理上的方便改写为：

L→Elist ] | id

Elist →Elist, E | id [ E

即把数组的名字id与最左下标表达式E 相联系，而不是在形成L时与Elist相联系。其目的是使我们在整个下标表达式串Elist的翻译过程中随时都知道符号表中相应于数组名字id的全部信息。对于非终结符号Elist引进综合属性arry，用来纪录指向符号表中相应数组名字表项的指针。

我们还利用Elist.ndim来纪录Elist中的下表表达式的个数，即维数。函数Limit(arry, j) 返回nj ，即由arry所指示的数组的第j 维的长度。最后，Elist.place表示临时变量，用来临时存放由Elist中的下标表达式计算出来的值。

一个Elist可以产生一个k- 维数组引用A[i1,i2,…ik]的前m维下标，并将生成计算下面式子的三地址代码。

（ …( ( i1*n2 +i2)n3)…)nm + im 利用如下的递归公式进行计算：

e1 = i1, em = em-1* nm + im

于是 当m=k时将ek乘以元素的宽度w便可计算出（4.6）的第一个子项。 描述L的左值（基地值）用两个属性L.place和L.offset.如果L仅为一个简单名字，L.place就为指向符号表中相应此名字表项的指针，而offset为null，表示这个左只是一个简单名字而非数组的引用。

4.4.3 记录中域的作用

编译器必须将记录中的域的类型和相对地址保持下来。一般说来，把这些信息保存在相应的域名的符号表表项之中。这样做的好处是可以把用在符号表中查找名字的程序同样用来查找域名。在此意义下，利用上一节图4．9中的语义动作可为每一个记录类型建立一张单独的符号表。如果t是一个指向某个记录类型的指

30

针，把类型构造符record 施于该指针，返回所形成的类型record(t)作为属性T．type的值。p 是一个指向某个记录的指针，这个记录有一个类型为算术型的域名info。如果类型像图4．8和图4．9一样构造，则p?的类型可以由类型表达式pointer(record(t))给出。于是p的类型是record(t)，t可由此先取出来。也就是说域名info将可以在t所指向的符号表中查找。 4.5 布尔表达式的翻译

在程序设计语言中，布尔表达式有两个基本作用： 一个使用作计算逻辑值；另一个是用作控制流语句如

if-then、if-then-else和 while-do等之中的条件表达式。

布尔表达式是用布尔运算符号（and、 or、not ）作用到布尔变量或关系表达式上而组成的。关系表达式形式如E1 relop E2, 其中E1和E2是算术表达式， relop为关系运算符 （ < ,<=, = >, > , =, ≠）。 把A or B解释成if A then true else B 把A and B解释成 if A then B else false 把not A解释成then false else tree

上述这两种计算法对于不包含布尔函数调用的式子是没有什么差别的。但是，假设一个布尔式中含有布尔函数调用，并且这种函数调用引起副作用(指对全局量的赋值)。那么，上述两种计算法未必是等价的。有些程序语言规定，函数过程调用应不影响这个调用所处环境的计值。或者说，函数过程的工作不许产生副作用。在这种规定下，我们可任选上述的一种方法。下面我们将分别用这两种方法来讨论如何把布尔表达式翻译成地址代码。从表达式各部分的值计算出整个表达式的值。

4.5.1 数值表示法

首先考虑用1表示真，0表示假来实现布尔表达式的翻译。

一个形如 a

100： if a

101： T:=0

102： goto 104 103： T:= 1 104：

4.5.2 作为条件控制的布尔式翻译 出现在条件语句：

if E then S1 else S2 （4.10）

中的布尔表达式E，它的作用仅在于控制对S1和S2的选择。只要能完成这一使命，E 的值就无需最终保留在某个临时单元中。因此，作为转移条件的布尔式 E，我们可以赋予它两种―出口‖。 一个是―真‖出口，出向S1；一个是―假‖出口，出向S2。于是语句（4.10）可翻译成如图7.15所示的形式。图7.15 if－then－

31

else语句的代码结构

对布尔表达式进行翻译的语义规则的最容易方法是经过两遍扫描。首先，为给定的输入串构造一棵语法树；然后，对语法树进行深度优先遍历，进行语义规则中规定的翻译。通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于，当生成某些转移语句时我们可能还不知道该语句将要转移到的标号究竟是什么。为了解决这个问题，我们可以在生成形式分支的跳转指令时暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指令的标号键入这个链表。一旦目标确定之后再把它填入有关的跳转指令中。这种技术称为回填。

按照这个思想，我们为非终结符E赋予两个综合属性E．truelist和E．falselist。它们分别记录布尔表达式E所应的四元式中需回填?真?、?假?出口的四元式的标号所构成的链表。具体实现时，我们可以借助于需要回填的跳转四元式的第四区段来构造这种链。

4.6 控制语句的翻译 4.6.1 控制流语句 我们考虑文法：

S→ if E then S1

|if E then S1 else S2 | while E do S1 其中E 布尔表达式。 与上一节一样，我们先讨论对这些语句进行翻译的一般语义规则。然后讨论如何通过一遍扫描产生上述语句的代码，给出相应的翻译模式。

关于这三条语句的代码结构如图4.17所示。条件语句S的语义规则允许控制从S 的代码S.code之内转移到紧接S.code之后的那条三地址指令。但是，有时候此条紧接S.code之后的指令是一条无条件转移指令，它转移到标号为L的指令。通过使用继承属性S.next可以避免上述连续转移的发生，而从S.code之内直接

转移到标号为L的指令。S.next 之值是一个标号，他指出继S 的代码之后将被执行的第一条三地址指令。在翻译if-then语句S→if E then S1时，我们建立了一个新的标号E.true，并且用它来标识S1的代码的第一条指令，如图7.17（a）所示。表7.8给出了一个属性文法。在E的代码中将有这样的转移指令：若E为真则转移到E.true,并且若E为假则转移到S.next.因为我们臵E.false为S.next.

图4.17控制语句的代码结构

在翻译if-then-else 语句S→ if E then S1 else S2时， 布尔表达式E的代码中有这样的转移指令：若E为真则转移到S1的第一条指令， 若E为假则转移到S2的得一条指令。如图7.17（b）所示。

32

图4.17（c）

语句S→while E do S1的结构图如4.17（c）与上边两个语句相似，不再重述。使用回填技术通过一遍扫描翻译控制流语句的翻译模式应该掌握。

4.6.2 标号与goto语句

很多语句都保留了标号和goto语句作为最基本的程序设计语言成分。一个带标号的语句形式是L：‘S。当这种语句被处理之后，标号L称为?定义了?的。也就是在符号表中标号L的?地址?栏将登记上语句S的第一个四元式的地址(编号)。 如果goto L是一个向后转移的语句，那么，当编译程序碰到这个语句时，l必是已定义了的。通过对L查找符号表获得它的定义地址p，编译程序可立即产生出相应于这个goto L的四元式(j，—，—，p)。 如果goto L是一个向前转移的语句，也就是说标号L尚未定义，那么，若l是第一次出现，则把它填进符号表中并标志上?未定义?。由于L尚未定义，对goto L我们只能产生一个不完全的四元式(j，—，—，—)，它的转移目标须待l定义时再回填进去。在这种情况下，必须把所有那些以L为转移目标的四元式的地址全都记录下来，以便call定义时就可对这些四元式进行回填。

4.6.3 CASE语句的翻译

4.7 过程调用的处理

过程是程序设计语言中最常用的一种结构。我们这一节所讨论的过程也包括函数，实际上函数可以看作是返回结果值的过程。 我们考虑过程调用文法如下： （1） S→call id (Elist) (2) Elist →Elist, E (3) Elist →E

其传地址的翻译模式应掌握。

4.8 类型检查

33

授课题目（教学章、节或主题）： 第六章 运行时存储空间组织 教学目的、要求（分掌握、熟悉、了解三个层次）： 熟悉栈式存储分配的实现 掌握参数的传递 教学重点和难点：参数的传递、栈式存储分配的实现 课时安排 授课时间 6 第13周 第3、4节 第14周 第1-4节 授课类型（请打√）：理论课? 讨论课□ 实验课□ 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P268：1，4，9

教学内容

第六章 运行时存储空间组织

编译程序在完成词法、语法和语义分析后，在生成目标代码之前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来，弄清楚将来在代码运行时刻，源代码中的各种变量、常量等用户定义的量是如何存放的，如何去访问它们。 在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。在程序语言中，程序使用的存储单元都是由标识符来表示的。它们对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。所以对于编译程序来说存储组织与管理是一个复杂而又十分重要的问题。这一章就是对目标程序运行时的活动和运行环境进行讨论，主要讨论存储组织与管理, 包括活动纪录的建立与管理、存储器的组织与存储分配的策略、非局部名称的访问等问 6.1 目标程序运行时的活动 6.1.1 过程的活动

这一节讨论一个过程的静态源程序和它的目标程序在运行时的活动之间的关系。 一个过程的活动指的是该过程的一次执行。 关于过程P一个活动的生存期，指的是从执行该构成体第一步操作到最后一步操作之间的操作序列，包括执行P时调用其他过程化费的时间。一般来说，术语―生存期‖指的是在程序执行过程中若干步骤的一个顺序序列。 一个说明在程序里能起作用的范围成为该说明的作用域。 6.1.2 参数传递

要掌握在过程调用时出现的：形式参数，实在参数等基本概念。

传地址，传值，传名三种参数传递方法。由于传递参数的方法不同，同样的程序运行的结果可能大不相同。

6.2 运行时存储器的划分

34

6.2.1 运行时存储器的划分

编译程序为了使它编译后得到的目标程序能够运行，要从操作系统中获得一块存储空间。从上一节的讨论我们知道，对这块提供运行的空间应该进行划分以便存放其中包括生成的目标代码、数据对象和跟踪过程活动的控制栈。 6.2.2 活动纪录

为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，我们把这样的一个连续存储块称为活动纪录。 当前活动纪录一般包括如下内容： 连接数据 返回地址

动态链：指向调用该过程前的最新活动纪录地址的 指针。运行时，是运行栈上各数据区按动态建立的次序结成链。链头为栈顶起始位臵。

静态链：指向静态直接外层最新活动纪录地址的指针，用来访问非局部数据。 形式单元：存放相应的实在参数的地址或值。

局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。

6.2.3存储分配策略

不同的编译程序关于数据空间的存储分配策略可能不同。静态分配策略在编译是对所有对象分配固定的存储单元。且在运行是保持不变。栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态的分配于栈顶，一旦退出，它所占空间就予以释放。堆式动态存储策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者分给一块，凡释放者退回给堆。 6.3静态存储分配

如果在编译时就能够确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。 这一节要特别注意临时变量的地址分配方法。 尽管在翻译时大量引进了临时变量名，但是并不是对每一个名字分配一个不同的存储单元，那样做太浪费空间了。一个一般的原则是如果两个临时变量的名字 作用域不相交，则他们可分配在同一单元中，一个临时变量名自它第一次被定值（赋值）的地方起直至它最后一次被引用的地方止，这区间的程序所能到达的全体四元式，构成了它的作用域。

对于用来暂存表达式中间结果的临时变量名而言，只存在一次定值和一次引用，并且在定值和引用之间不存在分叉转移（无论转进或转出）这类临时变量名作用域的确定是非常简单的。它们的存储分配可用一种特别简易的办法实现。

我们说过，大部分的临时变量名是用来存放表达式的中间结果。这些临时变量有一个特点。它们均只被定值一次，被引用一次。它们的作用域如同配对的括号序列所管辖的区一样是层次嵌套的。因此我们可以设想用一个栈（先进后出区）来存放这类临时变量名的值。也就是说，可以用一个栈来存放表达式记值 过程中的中间结果。为简单起见，我们假定所有临时变量值只需要一种同一长度 栈单元。令k为栈的指示器，设它的初值是局部区中用来存放临时变量值的区域首地址。每当发现一个新的临时变量名Ti 定值时，就用k 的现行值作为Ti的 地

35

址。然后把k 累增1 。每当引用了某个临时变量名Ti 作为操作数时 （此时Ti 的地址必已分配） ，就把指示器k 的值递减1 。

6.4 简单的栈式存储分配

使用栈式存储分配法意味着把存储组成一个栈，运行时，每当一个过程（一个新的活动开始）时， 就把它的活动纪录压入栈（累筑于栈顶），从而形成过程工作时的数据区，一个过程的活动纪录的体积在编译是是可静态确定的。当该过程结束（过程退出）时，再把它的活动过程弹出栈。这样在栈顶的数据区也随即不复存在。

此时运行栈最顶端数据取得是两个指示器SP和TOP:

SP 总是指向现行过程活动纪录的起点，用于访问局部数据。 TOP始终指向（已占用）栈顶单元。

这两个指示器实际上是固定分配了两个变址器。当进入一个过程时，TOP指向为此过程创建的活动记录的顶端，在分配数组之后，TOP就改指向数组区（整个数据区）的顶端。 6.4.1 C的活动纪录

C的活动纪录有以下四个项目。 连接数据， 有两个：

（1）老SP值，即前一个活动纪录的地址； （2）返回地址。 参数个数。

形式单元（存放实在参数的值或地址）。

过程的局部变量、数组内情向量和临时工作单元。其结构如图9.14所示。

由图9.14所示，过程的每一个局部变量或形参在活动纪录中的位臵是确定的，就是说，对它们都分配了存储单元，其地址是相对于活动纪录的基地址（SP)的。

因此，变量和形参运行实时在栈上的绝对地址是： 绝对地址=活动纪录基地址+相对地址

6.4.2 C的过程调用、过程进入、数组空间分配和过程返回 我们说过，过程调用的四元式序列： par T1 par T2 ……

par Tn

call P, n

现在我们考虑在运行时四元式par 和 call 是如何执行的，或者说，对于par

36

和call应该生成些什么相应的目标代码。由于TOP总是指向栈顶，而形式单元和活动纪录起点之间的距离是确定的（等于3），因此每个par Ti (i= 1,2,…n ) 可直接翻译成如下指令：

（i+3 ）[TOP]:=Ti (传递参数值) 或（i +3)[TOP]: add(Ti) (传递参数的地址）

这些指令的作用是将实参的值或地址一一传进新的过程的形式单元中。此处我们假定每个形式单元，不论用来存放实参的值或地址，均只用一个机器字。注意，在执行这些指令时TOP的值不受影响。 四元式call P, n应被翻译成：

1[TOP]:= SP (保护现行SP ) 2[TOP] := n (传送参数个数)

3JSR P (转子指令，转向P的第一条指令 ）

转进过程P后，首先要做的工作是定义新活动纪录的SP，保护返回地址和定义这个纪录的TOP值。也就是说执行如下指令： SP := TOP +1 (定义新SP ） 1 [SP] := 返回地址 （保护返回地址 ） TOP := TOP + L (定义新的TOP ）

其中，L是过程P 的活动纪录所需的单元数，这个数在编译是可静态地计算出来。

在过程段执行语句的工作过程中，凡引用形式参数、局部变量或数组元素都是以SP为变址器进行变址访问的。

C语言以及其它一些相似的语言含有下面形式的返回语句 return (E) 其中，E为表达式。 假定E的值已计算出来并已放到某个特定的寄存器中（调用段将从这个特定的寄存器中获得被调用过程的结果值）。然后，剩下的工作是恢复SP和TOP为进入过程前的老值，并返回地址实行无条件转移。即执行下述指令序列：

TOP := SP-1 SP := 0[SP]

X := 2[TOP] (X为某一变址器） UJ 0[X]

此处 UJ为无条件转移指令，按 X 中的返回地址实行变址转移。 6.5 嵌套过程语言的栈式实现

在本节的讨论中，常常要用到过程定义的―嵌套层次‖（简称 层次），我们始终假定主过程的层次为0，因此，主程序称为第0层过程。如过程Q是在层数为i 的 过程P内定义，并且P是包围Q的最小过程，那么Q的层数为 i +1 .这时，我们把P 称为Q的直接外层过程，而Q 称为P 的内层过程。当编译程序处理过程说明时，过程的层数将作为过程名的一个重要属性登记在符号表中。计数每个过程的层数是很容易的。使用一个计数器level（初始值为0 ），每逢一到proc Begin 时，将它累加1 。每逢一到 proc end 时将它递减1。于是对于每个过程说明我们就可用level来定义它的层数。 6.5.1 非局部名字的访问的实现 由于过程的定义是嵌套的，一个过程可以引用包围它的任意过程所定义的变量

37

或数组，也就是说，运行时， 一个过程Q可能引用它的任意一个外层过程P 的最新活动纪录中的某些数据（这些数据视为过程Q的非局部量）。为了在活动纪录中查找非局部名字所对应的存储空间，过程Q运行时必须知道它所有外层过程的最新活动纪录的地址。由于容许递归性，过程的活动纪录的位臵（即使是相对位臵）也往往是变迁的。因此，必须设法跟踪每个外层过程的最新活动纪录的位臵。跟踪的方法很多，本节讨论两种：一种是通过静态链；另一种是通过显示表（display ）。 这两种方法都应该掌握。

6.6 堆式动态存储分配

6.6.1 堆式动态存储分配的实现 6.6.2 隐式存储回收

38

授课题目（教学章、节或主题）： 第七章 目标代码生成 教学目的、要求（分掌握、熟悉、了解三个层次）： 了解相关代码生成概念与基本原理 教学重点和难点：寄存器分配 课时安排 4 授课时间 第15周 第1-4节 授课类型（请打√）：理论课? 讨论课□ 实验课□ 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P327：1，2，6 教学内容 第七章 目标代码生成

代码生成器的输入包括中间代码和符号表中的信息。 目标代码一般有以下三种形式：

（1）能独立执行的机器语言代码，所有地址均以定位（代真） 。

（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。

（3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。 代码生成器着重考虑两个问题: 一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。基本问题:所有代码生成器都要面对何种中间代码输入，（是逆波兰式，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提.

为此本书建立了目标机器模型:并把中间代码对应的目标代码做了规定.利用待用信息,寄存器描述数组AVALUE,变量地址描述数组AVALUE等概念建立了代码生成算法.

P316[例8.2]同学们应该好好研究。

P317 表8.4 各中间代码对应的目标代码应该熟悉。

寄存器分配：利用执行代价的概念说明如何建立更佳的寄存器分配方案。 对于循环L中某变量M，如果分配一个寄存器给它专用，那么，每执行循环一次，执行代价的节省数可用公式（7.1）计算。这个计算公式应该掌握。[例7.3]图7.4代表某程序的最内层循环，其中无条件转移和条件转移指令均以改用箭头来表示。各基本块入口之前和出口之后的活跃变量已列在图中。假定R0,R1和R2三个寄存器在该循环中将固定分配给某三个变量使用。现在，我们利用公式（7.1）

39

计算各变量的执行代价节省数，并且取执行代价节省数最高的来确定这三个变量。

解：因为B1中引用a前已对a定值，所以use(a,B1)=0;

在B2,B3中a被各引用一次，且在引用前未对a定值，所以use(a,B2)=use(a,B3)=1; B4中未引用a，所以use(a,B4)=0.

因为a在B1中被定值且a在B1出口是活跃的， a在B2,B3和B4出口后不是活跃的则：live( a, B1)=1

Live( a, B2)=live(a,B3)=live(a, B4) = 0;所以代价节省数为：1+1+2*1=4。同样可以算出b,c,d,e,f 的执行代价节省数分别为： 6，3，6，4，4。按照代价节省数的大小我们把寄存器R0分配给d, R1分配给b; a,e,f 的执行代价相同,可人选其一将R2分配给a. DAG的目标代码

为了生成更有效的目标代码，要考虑的另一个问题是，对基本块中中间代码序列，我们应按怎样的次序来生成其目标代码呢？本节P323给出了利用基本块的DAG图给出了基本块中中间代码序列排序的方法，以便生成较优的目标代码。 下面我们学习一个例子，以加深其理解： [例7.6] 考察下面中间代码序列 G1:

T1 := A+B

T2 := A- B F := T1 * T2 T1 := A- B T2 := A – C T3 := B - C T1 := T1 * T2 G := T1 * T3

其对应的DAG图中含有7个结点，我们应用课本中的算法。把它们排序，主要步骤如下。

第一步臵初值： i = 7； T的所有元素全为空null。内部结点n3和n7均满足第三步的要求，假定我们选取T[7]为结点n3。结点n3的最左子结点（内部）n1满足第5步的要求，因此按第6步，T[6]=n1.但n1的最左子结A为叶结，不满足第6步的要求。则现在只有n7满足第3步要求，于是T[5]=n7。 结点n7 的最左子结n6满足第5步的要求，因此T[4]=n6。 结点n6的最左子结点n2同样满足第5步的要求，因此T[3]=n2. 余下的满足第3步要求的尚有n4和n5，假定选取T[2]=n4。当把n5列为T[1]后，算法工作结束。至此，我们求出的图的内结点顺序为：n5, n4, n2, n6, n1, n3.按这个次序从新表示中间代码序列为G1?为：

T3 := B-C ; T2 := A- C ; S1 := A – B ; T1 := S1 * T2;

G := T1 * T3; S2 := A + B ; F := S2 * S1 。 如前所述按后一个中间代码序列生成中间代码将会较优。

窥孔优化

几种窥孔优化的方法都比较好理解，这里不再重述课本内容。

40