《编译原理》教案

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

2、，学习方法介绍，成绩考核标准。第一章 引论1.1 什么叫编译程序？ 通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序)，而后者与前者在逻辑上是等价的。如果 源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序。 高级语言程序除了像上面所说的先编译后执行外，有时也可“解释”执行。一个源语言的解释程序是这样的程序，它以该语言写的源程序作为输入，但不产生目标程序，而是 边解释边执行源程序本身。本书将

3、不对解释程序作专门的讨论。实际上，许多编译程序的构造与实现技术同样适用于解释程序。 根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试 的编译程序称为诊断编译程序(Diagnostic Compiler)，着重于提高目标代码效率的编译程序叫优化编译程序(Optimizing Compiler)。现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过“开关”进行选择。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。 如果一个编译程序产生不同于其宿主机的机器代码， 则称它为交叉编译程序(CrOSS Compiler)。如果不需重写编译程序中与机

4、器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序(Retargetable Compiler)。1.2 编译过程概述编译程序过程: 从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成.1.3 编译程序的结构 编译程序的结构可以按照从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成。 编译程序总框 编译程序的结构可以按照这五个阶段的任务分模块进行设计。下图给出了编译程序的总框。 表格与表格管理 编译程序在工作过程中需要保持一系

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

6、符)后，它把该名字填人到符号表中。但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填人。例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确定。 由此可见，编译各阶段都涉及到构造、查找或更新有关的表格。 出错处理 遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生产新的中间结果或目标程序。一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。这部分工作是由专门的一组程序(叫做出错处理程序)完成的。一个好的编译程序应能最大限度地发现源

7、程序中的各种错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。如果不仅能够发现错误，而且还能自动校正错、误，那当然就更好了。但是，自动校正错误的代价是非常高的。 编译过程的每一阶段都可能检测出错误，其中，绝大多数错误可以在编译的前三阶段检测出来。源程序中的错误通常分为语法错误和语义错误两大类。语法错误是指源程序中不符合语法(或词法)规则的错误，它们可在词法分析或语法分析时检测出来。例如，词法分析阶段能够检测出“非法字符”之类的错误；语法分析阶段能够检测出诸如“括号不匹配”、“缺少；”之

8、类的错误。语义错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。语义错误通常包括：说明错误、作用域错误、类型不一致等等。 遍 遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生产新的中间结果或目标程序。通常，每遍的工作由从外存上获得的前一遍的中间结果开始(对于第一遍而言，从外存上获得源程序)，完成它所含的有关工作之后，再把结果记录于外存。既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。例如，词法分析这一阶段可以单独作为一遍，但更多的时候是把它与语法分析合并为一遍；为了便于处理，语法分析和语义分析与中

9、间代码产生又常常合为一遍。在优化要求很高时，往往还可把优化阶段分为若干遍来实现。 当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如，我们可以把词法分析、语法分析及语义分析与中间代码产生这三阶段安排成一遍。这时，语法分析器处于核心位置，当它在识别语法结构而需要下一单词符号时，它就调用词法分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语义分析并产生相应的中间代码。 一个编译程序究竟应分成几遍，如何划分，是与源语言、设计要求、硬件设备等诸因素有关的，因此难于统一划定。遍数多一点有个好处，即整个编译程序的逻辑结构可能清晰一点。但遍数多势必增加输入输出所消耗的时间。因此，在主

10、存可能的前提下，一般还是遍数尽可能少一点为好。应当注意的是，并不是每种语言都可以用单遍编译程序实现。 编译前端与后端 概念上，我们有时把编译程序划分为编译前端和编译后端。前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。 可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程序。如果后端的设计是经过精心考虑的，那么后端的改写将用不了太大工作量，这样就可实现编译

11、程序的目标机改变。也可以设想将几种源语言编译成相同的中间语言，然后为不同的前端配上相同的后端，这样就可为同一台机器生成不同语言的编译程序。然而，由于不同语言存在某些微妙的区别，因此在这方面所取得的成果还非常有限。 为了实现编译程序可改变目标机，通常需要有一种定义良好的中间语言支持。例如在著名的Ada程序设计环境APSE中，使用的是一种称为Diana的树形结构的中间语言一个Ada源程序通过前编译转换为Diana中间代码，由编译后端把Diana中间代码转换为目标代码。编译前端与不同的编译后端以Diana为界面，实现编译程序的目标机改变。 又如，在Java语言环境中，为了使编译后的程序从一个平台移到

12、另一个平台，Java定义一种虚拟机代码-Bytecode。只要实际使用的操作平台上实现了的Java解释器，这个操作平台就可以执行各种Java程序。这就是所谓Java语言操作平台无关性。1.4 编译程序与程序设计环境 开发通常还需要一些其它的工具；如编辑程序、连接程序，调试工具等等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。 在高级语言发展的早期，这些程序设计工具往往是独立的，缺乏整体性，而且也缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，现在人们越来越倾向于构造集成化的程序设计环境。一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具集成起来，以便为程序员提供完整

13、的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全生命周期。有代表性的集成化程序设计环境有Ada语言程序设计环境APSE、LISP语言程序设计环境INTERLISP等。广大读者所熟悉的Pascal、TurboC、VisualC+等语言环境也都可认为是集成化的程序设计环境。1.5 编译程序的生成 以前人们构造编译程序大多是用机器语言或汇编语言做工具的。为了发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然采用这种工具来构造编译程序。但是，越来越多的人倾向于使用高级语

14、言作为工具来构造编译程序。因为，这样可以节省大量的程序设计时间，而且所构造出来的编译程序也易于阅读、修改和移植。 人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器，有些可用于自动产生语法分析器，有些甚至可用来自动产生整个的编译程序。如：编译程序-编译程序、编译程序产生器、翻译程序书写系统等，它们是按照对源语言和目标语言（或机器）的形式描述（作为输入数据）而自动产生编译程序的。本课程将把自动产生器作为一个重要课题来讨论。 近些年来，有些人主张采用“自编译方式”产生编译程序。意思是，先对语言的核心部分构造一个小小的编译程序（可用手编实现），再以它为工具构造一个能

15、够编译更多语言成分的较大编译程序。如此扩展下去，就象滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。这种通过一系列自展途径而形成编译程序的过程叫作自编译过程。 现在，有些编译程序是通过“移植”得到的。即把某一机器上的编译程序移植到另一机器上。着需要寻求某种适当的“中间语言”。但是，由于建立通用中间语言实际上办不到，因此，移植也只能在几种语言和几种机器之间进行。授课题目（教学章、节或主题）：第二章 词法分析课时安排12授课时间第1周 第3-6节 第2周 第1-6节第3周 第1、2节 教学目的、要求（分掌握、熟悉、了解三个层次）：了解词法分析器的构造方法熟悉词法分析的任务和过程掌握正规式和

16、有限自动机的基本概念教学重点和难点：词法分析器的设计、正规表达式和有限自动机、正规表达式和有限自动机的等价性、正规文法和有限自动机间的转换授课类型（请打）：理论课þ 讨论课 实验课þ 练习课þ 其他教学方式（请打）：讲授þ 讨论 示教 指导þ 其他教学资源（请打）：多媒体þ 模型 实物 挂图 音像 其他讨论、思考题、作业：P63：3，6，7，8，12，14教学内容第二章 词法分析2.1 对于词法分析器的要求 首先讨论词法分析器输出的单词符号的一般形式，然后研究词法分析器应如何和语法分析器相衔接。2.1.1 词法分析器的功能和输出形式

17、词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号，程序语言的单词符号一般可分为下列五种：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 标识符 用来表示各种名字，如变量名、数组名和过程名等等；3 常 数 各种类型的常数，如125，0.718、TRUE等等； 4 运算符 如+、-、*、/等等； 5 界 符 如逗号、括号、分号等等。 标识符一般统归为一种。常数则宜按类型（整、实、复或布尔）分种。基本字可将其全体视为一种，也可以一字一种。运算符可采用一符一种的分法，但也可以把具有一定共性的算符（如所有关系符）视为一种。界符一般用一符一种的分法

18、。 如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有许多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给出自身的值。2.1.2 词法分析器作为一个独立子程序 可以使整个编译程序的结构更简洁、清晰和条例化。2.2 词法分析器的设计 我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。2.2.1 输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称为输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的

19、识别工作将是比较方便的。 预处理的工作包括：剔除无用的空白、跳格、回车和换行符等编辑性字符；预处理工作还可以包括源程序和出错信息的列表打印。2.2.2 单词符号的识别：超前搜索词法分析器的结构如下图所示：当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，扫描器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。图3.1 词法分析器下面我们来介绍一下单词符号识别的一个简单方法超前搜索。 基本字的识别 有些语言的基本字的输入表示有特殊标志，如加双引号（如“BEGIN”），在这种情况下，基本字的识别是很直接的，不存在什么困难。 象FORTRAN

20、这样的语言，基本字不加特殊保护，基本字和用户自定义的标识符或标号之间没有特殊的界符作间隔，这就使得基本字的识别甚为麻烦。这里就需要用到超前搜索。2.2.3 状态转换图 使用状态转换图是设计词法分析程序(扫描器)的一种好途径。转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结(即箭弧始节)状态下可能出现的输入字符或字符类。如下图3.2（a）所示。在状态1下，若输入字符X，则读进X，并转换到状态2。若输入字符Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态

21、（用双圈表示）。图3.2（a）状态转换图示例2.2.4 状态转换图的实现 一个状态转换图可用于识别（或接受）一定的字符。大多数程序语言的单词符号都可以用转换图予以识别。转换图非常易于用程序实现，最简单的办法是让每个状态结点对应一小段程序。下面我们将引进一组全局变量和过程，把它们作为实现转换图的基本成分。这些变量和过程是：1. CHAR 字符变量，存放最新读进的源程序字符。2. TOKEN 字符数组，存放构成单词符号的字符串。3. GETCHAR 子程序过程，把下一个输入字符读到CHAR中，把搜索指示器前移一字节位置。4. GETBC 子程序过程，检查CHAR中的字符是否为空白.若是，则GETC

22、HAR直到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 子程序过程，把搜索指示器回调一个字节位置，把C

23、HAR中的字符置为空白。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）*也都是

24、正规式，它们所表示的正规集分别为L（U）ÈL（V）、L（U）.L（V）（连接积）和 （L（U）*（闭包）。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。算符的优先顺序为：先"*"，次"."，最后"|"。例如，令 =a，b ，下面是 上的正规式和相应的正规集：ba*： 上所有以b为首后跟任意多个a的字a(a| b)* ： 上所有以a为首的字(a| b)* (aa| bb)(a|b)*： 上所有含有两个相继的a或两个相继的b的字 又例如，令=A，B，0，1 ，则 (A|B)(A|

25、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.

26、 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,

27、b)=2f(1,a)=3 f(4,b)=2f(2,a)=1 f(2,b)=3f(3,a)=3 f(3,b)=3则对应的状态转换矩阵如下表3.2所示：表3.2 状态转换矩阵状态ab012132213333一个DFA也可以表示成一张（确定的）状态转换图。对于*中的任何字a，若存在一条从初态结到某一条终态结的道路，且这条路上所有弧的标记符连接成的字等于a，则称a可为DFA M 所识别（读出或接受）。若 M的初态结同时又是终态结， 则空字可为M所识别（或接受）。上例所定义的DFA M相应的状态转换图如下所示：它能识别上所有含有相继两个a或相继两个b的字。图3.5 状态转换图2.3.3 非确定有限自动机

28、(NFA) 设一个确定的有限自动机（DFA）M是一个五元式M=(S,f,S0, Z)其中1. S是一个有限集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入字符；3. f是一个从S×*到S的子集的映照，即 f：S×*® 2S4. S0ÍS，是非空初态集；5. Z ÍS，是一个终态集（可空）。2.3.4 正规文法与有限自动机的等价性 对于正规文法G和有限自动机M，如果L（G）L（M），则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：（1） 对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机

29、（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.

30、4.1 语言LEX的一般描述 一个LEX源程序主要包括两部分。一部分是正规定义式，另一个是识别规则。 产生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。一个产生式的 形式是 A®a 其中，箭头(有时也用：)左边的A是一个非终结符，称为产生式的左部符号；箭头右边的a是由终结符号或非终结符号组成的符号串，称为产生式的右部。我们有时也说，产生式A®a是关于A的一条产生规则。产生式是用来定义语法范畴的。例如，令i 代表已定义的范畴“变量”，那么，产生式 算术表达式®i 意味着把“算术表达式”这个范畴定义为“变量”。在有的书上，“®”也用“：”表示：这

31、种表示方法也称巴科斯范式。2.4.2 超前搜索 在某些语言中，要识别一个单词符号必须超前看若干字符。2.4.3 LEX的实现 LEX的编译程序旨在将一个LEX源程序改造为一个词法分析器L，这个词法分析器L将像有限自动机那样工作。相关介绍：人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器(如LEX)，有些可用于自动产生语法分析器(如YACC)，有些甚至可用来自动产生整个的编译程序。这些构造编译程序的工具称为编译程序编译程序、编译程序产生器或翻译程序书写系统，它们是按对源程序和目标语言(或机器)的形式描述(作为输入数据)而自动产生编译程序的。授课题目（教学章、节或

32、主题）：第三章 语法分析-上下文无关文法、形式语言和文法课时安排6授课时间 第3周 第3-6节 第4周 第1、2节 教学目的、要求（分掌握、熟悉、了解三个层次）：理解和定义上下文无关文法，为学习和构造编译程序打下良好基础。理解语言和文法的定义掌握文法的等价变换及语法描述方法了解文法的分类教学重点和难点：文法的直观概念、文法和语言的形式定义、文法的类型、语法树和二义性、文法中的实用限制、句型的分析授课类型（请打）：理论课þ 讨论课 实验课 练习课þ 其他教学方式（请打）：讲授þ 讨论 示教 指导þ 其他教学资源（请打）：多媒体þ 模型 实物 挂图

33、 音像 其他讨论、思考题、作业：P36：6，8，11教学内容 上下文无关文法 箭头->读为“定义为”，直竖|读为“或”，它们是元语言符号。在后面的讨论中，根据不同情况，我们将用大写字母A、B、C或汉语词组(如，算术表达式)代表非终结符号，特别是用小写字母a、b、c代表终结符，用、等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。 例如，下面是一个上下文无关文法：E->i|EAEA->+|*其中，E、A是非终结符，E是开始符号，而i、+和*是终结符。一个上下文无关文法如何定义一个语言呢?其中心思想是，从文法的开始符号出发，反复

34、连续使用产生式，对非终结符施行替换和展开。例如，我们考虑下面的文法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+

35、E)中的E相继两次使用规则E->i之后，我们就有(E) Þ(E+E)Þ(i+E)Þ(i+i)。我们称这样的一串替换序列是从E推出(i+i)的一个推导。这个推导提供了一个证明，证明(i+i)是文法(2.1)所定义的一个算术表达式。注意，推导每前进一步总是引用一条规则(产生式),而符号Þ指仅推导一步的意思。我们可以用一种图示化的方法来表示这种推导，如下图2.1，说明He gave me a book是一个语法正确的句子。这种图形表示称为语法分析树。定义 “he gave me a book”这个英文句子的规则可以说就是一个上下文无关文法。其中，He，m

36、e，book，gave，a等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非终结符号；这个文法最终是要定义<句子>的语法结构，所以<句子>在这里称为开始符号；<间接宾语>-><冠词><名词>这种书写形式称为产生式。归纳起来，一个上下文无关文法C包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。 所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析

37、的角度来看，终结符号是一个语言的不可再分的基本符号。<句子><主语><谓语><形容词><名词><动词><宾语><形容词><名词> hegavemeabook图2.1语法树非终结符号(也称语法变量)用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、“赋值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范畴。我们也可以说，一个非终结符代表一个一定的语法概念。因此，一个非终结符是一个类(或集合)记号，而不是一个个体记号。例如，“算术表达式”这个非终结符乃代表一定算术式组成的类

38、。因而，也可以说，每个非终结符号表示一定符号串的集合(由终结符号和非终结符号组成的符号串)。开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”。但在程序语言中，我们最终感兴趣的是“程序”这个语法范畴，而其它的语法范畴都只不过是构造“程序”的一块块砖石。 语法分析树与二义性 前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，枝叶在下。语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结

39、符的相应结就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。例如，对于文法(2.1)，关于(i*i+i)的推导(2.2)的语法树如图2.2所示。图2.2 语法树这就是说，一棵语法树表示了一个句型种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表。如果我们坚持使用最左(最右)推导，那么，一棵语法树就完全等价于一个最左(最右)推导，这种等价性包括树的步步成长和推导的步步

40、展开之间的完全一致性。但是，一个句型是否只对应唯一的一棵语法树呢?也就是，它是否只有唯一的一个最左(最右)推导呢?不尽然。 形式语言鸟瞰 前面乔姆斯基把文法分成四种类型，即0型，1型，2型，和3型。0型强于1型，1型强于2型，2型强于3型。这几类文法的差别在于对产生式施加不同的限制。 0型文法：也称短语文法，其能力相当于图灵机。任何0型语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。 1型文法：也称上下文有关文法，对非终结符进行替换时务必联系上下文，并且一般不允许替换成空串。 2型文法：也称上下文无关文法 3型文法：也称右线性文法，这类文法等价于正规式，所以也称正规文法。只有下面两

41、种形式的产生式：ABa 或Aa。文法等价的概念： 若L(G1)=L(G2),则称文法G1和G2是等价的例如：下列两个文法是等价的G1A: A 0R A 01 R A1G2A：S 0S1 S 01因为L(G1)=L(G2)=0n1n|n 1定义：对文法进行变换，使变换后的文法满足某种要求并于原文法等价，这种变换成为文法的等价变换。、增广文法定义：设文法GS=VN,VT,P,S，构造文法GS=(VNS,VT,P,S),其中，P=A |A PS S,显然L(G)= L(G)，称G为文法G的增广文法。例：Z:Z abZA|a Ab经等价变换后可得到增广文法GA: Z Z Z abZA|a Ab、提取左

42、因子定义：若文法中有产生式P1|2|n,则称该文发含有左因子。其中P VN ，1，2 n (VN VT)*。例：文法S: S iEtS|iEtSeS|a E b提取左因子该文法变为： GS: S iEtSS|a S eS| E b、消除左递归定义：若文法中存在推导：P Þ+ P,则称该文法含有左递归。若存在产生式P Þ P,则称该文法含有直接左递归。若存在产生式P Þ P1，P1 ÞP2, ,Pn-1 ÞPn，Pn Þ P,则称该文法含有间接左递归。其中P,P1, ,Pn VN, , , , (VN VT)*。直接左递归的消除方法：假

43、设非终结符P存在产生式P ÞP|删除左递归产生式P ÞP引入新的非终结符P消除文法中的左递归，得： P ÞP P ÞP|间接左递归的消除方法：将间接左递归转化为直接左递归；消除直接左递归；化简文法，删除含有从起始符号无法到达的非终结符的产生式最后，作为描述程序语言的上下文无关文法，我们对它有几点限制。 （1）文法中不含任何下面形式的产生式： PP因为这种产生式除了产生二义性外没有任何用处。（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导 SÞ*aPb. 另一方面意味着，必须存在终结符串g

44、06;VT*,使得PÞ+g；也就是，对于P不存在永不终结的回路。 我们以后所讨论的文法均假定满足上述两条件。授课题目（教学章、节或主题）：第三章 语法分析自上而下分析课时安排12授课时间 第4周 第3-6节 第6周 第1-6节 第7周 第1-2节 教学目的、要求（分掌握、熟悉、了解三个层次）：了解确定的自顶向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等价变换掌握LL（1）文法的判别、确定的自顶向下分析方法教学重点和难点：语法分析器的功能、确定的自顶向下分析思想、LL（1）文法的判别、某些非LL（1）文法到LL（1）文法的等价变换、不确定的自顶向下分析思想、确定的自顶向下分析

45、方法授课类型（请打）：理论课þ 讨论课 实验课þ 练习课þ 其他教学方式（请打）：讲授þ 讨论 示教 指导þ 其他教学资源（请打）：多媒体þ 模型 实物 挂图 音像 其他讨论、思考题、作业：P81：1，2，4教学内容第三章 语法分析自上而下分析3.1 语法分析器的功能 语法分析器：是这样的一个程序，它将按文法的产生式，识别输入符号串是否为一个句子。输入串是指由单词符号（文法的终结符）组成的有限序列。语法分析的方法：可大致分为两类，一类是自下而上分析法，另一类是自上而下分析法。所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归

46、约到文法的开始符号。自上而下分析过程恰好与此相反，它从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入串的推导。3.2 自上而下分析面临的问题 本节主要是通过例子使我们认识到，作自上而下分析所遇到的主要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒重来，为解决这些问题我们要消除左递归和消除回溯。3.3 LL(1)分析法 自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。3.3.1 左递归的消除 假定关于非终结符P的规则为 :P-> P| 其中，每个 都不以P开头

47、，那么我们可以把P的规则改写成如下的非直接左递归形式：p -p'p'- p'|( 为空字)这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。3.3.2 消除回溯、提左因子 我们首先来看一下在不得回溯的情况下对于文法有什么要求。前面已经说过，欲实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，对G 的所有的非终结符号的每个候选a定义它的终结首符集FIRST(a)为： FIRST(a)=a|aÞ*a,aÎVT特别是，若aÞ*，则规定ÎFIRST(a)。换句话说FIRST(a)是a的所有可能推导的开头终结

48、符或可能的。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同的候选ai和aj FIRST(ai)ÇFIRST(aj) = f那么，当要求A匹配输入串时，A 就能根据它所面临的第一个输入符号a，准确地指派某个候选前去执行任务。这个候选就是那个终结首符集含a的a。如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是提取公共左因子。例如，假定关于A 的规则是 A®db1|db2|dbn|g1|g2| |gm （其中每个g不以d开头）那么，可以把这些规则改写成：A®dA|g1|g2| |gmA®|b1|b2|bn 3.3.3 LL

49、(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(ai)ÇFIRST(aj) = f（i¹j ） (3) 对文法中每一个终结符A，若它存在

50、某个候选首符集包含，则 FIRST(A) ÇFLLOW(A)= f一个文法若满足以上条件，则称该文法G为LL(1)文法3.4 递归下降分析程序构造 在不含左递归和每个非终结符的所有候选终结首符集都两两不相交的条件下，可能（仅是可能）构造一个不带回溯的自上而下分析程序. 文法如下：E-> TE E-> +TE/T-> FT T-> *FT/F-> （E）/i 当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。3.5 预测

51、分析程序 用高级语言的递归过程描述递归下降分析器只有当具有实现这种过程的编译系统刚才有实际意义。实现LL(1)分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。我们现在要介绍的预测分析程序就是属于这种类型的LL(1)分析器3.5.1 预测分析程序工作过程 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a行事的。3.5.2 预测分析表的构造 为了构造预测分析表M，我们需要先构造与文法G有关的集合FIRST和FOLLOW. 消除左递归和提取左因子将有助于获得无多重定义的分析表M。 可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。

52、3.6 LL(1)分析中的错误处理 我们以预测分析为例。在预测分析过程中，出现了下列两种情况，则说明遇到了语法错误。(1)栈顶的终结符与当前的输入符号不匹配。(2)非终结符A处于栈顶，面临的输入符号为a，但分析表M中的MIA，a为空。发现错误后，要尽快地从错误中恢复过来，使分析能继续进行下去。基本的做法就是跳过输入串中的一些符号直至遇到“同步符号”为止。这种做法的效果有赖于同步符号集的选择。我们可以从以下几个方面考虑同步符号集的选择。(1)把FOLLOW(A)中的所有符号放人非终结符A的同步符号集。如果我们跳读一些输入符号直到出现FOLLOW(A)中的符号，把A从栈中弹出，这样就可能使分析继续

53、下去。(2)对于非终结符A来说，只用FOLLOW(A)作为它的同步符号集是不够的。例如，如果分号作为语句的结束符(C语言中就是这样的)，那么作为语句开头的关键字就可能不在产生表达式的非终结符的FOLIDW集中。这样，在一个赋值语句后少一个分号就可能导致作为下一语句开头的关键字被跳过。(3)如果把FIRST(A)中的符号加入非终结符A的同步符号集，那么，当FIRST(A)中的一个符号在输人中出现时，可以根据A恢复语法分析。(4)如果一个非终结符产生空串，那么，推导6的产生式可以作为缺省的情况，这样做可以推迟某些错误检查，但不能导致放弃一个错误。这种方法减少在错误恢复期间必须考虑的非终结符数。(5

54、)如果不能匹配栈顶的终结符号，一种简单的想法是弹出栈顶的这个终结符号，并发出一条信息，说明已经插入这个终结符，继续进行语法分析。结果，这种方法使一个单词符号的同步符号集包含所有其它单词符号。授课题目（教学章、节或主题）：第三章 语法分析自下而上分析课时安排16授课时间 第7周 第3-4节第8周 第1-4节 第9周 第1-4节第10周 第1-4节第11周 第1-2节教学目的、要求（分掌握、熟悉、了解三个层次）：熟悉自下而上分析思想了解算符优先分析法掌握LR分析法教学重点和难点：自下而上分析思想、算符优先分析法、LR分析法授课类型（请打）：理论课þ 讨论课 实验课þ 练习课&#

55、254; 其他教学方式（请打）：讲授þ 讨论 示教 指导þ 其他教学资源（请打）：多媒体þ 模型 实物 挂图 音像 其他讨论、思考题、作业：P133：1，2，3，5教学内容第三章 语法分析程序-自下而上分析所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。5.1 自下而上分析基本问题 我们首先讨论自下而上分析法的基本思想和基本概念 3.1.1 归约 “移进-归约”：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换

56、（归约为）该产生式的左部符号。我们可用句柄来刻画移进归约过程的“可归约串”。3.1.2 规范归约简述 规范规约是关于的一个最右推导的逆过程。因此，规范规约也称最左规约。最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的，那么规范推导的逆过程必是规范规约。 句柄：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有SÞ*A且AÞ则称是句型相对于非终结符A的短语。特别是，如果有AÞ则称是句型相对于规则A®b的直接短语。一个句型的最左直接短语称为该句型的句柄。3.1.3 符号栈的使用与语法树的表示 在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的，那么，规范推导(最右推导)的逆过程必是规范归约