《编译原理》教案设计

《编译原理》教案

授课题目（教学章、节或主题）：课时支配2

第一章引论

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

教学目的、要求（分驾驭、熟识、了解三个层次）：

简洁介绍学习此课程的目的和要求

初步了解编译技术的基本原理和方法

熟识Compiler的基本概念

驾驭Compiler的结构和功能

教学重点和难点：编译程序的基本结构和功能

授课类型（请打J）：理论课目探讨课口试验课口练习课口其他口

教学方式（请打J）：讲授I3探讨口示教口指导因其他口

教学资源（请打J）：多媒体因模型口实物口挂图口音像口其他口

探讨、思索题、作业：

编译程序的基本结构如何？各部分功能？

教学内容

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

第一章引论

1.1什么叫编译程序？

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

言程序）转换成另一种语言程序（称为目标语言程序），而后者与前者在逻辑上是

等价的。假如源语言是诸如FORTRAN、Pascal.C、Ada、SmaIItaIk或Java这

样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，

这样的一个翻译程序就称为编译程序。

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

源语言的说明程序是这样的程序，它以该语言写的源程序作为输入，但不产生目

标程序，而是边说明边执行源程序本身。本书将不对说明程序作特地的探讨。

事实上，很多编译程序的构造与实现技术同样适用于说明程序。

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

调试的编译程序称为诊断编译程序（DiagnosticC。叩iler）,着重于提高目标代

码效率的编译程序叫优化编译程序（OptimizingCompiIer）,,现在很多编译程序

同时供应了调试、优化等多种功能，用户可以通过“开关”进行选择。运行编译

程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。

假如一个编译程序产生不同于其宿主机的机器代码，则称它为交叉编译程序

（CrOSSC。叩iler）。假如不需重写编译程序中与机器无关的部分就能变更目标

机，则称该编译程序为可变目标编译程序（RetargetabIeCompiIer）o

1.2编译过程概述

编译程序过程：从输入源程序起先到输出目标程序为止的整个编译过程可分为

以下五个阶段：词法分析，语法分析，语义分析，中间代码产生，优化和目标代码生

成.

1.3编译程序的结构

编译程序的结构可以依据从输入源程序起先到输出目标程序为止的整个编译过

程可分为以下五个阶段：词法分析，语法分析，语义分析，中间代码产生，优化和目

标代码生成。

1.3.1编译程序总框

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

序的总框。

日痴2库

1.3.2表格与表格管理

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

译各阶段的进展状况。在编译程序运用的表格中，最合理的是符号表。编译程

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

的进展状况。合理地设计和运用表格是编译程序构造的一个重要问题。在编译程

序运用的表格中，最重要的是符号表。它用来登记源程序中出现的每个名字以及

名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等；假如是

变量名，它的类型是什么、所占内存是多大、地址是什么等等。通常，编译程序

在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到

名字的运用性出现时，要对名字的属性进行查证。

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

完全确定名字的属性，它的各种属性要在后续的各阶段才能填入。例如，名字的

类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确

定。

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

1.3.3出错处理

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

生产新的中间结果或目标程序。一个编译程序不仅应能对书写正确的程序进行翻

译，而且应能对出现在源程序中的错误进行处理。假如源程序有错误，编译程序

应设法发觉错误，把有关错误信息报告给用户。这部分工作是由特地的一组程序

（叫做出错处理程序）完成的。一个好的编译程序应能最大限度地发觉源程序中的

各种错误，精确地指出错误的性质和发生错误的地点，并且能将错误所造成的影

响限制在尽可能小的范围内，使得源程序的其余部分能接着被编译下去，以便进

一步发觉其它可能的错误。假如不仅能够发觉错误，而且还能自动校正错、误，

那当然就更好了。但是，自动校正错误的代价是特别高的。

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

阶段检测出来。源程序中的错误通常分为语法错误和语义错误两大类。语法错误

是指源程序中不符合语法（或词法）规则的错误，它们可在词法分析或语法分析时

检测出来。例如，词法分析阶段能够检测出“非法字符”之类的错误；语法分析

阶段能够检测出诸如“括号不匹配”、“缺少；”之类的错误。语义错误是指源程

序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错

误要在运行时才能检测出来。语义错误通常包括：说明错误、作用域错误、类型

不一样等等。

1.3.4遍

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

生产新的中间结果或目标程序。通常，每遍的工作由从外存上获得的前一遍的中

间结果起先（对于第一遍而言，从外存上获得源程序），完成它所含的有关工作之

后，再把结果记录于外存。既可以将几个不同阶段合为一遍，也可以把一个阶段

的工作分为若干遍。例如，词法分析这一阶段可以单独作为一遍，但更多的时候

是把它与语法分析合并为一遍；为了便于处理，语法分析和语义分析与中间代码

产生又经常合为一遍。在优化要求很高时，往往还可把优化阶段分为若干遍来实

现。

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

分析、语法分析及语义分析与中间代码产生这三阶段支配成一遍。这时，语法分

析器处于核心位置，当它在识别语法结构而须要下一单词符号时，它就调用词法

分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语

义分析并产生相应的中间代码。

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

诸因素有关的，因此难于统一划定。遍数多一点有个好处，即整个编译程序的逻

辑结构可能清晰一点。但遍数多势必增加输入/输出所消耗的时间。因此，在主

存可能的前提下，一般还是遍数尽可能少一点为好。应当留意的是，并不是每种

语言都可以用单遍编译程序实现。

1.3.5编译前端与后端

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

有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、

语义分析与中间代码产生，有的代码优化工作也可包括在前端。后端包括编译程

序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。

通常，后端不依靠于源语言而仅仅依靠于中间语言。

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

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

这样就可实现编译程序的目标机变更。也可以设想将几种源语言编译成相同的中

间语言，然后为不同的前端配上相同的后端，这样就可为同一台机器生成不同语

言的编译程序。然而，由于不同语言存在某些微妙的区分，因此在这方面所取得

的成果还特别有限。

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

如.在闻名的Ada程序设计环境APSE中，运用的是一种称为Diana的树形结构

的中间语言一个Ada源程序通过前编译转换为Diana中间代码，由编译后端把

Diana中间代码转换为目标代码。编译前端与不同的编译后端以Diana为界面，

实现编译程序的目标机变更。

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

Java定义一种虚拟机代码一Bytecode。只栗实际运用的操作平台上实现了的

Java说明器，这个操作平台就可以执行各种Java程序。这就是所谓Java语言

操作平台无关性。

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

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

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

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

缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，现在人们越来越

倾向于构造集成化的程序设计环境。一个集成化的程序设计环境的特点是，它将

相互独立的程序设计工具集成起来，以便为程序员供应完整的、一体化的支持，

从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境

中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发

的全生命周期。有代表性的集成化程序设计环境有Ada语言程序设计环境APSE、

LISP语言程序设计环境INTERLISP等。广阔读者所熟识的Pascal.TurboC、

VisuaIC++等语言环境也都可认为是集成化的程序设计环境。

1.5编译程序的生成

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

同硬件系统的效率，为了满意各种不同的具体要求，现在很多人仍旧采纳这种工

具来构造编译程序。但是，越来越多的人倾向于运用高级语言作为工具来构造编

译程序。因为，这样可以节约大量的程序设计时间，而且所构造出来的编译程序

也易于阅读、修改和移植。

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

自动产生扫描器，有些可用于自动产生语法分析器，有些甚至可用来自动产生完

全的编译程序。如：编译程序-编译程序、编译程序产生器、翻译程序书写系统

等，它们是依据对源语言和目标语言（或机器）的形式描述（作为输入数据）而

自动产生编译程序的。本课程将把自动产生器作为一个重要课题来探讨。近些

年来，有些人主见采纳“自编译方式”产生编译程序。意思是，先对语言的核心

部分构造一个小小的编译程序（可用手编实现），再以它为工具构造一个能够编

译更多语言成分的较大编译程序。如此扩展下去，就象滚雪球一样，越滚越大，

最终形成人们所期望的整个编译程序。这种通过一系列自展途径而形成编译程序

的过程叫作自编译过程。

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

另一机器上。着须要寻求某种适当的‘'中间语言但是，由于建立通用中间语

言事实上办不到，因此，移植也只能在几种语言和几种机器之间进行。

授课题目（教学章、节或主题）：课时支配12

其次章词法分析第1周第3-6节

授课时间第2周第1-6节

第3周第1、2节

教学目的、要求（分驾驭、熟识、了解三个层次）：

了解词法分析器的构造方法

熟识词法分析的任务和过程

驾驭正规式和有限自动机的基本概念

教学重点和难点：词法分析器的设计、正规表达式和有限自动机、正规表达式和有限自动机

的等价性、正规文法和有限自动机间的转换

授课类型（请打J）：理论课EI探讨课口试验课团练习课13其他口

教学方式（请打J）：讲授因探讨口示教口指导因其他口

教学资源（请打J）：多媒体因模型口实物口挂图口音像口其他口

探讨、思索题、作业：

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词法分析器作为一个独立子程序

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

2.2词法分析器的设计

我们将依据词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的

设计。

2.2.1输入、预处理

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

这个缓冲区称为输入缓冲区。词法分析的工作（单词符号的识别）可以干脆在这

个缓冲区中进行。但在很多状况下，把输入串预处理一下，对单词符号的识别工

作将是比较便利的。

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

处理工作还可以包括源程序和出错信息的列表打印。

2.2.2单词符号的识别：超前搜寻

词法分析器的结构如下图所示：当词法分析器调用预处理子程序处理出一串输入

字符放进扫描缓冲区之后，扫描器就从今缓冲区中逐一识别单词符号。当缓冲区

里的字符串被处理完之后，它又调用预处理程序装入新串。

图3.1词法分析器

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

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

“BEGIN"），在这种状况下，基本字的识别是很干脆的，不存在什么困难。象

FORTRAN这样的语言，基本字不加特殊爱护，基本字和用户自定义的标识符或

标号之间没有特殊的界符作间隔，这就使得基本字的识别甚为麻炀。这里就须要

用到超前搜寻。

2.2.3状态转换图

运用状态转换图是设计词法分析程序（扫描器）的一种好途径。转换图是一张有限

方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。

箭弧上的标记（字符）代表在射出结（即箭弧始节）状态下可能出现的输入字符或

字符类。如下图3.2（a）所示。

在状态1下，若输入字符X,则读进X,并转换到状态2。若输入字符Y,则读

进Y,并转换到状态3o一张转换图只包含有限个状态（即有限个结点），其中

有一个被认为是初态，而且事实上至少要有一个终态（用双圈表示）。

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或假值FALSEo

7.RESERVE整型函数过程，对TOKEN中的字符串查找保留字表，若它是一个

保留字则返回它的编码，否则返回0值(假定0不是保留字的编码)。

8.RETRACT子程序过程，把搜寻指示器回调一个字节位置，把CHAR中的字符

置为空白。

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

2.3.1正规式与正规集

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

串)是指由W中的字符所构成的一个有穷序列。不包含任何字符的序列称为空字，

记为E。用Z*表示2上的全部字的全体，空字£也包括在其中。例如，若Z

={a,b},则£*={£1力声2/1)方2,附/22}下面是正规式和正规集的递归定义：

1.和①都是上的正规式，它们所表示的正规集分别为{£}和①；

2.任何a62,是Z上的一个正规式，它所表示的正规集为{a};

3.假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V),

那么，(UV)、(U|V)和(U)*也都是正规式，它们所表示的正规集分别为L(U)

UL(V)、L(U).L(V)(连接积)和(L(U))*(闭包)。

仅由有限次运用上述三步骤而定义的表达式才是2上的正规式，仅由这些正规式

所表示的字集才是E上的正规集。算符的优先依次为：先“*”，次最终T。

例如，令W={a,b},下面是W上的正规式和相应的正规集：

ba*:2上全部以b为首后跟随意多个a的字

a(a|b)*:W上全部以a为首的字

(a|b)*(aa|bb)(a|b)*：2上全部含有两个相继的a或两个相继的b的字

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

(A|B)(A|B|0|l)*:2上的"标识符"的全体

(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.eU=Ue=U

2.3.2确定有限自动机(DFA)

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

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

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

3.f是一个从SXW至S的(单值)部分映照。f(s,a)=C意味着：当现行状态

为s,输入字符a时，将转换到下一状态s'o我们把s，称为s的一个后继状态；

4.SOeS,是唯一■的一■个初态；

5.ZcS,是一个终态集(可空)。

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

素表示f(s,a)的值，这个矩阵称为状态转换矩阵。

例如，有DFAM=({0,l,2,3,{a,b,f,0,{3}其中f为：

f(0,a)=lf(0,b)=2

f(l,a)=3f(4,b)=2

f(2,a)=lf(2,b)=3

f(3,a)=3f(3,b)=3

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

表3.2状态转换矩阵

状态ab

012

132

213

333

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

对于2*中的任何字a,若存在一条从初态结到某一条终态结的道路，且这条路上

全部弧的标记符连接成的字等于a,则称a可为DFAM所识别(读出或接受)。

若M的初态结同时又是终态结，则空字E可为M所识别(或接受)。

上例所定义的DFAM相应的状态转换图如下所示：它能识别2上全部含有相继

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

图3.5状态转换图

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

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

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

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

3.f是一个从SX2*到S的子集的映照，即f:SX2*f2S

4.SOcS,是非空初态集；

5.ZcS,是一个终态集(可空)。

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

对于正规文法G和有限自动机M,假如L(G)=L(M),则称G和M是等价

的。关于正规文法和有限自动机的等价性，有以下结论：

(1)对每一个右线性正规文法G或左线性正规文法G,都存在一个有限自动机

(FA)M,使得L(M)=L(G)o

(2)对每一个FAM,都存在一个右线性正规文法GR或左线性正规文法GL,

使得L(M)=L(GR)=L(GL)

2.3.5正规式与有限自动机的等价性

我们可以证明：

(1)对任何FAM,都存在一个正规式r,使得L(r)=L(M)。

(2)对任何的正规式r,都存在一个FAM,使得L(M)=L(r)。

上述结论加上前面章节所证明的结论，说明正规文法、正规式、确定有限自动机

和非确定有限自动机在接收语言的实力上是相互等价的。

2.3.6确定有限自动机的化简

等价状态；最少化。

2.4词法分析器的自动产生

教学目的：运用状态转换图构造词法分析程序；上机实践LEX的实现。

2.4.1语言LEX的一般描述

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

生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。一个产生式的

形式是Afa其中，箭头(有时也用：：=)左边的A是一个非终结符，称为产生

式的左部符号；箭头右边的a是由终结符号或非终结符号组成的符号串，称为产

生式的右部。我们有时也说，产生式Afa是关于A的一条产生规则。产生式是

用来定义语法范畴的。

例如，令i代表已定义的范畴“变量”，那么，产生式算术表达式fi意味着把

“算术表达式”这个范畴定义为“变量”。在有的书上，“一”也用“：：="表

示：这种表示方法也称巴科斯范式。

2.4.2超前搜寻

在某些语言中，要识别一个单词符号必需超前看若干字符。

2.4.3LEX的实现

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

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

相关介绍：人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有

些能用于自动产生扫描器（如LEX）,有些可用于自动产生语法分析器（如YACC）,

有些甚至可用来自动产生完全的编译程序。这些构造编译程序的工具称为编译程

序——编译程序、编译程序产生器或翻译程序书写系统，它们是按对源程序和目

标语言（或机器）的形式描述（作为输入数据）而自动产生编译程序的。

授课题目（教学章、节或主题）：

课时支配6

第三章语法分析-上下文无关文法、形式语言和文法第3周第3-6节

授课时间

第4周第1、2节

教学目的、要求（分驾驭、熟识、了解三个层次）：

理解和定义上下文无关文法，为学习和构造编译程序打下良好基础。

理解语言和文法的定义

驾驭文法的等价变换及语法描述方法

了解文法的分类

教学重点和难点：文法的直观概念、文法和语言的形式定义、文法的类型、语法树和二义性、

文法中的好用限制、句型的分析

授课类型（请打J）:理论课团探讨课口试验课口练习课因其他口

教学方式（请打J）:讲授囱探讨口示教口指导因其他口

教学资源（请打J）:多媒体因模型口实物口挂图口音像口其他口

探讨、思索题、作业：

P36：6,8,11

教学内容

3.1.1上下文无关文法

箭头'一>'读为“定义为"，直竖'|'读为"或”，它们是元语言符号。在后面

的探讨中，依据不同状况，我们将用大写字母A、B、C…或汉语词组（如，算术

表达式）代表非终结符号，特殊是用小写字母a、b、c…代表终结符，用a、8、

Y等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例

子时，仅列出产生式和指出起先符号。

例如，下面是一个上下文无关文法：

E—>i|EAE

A—>+1*

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

一个上下文无关文法如何定义一个语言呢？其中心思想是，从文法的起先符号动

身，反复连续运用产生式，对非终结符施行替换和绽开。例如，我们考虑下面的

文法G：

E—>E十E|E*E|（E）|i

其中，唯一的非终结符E可以看成是代表一类算术表达式。我们可以从E动身，

进行一系列的推导，推出种种不同的算术表达式来。例如，依据规则E-XE）

我们可以说：从'E'可干脆（一步地）推出'（E）'。与前面一样，我们用'=>'

表示“干脆推出”，这样，这句话就可表示为：En（E）。若对'（E）'中的E运用

规则E—>E+E,就有

（E）=>（E+E）o即，从'（E）'可干脆推出'（E+E）'。把上述这两步合并起来，就

有

En（E）n（E+E）。再对'（E+E）'中的E相继两次运用规则E—>i之后，我们就有

（E）=>（E+E）=>（i+E）=>（i+i）o

我们称这样的一串替换序列是从E推出（i+i）的一个推导。这个推导供应了一个

证明，证明（i+i）是文法（2.1）所定义的一个算术表达式。留意，推导每前进一步

总是引用一条规则（产生式），而符号指仅推导一步的意思。

我们可以用一种图示化的方法来表示这种推导，如下图2.1,说明Hegavemea

book是一个语法正确的句子。这种图形表示称为语法分析树。

定义"hegavemeabook”这个英文句子的规则可以说就是一个上下文无关文

法。其中，He,me,book,gave,a等，称为终结符号；〈句子〉、〈主语〉、〈谓

语〉、〈动词〉、〈代词〉等，称为非终结符号；这个文法最终是要定义＜句子》的语

法结构，所以〈句子＞在这里称为起先符号；〈间接宾语〉冠词X名词》这种书

写形式称为产生式。

归纳起来，一个上下文无关文法C包括四个组成部分：一组终结符号，一组非终

结符号，一个起先符号，以及一组产生式。

所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的

单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，

终结符号是一个语言的不行再分的基本符号。

图2.1语法树

非终结符号（也称语法变量）用来代表语法范畴。例如，“算术表达式”、“布尔表

达式”、“赋值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范

畴。我们也可以说，一个非终结符代表一个肯定的语法概念。因此，一个非终结

符是一个类（或集合）记号，而不是一个个体记号。例如，“算术表达式”这个非

终结符乃代表肯定算术式组成的类。因而，也可以说，每个非终结符号表示肯定

符号串的集合（由终结符号和非终结符号组成的符号串）。

起先符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感爱好的语

法范畴，这个语法范畴通常称为“句子”。但在程序语言中，我们最终感爱好的

是“程序”这个语法范畴，而其它的语法范畴都只不过是构造“程序”的一块块

砖石O

3.1.2语法分析树与二义性

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

或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示

成一棵倒立的树，根在上，枝叶在下。语法树的根结由起先符号所标记。随着推

导的绽开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结

就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符

号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过

程中的任何时刻，全部那些没有后代的端末结自左至右排列起来就是一个句型。

例如，对于文法（2.1）,关于（i*i+i）的推导（2.2）的语法树如图2.2所示。

这就是说，一棵语法树表示了一个句型种种可能的（但未必是全部的）不同推导过

程，包括最左（最右）推导。这样的一棵语法树是这些不同推导过程的共性抽象，

是它们的代表。

假如我们坚持运用最左（最右）推导，那么，一棵语法树就完全等价于一个最左（最

右）推导，这种等价性包括树的步步成长和推导的步步绽开之间的完全一样性。

但是，一个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一

个最左（最右）推导呢？不尽然。

3.1.3形式语言俯视

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

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

限制。

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

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

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

一般不允许替换成空串。

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

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

下面两种形式的产生式：ATBa或ATa。

3.2.1文法等价的概念：

若L（G1）=L（G2）,则称文法G1和G2是等价的

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

G1[A]:AORA01RA1

G2[A]:S0S1S01

因为L（G1）=L（G2）={0n1n|n21}

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

为文法的等价变换。

3.2.2、增广文法

定义：设文法G[S]={VN,VT,P,S},构造文法G，[S']=(VNU{S'},VT,P\S'),其中，P5={A

a|Aa6P}USS},明显L(G)=L(G'),称G'为文法G的增广文法。

例：[Z]:ZTabZA|aATb

经等价变换后可得到增广文法GEA1]：

Z'TZ

ZTabZA|a

ATb

3.2.3、提取左因子

定义：若文法中有产生式PT501|502|...|6Bn,则称该文发含有左因子5。其中

PeVN,01,02...BnW(VNUVT)*。

例：文法[S]:S->iEtS|iEtSeS|aE->b

提取左因子该文法变为：

G[S]：STiEtSS'|a

S5TeS|£

ETb

3.2.4、消退左递归

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

a,则称该文法含有干脆左递归。若存在产生式PnP1a,P1nP2B,……,Pn-1

=>PnY,PnnP5,则称该文法含有间接左递归。其中P,P1,…，PnGVN,a,

d,Y,5e(VNUVT)*O

干脆左递归的消退方法：

假设非终结符P存在产生式PnPa|。

删除左递归产生式PnPa

引入新的非终结符P，消退文法中的左递归，得：

PnBP，

P，naP，|E

间接左递归的消退方法：

将间接左递归转化为干脆左递归；

消退干脆左递归；

化简文法，删除含有从起始符号无法到达的非终结符的产生式

最终，作为描述程序语言的上下文无关文法，我们对它有几点限制。

(1)文法中不含任何下面形式的产生式：P-4P因为这种产生式除了产生二义性

外没有任何用处。

(2)每个非终结符P必需有用处。这一方面意味着，必需存在含P的句型；也

就是，从起先符号动身，存在推导S=>*aPp.

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

永不终结的回路。

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

授课题目(教学章、节或主题)：课时支配12

第三章语法分析——自上而下分析第4周第3-6节

授课时间第6周第1-6节

第7周第1-2节

教学目的、要求(分驾驭、熟识、了解三个层次)：

了解确定的自顶向下分析思想

熟识某些非LL(1)文法到LL(1)文法的等价变换

驾驭LL(1)文法的判别、确定的自顶向下分析方法

教学重点和难点：语法分析器的功能、确定的自顶向下分析思想、LL(1)文法的判别、某

些非LL(1)文法到LL(1)文法的等价变换、不确定的自顶向下分析思

想、确定的自顶向下分析方法

授课类型(请打J)：理论课目探讨课口试验课因练习课囱其他口

教学方式(请打J)：讲授团探讨口示教口指导因其他口

教学资源(请打J)：多媒体因模型口实物口挂图口音像口其他口

探讨、思索题、作业：

P81：1,2,4

教学内容

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

3.1语法分析器的功能

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

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

语法分析的方法：可大致分为两类，一类是自下而上分析法，另一类是自上而下

分析法。所谓自下而上分析法就是从输入串起先，逐步进行''归约"，直至归约

到文法的起先符号。自上而下分析过程恰好与此相反，它从文法的起先符号动身，

反复运用各种产生式，找寻“匹配”于输入串的推导。

3.2自上而下分析面临的问题

本节主要是通过例子使我们相识到，作自上而下分析所遇到的主要困难是语法的

左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒

重来，为解决这些问题我们要消退左递归和消退回溯。

3.3LL(1)分析法

自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析

算法，首先要消退文法的左递归性，并找出克服回溯的充分必要条件。

3.3.1左递归的消退

假定关于非终结符P的规则为：P—>P|a0

其中，每个都不以P开头，那么我们可以把P的规则改写成如下的非干脆左递

归形式：

p—PP'

p'—ap'|E(E为空字)

这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。

3.3.2消退回溯、提左因子

我们首先来看一下在不得回溯的状况下对于文法有什么要求。前面已经说过，欲

实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，对G

的全部的非终结符号的每个候选a定义它的终结首符集FIRST(a)为：

FIRST(a)={a|a=>*a...,aeVT)

特殊是，若a=*E,则规定£sFIRST(a)o换句话说FIRST(a)是a的全部可能推

导的开头终结符或可能的so假如非终结符A的全部候选首符集两两不相交，即

A的任何两个不同的候选ai和aj

FIRST(ai)cFIRST(aj)那么，当要求A匹配输入串时，A就能依据它所面临

的第一个输入符号a,精确地指派某个候选前去执行任务。这个候选就是那个终

结首符集含a的a。

如何把一个文法改造成任何终结首符集的全部候选首符集两两不相交呢？其方

法是提取公共左因子。例如，假定关于A的规则是

A^8pl|5p2|...|8PnlyllY2|...lym(其中每个丫不以3开头)

刃卜么，可以把这些规则改写成：A.3A'|yl|丫2|…lym

A^|pl|p2l...lpn

3.3.3LL(1)分析条件

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

FOLLOW(A)={a|S=*...Aa...,a/}

特殊是，若Sn*...A,则规定#eFOLLOW(A).也就是说，FOLLOW(A)是全部句型

中出现在紧接A之后的终结符或者中，。推断某给定文法是否为LL(1)文法其条件

为：

(1)文法不含左递归。

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

即，若

A―^a1|a2|...|an则：

FIRST(ai)nFIRST(aj)=(|)(iwj)

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

FIRST(A)nFLLOW(A)=(|)一个文法若满意以上条件，

则称该文法G为LL⑴文法

3.4递归下降分析程序构造

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

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

文法如下：

E—>TE5E—+TEVE

T—>FTT—*FTVE

F—>(E)/i

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

析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终

结符。这样的一个分析程序称为递归下降分析器。

3.5预料分析程序

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

统刚才有实际意义。实现LL(1)分析的另一种有效方法是运用一张分析表和一个

栈进行联合限制。我们现在要介绍的预料分析程序就是属于这种类型的LL(1)分

析器

3.5.1预料分析程序工作过程

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

a行事的。

3.5.2预料分析表的构造

为了构造预料分析表M,我们须要先构造与文法G有关的集合FIRST和FOLLOW.

消退左递归和提取左因子将有助于获得无多重定义的分析表Mo

可以证明，一个文法G的预料分析表M不含多重定义入口，当且仅当该文法为LL(1)

的。

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

我们以预料分析为例。在预料分析过程中，出现了下列两种状况，则说明遇到了

语法错误。

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

(2)非终结符A处于栈顶，面临的输入符号为a,但分析表M中的MIA,a］为空。

发觉错误后，要尽快地从错误中复原过来，使分析能接着进行下去。基本的做法

就是跳过输入串中的一些符号直至遇到“同步符号”为止。这种做法的效果有赖

于同步符号集的选择。我们可以从以下几个方面考虑同步符号集的选择。

(1)把FOLLOW(A)中的全部符号放人非终结符A的同步符号集。假如我们跳读一些

输入符号直到出现FOLLOWS)中的符号，把A从栈中弹出，这样就可能使分析接

着下去。

(2)对于非终结符A来说，只用FOLLOWS)作为它的同步符号集是不够的。例如，

假如分号作为语句的结束符(C语言中就是这样的)，那么作为语句开头的关键字

就可能不在产生表达式的非终结符的FOLIDW集中。这样，在一个赋值语句后少

一个分号就可能导致作为下一语句开头的关键字被跳过。

(3)假如把FIRSTS)中的符号加入非终结符A的同步符号集，那么，当FIRSTS)

中的一个符号在输入中出现时，可以依据A复原语法分析。

(4)假如一个非终结符产生空串，那么，推导6的产生式可以作为缺省的状况，

这样做可以推迟某些错误检查，但不能导致放弃一个错误。这种方法削减在错误

复原期间必需考虑的非终结符数。

⑸假如不能匹配栈顶的终