教材资料

授课顺序：1

教学目的：正确理解什么是编译程序；了解编译程序工作的基本过程及其各阶段的基本任

务；熟悉编译程序总框；了解编译程序的生成过程和构造工具。 教学重点与难点：

编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。

授课学时：2学时 教学方式：多媒体讲授 教学内容：

第一章 引论 1.1 什么是编译程序

一、基本概念

1、翻译程序：是指这样的一种程序，它能够把一种语言程序(源语言程序)转换成另一种功能等价的语言程序(目标语言程序)。

2、编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。通常是一次性翻译方式。如TC等高级语言编译程序。

3、解释程序也是一种翻译程序，它与编译程序的区别：立即执行源程序，通常是逐句翻译执行。如BASIC、SQL、JAVA的BYTECODE解释程序等。

二、高级语言程序的处理过程

高级程序设计语言程序的典型处理过程如下图所示：

1.2编译过程和编译程序结构

一、编译过程的阶段划分

一般编译程序的工作过程按阶段进行，每个阶段将源程序从一种表示形式转换成另一种表示形式。典型的阶段划分方法是将整个编译过程分为如下六个阶段：

1、词法分析：

任务：对构成源程序的字符串进行扫描和分解，识别出单词(如标识符等)符号。

输入：源程序

输出：单词符号序列

例子：有待分析源程序： main() {

int x=10,y; }

词法分析后的输出：

1）保留字： main 2）界符：左圆括号 ( 3）界符：右圆括号) 4）界符：左大括号{ 5)保留字：int 6)标识符：x 7)运算符：=

8)常数：10 ，界符：， 9)标识符：y 10)界符：；

11）界符：右大括号 }

2、语法分析

任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析，识别出各类语法短语(可表示成语法树的语法单位)，判断输入串在语法上是否正确。

输入：单词序列

输出：语法分析后的单词序列 3、语义分析

任务：按语义规则对语法分析器归约出的语法单位进行语义分析，审查有无语义错误，为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理。 输入：语法分析后的单词序列

输出：语义分析后带语义信息的单词序列

4、中间代码生成（并非所有的编译程序都包含此阶段）

任务：将语义分析得到的源程序变成一种结构简单、含义明确、易生成、易翻译成目标代码的内在代码形式。常用的中间代码形式是四元式（算符，运算对象1，运算对象2，结果）。 输入：语义分析后的单词序列 输出：中间代码

5、代码优化（可放到目标代码生成阶段后）

任务：对中间代码或目标代码进行变换改造等优化处理，使生成的代码更高效。 输入：中间代码或目标代码

输出：优化后的中间代码或目标代码 6、目标代码生成

任务：将中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码。 输入：语义分析后的单词序列或优化后的中间代码 输出：目标代码

二、编译程序结构

上述六个阶段的任务分别由六个模块来完成。一个完整的编译程序还应包括表格管理和出错处理程序。典型编译程序结构框图如下：

三、编译阶段的组合 1、前后端组合法

编译前端：与源语言有关与目标机无关的部分(第1-4阶段)。 编译后端：与目标机有关的部分(第6阶段) 注：第5阶段置前或后端都可以。组合方式：

1）同一源语言的编译前端+不同后端=不同机器上同一源语言的编译程序；

2）不同源语言的编译前端生成同一种中间语言+使用共同后端=同一机器上不同语言的编译程序。

2、遍组合法

遍/趟：对源程序或源程序的中间结果从头到尾扫描一次称为一遍。每一遍扫视完成一个或几个阶段的工作。一个编译程序可由一遍或多遍完成.实际编译程序分遍的主要参考因素是源语言与目标机器的特征。

1.3编译技术和软件工具

一、编译技术的发展

1950S早期：算术工式译成机器代码。 1950S中期：FORTRAN编译系统。

1950S末期：自动生成工具出现，如：LEX、YACC。 1960S：自展技术。

1971年：用自展技术生成PASCAL编译程序。 现代：并行编译技术。

二、编译技术与软件工具

1、先进的软件开发技术和软件工具能提高编程效率、缩短调试时间。 2、编译程序本身是一种软件工具。

3、大部分软件工具的开发常用到编译技术和方法。

4、进行源程序处理的软件工具实质上都在不同程度上用到了编译程序各个部分的技术和方法。如：

（1）语言结构化编辑器（语法）；

（2）语言程序调试工具（语法、语义）；

（3）语言程序测试工具（静、动态测试，发现错误）；

（4）高级语言之间的转换工具；

（5）程序格式化工具、程序理解工具等。

1.4程序设计语言规范

从支持的计算模式来看，程序设计语言（是指书写计算机程序的高级语言）规范有如下几种：

1、强制命令式语言，即过程式语言

该型 语言中，一个过程可看作是一系列动作，其动作由命令驱动，以语句形式表示，一个语句接一个语句的执行。属于这种规范的语言如PASCAL、C、FORTRAN等，C++、Ada、COBOL等也支持这种模式。本课程介绍的编译技术针对这型语句。 2、函数式语言，即应用式语言

该型语言注重程序所表示的功能，程序的开发过程是从前面已有函数出发构造出更加复杂的函数，对初始数据集进行操作，直到最后形成的函数可以得到最终结果。属于这种规范的语言如ML、LISP等。

3、基于规则（逻辑）的语言

该型语言程序的执行过程是检查一定的使能条件，满足时，则执行适当的动作。如逻辑程序设计语言PROLOG，其基本的使能条件是某种谓词逻辑表达式；再如YACC，其使能条件是程序的形式语法（BNF）。 4、面向对象语言

该型语言的主要特点是提供抽象数据类型，支持封装性、继承性和多态性。C++、Ada、Java等也支持这种模式。

1.5编译程序的构造

一、编译程序的构造途径 1、用某种程序语言编写；

2、用编译程序自动构造工具构造。

3、通过现有的编译基础设施进行改造和组装。

二、T型图

T型图是用来表示一个编译程序所涉及到的三个方面的语言的一种工具，将源语言S通过用语言H书写的编译器翻译成目标语言T的编译程序可用如下T型图THST表示。

T型图的两种组合方式：

三、编译程序的自展

1、方法：用“滚雪球”的方式生成编译程序。

2、思想：先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，再用这个子集作为书写语言（属于高级语言），实现源语言的编译程序。

例：设 ， 目标机A的语言为A，则两层自展构造实现语言C对应A

机器的编译程序过程可描述为如下：

其自展过程：用语言A编写语言C1的编译程序TAC1A；再用C1书写语言C的编译程序TC1CA；最后再将TC1CA经过TAC1A编译得到 TACA。

四、编译程序的移植、自编译、交叉编译

1、移植：将某一机器(宿主机)上已有的软件移植到另一机器(目标机)上的过程。 2、自编译：用某种语言本身书写自己的编译程序的过程。 例如：在机器A上已有语言C的编译程序（将语言C翻译成A的机器码A），现希望利用此编译程序生成机器B上的语言C的编译程序（将语言C翻译成B的机器码B）。

3、交叉编译：把某源语言在宿主机上经过编译而产生目标机的汇编语言或机器语言的过程。

五、可重定向编译程序

1、由于交叉编译是在一个平台上生成另一个平台上的可执行代码的过程。交叉编译受限较多。

2、编译基础设施：为开发各种编译程序成分提供相应生成工具。

3、可重定向编译程序：能够根据不同的目标机生成相应目标代码的编译程序。它将与目标机相关的部分单独编写成不同模块，根据不同的目标机调用不同的模块。自由软件GCC(GNU工程的编译程序集合)是目前使用广泛的可重定向编译程序。 ４、支持可重定向编译的关键技术

1）中间表示技术：区别于四元式等传统的中间表示，支持可重定向编译的中间表示应在适当的抽象层次上，向上能够支持多语言映射、向下能够适应多平台转换后宜于进行各种优化。

2)机器描述技术：区别于传统的假定式体系结构抽象模型的描述技术，支持可重定向编译的机器描述机制应能描述系统和硬件的共性，又能描述它们各自的特性，且能适应于不同编译程序的处理。研究表明，基于体系结构描述语言详细地指定了体系结构是产生高质量机器级工具的关键技术。

3）代码生成程序的构造技术：为简化开始过程、提高代码可靠性，支持代码生成程序的自动构造工具是关键技术和主要难点。

4）目标机描述与目标代码生成的接口技术：在重定向编译程序的开始过程中，抽取一系列函数和数据结构作为目标机描述与目标代码生成的接口可以简化编译程序的开发，提高编译程序的效率。

授课顺序：2

教学目的：使学生了解文法的直观描述、符号和符号串，掌握文法和语言的形

式定义、文法的分类。

教学重点：文法和语言的形式定义、文法的分类 教学难点：文法和语言的形式定义 授课学时：2学时

教学方式：多媒体讲授 教学内容：

第三章文法和语言

一、基本概念

1、语言：是由句子组成的集合，是由一组符号所构成的集合。 2、汉语：所有符合汉语语法的句子的全体。 3、英语：所有符合英语语法的句子的全体。

4、程序设计语言：所有该语言的程序的全体。

二、语言研究的内容 1、语法（Syntax）：每个句子构成的规律/每个程序构成的规律。表示构成语言句子的各个记号之间的组合规律。在形式语言理论中，阐明语法的工具是文法。 2、语义（Semantics）：每个句子的含义/每个程序的含义。表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）。 3、语用（Pragmatics）：每个句子和使用者的关系/每个程序和使用者的关系。表示在各个记号所出现的行为中，它们的来源、使用和影响。

三、文法的直观描述

通常，用句子表述一种语言，但是句子是无穷的。 1、例子

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。下面采用EBNF来表示句子的构成规则。先给定如下一组规则：

〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他

〈名词〉∷=王明｜学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习

〈直接宾语〉∷=〈代词〉｜〈名词〉

有了这一组规则后，用它们导出句子的方式如下：

1）找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：

〈句子〉 ? 〈主语〉〈谓语〉 2）在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。

比如：选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉， 那么得到： 〈主语〉〈谓语〉 ? 〈代词〉〈谓语〉，

3.1语言概述和文法的直观概念

3）重复上述步骤。

导出句子：“你是学生”的全部动作过程是： 〈句子〉 ? 〈主语〉〈谓语〉? 〈代词〉〈谓语〉?你〈谓语〉?你〈动词〉〈直接宾语〉? 你是〈直接宾语〉?你是〈名词〉?你是学生

因此，“你是学生”的构成符合上述规则，而“你学生是”不符合上述规则，因此，它不是句子。

2、文法的直观定义

上例中的规则就是我们判别句子结构合法与否的依据，可以将这些规则看成是一种元语言，用它描述汉语。由此可得文法的直观定义如下： 文法：就是这样一些规则的有穷集合，它是以有穷规则集来刻划无穷句子集合的工具。

3.2符号和符号串

一、基本概念

1、字母表：元素的非空有穷集，记为 Σ。 2、符号：字母表中的元素。 3、符号串：符号的有穷序列。

4、空符号串：什么符号也不含的符号串，记为ε。

例： Σ={a，b，c，d，……z}。a、b、c……都称为符号。hello、stri、aezfg、main、fjfka都是Σ上的符号串。

二、符号串的基本操作

1、符号串的长度：符号所包含符号的个数，设x是一符号串，其长度记为|x|。 例：|hello|=5，|main|=4，| ε |=0。

2、符号串的连接：设x、y是两个符号串，则xy被称为x与y的连接。特别有： x=xε=εx=εxε

例：x=my，y=classmate，则xy=myclassmate。

3、符号串的方幂：设x是符号串，x自身的连接称为符号串的方幂，有： 例：x=ba， x0 = ε， x1 =ba， x2 =bababa

4、符号串的集合：若集合A中元素都是某字母表Σ上的符号串，则A是Σ上的符号串集合。

5、符号串集合的乘积：若A、B均为Σ上的符号串集合，则AB={xy|x∈A，y∈ B } 例：设A={ab，cd}，B={ef，jh}，则AB={abef，abjh，cdef，cdjh} A{ε}=A，φ A=Aφ =φ。

6、符号串集合的正闭包：设符号串集合A，A的正闭包记为A+，A的闭包记为A*。 例： 设Σ={0，1}，则 Σ+ ={0，1，00，01，10，11，000，001……}。 Σ* ={ε，0，1，00，01，10……}。

3.3文法和语言的形式定义

一、基本概念 1、产生式

设VN，VT分别是非空有限的非终结符号集和终结符集。V= VN∪ VT， VN ∩ VT=φ。所谓产生式是一个序偶对(α， β )，其中α∈ V+，β∈V*，通常表示为： α → β或α∷ =β，产生式也叫规则、重写规则、生成式。 例：<阿拉伯数字> → 0|1|2|3…|9 2、文法

文法G是一个四元组，G=(VN，VT， P， S)。其中：VN，VT分别是非空有限的非终结符集和终结符集，且二者交集为φ；P为产生式集；S∈ VN，是文法的开始符号(或识别符)，它是一个非终结符，至少要在一条规则中作为左部出现。

例：文法G=(VN，VT， P， S)，其中VN ={S，B}， VT ={0，1}，P={S→ 0B，B→ 1，B→ 1B}。开始符为S。可用文法的通俗表示法表示如下：

G[S]： S→ 0B，B→ 1，B→ 1B

这个文法表示所有形如01，011，0111，01111的串。 3、直接推导

设α→β是文法G=(VN，VT， P， S) 的产生式，γ，δ∈ (VN∪ VT) *，若有符号串v，w满足v=γαδ，w=γβδ，则称w是v的直接推导，或称v是w的直接归约。记作v=>w。 例：现有文法G[E]：E→E+T | T T→T*F | F F→(E) | i 设v=E+F*i，w=E+i*i，则有v=>w或 E+F*i => E+i*i。 4、推导

如存在一直接推导序列v=>α0=>α1=>α2....=>αn=u (n>0)，则称符号串u为符号串v的一个推导(或者说v是u的一个归约)，记为v=+> u；若有v=+>u，且有v=u，则记作v=*>u。 例：对于上例中文法G[E]：E→E+T | T T→T*F | F F→(E) | i 设v=E，u=i+i*i，则有：v=+>u。相应的直接推导序列为： E=>E+T=>E+T*F=>E+F*F=>T+F*F=>F+F*F=>F+F*i=>F+i*i=>i+i*i 5、句型和句子

设G[S]是一文法，如有 S=*> x，则称x是文法G[S]的句型。若x是G[S]的句型，且x∈ VT*，则称x是G[S]的句子。 6、语言

文法G[S]的语言是G[S]的所有句子构成的集合。即L(G) ={x|S =*>x，且x∈VT*}。 例：文法G[S]：S→MVD M→小王|小张 V→是|不是 D→大学生 则文法G[S]表示的语言可定义为：

L(G) ={小王是大学生，小王不是大学生，小张是大学生，小张不是大学生} MVD,M是D,M是大学生等均是G[S]的句型。 7、文法的等价

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

3.4文法的类型

Chomsky将文法按其所表示的语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。 一、定义

（1）0型文法

如果文法G的产生式α→β，其中α∈ (VN∪VT) *， 且至少含有一个非终结符号，β∈ (VN∪VT) *。则称G为0型文法。0型文法又称短语结构文法。 （2）1型文法

如果0型文法G的产生式α→β满足|β|>=|α|，仅当β= ε时例外。则称此文法G是1型文法。1型文法也称上下文有关文法。 （3）2型文法

一个1型文法G，如果满足α∈VN，则称为2型文法。或者说2型文法的产生式都形如A →β。2型文法也称上下文无关文法。 （4）3型文法

一个2型文法G，如果产生式全都是形如 A →a或A →aB，其中：A、B∈ VN ，a∈ ∪VT *，则G为3型文法。3型文法也称正则文法或正规文法或右线性文法。它对应有穷自动机。

（5）四类文法产生对应的四类语言。

二、文法之间的关系

四类文法的定义是通过逐步增加限制条件进行的。即有： 3型文法?2型文法?1型文法?0型文法。 三、例题

判断下列文法类型：

例1：文法G[S]：S →aSYZ S→aYZ aY→ay yY→yy yZ→yz ZY→YZ zZ→zz 0，1

例2：文法G[S]：S →xSYZ S→xYZ xY→x yY→yy yZ→yz ZY→YZ zZ→zz 0，1

例3：文法G[S]：S→aT T→bT|cT|b|c 0，1，2，3

例4：文法G[S]：S→xB|c B→Az A→cS 0，1，2，3

授课顺序：3

教学目的：使学生掌握语法树的构造、句型分析的方法，了解二义性文法的改

造和有关文法实用性的一些说明。

教学重点：句型分析

教学难点：二义性文法的改造、句型分析 授课学时：2学时

教学方式：多媒体讲授 教学内容：

3.4 上下文无关文法及语法树

上下文无关文法有足够的能力来描述现今程序设计语言的语法结构。今后如无特别说明，“文法”一词均指上下文无关文法。 一、语法树

语法树也称推导树，给定文法G=(VN， VT，P，S)，对于文法G的任意一个句型都存在一个相应的语法树，它满足：

(1)树中每一个结点都有一个标记，此标记是V= VN∪VT中的一个符号。 (2)根的标记是S。

(3)苦树的一结点A至少有一个子女，则A∈VN。

(4)如结点A的子女结点从左到右次序为B1，B2...Bn，则必有产生式A→B1B2...Bn。 例：G[S]： S→aAS | a

A→SbA |SS |ba

对句型aabbaa的推导过程可表示为下图所示语法树。

下面两个推导过程均可由上图表示。

(1) S?aAS?aSbAS?aabAS?aabbaS?aabbaa (2) S?aAS?aAa?aSbAa?aSbbaa?aabbaa

这说明同一语法树可以表示对同一句型不同的推导过程。

二、最左(右)推导

1、如果每一步α?β中，都是对α中最左(右)非终结符进行替换， 则称之为最左(右)推导。

2、最右推导称为规范推导，由规范推导所得的句型称为规范句型。 3、同一语法树最多对应唯一的最左(右)推导。 4、一个句型有可能对应着不同的语法树。 例：文法G[E]： E→i | E+E | E*E | (E)，则句型 i*i+i可能对应着下面两个最右推导： (1) E?E+E?E+i?E*E+i?E*i+i?i*i+i (2) E?E*E?E*E+E?E*E+i?E*i+i?i*i+i

三、二义性语法树

1、如果一个文法存在某个句子对应着两棵不同的语法树，则称此文法是二义的。不存在一种算法能在有限步骤内判断一个2型文法是否是二义的。

2、实际应用中，常找出一组无二义性的充分条件来构造无二义性文法。 3、例子

例1：下列简单算术表达式的文法是二义性文法。

E→E+E|E-E|E*E|E/E|(E) |id

引入新的非终结符后可变换为非二义性文法。

E→E+T|E-T|T T→T*F|T/F|F F→(E) |id

例2：If语句的文法G[S]：

S→if E then S S→if E then S else S S→E E→a≠0|a>0|b=1|b=-1|b=0 假设执行下列语句前b=0，有If句子：if a≠0 then if a>0 then b=1 else b=-1 则当a=1时，b=1;当a=-1时，b=-1; 当a=0时，b=0。 通过引入新非终结符、加ε规则进行改造后得文法：

(1)S→U|M|E (2) U→if E then S (3) U→if E then M else U (4) M→if E then M else M (5) M→ S (6) M→ ε (7) E→a≠0|a>0|b=1|b=-1|b=0

课堂作业：为上述改造前和和改造后的文法构造唯一的语法树。

3.6句型的分析

句型的分析就是识别一个符号串是否为某文法的一个句型。本课程介绍的分析算法都是从左到右的分析算法。它们分为两大类：自顶向下分析、自底向上分析 一、自顶向下分析

自顶向下分析：由根向下逐步建立语法树，是一个逐步推导的过程。 例：文法G[S]： S→cAd A→ab |a

对输入串cabd进行识别过程为：S?cAd?cabd，构造语法树步骤如图所示：

识别过程也有可能是S?cAd?cad，此时无法识别出串cabd，需要回溯。

二、自底向上分析

自底向上分析：自叶向上构造语法树，是一个逐步约的过程。自底向上分析法的核心在于寻找“可归约串”。

例：对串cabd归约过程为 cabd?cAd?S，构造语法树步骤如图所示：

归约过程也有可能是cabd?cAbd，此时无法识别出串cabd，也需要回溯。

三、句型分析的有关问题 1、基本概念

（1）令G[S]是一文法，αβδ是文法G的一个句型，如果有：S =*> αAδ，且A =+>β，则称β是句型αβδ相对于非终结符A的短语，如有A?β，则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语(也叫简单短语)。

（2）一个句型的最左直接短语称为该句型的句柄。

注意： 作为短语的β必须是需要分析的句型αβδ的一部分。 2、例子

例1：已知文法G[E]： E→E+T | T T→T*F | F F→(E) | i 对于给定的句型i*i+i，指出该句型的所有短语、直接短语和句柄。 解：将句型改写为i1*i2+i3，则：

1）因 E=+>i1*i2+i3， E=+>i1*i2，故句型相对于E的短语有：i1*i2+i3，i1*i2。 2）因 T=+>i1*i2，T=+>i1，T=+>i3，故句型相对于T的短语有i1*i2， i1， i3。 3）因 F=+>i1，F=+>i2， F=+>i3，故句型相对于F的短语为：i1， i2， i3;且i1， i2， i3均为句型相对于规则F→i 的直接短语，其中i1为句柄。 下面根据语法树进行分析：

例2： G[S]： S→aAS S→ a A→SbA A→ SS A→ ba 要求对句型aabbaa的进行分析。

解：将句型改写为a1a2b1b2a3a4，则：

1）该句型相对于S的短语： a1a2b1b2a3a4和 a4； 2）该句型相对于A的短语： a2b1b2a3和b2a3； 3）该句型相对于Sàa的直接短语： a2，a4； 4）该句型相对于Aàba的直接短语： b2a3； 5）句柄：a2。

问题： a1、b1、b2、a3为什么不是短语？

3.7文法实用性的一些说明

一、有关文法的实用限制

1、在实用中，文法中不得含有害规则或多余规则。 2、形如U→U的规则为有害规则。

3、不可达规则或不可终止规则为多余规则。 例：G[S]：S→Ab|Cd A→b D→e C→Ca

二、限制使用ε规则

即形如A→ε的规则，它会使有关文法的证明和讨论变得复杂。

习题讲解

P48第11题扩展： 令文法G［E］为：E→T|E+T|E-T T→F|T*F|T/F F→(E) |i

要求证明F+T*F是它的一个句型，构造其语法树，并指出这个句型的所有短语、直接短语和句柄。

解：1）证明：因为E? E+T? T+T? F+T? F+T*F，即有E=*> F+T*F，故：F+T*F是G［E］的一个句型。语法树如下图所示。

2）句型分析

该句型相对于E的短语： F+T*F、F； 该句型相对于T的短语： T*F、F；

该句型相对于T→F的直接短语F，相对于T→T*F的直接短语：T*F； 该句型的句柄：F。

作业：P47练习 2、5、9、11、16

授课顺序：4

教学目的：让学生了解词法分析程序的概念及设计原则、单词的分类，掌握正

规文法、正规式的相关概念及等价转换方法。

教学重点：正规文法和正规式的相关概念及等价转换 教学难点：正规文法和正规式的等价转换

授课学时：2学时 教学方式：多媒体讲授 教学内容：

第四章词法分析 4.1 词法分析程序的设计

一、词法分析程序的设计思想

通常将词法分析程序（扫描器）设计为子程序形式，当语法分析程序需要单词时，则调用该子程序。

二、单词分类

通常分为5类： (1)基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用； (2)标识符：表示各种名字；

(3)常量：整型、实型、布尔型、字符型； (4)运算符：算术、逻辑、关系运算符； (5)界符：包括.，;，(，)，:，，等，有时也把运算符称作界符。

三、词法分析程序的设计原则 (1）把扫描器当作语法分析的一个过程，当语法分析需要一个单词时，便调用扫描器。 (2)扫描器从初态出发，当识别一个单词后便进入终态，同时输出二元组。

四、词法分析程序的输出

词法分析程序扫描后输出单词序列表示为如下二元组形式： 二元组：（单词种别，单词自身值或指针）

例：若规定标识符、常数、基本字、运算符、界符的种别用整数编码分别为1、2、3、4、5，则对程序段 ： “ if k=7 then a:=b ; ” ，则其经扫描器扫描后输出的单词符号及其二元组为：

基本字if (3， ?if?)

标识符k (1，?指向k的符号表入口的指针 )

等号= (4， ?=?)? 常数7 （2，?7?） 基本字then (3， ?then?)

标识符a (1， 指向a的符号表入口的指针) 赋值号:= (4， ?:=?)

标识符b (1， 指向b的符号表入口的指针) 分号； (5， ?;?)

五、词法分析程序独立设计的优点

(1)使整个编译程序的结构更加简洁、清晰、条理化； (2)改进了编译程序的效率；

(3）增加了编译程序的可移植性。

4.2?单词的描述工具

一、正规文法

3型文法，又称右线性文法或正规文法(Regular Grammars)，其表达式形如：A→aB或

A→a。正规文法描述的语言是VT*上的正规集。绝大部分程序设计语言的单词都能用正规文法来描述。

二、正规式和正规集 1、定义

正规式也称正规表达式，是表示正规集的工具，递归定义如下：

1)ε和φ都是字母表?上的正规式，表示正规集为{ε}和φ； 2)?a∈?，a是?上的正规式，表示正规集{a}；

3)假定e1、e2都是?上的正规式，对应正规集为L(e1)、L(e2)，则(e1)、e1|e2、e1.e2、e1*也是正规式，分别表示的正规集为L(e1)，L(e1)∪ L(e2)，L(e1).L(e2)，和L(e1)*；

4)仅由有限次运用上述步骤产生的表达式才是?上的正规式，仅由这些正规式产生的字集才是?上的正规集。

例: 设?={0，1}，则有：

正规式 正规集 0 {0}

0|1 01 1* (0|1)*

{0，1} {01}

{ε，1，11，111...} {ε，0，1，01，10......}

3、正规式服从的代数规则

设r，s，t为正规式，则正规式服从如下的代数规则：

r|s=s|r ('或'满足交换律) r|(s|t)=(r|s)|t ('或'满足结合律) r(st)=(rs)t ('连接'满足结合律) r(s|t)=rs | rt (分配律)

rε=εr=r (ε是连接的恒等元素)

注意： rs?sr r|(st)?rs | rt

三、正规式和正规文法的等价性

任意一个正规语言既可以由正规式定义，也可由正规文法来定义。正规式和正规文法之间可进行等价转换。

1、正规式转换成正规文法

将?=VT上的正规式r换成正规文法G =(VN， VT，P，S)方法如下：

(1)令S→r

(2)对形如A→xy的产生式，可分解成A→xB，B→y (3)对形如A→x*y的产生式，可分解成为A→xA， A→y (4)对形如A→x|y 的产生式，可分解为 A→x ，A→y 反复利用上述规则，直至所有产生式中最多只含一个终结符。 例：将R=a(a|d)*转换成相应的正规文法。 解：步骤如下： (1) S→a(a|d)*

(2) S→aB， B→(a|d)B， B→ε

(3) S→aB， B→aB ，B→dB， B→ε

相应的正规文法如(3)式所示，即G[S]: S→aB B→aB|dB|ε 2、正规文法转换成正规式

将正规文法G=(VN， VT，P，S)换成?=VT上的正规式r的转换规则：

1）将产生式A→xB B→y 合写为A=xy；

2）将产生式A→xA A→y 合写为A=x*y； 3）将产生式A→x A→y 合写为A= x|y

反复利用上述规则，直至只剩下一个由开始符定义的产生式，且该产生式右部不含一个非终结符。

例：将正规文法G[S]: S→dA|eB A→aA|b B→bB|c换成正规式。 解：步骤如下：

(1)由A→aA|b，将A转换成a*b；由B→bB|c，将 B转换成b*c； (2)由 S→dA|eB，将S可转换成(da*b)|(eb*c) 故所求正规式为R=(da*b)|(eb*c)。

授课顺序：5

教学目的：让学生掌握DFA和NFA的定义，了解DFA和NFA的表示方法，掌

握NFA与DFA的等价转换方法及DFA的化简方法。

教学重点：DFA和NFA的定义、等价转换及DFA的化简 教学难点：DFA和NFA的等价转换、DFA的化简 授课学时：2学时 教学方式：多媒体讲授 教学内容：

4.3有穷自动机

一、概述

有穷自动机(Finite Automata):可准确识别正规集（即识别正规文法所定义的语言和正规式所表示的集合）的一种装置。它分为两类:

(1)确定的有穷自动机(Deterministic Finite Automata，简称DFA)

(2)不确定的有穷自动机(Nondeterministic Finite Automata，简称NFA)

二、确定的有穷自动机(DFA) 1、定义

确定的有穷自动机表示为一个五元组：M=(K，?，f，S，Z)，其中：

(1) K是一有穷状态集；

(2)?是一有穷字母表，称输入符号字母表；

(3) f是转换函数，是在K??→K上的映射。如f(ki，a)=kj； (4) S是唯一的一个初态；

(5) Z?K，是一终态集，终态也称结束态或可接受态。

2、DFA的状态图表示

假设DFA M有m个状态，n个输入字符，则：

(1)状态图有m个结点，每个结点最多有n条弧射出； (2)有唯一的一个初态结点，前面冠以“=>”或“-”标记； (3)有若干终态结点，用双圆圈或“+”标记；

例：下图所示DFA可识别正则集L(ab*c)，如串abbc可被认别。

3、DFA的矩阵表示 (1)行表示状态；

(2)列表示输入字符则；

(3)矩阵元素表示相应状态行和输入字符列下新状态（即k行a列为f(k，a)的值）； (4)用“=>”标记行或第一行表示初态；

(5)终态行右端标以1，非终态行右端标以0。 例：上图也可表示为矩阵形式：

a b c

S A 0

A A B 0 B 1 4、转换函数定义扩充

方便起见，对DFA中转换函数定义进行扩充：f是转换函数，是在K??*→K上的映

射，有：

(1) f(k1，ε)=k1

(2) f(k1，aα)=f(f(k1，a)，α) 其中，k1∈K，a∈? ，α∈?*。 5、接受(识别)

设DFA=(K，?，f，S，Z)，若f(S，α)=P∈Z，则称符号串α∈?*可被该DFA接受(识别)。

例:试证串abbc可被图示DFA识别。

证：f(S，abbc)=f(f(S，a)，bbc)=f(f(A，b)，bc) =f(f(A，b)，c)=f(A，c)=B 由于B为终态，得证。 6、语言

确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论

(1)?上的一个字符串集V??*是正规集，当且仅当存在着一个?上的确定有穷自动机M，使得V=L(M)。

(2) DFA的确定性表现在状态转换函数是单值函数，即f(k，a)唯一确定一个后继状态。

二、不确定的有穷自动机(NFA) 1、定义

不确定的有穷自动机表示为一个五元组：NFA M=(K，?，f，S，Z)，其中：

(1) K是一有穷状态集

(1)?是一有穷字母表，称输入符号字母表

(3) f是转换函数，是在K??*→K的子集上的映射。 (4)S是初态集

(5) Z?K，是一终态集，终态也称结束态或可接受态。

例：状态图表示的NFA如下：

状态图表示的DFA如下：

4、转换函数定义扩充

因为f是转换函数，是在K??*→K的子集上的映射，有： (1) f(k，aα)=f(k1，α)∪f(k2，α)...∪f(kn，α)

其中，ki∈K，a∈? ，α∈?*，且f(k，a)={k1，k2，....kn} 5、接受(识别)

设NFA=(K，?，f，S，Z)，如果z0∈f(S，α)且z0∈Z，则称符号串α∈?*可被该NFA接受(识别)。

例:试证串abc可被图示NFA识别。

证：f(S，abc)=f(A，bc)=f(A，c)∪f(C，c)=B，又因为B∈ 终态集{B}，得证。 6、语言

不确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论

(1）对于每个NFA M，必存在一个DFA M1，使得L(M)=L(M1)；

(2)对于任何两个有穷自动机M1和M2，若L(M1)=L(M2)，则称有穷自动机M1和M2等价。

三、ＮFA到DFA的转换 1、相关概念

ε闭包：ε-closure(I)表示状态集I中任何状态A经任意条ε弧而能到达的状态集。 状态集I的a弧转换：表示为J=move(I，a)，J是所有那些从I中任一状态经一条a弧而到达的后继状态全体。

令:Ia=ε-closure(J)=ε-closure(move(I，a))

例：对下图NFA，取I={S，1}，则ε-closure(I)＝{S，1，2}，J=move(I，0)={1}， I0=ε-closure(J)={1，2}

2、NFA的确定化

用造表法将NFA确定化过程如下： (0)表的第0行和第0列作标识行列的值。 (1)将ε-closure(I)作为表中第1行第1列。

(1)假定?={a1，a2，...an}，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。

(3)反复重复第(1)步，直至无新状态出现为止。 (4)重新命名新状态。

例：将上图所示NFA确定化(0-3步：造表)

整理后得： 重新命名新状态得DFA如下图所示：

四、DFA的化简 1、相关概念

(1)一个DFA是化简(最小化)了的，即它没有多余状态且其状态中没有相互等价的。 (2)多余状态是指从自动机的开始状态出发，任何输入串也不可达的状态。 2、状态等价

在DFA中，两个状态s和t等价的条件是：

(1)一致性条件：状态s和t必须同时为可接受态和不可接受态。

(2)蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。 3、DFA最小化处理

对DFA最小化的本质：消除多余状态、合并等价状态。

DFA最小化具体过程：用分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。 例：对左图所示DFA最小化。

解：P0={{1，2，3}，{4，5，6，7}}

根据各子集输出弧0和1所达到状态是否为终态，划分为：P1={{1}， {2}， {3}，{4，5，6，7}}，最小化后DFA如上右图所示。

授课顺序：6

教学目的：让学生掌握正规文法、正规式和有穷自动机的等价转换方法，了解

词法分析程序自动构造工具LEX的工作原理及基本使用方法。

教学重点：正规文法、正规式和有穷自动机的等价转换 教学难点：正规文法、正规式和有穷自动机的等价转换 授课学时：2学时 教学方式：多媒体讲授 教学内容：

4.4 正规式和NFA的等价性

一、概述

对于?上的每个NFA M，可以构造一个相应的?上的正规式R，使得L(R)=L(M)。 对于?上的每个正规式R，可以构造一个相应的?上的NFA M，使得L(R)=L(M)。

二、为NFA M构造相应的正规式R

首先，引入两个新结点x，y;x经ε弧到所有初态，所有终态经ε弧到y；然后，再用如下消解规则消去除x，y外的所有结点，最后x，y间弧上的标记串就是所求正规式。

例：给出与图示NFA M等价的正规式R。

解：R=(0|1)*(00|11)(0|1)*

三、由正规式R构造相应的NFA N

其过程与上述过程相反。用如下规则构造NFA：

对R=ε、R=a和R=st（其中，s、t分别为正规式）分别构造:

对R=s|t和R=s*分别构造：

例：为R=(a|b)*abb构造NFA N，使L(R)=L(N)。 解：与R=(a|b)*abb等价的NFA N如下：

4.5 NFA和正规文法的转换

一、概述

对于?上的每个NFA M，可以构造一个相应的?上的正规文法G，使得L(G)=L(M)。 对于?上的每个正规文法G，可以构造一个相应的?上的NFA M，使得L(M)=L(G)。

二、构造正规文法G等价的NFA M

(1)为G中每个非终结符生成M一个状态，开始符为初态。 (2)增加一新状态Z，做为NFA M的终态。

(3)对形如A→aB或A→B的产生式，构造M的转换函数f(A，a)=B或f(A，ε)=B。 (4)对形如A→a的产生式，构造M的转换函数f(A，a)=

授课顺序：7

教学目的：让学生了解自顶向下语法分析思想，掌握LL(1)文法的概念及判别方

法。

教学重点：FIRST(α)集和FOLLW(A)集的计算、LL(1)文法的判别 教学难点：FIRST(α)集和FOLLW(A)集的计算、LL(1)文法的判别 授课学时：2学时

教学方式：多媒体讲授 教学内容：

第五章 自顶向下语法分析方法

语法分析是编译程序的核心部分，其作用是检查由扫描器输出的单词符号序列是否是符合该语言文法的句子。语法分析器的输入是单词符号序列，输出是分析树。 语法分析方法（当今编译程序构造的实用方法）：

1、自顶向下分析：确定的自顶向下分析（递归下降法、预测分析法）、不确定(带回溯)的自顶向下分析。

2、自底向上分析：算符优先分析、LR分析（LR(0)分析、SLR(1)分析、 LR(1)分析、LALR(0)分析）

5.1 自顶向下分析思想

一、自顶向下的分析方法的基本思想(面向目标) 寻找输入符号串最左推导，试图根据当前输入单词判断使用哪个产生式。基本过程是 从根开始，按与最左推导相对应的顺序，构造输入符号串的分析树。

例：根据下面文法G[E]，对符号串 i + i * i进行分析，并按照最左推导构造分析树。

E → T E? E?→ + T E?｜ε T → F T? T?→ * F T?｜ε F → ( E )｜i

解：与最左推导对应的语法树：

二、候选式的确定与回溯

给定文法S→cAd A→ab|a，判断句子cad是否该文法定义语言的句子。

产生式(候选式)的选择与回溯(Backtracking)：当要进行关于某个语法变量的推导时，希望能够根据当前符号确定候选式。

三、FIRST(α)集 1、定义

对于α?、 β∈(ＶT∪ＶN) *， 定义α的首符号集为：FIRST(α)={a|α=*> aβ， a∈ＶT}。

2、各文法符号的FIRST集

各文法符号的 FIRST集计算方法如下：

(1)对X∈?ＶT，FIRST(X)={X}；

(2)对X∈?ＶN，且X→a…，a∈ＶT，则 a∈FIRST(X)； (3)对X∈?ＶN，且X→ε， 则ε∈ FIRST(X)；

(4)对X∈?ＶN，Y1，Y2，…都∈ＶN，且X→Y1Y2…Yn， 则： ① 当Y1不能=*>ε时，FIRST(X)=FIRST(Y1)；

② 当Yi都能=*>ε( i∈[1，n-1] )时，FIRST(X)={ FIRST(Yi)的并集-{ε}}∪ FIRST(Yj)，其中 i∈[1，n-1]，j∈[1，n]。 即：当规则右部Y1Y2…Yn只有前面部分能推导出ε时，FIRST(X)中不含ε。

③ 当Yi都能=*>ε( i∈[1，n] )时，FIRST(X)= FIRST(Yi)的并集，其中 i∈[1，n]。即：当规则右部Y1Y2…Yn都能推导出ε时，FIRST(X)中才会含ε(因为FIRST(Yi)中都含ε)。 ④ 对X∈?ＶN，重复如上述过程，直到所有FIRST集不变为止。 3、符号串的FIRST集

计算符号串（设串α = X1 X2…Xn）的FIRST集方法如下：

1)当X1不能=*>ε时，则FIRST(α)=FIRST(X1)。即：当串α的第一个符号X1不能推导出ε时，只考虑FIRST(X(1)。

(2)当X1能=*>ε，但存在Xi不能=*>ε ( i∈[2，n] )时，则 FIRST(α)=FIRST(Xi)的并集-{ε}。即：当串α的第一个符号能推导出ε，但串中存在某个符号不能推导出ε时， FIRST(α)不含ε。

(3)当X1能=*>ε，其余所有Xi也都能=*>ε ( i∈[2，n] )时，则FIRST(α)=FIRST(Xi)的

并集。即：当串α的所有符号都能推导出ε时，FIRST(α)才含ε。 例：计算表达式文法的语法符号的 FIRST集。

G[E]：E→TE' E'→+TE? E'→ε T→FT' T'→*FT? T'→ε F→(E) F→i 解：FIRST(E')={+，ε} FIRST(+)={+} FIRST(T')={*，ε} FIRST(*)={*}

FIRST(( )={( } FIRST( ))={ )} FIRST(i)={i}

FIRST(F)={(，i} FIRST(T)=FIRST(F)={(，i} FIRST(E)=FIRST(T)={(，i}

若换成：T→T?F E→E?T

则：FIRST(T)={FIRST(T?)-{ε}}∪ FIRST(F)={(，i，*} FIRST(E)={FIRST(E?)-{ε}}∪ FIRST(T)={(，i，+，*}

四、FOLLOW( A )集

1、定义：对于A∈?ＶN定义A的后续符号集：

FOLLOW(A)={a|S uAβ， a∈ＶT，且a∈ FIRST(β)，u∈ＶT，*， β∈Ｖ+ }; 若β=*>ε，则 #∈FOLLOW(A)。

也可以定义为：FOLLOW(A)={a|S …Aa…， a∈ＶT}。若有S=*>…A，则规定#∈FOLLOW(A)。

2、计算FOLLOW集

对于所有出现在规则右部的非终结符，重复进行以下计算： (1)将 #加入到 FOLLOW(S)，其中#为句子的结束符。

(2)若 A→αBβ，且β不能=*>ε，则 FOLLOW(B)=FIRST(β)。 (3)如果 A→αB，则：FOLLOW(B)= FOLLOW(A)。

(4)如果 A→αBβ，且β=*>ε，则：FOLLOW(B)={FIRST(β)-{ε}}∪FOLLOW(A)。 注意：只考虑FIRST(β)中非空元素。

例：求下列表达式文法G[E]的语法变量（即非终结符）的FOLLOW集。 G[E]：E→TE' E'→+TE?|ε T→FT' T'→*FT?|ε F→(E)|i 解：FOLLOW(E) = FIRST( ))∪{#} = { )，# } 联FOLLOW(E')= FOLLOW(E) = { )，# } FOLLOW(T)={FIRST(E')-{ε}}∪FOLLOW(E)∪ FOLLOW(E') = { +， )， #} FOLLOW(T')= FOLLOW(T) = { +， )， #}

FOLLOW(F) ={FIRST(T') -{ε}}∪FOLLOW(T)∪ FOLLOW(T')={ *， +，)， #} 五、SELECT集

对于 G的每个非终结符 A的候选式 A→α， (1)若α不能=*>ε，则SELECT(A→α)=FIRST(α)

(2)若α=*>ε，则SELECT(A→α)={FIRST(α)-{ε}}∪FOLLOW(A)

5.2 LL(1)文法的判别

一、LL(1)文法的定义

LL(1)文法表示了自顶向下方法能够处理的一类文法。第一个 L表示从左向右扫描输入符号串，第二个 L表示生成最左推导，1表示读入一个符号可确定下一步推导。

G是LL(1)文法的充要条件：对于 G的每个非终结符 A的任何两个不同的候选式 A→α|β，满足：SELECT(A→α)∩SELECT(A→β)=φ。其中，α、β不能同时=*>ε。

二、LL(1)文法的判别

1、判别原则：文法Ｇ是 LL(1)文法的充要条件。 2、判别步骤

1）画出各非终结符能否推导出ε的情况表；

2）用定义法或关系图法计算FIRST、FOLLOW集； 3）计算各规则的SELECT集； 4）根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL(1)文法。

三、用关系图计算FIRST集

1、终结符a结点用符号本身标记，非终结符A结点用FIRST(A)标记；

2、对A→αXβ且α=*>ε，则从A到X连一条箭弧(注意：A→aB或A→a已包含在其中)；

3、凡从FIRST(A)结点出发有路径可达到的所有终结符都为FIRST(A)的成员； 4、再根据A能否推导出ε的情况，若能推导出ε，则将ε加入FIRST(A)。

四、用关系图计算FOLLOW集

1、终结符a和#结点用符号本身标记，非终结符A结点用FIRST(A)或FOLLOW (A)标记；

2、从开始符S的FOLLOW(S)到#号连一条箭弧；

3、对规则 A→αBβX且β=*>ε，则从FOLLOW(B)到FIRST(X)连一条箭弧，当X∈ＶT时，则与X相连；

4、对A→αBβ且β=*>ε，则从FOLLOW(B)到FOLLOW(A)连一条箭弧； 5、对每一个FIRST(A)结点，若有规则A→αXβ，且α=*>ε，则从FIRST(A)到FIRST(X)连一条箭弧；

6、凡从FOLLOW(A)结点出发有路径可到达的所有终结符或#，都为FOLLOW(A)的成员；

五、例题

例1：判别下列G[S]是否为LL(1)文法，要求用关系图求FIRST集和FOLLOW集。 G[S]：S → AB|bC A →ε|b B →ε|aD C → b|AD D → aS|c 解：(1)画出非终结符推导ε的情况表，如下图1所示：

(2)用关系图计算各非终结符的FIRST集，如下图2、图3所示：

图1 图2

图3

(3)用关系图求出FOLLOW集，如下图4、图5所示：

图4 图5

4)根据前述三张表计算SELECTT集如下：

(5)判别是否为LL(1)文法

由于：SELECT(S →AB)∩SELECT(S → bC)={b}≠φ，SELECT(C → b)∩SELECT(C → AD)={b}≠φ。故 G[S]不是 LL((1)文法。 例2：LL((1)文法例子。

G[E]：E → T E' E'→ + T E'｜ε T → F T' T'→ * F T'｜ε F → ( E )｜i 解：由于SELECT(E'→+TE')={+} SELECT(E'→ε)={#，)}

SELECT(T'→ * F T')={*} SELECT(T'→ε)={+，#，)} SELECT(F →( E )) ={(} SELECT(F →i)={i} SELECT( E'→+TE')∩SELECT (E'→ε) = {+}∩{#，)} =φ

SELECT (T'→ * F T') ∩SELECT (T'→ε) = {*}∩{+，#，)} =φ SELECT (F →( E ))∩SELECT (F →i) = {(}∩{i} =φ 故 G[E]是 LL((1)文法。

例3：非LL((1)文法例子。对下列文法G[S]作输入串cad的分析。 G[S]：S→cAd A→ab|a

结论：非 LL(1)文法具有不确定性。 不确定性的解决方法：

（1） 采用带回朔的（即确定的）自顶向下分析法：过于复杂，代价很高，实用编译程序几乎不用。

（2）改写文法：将非 LL((1)文法改写为等价的 LL((1)文法。 授课顺序：8

教学目的：让学生掌握非LL(1)文法到LL(1)文法的转换方法、了解递归子程序

分析法的基本原理，掌握预测分析方法及应用。

教学重点：非LL(1)文法到LL(1)文法的转换、预测分析表的构造、预测分析方法的应用

教学难点：非LL(1)文法到LL(1)文法的转换、预测分析方法的应用 授课学时：2学时

教学方式：多媒体讲授 教学内容：

5.3某些非LL(1)向LL(1)文法的等价转换

非LL(1)的文法不能用确定的自顶向下分析法。可通过消除左递归、提取左公共因子的方法将非LL(1)文法转换成LL(1)文法。 一、提取左公共因子

1、左公共因子引发的问题

文法G中有形如： A→ αβ|αγ的规则时，会导致：FIRST(αβ)与 FIRST(αγ )相交，使得：SELECT( A→ αβ)∩ SELECT( A→ αγ) ≠φ，则G必为非LL(1)文法。 2、提取左公共因子的方法

（1）特殊形式：将形如 A → αβ|αγ的规则先提取左公共因子： A → α(β|γ)， 再引进新非终结符A?，改为： A → α A?和 A? →β|γ。 （2）一般形式：将形如 A→αβ1|αβ2|…|αβn的规则改写为：A→αA?和 A'→β1|β2|…|βn。 （3）推广：将形如 A→αβ1|αβ2|…|αβn |γ1|γ2|… | γm的规则改写为：A→αA?|γ1|γ2|… | γm和 A'→β1|β2|…|βn 例1：（显式） G[S]：S→aSb|aS|ε

解：提取左公共因子：S→aS(b|ε)|ε，引进新非终结符A得：S→aSA|ε和A→b|ε 例2：（隐式）G[A]：A→ad|Bc B→aA|bB 解：作变换：A→ad|(aA|bB)c即 A→ad|aAc|bBc， 提取左公共因子得： A→a(d|Ac)|bBc引进新非终结符A?得G?[A]：A→aA?|bBc A?→d|Ac B→aA|bB。 显然，改造后的G?[A]为LL(1)文法。因为：SELECT( A→aA?) ∩ SELECT( A→bBc)=φ， SELECT(A?→d) ∩ SELECT(A?→Ac)=φ， SELECT(B→aA) ∩ SELECT(B→bB)=φ。 3、变换后的压缩

通过提取左公共因子和引进新非终结符，作变换后，可能使原来某些规则无用，必须消除掉。

例3： 对G[S]：S→aSd|Ac A→aS|b

解：通过提取左公共因子和引进新非终结符作等价变换后得：S→aSB|bc B → d|c A→aS|b。此时，A不可达，则以A为左部的规则必须消去。

二、消除左递归

1、左递归引发的问题

（1）无法根据左递归文法进行自顶向下的分析；

（2）产生回溯现象：例如文法G[S]：S→Sa|b对baa进行识别出现的问题； （3）递归分析时死循环，无法编递归子程序。 2、左递归的类型

（1）直接左递归 A → A β

（2）间接左递归 A → B β且 B → A α 其中A、B∈ＶN ， α、β∈Ｖ*。

三、左递归的消除

1、直接左递归的消除方法

将A→Aα|β替换为：A→βA?和 A? →αA?｜ε 例：表达式文法

E → E + T｜T T → T * F｜F F → ( E )｜i

消除直接左递归后为：

E→ T E? E?→ + T E?|ε T→ F T? T?→* F T?｜ε F→

( E )｜i

2、间接左递归的消除

先将间接左递归化为直接左递归，再消除。 例：G[S]：S→Ac|c A→Bb|b B→Sa|a (1)将B的定义代入A产生式得： A→Sab|ab|b (2)将A的定义代入S产生式得： S→Sabc|abc|bc|c

(3)消除直接左递归：S→abcS?|bcS?|cS? S?→abcS?|ε (4)删除“多余的”产生式：A→Sab|ab|b和B→Sa|a (5)结果G[S]： S→abcS?|bcS?|cS? S?→abcS?|ε 3、消除左递归的一般方法

将产生式组A→Aα1|Aα2|…|Aαn|β1|β2|…|βn用产生式组A→β1 B|β2 B |…|βnB，B→α1 B|α2 B |…|αn B|ε代换。其中：B为新变量，相当于A?。 4、消除左递归算法描述

若非终结符排序为A1，A2....An，则：

for(i=1;i<=n;i++) { for(j=1;j<=i-1;j++) {

若Aj所有产生式为Aj→α1|α2...|αk， 则替换形如Ai→Ajβ的产生式中Aj，变为形如Ai→α1 β |α2 β...|αk β的产生式。即化间接左递归为直接左递归。 }消除Ai中一切直接左递归。 }删除无用规则。

例：G[S]：S→Qc |c Q→Rb |b R→Sa |a

解：不妨设非终结符排序为S、Q、R(非终结符排序交换时，得不同文法，但各文法相互等价)。

(1)将S产生式代入R产生式中： R→ Qca|ca|a

(2)将Q产生式代入R产生式中得：R→Rbca|bca|ca|a (3)消除左递归得： R→(bca|ca|a)M和 M→bcaM|ε

(4)删除多余的产生式，结果为G[S]： R→(bca|ca|a)M M→bcaM|ε 同样，按R、Q、S排列可有：S→(abc|bc|c)M M→abcM|ε 和按R、S、Q排列有：Q→(cab|ab|b)M M→cabM|ε

5.4确定的自顶向下分析法

常用的确定的自顶向下分析法有递归下降分析法（递归子程序法）和预测分析方法。

5.4.1递归子程序法

一、基本实现思想

对应文法中的第一个非终结符编写一个递归下过程，每个过程的功能是识别由该非终结符推出的串，当某个非终结符的规则有多条时能够按LL(1)形式唯一确定候选规则进行推导。

二、采用数据结构

递归子程序法对每个过程可能存在直接或间接调用，通常需要在入口时需要保留某些信息，出口时恢复。常用先进后出栈来处理。

三、用递归子程序法构造语法分析程序过程

(1)改造文法：消除二义性、消除左递归、提取左因子； (2)求每个候选式的FIRST集和变量的FOLLOW集；

(3)检查是不是 LL((1)文法。若不是 LL(1)，说明文法的复杂性超过自顶向下方法的分析能力，需要附加新的“信息”。 (4)按照 LL((1)文法画语法图； (5)化简语法图；

(6)按照语法图，为每个非终结符设置一个子程序。 事实上，如果有一个恰当的文法，可以直接根据每个语法变量的产生式设计相应的程序。

四、优缺点分析

1、优点：(1)直观、简单、可读性好；（2)便于扩充。 2、缺点

(1)递归算法速度慢、占用空间多，其实现效率低；

(2)处理能力相对有限，要求文法必须为LL(1)文法，所以通用性差； (3)难以自动生成。

5.4.2 预测分析法

对于LL(1)型文法，可用预测分析法。在使用预测分析法时，必须先将文法化为LL(1)型文法。

一、预测分析器的构造

预测分析器由三部份组成： (1)预测分析表(矩阵)；

(2)先进后出栈：用来存放分析过程的语法符号； (3)预测分析程序。

二、预测分析表

1、预测分析表为一个二维矩阵，其形式为M[A，a]，其中A∈VN ，a∈VT或#。 2、若有产生式A→α，使得a∈SELECT(A→α)，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。

3、对所有没有值的M[A，a]标记为出错。

例：文法G[E]：E→T E? E?→+T E?|ε T→ F T? T?→* F T?｜ε F→ ( E )｜i

解：计算G[E]的SELECT集：

SELECT(E→ T E?)={(，i} SELECT(E?→ + T E?)={+} SELECT(E?→ε)={#，)} SELECT(T→ F T?)={(，i} SELECT(T?→* F T?)={*} SELECT(T?→ε)={+，#，)} SELECT(F→( E ))={(} SELECT(F→i)={i}

根据SELECT集构造G[E]的预测分析矩阵M[X，a]如下：

四、预测分析程序

1、一些符号的约定

#：句子结束符；S：文法开始符；a：当前输入符号a，输入指针指向的符号；X：工作栈栈顶符号。 2、算法描述

#，S进栈 ; //初始化工作 do{

X=当前栈顶符号;a=当前输入符号； if (X∈ＶT∪{#}) {if (X==a)

{if (X ! =#) {将X弹出，且前移输入指针}} else error() }

else {

if (M[X，a]==Y1Y2…Yk )

{将X弹出;依次Yk…Y2Y1将压入栈;} else error()}; }while( X ! =#);

3、例：根据上例中G[E]的预测分析矩阵M[X，a]，对串w=i+i*i进行分析。

解：对输入串w=i+i*i#的分析过程如下表所示（注意：规则右部以逆序入栈）：

课堂作业：对输入串w=i*i+i*i#作分析。

作业：教材P99-101的1、2、4题，6题的（1）（2）（3）小题。

授课顺序：9

教学目的：让学生了解自底向上优先分析的基本思想，掌握优先关系、简单优

先文法的定义、简单优先分析法、直观算符优先分析法、算符优先文法的定义。

教学重点：优先关系表的构造、直观算符优先分析法的应用、算符优先文法的

定义

教学难点：优先关系表的构造、直观算符优先分析法的应用 授课学时：2学时

教学方式：多媒体讲授 教学内容：

第六章 自底向上优先分析法

6.1概述

一、知识回顾

1、最左推导(Left-most Derive)：每次推导都施加在句型的最左边的语法变量上。与最右归约对应。

2、最右推导(Right-most Derive)：每次推导都施加在句型的最右边的语法变量上。与最左归约（规范归约）对应，得规范句型。

3、令G[S]是一文法，αβδ是文法G的一个句型，如果有：S =*> αAδ，且A =+>β，则称β是句型αβδ相对于非终结符A的短语，如有A?β，则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语(也叫简单短语) 。

4、一个句型的最左直接短语称为该句型的句柄。

注意： 作为短语的β必须是需要分析的句型αβδ的一部分。 5、规范归约：设α为文法 G的句子，如果： (1) α=αn<=αn-1<=…<=α2<=α1=Ｓ；

(2)对每个i(1≤i≤n)，αi-1是将句型αi中的句柄归约后得到的句型； 则称由规范归约组成的序列 αn，…，α1为α的规范归约序列。 例子：一个简单的归约过程示例。设文法为G[S]： S→aAcBe A→Ab|b B→d 解：对句子abbcde的分析：

二、自底向上分析

1、思想：从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。

2、核心：寻找句型中的“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。

6.2 简单优先分析法

简单优先分析法的实现思想：按所有文法符号(包括非终结符和终结符)之间的优先关系来确定句柄。 一、优先关系

X≡Y：表示X和Y的优先关系相等； X≮Y：表示X比Y的优先性小； X≯Y：表示X比Y的优先性大。 1、优先关系的定义

X≡Y：当且仅当G中存在规则A→XY…。即XY并列出现。 X≮Y：当且仅当G中存在规则A→…XB…且B=+>Y…。即X与非终结符B并列（位于最前的Y经过至少一步归约后得到的B）。

X≯Y：当且仅当G中存在规则A→…BD…且B=+>…X和D=*>Y…。即非终结符B与D并列（位于最后的X经过至少一步归约后得到B，位于最前的Y经过0步或多步归约后得到D）。

2、例：G[S]：S→bAb A→(B|a B→Aa) 文法符号间优先关系如下：

≡： 由bA有b≡A，由Ab有A≡b，由(B有(≡B，由Aa有A≡a，由a)有a≡)； ≮： 因为 A?(B?(Aa)?(Ba)?…，A?(B?(Aa)?(aa)?…，A?a， 故由bA有b≮(，b≮a；因为 B?Aa)?(Ba)?(Aa) a)?…，B? Aa)?aa)，故由(B有(≮A，(≮(，(≮a；

≯： 因为 A?(B?(Aa)?(Ba)?…，A?(B?(Aa)?(aa)?…，A?a，故由Ab有B≯b，)≯b, a≯b；故由Aa有B≯a，a≯a，)≯a。

注意：对于符号S和#作特殊处理，定义#优先级≮所有与之相邻符号。所有与之相邻符号优先级≯#。

引入产生式S?→#S#来判断与#相邻符号与#的优先关系，且约定#≡#。

对前例：由#S有#≮S；由S?bAb和#S有#≮b；由S#有S≯#；由S?bAb和S#有b≯# 综上所述得如下优先关系矩阵：

二、简单优先文法的定义

(1)任意两符号间最多只有一种优先关系成立； (2)在文法中任意两产生式没有相同的右部。

三、简单优先分析法步骤

(1)将输入符号串a1a2a3…an#依次入栈，直到栈顶符号优先级高于下一个待输入符。 (2)以栈顶符号ai为句柄尾，往下找句柄头ak（当ak-1≮ak时，终止查找）， 并将句柄归约为一个非终结符，将句柄出栈，非终结符入栈；若无句柄可归约则报错。 (3)重复（1）和（2）。

(4)当栈中只剩S时，分析成功，否则报错。

课堂练习：根据前例对输入串b（aa）b#和b（aa）#用简单优先分析法进行分析。

四、简单优先分析法优缺点

准确、规范，分析效率低，实用价值不大。

6.3 算符优先分析法

6.3.1直观算符优先分析法

一、直观算符优先分析法中优先级和结合性的确定

1、算符优先文法只考虑算符(广义为终结符)之间的优先关系。 2、例G[E]：E→E+E|E*E|i， 对3+4*5#分析的过程如下：

3+4*5?E+4*5?E+E*5?E+E*E?E+E?E

思考：为何不将E+E归约成E?

关键：在于如何确定算符间的优先级和结合性。

3、直观算符优先分析法中优先级和结合性的确定方法：人为指定。

例：对文法E→E+E|E-E|E*E|E/E|E^E|(E) |i，我们可指定优先级和结合性如下： (1) 作运算对象的终结符i优先性最高； (2) ^右结合，且高于其它运算符(2^3^(2)，有：^≮^ , ^≯其它运算符，其它运算符≮^ ; (3) *，/高于+,-且左结合,有*≯*,*≯/,*≯+,*≯-, /≯*,/≯/,/≯+,/≯-,，+≯-,+≯+,-≯+,-≯-…

(4)括号的优先性大于括号外运算符，小于括号内运算符，内括号优先性大于外括号； (5) 对于#可#≮所有与之相邻符号；所有与之相邻符号优先级≯#。引入产生式E?→#E#来判断与之相邻符号。

对G[E?]：E?→#E# E→E+E|E-E|E*E|E/E|E^E|(E) |i有：

二、算符优先算法

设置两个工作栈：一个是用来寄存运算符的OPTR，另一个为用来寄存操作数或结果的OPND。算法描述如下：

(1)首先置操作数栈OPND为空，将#入OPTR栈。

(2)依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转[3]。

(3)查算符优先关系表，将当前读入的运算符θ2与OPTR栈顶元素θ1进行比较， 若 θ1<θ2，则：θ2进栈，转(2)；若 θ1＝θ2 ,如θ2为#，则分析成功；否则，OPTR栈顶元素θ1出栈，并转（（3）；若θ1＞θ2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b (t为运算符)，并将结果r存 入栈OPND后转（（2）。若θ1和θ2之间无优先关系，则报错。

例：根据前例文法，对5*(1+(4)作直观算符优先分析，其过程如下：

6.3.2算符优先文法

如果文法G=（ VN，VT，P，S）中不存在形如 A→…BC…的产生式，其中B、C为非终结符，则称之为算符文法(OG —operator Grammar)。即如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。 一、算符间的优先关系

设G=（VN，VT，P，S）为OG，则定义:

?a≡b A→…ab…∈P或者 A→…aBb…∈P

a≮ A→…aB…?b∈P且(B=+>b…或者B=+>Cb…) a≯ A→…Bb…?b∈P且(B=+>…a或者B=+>…aC)

二、算符优先文法

设G=（V，T，P，S）为OG，如果 a,b?∈VT, a≡b,a≮b,a≯b至多有一个成立，则称之为算符优先文法(OPG —Operator Precedence Grammar)。

在无ε产生式的算符文法Ｇ中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法。 授课顺序：10

教学目的：让学生掌握算符优先关系表的构造、算符优先分析算法、优先函数

的计算，了解算符优先分析法的局限性。

教学重点：算符优先关系表的构造、算符优先分析法的应用、优先函数的计算 教学难点：算符优先关系表的构造、算符优先分析法的应用、优先函数的计算 授课学时：2学时

教学方式：多媒体讲授 教学内容：

6.3.3算符优先关系表的构造

一、由定义直接构造优先矩阵 对语法变量A定义：

1、FIRSTVT(A) ={b| A?+b…或者 A?+Cb…} 2、LASTVT(A) ={b|A?+…b或者A?+…bC}

则对产生式A→X1X2…Xn按如下方法构造各文法符号对之间的优先关系后填入算符优先关系表：

(1)如果XiXi+1∈ VTVT 则： Xi≡Xi+1

(2)如果XiXi+1Xi+2∈VTVNVT 则：Xi≡Xi+2

(3)如果XiXi+1∈VTVN 则： a?∈FIRSTVT(Xi+(1)，Xi≮a (4)如果XiXi+1∈VNVT 则：a?∈LASTVT(Xi)， a≯Xi+1

例：文法G[E?]： E?→#E# E→E+T|T T→T*F|F F→P^F|P P→(E) |i,则求出非终结符的FIRSTVT、 LASTVT集：

现对形如A→…aB…的规则根据FIRSTVT集求≮关系，对形如A→…Bb…的规则根据LASTVT集求≯关系，如下表：

由定义直接求出前例的优先矩阵为 ：

二、用算法构造优先矩阵

1、优先矩阵的构造算法基于两条原则

(1)若有规则A→a…或A→Ba…,则a∈FIRSTVT(A) ;

(2)若a∈FIRSTVT(B)且有规则A→B…,则a∈FIRSTVT(A) ; 2、求FIRSTVT集的算法步骤

先设立一个布尔数组F[A,a]，其值为真时，当且仅当a∈FIRSTVT(A)，则：

第1步：按原则(1)对每个数组元素F[A,a]置初值，并对F[A,a]初值为真的符号对(A,a)入栈；

第2步：处理栈。当栈不空时，弹出栈项元素(B,a)，再按原则(2)，对形如A→B…的

规则若有F[A,a]为假，则使其变为真，再让(A,a)入栈； 第3步：重复至栈空为止。

3、求FIRSTVT集的算法描述

void insert(A,a) { if !F[A,a] then

{ F[A,a]=1; push(A,a) to stack; } } void main()

{ for (每一个非终结符A和终结符a) F[A,a]=0;

for (每一个形如A→a…或A→Ba…的规则) insert(A,a) ; while (stack不空)

{ op(B,a) ; for(每一个形如A→B…的规则) insert(A,a) ; } }

对前例G[E?]：E?→#E# E→E+T|T T→T*F|F F→P^F|P P→(E) |i 对各非终结符第一次扫描规则后，栈初值如下：

(6) (p,i) (5) (p,() (4) (F,^) (3) (T,*) (2) (E,+) (1) (E?,#)

对栈项(6) (p,i)，由规则 F→P,T→F ,E→T，使(6)依次变为：(F,i) ,(T,i) ,(E,i)。当(E,i)出栈后，无入栈项，此时栈顶为：(5) (p,()。 同理，可得下述栈项：(4) (F,^)、(3) (T,*)、(2) (E,+)、(1) (E?,#)。最后，当(E?,#)出栈后，无入栈项，栈为空。 4、根据算法求FIRSTVT集

凡在栈中出现过的(A,a)，其 F[A,a]值必为1。根据各个A的F[A,a]值，即可求出FIRSTVT(A)。对前例，有：

5、由关系图求FIRSTVT集 （1）图中结点为FIRSTVT(A)和a；

（2）对形如A→a…或A→Ba…的规则,从FIRSTVT(A)连弧到a； （3）对形如A→B…的规则,从FIRSTVT(A)连弧到FIRSTVT(B)；

（4）凡是从FIRSTVT(A)经所有路径可达到a，都有a∈FIRSTVT(A) 。 对前例按关系图求出各非终结符的FIRSTVT如下：

用类似方法求出各非终结符的LASTVT集。 6、构造优先矩阵的算法

void table()

{ for (每个规则X1X2…Xn)?A for (k=1;k< SPAN>

{ if (XkXk+1∈VTVT) Xi≡Xi+1;

if (k && (XkXk+1Xk+2∈VTVNVT) Xk≡Xk+2;

if ( XkXk+1∈VTVN )

for (FIRSTVT(Xk+(1)中每个b) Xk≮b; if ( XkXk+1∈VN VT)

for (LASTVT(Xk+(1)中每个a) a≯Xk+1; } }

用算法求出优先矩阵为 ：

6.3.4 算符优先分析

算符优先分析和规范归约的核心均为寻找句柄。规范归约的句柄是“最

左直接短语”。算符优先分析的句柄是“最左素短语”。

一、素短语与最左素短语 1、什么是素短语？ Ｓ=*> αＡβ and A=+>γ，γ至少含一个终结符，且不含更小的含终结符的

短语，则称γ是句型αγβ的相对于变量A的素短语。句型的至少含一个终结符且不含其它素短语的短语。

最左边的素短语称为最左素短语。 2、例： E→T+E|T T→T*F|F F→(E) |id

解：句型 T+T*F+i的短语有：T*F，i，T*F+i, T+T*F+i;其中的素短语

为：T*F和 i;

3、T*F为最左素短语，是被归约的对象。

课堂作业：按照文法E→E+E|E*E|(E) |id，求i+E*i+i的短语和素短语。 解：

句型i+E*i+i的短语：i，E*i,i, i,i+E*i和i+E*i+i;其中的素短语为：i, i, i。 3、最左素短语总结

设句型的一般形式为#N1a1 N2a2… Nnan #,其中：

Ni∈VN∪{ε},ai∈VT，则它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1… Njaj Nj+1， 其中： ai-1≮ai, ai≡ai+1≡…≡aj-1≡aj，aj≯aj+1。

二、算符优先分析法的实现 1、分析算法描述

设单元a中存放当前输入符，S为一个符号栈，则： (1)将当前输入符存放到a中，将#入符号栈。

(2)将栈顶第一个终结符b与a比较。如果b≡a，而 b== #且栈中只剩一

个非终结符时，则成功；否则a入栈；如果b≮a,则a入栈；如果b≯a,在栈顶寻找最左素短

语，并将最左素短语归约为一个非终结符；如果文法中找不到相应规则，则出错；

(3)重复(2)至成功或失败。

2、例文法G[E']：E'→#E# E→E+T|T T→T*F|F F→P^F|P P→(E)|i，其优

先矩阵为：

对句子i+i作规范归约和算符优先分析的语法树比较：

对串i+i#规范归约的过程如下： 对串i+i#算符优先分析的过程

如下：

现取i分别为3、2、4，则有串3+2*4#，对该串进行算符优先分析过程如下：

6.3.5 优先函数

2(n+1) )。

用优先函数代替优先矩阵可节约存储空间（由(n+1) (n+1)减少到

二、优先函数的定义

优先函数用值为整数的两个函数f和g来表示，其中f和g满足如下条

件：

若a≡b,则令f(a) =g(b)； 若a≮ b,则令f(a) < SPAN>； 若a≯ b,则令

f(a) >g(b)。

三、优先函数的构造

1、由定义直接构造(Floyed算法)

根据各终结符对的优先关系，构造f和g步骤如下：

第1步：对终结符a(含#)，令f(a) =g(a) =1(或其它常整数)。再对优先关

系矩阵逐行扫描,重复2-4步。

第2步：若a≯b,而f(a) <=g(b)，则令f(a) =g(b) +1； 第3步：若a≮b,而f(a) >=g(b)，则令g(b) =f(a) +1；

第4步：若a ≡ b,而f(a) ≠g(b)，则令min{g(b) ,f(a) }=max{g(b) ,f(a) }； 第5步： 重复2-4步，直到过程收敛。

若对优先关系矩阵逐行扫描，扫描矩阵一遍相当于进行一次迭代。重复2-4

步过程中出现了大于2n的值，表明该优先文法不存大算符优先函数。

2、例子

对前例的表达式文法，根据优先矩阵，其优先函数的计算过程如下： （1）扫描第一行：

+≯+, f( + ) =g( + ) +1=2; +≮*, g( * ) =f( + ) +1=3; +≮^, g( ^ ) =f( + ) +1=3; +≮i, g( i ) =f( + ) +1=3; +≮( , g( ( ) =f( + ) +1=3; +≯) ,满足 f( + ) >g( ) ) ; +≯#,满足 f( + ) > g( # ) ; （2）扫描第二行：

*≯+, f( * ) =g( + ) +1=2; *≯*, f( * ) =g( * ) +1=4; *≮^, g( ^ ) =f( * ) +1=5; *≮i, g( i ) =f( * ) +1=5; *≮( , g( ( ) =f( * ) +1=5; *≯) ,满足 f( * ) > g( ) ) ; *≯#,满足 f( * ) > g( # ) ; （3）扫描第三行： ^≯*, f( ^ ) =g( * ) +1=4;

（4）扫描第四行： i≯^, f( i ) =g( ^ ) +1=6; （5）扫描第五行： (≮ +, g( + ) = f( ( ) +1=2; （6）扫描第六行： ) ≯^, f( ) ) =g( ^ ) +1=6;

第一遍扫描完关系矩阵后，将各f、g函数的最大值填入下表。再用相同

方法处理第二遍、第三遍…扫描，直到各f、g函数的最大值不再变化（即为所求）才终止扫描。

注意：实际迭代过程中，每次只需考虑最新变化了的函数。

3、由关系图构造优先函数

根据优先矩阵按如下步骤构造关系图：

第1步：对所有终结符a(含#)，用带和下标的fa 和ga作结点，构造2n个

结点；

第2步：若a≯b或 a≡b,则从fa连弧到gb；若a≮b或 a≡b,则从gb连弧到

fa；

第3步：从每一个结点出发所能到达的结点个数（含本身），即为该结点对

应的优先函数值。

第4步：对优先函数按优先矩阵检查一遍，若不满足优先矩阵中优先关系，

则关系图中存在回路，说明不存在优先函数。

例1：对下面优先矩阵利用关系图求优先函数：

优先矩阵 优先函数

优先关系图

例2：对下面优先矩阵利用关系图求优先函数。

优先矩阵 优先函数 优先关系图

该例中由于优先函数值都相等，对应优先关系为： a≡a、a≡b、b≡a、b ≡

b,显然不满足优先矩阵中优先关系，即关系图中存在回路，所以优先矩阵不存在优先函数。

四、优先函数和优先矩阵的关系

1、一个优先关系矩阵对应的优先函数不唯一（各函数值加上同一常数后，

优先关系不变）；

2、所表示的优先关系唯一的矩阵不一定存在优先函数。

五、优先函数的缺点

当两个终结符对之间无优先关系时，优先矩阵可以将相应元素置出错信

息，而使用优先函数却无法识别这种情况，不能准确指出出错位置。

6.3.6算符优先分析法的局限性

一、优点

效率高，(原因，只考虑终结符之间的优先关系确定句柄，而与非终结符无关)。

二、缺点

由于去掉了单非终结符之间的归约(如：T→F)，有可能将错误的句子识别

为正确的。

例：文法G[S]： S→S;D|D D→D(T) |H H→a|(S) T→T+S|S 要求现对给定串(a+a) #进行算符优先分析。

解：其优先矩阵和对给定串(a+a) #的分析过程如下所示：

优先矩阵 对给定串(a+a) #

的分析过程

可见用算符优先分析法对串(a+a) #能分析成功，但(a+a) #不是文法G[S]

的句子。这就是由于去掉了单非终结符之间的归约所造成的。

三、适用范围

表达式的语法分析。

作业：教材P122的1、2、3、4题

授课顺序：11 教学目的：让学生了解LR分析基本思想，掌握可归前缀和子前缀的计算方法及

LR(0)分析方法。

教学重点：可归前缀和子前缀的计算方法、LR(0)项目集规范族和分析表的构造、

LR(0)分析方法的应用

教学难点：可归前缀和子前缀的计算方法、LR(0)项目集规范族和分析表的构造、

LR(0)分析方法的应用 授课学时：2学时

教学方式：多媒体讲授 教学内容：

第七章 LR分析法 7.1 LR(Left-Right)分析概述

一、算符优先分析法存在的问题

强调算符之间的优先关系的唯一性，这使得它的适应面比较窄；算法在

发现最左素短语的尾时，需要返回来寻找对应的最左素短语头。

二、LR(k)分析法

L：从左到右扫描输入符号， R：最右推导对应的最左归约,

k：超前读入k个符号，用以确定归约所用的规则。

三、LR分析器工作示意图

四、LR分析表

LR分析表包括action[s,a]、goto[s,X]表两部分，LR(0)、SLR(1)、LR(1)、

LALR (1)将以不同的原则构造这张分析表。构造表时约定：用sn表示将符号a、状态n压入栈；用rn表示用第n个产生式进行归约。

7.2 LR(0)分析法

一、引言

LR(0)分析表构造的思想和方法是构造其他LR分析表的基础。

例:G[S]:S→aAcBe[1] A→Ab[2] A→b[3] B→d[4]

(S'→S[0])

对句子abbcde分析过程如下:

ab[3]b[2]cd[4]e[1]?aAb[2]cd[4]e[1]?aAcd[4]e[1]?aAcBe[1]?S[0]?S' 其中：ab[3],aAb[2],aAcd[4],aAcBe[1]和S[0]称为可归前缀（即规范句型中每

步归约前句型的前部分串）。

可归前缀的前缀称活前缀。如：ab的活前缀有： ε、a、ab。

二、规范句型活前缀

1、活前缀和可归前缀的形式定义

若S?=*>αAγ=>αβγ是G的拓广文法G?的一个规范推导,则称αβ为可归前缀;

若有串W是αβ的前缀，则称W是G的一个活前缀（S?为文法拓广后的开始符，它只出现

在规则左部）。可归前缀是包含句柄的活前缀。

2、说明

（1）LR分析时，把αβ的前缀W列出在符号栈中，一旦出现αβ即说明句

柄形成，则用A→β归约。

（2）规范规约所得到的规范句型的活前缀是出现在分析栈中的符号串，所以，活前缀中不会出现句柄之后的任何字符。

三、识别活前缀的有穷自动机

例:G[S]:S→aAcBe[1] A→Ab[2] A→b[3] B→d[4]

(S'→S[0])

对句子abbcde,其可归前缀为：ab[3],aAb[2],aAcd[4],aAcBe[1],S[0]

对它们分别构造有穷自动机，然后，通过加入一开始状态X和一些ε

弧，将各可归前缀的有穷自动机合并成一个有穷自动机NFA。其中由S[0]得到的终态称为句子识别状态，用*标记。

上图是通过一个句子(abbcde)的归约过程直观的看出其活前缀和可归前

缀，然后构造其NFA。进一步将其确定化为DFA如下：

思考： 如何求一个文法的所有可归前缀？

四、求可归前缀的一般算法 1、定义

设文法G是一个2型文法，对于非终结符A，定义集合

LC(A)={α|S?=*>αAβ,α∈V*, β∈VT* }。LC(A)即A左边所出现的符号串集。

显然，LC(A)为所有不包括句柄的活前缀。若有产生式A→γ,即LC(A).γ

为一可归前缀。

习惯上将LC(A)写成[A]。 2、推论

若文法G中有产生式B→αAβ,则有LC(B).αLC(A) 证：S?=*>δBγ=>δαAβγ，显然有上推论成立。 3、求可归前缀的一般方法

利用此推论即可列出正规式方程组，求得所有的活前缀；再利用文法规

则和所求得的活前缀，即可求得可归前缀：

例1：对文法G[S']:S'→S S→aAcBe A→Ab A→b B→d,求所

有可归前缀。.

解：列方程组如右：[S']= ε [S]=[S']ε [A]=[S]a|[A]ε

[B]=[S]aAc

可解得： [S']= ε [S]= ε [A]=a [B]=aAc

4、在LR(0)方法中，含句柄在内的活前缀计算方法 LR（0）C(A→β) = LC(A).{β}

对前例：LR（0）C(S?→S) = S LR（0）C(S→aAcBe) = aAcBe LR（0）C(A→b) = ab LR（0）C(A→Ab) = aAb LR（0）C(B→d) = aAcd 即所求可归前缀为：

S , aAcBe , aAb , ab , aAcd

例2：对文法G[S?]:S?→E E→aA E→bB A→cA A→d B →cB

B→d ,求所有可归前缀和活前缀。

解：列方程组如右： [S']= ε [E]=[S']ε [A]=[E]a|[A]c [B]=[E]b

| [B]c

可解得： [S']= ε [E]= ε [A]=a|[A]c=a|(a|[A]c)c=…=a(ε|c|cc|…)=ac* [B]=b|[B]c=b|(b|[B]c)c=…=b(ε|c|cc|…)=bc*

则所求可归前缀有：LR（0）C(S?→E) = E LR（0）C(E→aA) =

aA

LR（0）C(E→bB) =bB LR（0）C(A→cA) =ac*cA LR（0）C(A→d) =ac*d LR（0）C(B→cB) =bc*cB LR（0）C(B→d) = bc*d 即S,aAcBe,aAb,ab,aAcd。

根据可归前缀构造文法对应NFA，再确定化为DFA：

五、LR(0)分析表的构造

以上方法从理论角度讲很严格，但实现复杂。实际中常用构造项目集规

范族的方法。

1、LR(0)项目

在文法G中每个产生式的右部适当位置添加一个圆点构成项目。圆点左

边代表该用产生式归约时句柄中已识别过的部份，右边为未识别过的部份。

例：产生式S→aAcBe对应的6个项目是 [0]S→.aAcBe [1]S→a.AcBe

[2]S→aA.cBe [3]S→aAc.Be [4]S→aAcB.e [5]S→aAcBe.。特别的，对A→ε有项目为 A→.。

2、项目的分类

移进项目：形如A→α.aβ；待约项目：形如A→α.Bβ；归约项目：形如

A→αBβ.；接受项目：形如S'→α.。

3、项目集规范族

项目的集合称项目集。识别活前缀的DFA项目集(状态)的全体称项目

集规范族。

4、项目集的闭包（Closure）求法： （1）I的项目均在CLOSURE(I)中；

（2）若A→α.Bβ∈ CLOSURE(I)，则每条形如 B→.γ的项目也∈

CLOSURE(I)；

（3）重复（2）直到CLOSURE(I)中不出现新项目为止。 5、后继项目和核

A→α.Xβ的后继项目是A→αX.β。新状态的初始项目称为核。所有圆点

不在规则右部最左位置(S?→.S除外)的项目都为核。

6、闭包之间的转移

go(I,X)=CLOSURE(J)={A→αX.β| A→α.Xβ∈I}，其中J为I状态中圆点

从X前移到X后形成的项目集状态。

状态转移的计算：确定在某状态遇到一个文法符号后的状态转移目标，

如图所示：

7、计算LR(0)项目集规范族Ｃ（即分析器状态集合）的算法 LR0FUNC( )

{ C = {closure({ S'→.S})}; While ( C中有新项目出现 ) { for?I∈C，??X∈ VN∪VT

if（go(I,X)≠Φ 且 C?go(I,X)） C=C∪go(I,X) }

例：文法G[S']:S'→E[0] E→aA[1] E→bB[2] A→cA[3] A→d[4] B→cB[5]

B→d[6],其规范项目集族构造如下：

8、LR(0)分析表的构造算法

设G?的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应的分析

器状态(即相应的DFA状态)。则：

（1）置0为开始状态； （2）对Ii∈C：

if (A→α.aβ∈Ii且go(Ii,a)=Ij ) action[i,a]=sj ; if (A→α.Bβ∈Ii且go(Ii,B)=Ij ) goto[i,B]=j ;

if (A→α.∈Ii ) for??a∈VT∪{#} do action[i,a]=rj ; if (S'→S.∈Ii ) action[i,#]=acc;

（3）所有空格置 error。

前例的LR（0）分析表如下：

六、LR(0)分析算法 1、算法描述

（1）置输入指针 ip指向输入串的第一个符号；令 s是栈顶状态， a

是 ip所指向的符号;将#压入符号栈，将开始状态0压入状态栈；

（2）重复执行如下过程： if（action[s,a]=sj）

{ 把符号a入符号栈，把状态j入状态栈； 使 ip指向下一个输入符号。 } else if（action[s,a]=rj）

{ 从栈顶弹出第j条规则右部串长|β|个符号；

把归约得到的非终结符A压入符号栈；将goto[s,A]的值j压入状态栈； 并输出规则 A→β。

} else if（action[s,a]=acc） return； else error()； }

2、例子

对文法G[S']:S'→E[0] E→aA[1] E→bB[2] A→cA[3] A→d[4] B→cB[5]

B→d[6]。对输入串bccd#分析如下：

七、LR（0）文法 1、冲突定义

如果 I中至少含两个归约项目，则称 I有归约—归约冲突

（Reduce/Reduce Conflict）。如果 I中既含归约项目，又含移进项目，则称 I有移进—归约冲突（Shift/Reduce Conflict）。

如果 I既没有归约—归约冲突，又没有移进—归约冲突，则称 I是相

容的(Consistent)，否则称 I是不相容的。

2、LR（0）文法定义

对文法G，如果?I∈C,都是相容的，则称G为LR(0)文法。

授课顺序：12

教学目的：让学生掌握SLR(1)分析法和LR(1)分析法。

教学重点：SLR(1)分析表的构造、LR(1)项目集规范族和分析表的构造、SLR(1)

和LR(1)分析方法的应用

教学难点：LR(1)分析表的构造、LR(1)项目集规范族和分析表的构造、SLR(1)

和LR(1)分析方法的应用 授课学时：2学时

教学方式：多媒体讲授 教学内容：

7.3 SLR(1)分析法

一、LR(0)分析存在的问题

例如教材P137的实型变量说明文法有移进归约冲突，不能用LR(0)分

析。再如下例也不能用LR（0）分析。

G[S?]：0)S? →S 1)S →A 2)S →B 3)A →aAc 4)A →a 5)B →bBd 6)B →b

二、解决方法

对含有移进—归约和归约—归约冲突的项目集：I={X→α.bβ，A → γ.，

B→δ. }，若所有含有A和B的句型中，满足：FOLLOW(A)∩FOLLOW(B)=Φ且FOLLOW (A)∩{b}=FOLLOW(B)∩{b} = Φ，则在状态I中面临输入符a的动作可由下面规定决策：

1、若a=b，则移进；

2、 若a∈FOLLOW(A)，则用A → γ.归约，若a∈FOLLOW(B)，则用

B→δ.归约;

3、此外报错。

类似，可推出含多个移进项目和归约项目的一般情况。能用上述方法解决冲突的文法称为SLR（1）文法。

三、SLR(1)分析表的构造算法 1、算法描述

设G?的LR(0)项目集规范族：{I0,I1,…,In}用i表示闭包Ii对应的分析

器状态(即相应的DFA状态)

（1）0为开始状态 （2）对Ii∈C：

if（A→α.aβ∈Ii且 go(Ii,a)=Ij）action[i,a]=sj ; if（A→α.Bβ∈Ii且 go(Ii,B)=Ij）goto[i,B]=j ; if

授课顺序：15

教学目的：让学生了解符号表的作用和地位、符号的主要属性及作用、符号表

的组织和管理，掌握目标程序运行时数据空间的使用和管理方法和常见的参数传递方法。

教学重点：目标程序运行时数据空间的使用和管理、参数传递方法 教学难点：目标程序运行时数据空间的使用和管理、参数传递方法

授课学时：2学时

教学方式：多媒体讲授

教学内容：

第九章 符号表 9.1 符号的一般结构和功能

一、概述

1、符号表在编译程序中用符号表来存放语言中出现的有关标识符的语

义特征属性信息。

2、在编译的每个阶段都要从符号表中存取不同的属性信息。 3、记录源程序中出现的各种符号的相关属性，为编译提供相应的信息：

地址、类型……

二、符号表的功能

1、收集符号属性

任何一个符号都可能有多种属性。如种类（Kind）、类型（Type）、长度、

作用域、标志（引用/定义）、地址等。

例：int A; 符号A可能有类型(整型)、值两个属性。

例：float B[5]；符号 B可能有类型(数组)、存储地址、长度等属性。 2、作为上下文语义合法性检查的依据

同一个标识符可能在程序的不同地方出现，需要通过符号表将其属性记

录下来，以作语义检查。

例：int a; float *a;

3、作为目标代码生成阶段地址分配的依据

（1）对于语言中的变量，在目码代码生成时要确定其相对位置。 （2）位置由两部份组成：存储所在区和在区中的相对位置。 例：static int i;/*分配在静态区域*/

9.2符号表的主要属性及作用

语言符号可分为保留字符号、操作符符号、标识符符号。程序设计语言

中通用的标识符属性主要有如下几种：

1、符号名

语言中的标识符可能是变量名、函数名、过程名等，常用特定的字符串

来表示。如a, c_df, hello等。为将不同符号名区分开来，常在符号表中给一个唯一的ID(一般就是符号表的入口地址)。

2、符号的类型

符号的数据类型，如整型、实型、字符型、布尔型、数组型等。不同的

类型的符号，其存储格式、在其上可实施的操作运算都可能不同。

3、符号的存储类别 如公共变量、静态变量、寄存器变量、局部变量等。一般用关键字指明，

或根据变量出现在程序中的位置来决定。存储类别是过程语义检查、处理、存储分配的重要依据。还决定了作用域、可视性、生命周期等问题。

4、符号的作用域和可视性

（1）作用域即该变量在程序中起作用的范围，一般由该定义该符号的

位置及存储类别决定。

（2）可视性不仅取决于作用域，对函数、过程来说，还同形参、局部

变量、分程序结构有关。

例：同名变量在函数体内和体外的可视性不同。 { int a;...... { char a;....... { float a;...... .. a .. }

.. a ... }

.. a ... }

为确立符号的作用域和可视性，在符号表属性中可引入 “层次”这一概

念。习惯上，定义最外层为第一层，内层依此类推。

5、符号变量的存储分配信息 （1）静态存储区

a）该存储区单元经定义分配后成为静态单元，在整个语言程序运行过

程中是不可变的。

b）生命周期为整个程序运行期。

c）在编译系统中一般设置一个固定空间作静态存储区。 d）该存储区又分为公共和局部静态区域。 （2）动态存储区：

a）设置该区是为了适应局部变量的生成和消亡。

b）在需要的时候给局部变量分配空间，用完后回收空间。 各符号变量应分配的存储区及在该区中所处具体位置：由其存储类别和

它本身出现的位置和次序来确定。

例:

int a; /* 放公共静态区 */ ......

float b; /* 放公共静态区 */ ......

struct | union A{

int d; /* 放局部静态区 */ float e; /* 放局部静态区 */ ...... } c; /* 放公共静态区 */ ......

相对于C语言上例中变量a、b、c、d、e在符号表中的位置属性如下：

思考：为什么当A定义为结构体时a、b、c、d、e在符号表中的位置

属性不是0、2、0、2、6？

注意：存放任何类型变量的地址都必须是其所需字节数的整数倍处地

址，如 int型 变量首址须为2的整数倍处：0、2、4、…。

6、其它属性

（1）数组的内情向量（首地址、维数、每维的长度）：用于确定数组分

配时所占空间及具体位置。

（2）记录结构的成员信息（ C中用struct，PAS中用record定义）：用

于确定结构型 变量存储分配时所占空间及具体位置。

（3）函数或过程的形参：用于作进程调用时的匹配处理和语义检查。

9.3 符号表的组织

一、符号表的总体组织

符号表的总体组织方式分为三种：

1、按属性完全相同的符号组织在一起，构造出多张表。其特点：有多

个符号表，每个符号表内部符号的属性个数和结构完全相同。对于单个符号管理方便，空间效率高，但从宏观上看，管理复杂。

例:设文法中有三类符号及其所需属性，按这类方法来组织如下：

2、把所有语言中出现的符号都组织在一张表中。其特点：把所有符号

的所有可能属性作为符号表的表项属性，便于集中一致管理，但导致了无用属性空间过多，管理繁杂。

例：对上例中按这类方法来组织如下:

3、上两种方案的折衷：根据符号的相似程度，由设计者自己根据需要

设计成多张表，各表都为定长，且可看成一个多元组，各元组又由若干属性组成，元组间有相同的成员个数和一致的排列，元组间的区分由唯一的一个“关键字栏”决定。

例：上例中表按这类方法可组织为：

二、 符号表项信息的排列方式

符号表中每一项对应着一个多元组。符号表总体上看就是一个多元组

集。符号表项的组织可分为线性组织、排序组织、散列组织等。

1、线性组织

（1） 规定符号表中表项按它的符号被扫描到的先后次序建立。 （2）适于事先确定符号个数且个数不大时。 例：...a...b...d...a...c..可组织为：

2、排序组织

（1） 符号表的表项中按符号的字符代码串的值的升/降序排列。 （2）通常在建立和查找符号项时用二分查找法。

（3）排序表的空间组织和存储开销同于线性表，但运行效率高，算法

也复杂。

3、散列组织

（1）符号表按散列表(hash)的形式进行组织，运行效率高。 （2）关键问题是解决冲突的方法和hash函数的选取。

（3）现代编译系统多采用它，其hash函数一般使用对符号代码的位操

作（如字段迭加、符号代码对折/多折）函数。

三、 关键字域的组织

1、关键字域就是符号本身。

2、采用关键字池的索引 结构，既能保证关键字段的等长，又能减少甚

至消除冗余。

3、索引 结构可用字符数组或字符串实现 ，前者用整数值表示关键字

在字池中的位置下标，后者通过指针指向其在字池中的位置。

四、其它域的组织

1、同类型且等长属性域的组织

表中各符号的该属性值具有相同的类型且等长，则用该长度和类型来定

义该域的类型结构。

(1)可给数据类型编码(码长固定)

(2)表示关系符号之间关系的属性 例:struct c{int a,float b} stv;可表示为

2、同类型但不等长属性域的组织

表中各符号的该属性值可能具有相同类型但长度不同，则另外设置相关

空间来存放该属性值，而在表项的某个域内设置一个指针指向相关另设空间（结构体/联合体变量、多态域）。

例:数组的组织：int a[1][2],b[2][9][1]；