北航编译原理课件

•

•

•

编译的起源：程序设计语言的发展

基本概念

编译过程和编译程序构造

•

编译技术的应用

北京航空航天大学计算机学院

1

机器语言

（机器指令）

面向用户

的语言

面向问题

的语言

汇编语言

低级语言

高级语言

北京航空航天大学计算机学院

2

•

•

低级语言（Low level Language)

–

字位码、机器语言、汇编语言

特点：与特定的机器有关，效率高、灵活，但使用复

杂、繁琐、编写费时、易出错

–

高级语言

-- Fortran、Pascal、C 语言等

–特点：不依赖具体机器，移植性好、便于描述问题处

理过程和算法、易使用、易维护等。

用高级语言编制的程序，计算机不能立即执行，

必须通过一个“翻译程序”加工，转化为与其等价的

机器语言程序，机器才能执行。

这种翻译程序，称之为“编译程序”。

北京航空航天大学计算机学院

3

•

•

源程序

用汇编语言或高级语言编写的程序称为源程序。

目标程序

用目标语言所表示的程序。

目标语言：可以是某种机器的机器语言或汇编语言，

也可以是介于源语言和机器语言之间的“中间语言”，

甚至可以是另一种高级语言。

•

翻译程序

将源程序转换为目标程序的程序称为翻译程序。

它是指各种语言的翻译器，包括汇编程序和编译程序，

是汇编程序、编译程序以及各种变换程序的总称。

北京航空航天大学计算机学院

4

源程序、翻译程序、目标程序三者关系：

源程序

翻译程序

目标程序

OBJECT

PROGRAM

SOURCE

PROGRAM

TRANSLATER

即源程序是翻译程序的输入，目标程序是翻译程序的输出

北京航空航天大学计算机学院

5

•

汇编程序

若源程序用汇编语言书写，经过翻译程序得到用机器语言

表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过

程称为“汇编”(Assemble）

•

编译程序

若源程序是用高级语言书写，经加工后得到目标程序，

这种翻译过程称“编译”（Compile)

汇编程序与编译程序都是翻译程序，主要区别是加工对象的

不同。

北京航空航天大学计算机学院

6

•

•

编译或汇编阶段

编译程序

或汇编程序

源程序

目标程序

输出数据

运行阶段

目标程序

+

运行子程序

输入数据

北京航空航天大学计算机学院

7

•

解释程序（Interpreter）

对源程序进行解释执行的程序。

•

工作过程

源程序

输入数据

输出数据

解释程序

北京航空航天大学计算机学院

8

源程序

编译程序

源程序的中间形式

输入数据

输出数据

解释程序

北京航空航天大学计算机学院

9

编译过程是指将高级语言程序翻译为等价的目标程

序的过程。

习惯上是将编译过程划分为5个基本阶段：

词法分析

语法分析

语义分析、生成中间代码

代码优化

生成目标程序

北京航空航天大学计算机学院

1

0

一、词法分析

任务：分析和识别单词。

源程序是由字符序列构成的，词法分析扫描源程序

(字符串),根据语言的词法规则分析并识别单词，并以某

种编码形式输出 。

•单词：是语言的基本语法单位，一般语言有四大类单词

<

<

<

<

1>语言定义的关键字或保留字（如BEGIN、END、IF）

2>标识符

3>常数

4>分界符（运算符） （如+、-、*、/、;、（、） ……）

北京航空航天大学计算机学院

11

二、语法分析

任务：根据语法规则（即语言的文法），分析并识别出

各种语法成分，如表达式、各种说明、各种语句、

过程、函数等，并进行语法正确性检查。

X1:= ( 2.0 + 0.8 ) * C1

赋值语句的文法 ：

<

<

<

<

赋值语句>→<变量><赋值操作符><表达式>

变量>→<简单标识符>

赋值操作符>→:=

表达式>→ ……

北京航空航天大学计算机学院

1

2

三、语义分析、生成中间代码

任务：对识别出的各种语法成分进行语义分析，

并产生相应的中间代码。

•

•

中间代码：一种介于源语言和目标语言之间的中间语言形式

生成中间代码的目的：

<

<

1> 便于做优化处理；

2> 便于编译程序的移植。

•

中间代码的形式：编译程序设计者可以自己设计，常用的有

四元式、三元式、逆波兰表示等。

北京航空航天大学计算机学院

1

3

四元式（三地址指令）

X1:= ( 2.0 + 0.8 ) * C1

运算符 左运算对象 右运算对象 结果

(1) +

(2) *

(3) :=

2.0

T1

X1

0.8

C1

T2

T1

T2

其中T1和T2为编译程序引入的工作单元

四元式的语义为： 2.0 + 0.8 → T1

T1 * C1 → T2

T2 → X1

这样所生成的四元式与原来的赋值语句在语言的

形式上不同，但语义上等价。

北京航空航天大学计算机学院

1

4

四、代码优化

目的: 是为了得到高质量的目标程序。

例如：前面的四元式中第一个四元式是计算常

量表达式值，该值在编译时就可以算出并存放在工

作单元中，不必生成目标指令来计算，这样四元式

可优化为：

编译时： 2.0 + 0.8 → T1

（

（

1) * T1 C1 T2

2) := X1 T2

北京航空航天大学计算机学院

1

5

五、生成目标程序

由中间代码很容易生成目标程序（地址指令序列）。这

部分工作与机器关系密切 ，所以要根据机器进行。在做这

部分工作时（要注意充分利用累加器），也可以进行优化

处理。

X1:= ( 2.0 + 0.8 ) * C1

注意：在翻译成目标程序的过程中，要切记保持

语义的等价性。

北京航空航天大学计算机学院

1

6

1.3.2 编译程序构造

一、 编译程序的逻辑结构

按逻辑功能不同，可将编译过程划分为五个基本阶段，

与此相对应，我们将实现整个编译过程的编译程序划分为

五个逻辑阶段（即五个逻辑子过程）。

语义分析

生成中间

代码

词法分析 语法分析

程序 程序

代码优化 生成目标

程序 程序

S.P

O.P

北京航空航天大学计算机学院

1

7

在上列五个阶段中都要做两件事：

（1）建表和查表；（2）出错处理；

所以编译程序中都要包括符号表管理和出错处理两部分

符号表管理

在整个编译过程中始终都要贯穿着建表（填表）和查表的工

作。即要及时地把源程序中的信息和编译过程中所产生的信息登

记在表格中，而在随后的编译过程中同时又要不断地查找这些表

格中的信息。

出错处理

规模较大的源程序难免有多种错误，编译程序必须要有出错

处理的功能。即能诊察出错误，并能报告用户错误的性质和位

置，以便用户修改源程序。出错处理能力的大小是衡量编译程

序质量好坏的一个重要指标。

北京航空航天大学计算机学院

1

8

典型的编译程序具有7个逻辑部分

S.P

词法分析程序

语法分析程序

语义分析、生成中间代码

代码优化程序

符

号

表

管

理

出

错

处

理

生成目标程序

O.P

北京航空航天大学计算机学院

1

9

二、 遍（PASS）

遍：对源程序（包括源程序中间形式）从头到尾扫描一次，

并做有关的加工处理 ，生成新的源程序中间形式或目标程序，

通常称之为一遍。

第一遍

第二遍

…

…

S.P

中间形式1

S.P

中间形式2

S.P

C1

C2

O.P

一遍

要注意遍与基本阶段的区别

五个基本阶段：是将源程序翻译为目标程序在逻辑上要完成的

工作。

遍：是指完成上述5个基本阶段的工作，要经过几次扫描处理。

北京航空航天大学计算机学院

2

0

一遍扫描即可完成整个编译工作的称为一遍扫描编译程序

其结构为：

语法成分

语义分析生成

目标程序

语法分析

S.P.

返回分析结果

取单词

返回单词

词法分析

整理目标程序

停机

O.P.

北京航空航天大学计算机学院

2

1

三、前端和后端

根据编译程序各部分功能，将编译程序分成前端和后端。

前端：通常将与源程序有关的编译部分称为前端。

词法分析、语法分析、语义分析、中间代码生成、

代码优化 -------分析部分

特点：与源语言有关

后端：与目标机有关的部分称为后端。

目标程序生成（与目标机有关的优化）

-------综合部分

特点：与目标机有关

北京航空航天大学计算机学院

2

2

源程序：多文件、宏定义和宏替换（调用），包含文件

目标程序：一般为汇编程序或可重定位的机器代码

框架源程序

可重定位机器码

（文件组）

预处理器

源程序

库目标、可重

定位目标文件

连接编辑

编译程序

可重定位机器码

目标程序（汇编）

加载器

汇编程序

可运行的机器代码

可重定位机器码

（Obj文件）

北京航空航天大学计算机学院

2

3

š

š

š

š

š

š

语法制导的结构化编辑器

程序格式化工具

软件分析与测试工具

程序理解工具

高级语言的翻译工具

等等

北京航空航天大学计算机学院

2

4

第二章 文法和语言的概念和表示

•

•

•

•

•

预备知识 - 形式语言基础

文法和语言的定义

若干术语和重要概念

文法的表示：扩充的BNF范式和语法图

文法和语言的分类

北京航空航天大学计算机学院

1

2

.1 预备知识

一、字母表和符号串

字母表： 符号的非空有限集 例：={a，b，c}

符号： 字母表中的元素 例： a，b，c

符号串： 符号的有穷序列 例：a, aa, ac, abc，..

空符号串：无任何符号的符号串(ε)

符号串的形式定义

有字母表，定义：

（

（

（

1）ε是上的符号串；

2）若x是上的符号串，且a ，则ax或xa是上的符号串；

3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。

符号串集合：由符号串构成的集合。

•

通常约定：

–

用英文字母表开头的小写字母和字母表靠近末尾

的大写字母来表示符号

如：a, b, c, d, … , r 和 S, T , U, V , W，X, Y, Z

–

–

用英文字母表靠近末尾的小写字母来表示符号串

如：s, t, u, v, w , x, y, z

用英文字母表开头的大写字母来表示符号串集合

如：A, B, C, D, … , R

北京航空航天大学计算机学院

3

二、符号串和符号串集合的运算

1

.符号串相等：若x、y是集合上的两个符号串，则x＝y

iff（当且仅当）组成x的每一个符号和组成y的每一个符号

依次相等。

2.符号串的长度：x为符号串，其长度|x|等于组成该符

号串的符号个数。

例： x＝STV ， |x|=3

北京航空航天大学计算机学院

4

3

.符号串的联接：若x、y是定义在Σ上的符号串， 且

x＝XY，y＝YX，则x和y的联接 xy＝XYYX也是Σ上的符号

串。

注意：一般xy≠yx，而εx＝xε

4

. 符号串集合的乘积运算：令A、B为符号串集合，

定义 AB＝{ xy |x∈A, y∈B}

例：A＝{s, t}, B = {u,v}, AB= ？

su，sv，tu，tv}

{

因为εx＝xε＝x，所以{ε}A=A {ε} =A

北京航空航天大学计算机学院

5

5

. 符号串集合的幂运算：有符号串集合A，定义

A₀ ={ε}, A₁=A, A₂=AA, A₃=AAA,

… …… A_n＝A_n-1A=AA_n-1 ，n>0

…

6

.符号串集合的闭包运算：设A是符号串集合，定义

A_＋＝A₁ ∪ A₂ ∪ A₃ ∪……∪ A_n ∪……

称为集合A的正闭包。

A_*＝A₀ ∪A_＋

称为集合A的闭包。

例：A={x,y}

A ＝{x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy, ……}

＋

A₁

A₂

A₃

{

ε, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy, ……}

A_* ＝

A₀ A₁

A₂

A₃

北京航空航天大学计算机学院

6

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？

若A为某语言的基本字符集 ( 把字符看作符号）

A＝{a, b, ……z, 0, 1, ……, 9, +, －, ×, _, /, ( , ), =, ……}

B为单词集

（单词是符号串）

B ={begin, end, if, then, else, for, ……,<标识符>,<常量>, ……}

则B  A_* 。

（

把单词看作符号，句子便是符号串）

语言的句子是定义在B上的符号串。

若令C为句子集合，则C  B * , 程序 C

北京航空航天大学计算机学院

7

2

.2文法的非形式讨论

1.什么是文法：文法是对语言结构的定义与描述。即从形式上

用于描述和规定语言结构的称为“文法”（或称为“语法”）。

例：有一句子：“我是大学生” 。这是一个在语法、

语义上都正确的句子，该句子的结构（称为语法结构）是由

它的语法决定的 。在本例中它为“主谓结构”。

如何定义句子的合法性？

•

•

有穷语言

无穷语言

北京航空航天大学计算机学院

8

2.语法规则：我们通过建立一组规则，来描述句子的语法结构。

规定用“::=”表示“由...组成”（或“定义为...”）。

<

句子>::=<主语><谓语>

<

<

<

<

<

<

主语>::=<代词>|<名词>

代词> ::=你|我|他

名词>::= 王民|大学生|工人|英语

谓语>::=<动词><直接宾语>

动词>::=是|学习

直接宾语>::=<代词>|<名词>

北京航空航天大学计算机学院

9

3

. 由规则推导句子：有了一组规则之后，可以按照一定的方式

用它们去推导或产生句子。

推导方法：从一个要识别的符号开始推导，即用相应规则的

右部来替代规则的左部，每次仅用一条规则去进行推导。

<

句子> => <主语><谓语>

<

主语> <谓语> => <代词> <谓语>

…

… ……

这种推导一直进行下去，直到所有带< >的符号都由终结符号

替代为止。

北京航空航天大学计算机学院

1

0

推导方法：从一个要识别的符号

开始推导，即用相应规则的

右部来替代规则的左部，

每次仅用一条规则去进行推导。

<

句子> => <主语><谓语>

=

=

> < 代词><谓语>

> 我<谓语>

=

=

=

=

>我<动词><直接宾语>

>我是<直接宾语>

>我是<名词>

>我是大学生

北京航空航天大学计算机学院

11

例：有一英语句子：The big elephant ate the peanut.

<

句子>::=<主语><谓语>

<

<

<

<

<

<

<

<

主语>::=<冠词><形容词><名词>

冠词> ::=the

形容词>::=big

名词>::=elephant

谓语>::=<动词><宾语>

动词>::=ate

宾语>::=<冠词><名词>

名词> ::=peanut

北京航空航天大学计算机学院

1

2

<

句子> => <主语><谓语>

=

=

=

=

=

=

=

=

=

> <冠词><形容词><名词><谓语>

> the <形容词><名词><谓语>

> the big <名词> <谓语>

> the big elephant <谓语>

> the big elephant <动词><宾语>

> the big elephant ate <宾语>

> the big elephant ate <冠词><名词>

> the big elephant ate the <名词>

> the big elephant ate the peanut

北京航空航天大学计算机学院

1

3

+

上述推导可写成<句子> => the big elephant ate the peanut

说明：

(1) 有若干语法成分同时存在时，我们总是从最左的语法成

分进行推导，这称之为最左推导，类似的有最右推导(还有一般

推导）。

(2) 从一组语法规则可推出不同的句子，如以上规则还可推出

大象吃象”、“大花生吃象”、“大花生吃花生”等句子，

“

它们 在语法上都正确，但在语义上都不正确。

所谓文法是在形式上对句子结构的定义与描述，而未

涉及语义问题。

北京航空航天大学计算机学院

1

4

4

.语法（推导）树：我们用语法（推导）树

来描述一个句子的语法结构。

<

句子>

<

主语>

<谓语>

<

冠词> <形容词> <名词> <动词>

<

宾语>

冠词> <名词>

the peanut

<

The

big

elephant ate

北京航空航天大学计算机学院

1

5

2.3 文法和语言的形式定义

2

.3.1文法的定义

定义1. 文法G=（Vn，Vt，P，Z）

Vn：非终结符号集

Vt：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号） Z∈Vn

规则的定义：

规则是一个有序对(U, x), 通常写为:

U :: x 或U  x ， | U| = 1 |x|  0

北京航空航天大学计算机学院

1

6

例：无符号整数的文法：

G[<无符号整数>]=（Vn，Vt，P，Z）

Vn＝{<无符号整数>,<数字串>, <数字>}

Vt = {0, 1, 2, 3, …… 9}

P = {<无符号整数> →<数字串> ，

<

<

<

<

数字串> → <数字串> <数字>，

数字串> →<数字> ，

数字> →0，

数字> →1，

…

………

<

数字> →9}

Z = <无符号整数>

北京航空航天大学计算机学院

1

7

几点说明：

产生式左边符号构成集合Vn，且Z ∈Vn

有些产生式具有相同的左部，可以合在一起

例：<无符号整数> →<数字串>

<

<

数字串> → <数字串> <数字> | <数字>

数字> →0| 1 | 2 | 3 | …… | 9

给定一个 文法，需给出产生式（规则）集合，并指定识别符号

例：G[<无符号整数>]：

<

<

<

无符号整数> →<数字串>

数字串> → <数字串> <数字> | <数字>

数字> →0| 1 | 2 | 3 | …… | 9

北京航空航天大学计算机学院

1

8

2

.3.2 推导的形式定义

定义2：文法G：v＝xUy，w＝xuy,

其中x、y ∈V^* ，U∈Vn , u ∈V*,

若U :: u∈P，则v w。

G

若x＝y＝ε，有U :: u，则U  u

G

根据文法和推导定义，可推出终结符号串，所谓通过文法

能推出句子来。

北京航空航天大学计算机学院

1

9

例如：G[<无符号整数>]

(4) <数字> →0

(5) <数字> →1

…………

(1) <无符号整数> →<数字串>

(2) <数字串> → <数字串> <数字>

(3) <数字串> → <数字>

(13) <数字> →9

<

无符号整数>==> <数字串> ==> <数字串> <数字>

(1)

(2)

<

1

数字><数字> =₍₄=₎ > 1 <数字>

=

=>

(3)

=

=>

0

(5)

当符号串已没有非终结符号时，推导就必须终止。因为

终结符不可能出现在规则左部，所以将在规则左部出现的符

号称为非终结符号。

北京航空航天大学计算机学院

2

0

定义3：文法G，u , u , u , ……，u ∈V+

0

1

2

n

=

=> ==>

==>

u ==>…… u ＝w

if v= u₀

＋

u

1

2

n

G

G

G

G

则v ==> w

G

例：<无符号整数>==> <数字串> ==> <数字串> <数字>

=

=> <数字><数字> ==>1 <数字>

=

＋

=>1 0

即<无符号整数>==> 10

G

北京航空航天大学计算机学院

2

1

定义4：文法G，有v，w ∈V+

＋

*

if v w , 或v=w，则v => w

=

>

G

G

*

定义5：规范推导：有xUy ==> xuy, 若 y ∈V ,则此推导为规范

t

|

的，记为xUy ==> xuy

直观意义：规范推导＝最右推导

最右推导：若规则右端符号串中有两个以上的非终结符时，先推右边的。

最左推导：若规则右端符号串中有两个以上的非终结符时，先推左边的。

+

若有v = u =|=> u =|=> u =|=>……=|=> u = w, 则 v =|=> w

0

1

2

n

北京航空航天大学计算机学院

2

2

2

.3.3 语言的形式定义

定义6：文法G[Z]

（

（

（

1）句型：x是句型 Z ^* x , 且x∈V* ；

+

2）句子：x是句子 Z  x , 且x∈V * ；

t

+

3）语言：L（G[Z]）={x | x∈V *, Z  x } ；

t

形式语言理论可以证明以下两点：

（

（

1）G →L(G）；

2）L(G) →G1，G2，……，Gn；

已知文法，求语言，通过推导；

已知语言，构造文法，无形式化方法，更多是凭经验。

北京航空航天大学计算机学院

2

3

例：{ ab_na | n≥1},构造其文法

G1[Z]：

Z→aBa,

B→b | bB

G2[Z]：

Z→aBa,

B→b | Bb

定义7. G和G’是两个不同的文法，若L(G) = L(G’) ,

则G和G’为等价文法。

北京航空航天大学计算机学院

2

4

编译感兴趣的问题是:

•

给定句子 x 以及文法 G , 求x  L(G) ?

G

yes

x 算法1

算法2 停机

x L(G) ?



no

出错处理

北京航空航天大学计算机学院

2

5

2

.3.4 递归文法

1

.递归规则：规则右部有与左部相同的符号（非终结符）

对于U::= xUy

若x=ε, 即U::= Uy， 左递归

若y=ε, 即U::= xU， 右递归

若x, y≠ε，即U::= xUy，自嵌入递归

2

.递归文法：文法G，存在U ∈Vn

+

if U==>…U…, 则G为递归文法；

+

if U==>U…, 则G为左递归文法；

+

if U==>…U, 则G为右递归文法。

北京航空航天大学计算机学院

2

6

3

. 递归文法的优点：可用有穷条规则，定义无穷语言

会造成死循环（后面将详细论述）

4

. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析

例：对于前面给出的无符号整数的文法是左递归文法，用13

条规则就可以定义出所有的无符号整数。若不用递归文法，那

将要用多少条规则呢？

<

<

<

无符号整数> →<数字串>

数字串> → <数字串> <数字> | <数字>

数字> →0| 1 | 2 | 3 | …… | 9

北京航空航天大学计算机学院

2

7

2

.3.5 句型的短语、简单短语和句柄

定义8. 给定文法G[Z], w = xuy∈V+，为该文法的句型,

*

＋

若Z ==> xUy, 且U ==>u, 则u是句型w相对于U的短语；

*

若Z ==> xUy, 且U ==>u, 则u是句型w相对于U的简单短语。

其中U ∈V_n，u ∈V+，x , y ∈V^*

直观理解：短语是前面句型中的某个非终结符所能推

出的符号串。

任何句型本身一定是相对于识别符号Z的短语

北京航空航天大学计算机学院

2

8

定义9. 任一句型的最左简单短语称为该句型的句柄。

给定句型找句柄的步骤：

短语

简单短语 句柄

例: 文法G[<无符号整数>], w = <数字串>1

<

无符号整数> => <数字串> => <数字串><数字>

=> <数字串>1

短语：<数字串>1，1 ； 简单短语：1；句柄：1

注意：短语、简单短语是相对于句型而言的，一个句型

可能有多个短语、简单短语，而句柄只能有一个。

北京航空航天大学计算机学院

2

9

Z

2.4 语法树与二义性文法

U

V

2

.4.1 推导与语法（推导）树

a

b c

d

（

1）语法（推导）树：句子( 句型）结构的图示表示法，

它是有向图，由结点和有向边组成。

结点：符号

根结点： 识别符号（非终结符）

中间结点：非终结符

叶结点： 终结符或非终结符

有向边：表示结点间的派生关系

北京航空航天大学计算机学院

3

0

( 2 ) 句型的推导及语法树的生成（自顶向下）

给定G[Z]，句型w：

*

G

可建立推导序列，Z ==> w

可建立语法树，以Z为树根结点，每步推导生成语法树

的一枝，最终可生成句型w的语法树。

注意一个重要事实：文法所能产生的句子，可以

用不同的推导序列（使用产生式顺序不同）将其

推导出来。语法树的生长规律不同，但最终生成的语

法树形状完全相同。某些文法有此性质，而某些文法

不具此性质。

北京航空航天大学计算机学院

3

1

G[<无符号整数>]：

<

<

<

无符号整数> →<数字串>

数字串> →<数字串> <数字> | <数字>

数字> →0 | 1 | 2 | 3 | …… | 9

一般推导：

<

无符号整数>

(1)

数字串>

<

(2)

<

数字串> <数字>

(3)

(4)

<

数字>

0

(5)

1

北京航空航天大学计算机学院

3

2

最左推导：

<

无符号整数>

(1)

数字串>

<

(2)

<

数字串> <数字>

(3)

(5)

<

数字>

0

(4)

1

北京航空航天大学计算机学院

3

3

最右推导

<

无符号整数>

(1)

数字串>

<

(2)

<

数字串> <数字>

(4)

(3)

<

数字>

0

(5)

1

北京航空航天大学计算机学院

3

4

( 3 ) 子树与短语

子树：语法树中的某个结点（子树的根）连同它向下

派生的部分所组成。

某子树的末端结点按自左向右顺序为句型中的符

定理

号串，则该符号串为该句型的相对于该子树根的短语。

只需画出句型的语法树，然后根据子树找短语→

简单短语→句柄。

北京航空航天大学计算机学院

3

5

( 4 ) 树与推导

句型推导过程<==> 该句型语法树的生长过程

由推导构造语法树

1

从识别符号开始，自左向右建立推导序列。

由根结点开始，自上而下建立语法树。

北京航空航天大学计算机学院

3

6

由语法树构造推导

2

自下而上地修剪子树的某些末端结点（短语），直至

把整棵树剪掉（留根），每剪一次对应一次归约。

从句型开始，自右向左地逐步进行归约，建立推导序列。

北京航空航天大学计算机学院

3

7

定义12. 对句型中最左简单短语（句柄）进行的归约称为

规范归约。

定义13. 通过规范推导或规范归约所得到的句型称为规范句型。

句型<数字><数字>不是文法的规范句型，因为：

<

无符号整数>==><数字串>

=

=

=><数字串><数字>

=><数字><数字>

不是规范推导

北京航空航天大学计算机学院

3

8

2

.4.2 文法的二义性

定义14.1 若对于一个文法的某一句子（或句型）

存在两棵不同的语法树，则该文法是二义性文法，

否则是无二义性文法。

换而言之，无二义性文法的句子只有一棵语法树，尽管推

导过程可以不同。

二义性文法举例：

G[E]:

E :：= E+E | E*E | (E) | i

V_n={E}

V_t={ +, * , ( , ) , i }

北京航空航天大学计算机学院

3

9

对于句子S＝i＋i * i ∈ L( G[E] ），存在不同的规

范推导：

(1) E==>E+E==>E+E*E ==>E+E*i ==>E+i*i ==> i＋i * i

(2) E==> E*E ==> E*i ==> E+E*i ==> E+i*i ==> i＋i * i

这两种不同的推导对应了两棵不同的语法树：

E

E

E + E

E * E

i

i

E

i

E

i

E

i

E

i

*

+

北京航空航天大学计算机学院

4

0

定义14.2 若一个文法的某句子存在两个不同的规范推导，则

该文法是二义性的，否则是无二义性的。

(1) E=|=>E+E=|=>E+E*E =|=>E+E*i =|=>E+i*i =|= > i＋i * i

|

|

|

|

|

(2) E==> E*E ==> E*i ==> E+E*i ==> E+i*i ==> i＋i * i

从自底向上的归约过程来看，上例中规范句型

E+E*i 是由i＋i * i通过两步规范归约得到的，但对于同

一个句型E+E* i，它有两个不同的句柄（对应上述两棵

不同的语法树）：i 和E＋E。因此，文法的二义性意味

着句型的句柄不唯一。

北京航空航天大学计算机学院

4

1

E

E

E + E

E * E

E

E

i

*

i

E + E

句柄：i

句柄：E＋E

定义14.3 若一个文法的某规范句型的句柄不唯一，则该文法

是二义性的，否则是无二义性的。

北京航空航天大学计算机学院

4

2

若文法是二义性的，则在编译时就会产生不确定性，

遗憾的是在理论上已经证明：文法的二义性是不可判定的，

即不可能构造出一个算法，通过有限步骤来判定任一文法

是否有二义性。

现在的解决办法是：提出一些限制条件，称为无二义性

的充分条件，当文法满足这些条件时，就可以判定文法是无

二义性的。

例:算术表达式的文法

E::= E+T | T

T ::= T*F | F

F ::= (E) | i

E::= E+E | E*E | (E) | i

北京航空航天大学计算机学院

4

3

句子：i+ i * i

E

E + T

E =|=> E+T =|=> E+T*F =|=> E+T*i

=

=

|=> E+F*i =|=> E+i*i =|=> T+i*i

|=> F+i*i =|=> i+i*i

T

F

T

F

F

i

*

i i

北京航空航天大学计算机学院

4

4

也可以采用另一种解决办法：即不改变二义性文法，而是确

定一种编译算法，使该算法满足无二义性充分条件。

例: Pascal 条件语句的文法

<

条件语句>::= If <布尔表达式>then<语句> |

If <布尔表达式> then <语句> else <语句>

<

语句> ::= <条件语句> | <非条件语句> |…….

If B then If B then stmt else stmt

北京航空航天大学计算机学院

4

5

2.5 句子的分析

任务：给定G[Z]: S ∈ V_t*, 判定是否有S  L (G[Z] ) ?

这是词法分析和语法分析所要做的工作，将在第三、

第四章中详细介绍。

北京航空航天大学计算机学院

4

6

2.6 有关文法的实用限制

若文法中有如U::=U的规则，则这就是有害规则，它会引

起二义性。

例如存在U::=U，U::= a | b,则有两棵语法树：

U

U

a

U

a

北京航空航天大学计算机学院

4

7

多余规则:（1）在推导文法的所有句子中，始终用不到的规则。

即该规则的左部非终结符不出现在任何句型中（不可达符号）

（

2）在推导句子的过程中，一旦使用了该规则，将推

不出任何终结符号串。即该规则中含有推不出任何终结符号串

的非终结符（不活动符号）

例如给定G[Z]，若其中关于U的规则只有如下一条：

U::=xUy

若还有U::=a，则此规则

并非多余

该规则是多余规则。

若某文法中无有害规则或多余规则，则称该文法是压缩过的。

北京航空航天大学计算机学院

4

8

例1：G[<Z>] :

例2： G[S] :

S ::= ccc

<

<

<

<

<

Z> ::= <B> e

A> ::= <A> e | e

B> ::= <C> e | <A> f

C> ::= <C> f

D> ::= f

S ::= Abccc

A ::= Ab

A ::= aBa

B ::= aBa

B ::= AD

D ::= Db

D ::= b

北京航空航天大学计算机学院

4

9

2

.7 文法的其它表示法

<

<

标识符>::＝字母{字母|数字}

无符号整数>::=数字{数字}

1

、扩充的BNF表示

•

BNF的元符号：< , >, ::= , |

•

扩充的BNF的元符号：< , >, ::= , | , { , } , [ , ] , ( , )

标识符

2

、语法图

字母

字母

数

字

无符号整数

数字

北京航空航天大学计算机学院

5

0

2.8 文法和语言分类

形式语言：用文法和自动机所描述的没有语义的语言。

文法定义：乔姆斯基将所有文法都定义为一个四元组：

G=（Vn，Vt，P，Z）

Vn：非终结符号集

Vt：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号） Z∈Vn

+

语言定义： L（G[Z]）={x| x∈Vt*, Z==>x }

北京航空航天大学计算机学院

5

1

文法和语言分类：0型、1型、2型、3型

这几类文法的差别在于对产生式（语法规则）施加不同的限制。

0

型： P：u ::= v

其中 u∈V_＋，v∈V* V = V_n∪ V_t

0型文法称为短语结构文法。规则的左部和右部都可

以是符号串，一个短语可以产生另一个短语。

0

型语言：L0 这种语言可以用图灵机(Turing)接受。

北京航空航天大学计算机学院

5

2

1

型： P：xUy ::= xuy

其中U∈Vn，

x、y、u∈V*

称为上下文敏感或上下文有关。也即只有在x、y这样的

上下文中才能把U改写为u

1

型语言：L1 这种语言可以由一种线性界限自动机接受。

北京航空航天大学计算机学院

5

3

2

型： P：U ::= u

其中U∈Vn，

u∈V*

称为上下文无关文法。也即把U改写为u时，不必考虑上下文。

(1型文法的规则中x，y均为 ε 时即为2型文法）

注意：2型文法与BNF表示相等价。

2

型语言：L2 这种语言可以由下推自动机接受。

北京航空航天大学计算机学院

5

4

3

型文法：

（

左线性）

P：U ::= t

（右线性）

P：U ::= t

或 U ::= Wt

其中U、W∈Vn

t∈Vt

或 U ::= tW

其中U、W∈Vn

t∈Vt

3

型文法称为正则文法。它是对2型文法进行进一步限制。

3型语言：L3 又称正则语言、正则集合

这种语言可以由有穷自动机接受。

北京航空航天大学计算机学院

5

5

•

•

•

•

根据上述讨论，L0  L1  L2  L3

0型文法可以产生L0、L1、L2、L3，

但2型文法只能产生L2，L3不能产生L0，L1

3型文法只能产生L3

北京航空航天大学计算机学院

5

6

第三章 词法分析

•

•

词法分析程序的功能及实现方案

单词的种类及词法分析程序的输出形式

正则文法和状态图

•

•

•

•

词法分析程序的设计与实现

正则表达式与有穷自动机

词法分析程序的自动生成器

北京航空航天大学计算机学院

1

3

.1 词法分析程序的功能及实现方案

™

词法分析程序的功能

¨

¨

¨

词法分析：根据词法规则识别及组合单词，进行词法检查。

对数字常数完成数字字符串到二进制数值的转换。

删去空格字符和注释。

北京航空航天大学计算机学院

2

实现方案：基本上有两种

1

.词法分析单独作为一遍

单词串

第二遍

第一遍

S.P.(字符串)

词法分析

S.P.(符号串)

语法分析

优点: 结构清晰、

各遍功能单一

缺点：效率低

2

.词法分析程序作为单独的子程序

取单词

词法分

析程序

语法分

析程序

S.P.(字符串)

单词

优点: 效率高

北京航空航天大学计算机学院

3

3

.2 单词的种类及词法分析程序的输出形式

单词的种类

1

2

3

4

. 保留字：begin、end、for、do...

. 标识符：由用户定义，表示各种名字

. 常 数：无符号数、布尔常数、字符串常数等

. 分界符：+、-、*、/、...

北京航空航天大学计算机学院

4

词法分析程序的输出形式-----单词的内部形式

单词类别 单词值

几种常用的单词内部形式：

1

2

3

、按单词种类分类

、保留字和分界符采用一符一类

、标识符和常数的单词值又为指示字（指针值）

北京航空航天大学计算机学院

5

1

、按单词种类分类

单词名称

单词值

类别编码

标识符

1

2

3

4

5

6

7

内部字符串

整数值

无符号常数(整)

无符号浮点数

布尔常数

字符串常数

保留字

数值

0 或 1

内部字符串

保留字或内部编码

分界符或内部编码

分界符

北京航空航天大学计算机学院

6

2

、保留字和分界符采用一符一类

类别编码

单词名称

单词值

1

2

3

4

5

6

7

8

9

标识符

内部字符串

整数值

无符号常数(整)

无符号浮点数

布尔常数

字符串常数

BEGIN

END

FOR

DO

数值

0 或 1

内部字符串

-

-

-

-

…

2

2

2

2

….

…

:

+

*

,

……

…..

-

-

-

0

1

2

3

-

…

….

(

--

北京航空航天大学计算机学院

7

3

.3 正则文法和状态图

•

状态图的画法（根据文法画出状态图）

例如：正则文法

Z::= U0 |V1

U ::=Z1 |1

V ::=Z0 | 0

左线性文法。该文法所定义的语言为：

L(G[Z]) = { B_n | n>0 }, 其中B= {01,10}

北京航空航天大学计算机学院

8

左线性文法的状态图的画法：

1

2

. 令G的每个非终结符都是一个状态；

. 设一个开始状态S；

T

3

. 若Q::=T, Q ∈Vn,T ∈Vt, 则：

Q

S

T

4

. 若Q::=RT, Q、R∈Vn,T ∈Vt, 则：

Q

R

5

. 按自动机方法，可加上开始状态和终止状态标志。

北京航空航天大学计算机学院

9

例如：正则文法

Z::= U0 |V1

U ::=Z1 |1

V ::=Z0 | 0

1

Start

其状态图为：

S

U

Z

0

1

0

0

V

1

北京航空航天大学计算机学院

1

0

•

识别算法

利用状态图可按如下步骤分析和识别字符串x：

1

、置初始状态为当前状态，从x的最左字符开始，

重复步骤2，直到x右端为止。

2

、扫描x的下一个字符，在当前状态所射出的弧中

找出标记有该字符的弧，并沿此弧过渡到下一个状

态；如果找不到标有该字符的弧，那么x不是句子，

过程到此结束；如果扫描的是x的最右端字符，并

从当前状态出发沿着标有该字符的弧过渡到下一个

状态为终止状态Z，则x是句子。

例：x=0110 和1011

北京航空航天大学计算机学院

11

•问题：

1、上述分析过程是属于自底向上分析？还是自顶向下

分析？

Z

2

、怎样确定句柄？

V

Z

U

Z =|=> V1 =|=>Z01 =|=>U001 =|=> 1001

1

0 0 1

北京航空航天大学计算机学院

1

2

3

.4 词法分析程序的设计与实现

词法规则 状态图 词法分析程序

北京航空航天大学计算机学院

1

3

3

.4.1 文法及其状态图

语言的单词符号

标识符

保留字(标识符的子集）

无符号整数

单分界符 + * ：，（ ）

双分界符 :=

两点说明：1. 空格的作用

2. 实数的表示

北京航空航天大学计算机学院

1

4

•

文法：1. <标识符>::= 字母| <标识符>字母| <标识符>数字

2. <无符号整数>::=数字| <无符号整数>数字

3. <单字符分界符>::= : | + | * | , | ( | )

4. <双字符分界符>::= <冒号>=

5. <冒号>::= :

字母、数字

字母

数字

非字母数字

非数字

标识符

S

标

数字

无符号整数

S

S

数

单字符分界符

其他字符

+ * ，

（ ）

单界

非 =

双字符分界符

：

=

S

双界

冒号

其他字符

查保留字表

字母、数字

非字母数字

标

读字符

字母

数字

S

标识符

数字

非数字

数

无符号整数

其他字符

+

* ，

（ ）

单界

单字符分界符

双字符分界符

非 =

：

=

冒号

双界

其他字符

其他

出错

返回S

北京航空航天大学计算机学院

1

6

3

.4.2 状态图的实现——构造词法分析程序

1

2

3

. 单词及内部表示

. 词法分析程序需要引用的公共（全局）变量和过程

. 词法分析程序算法

北京航空航天大学计算机学院

1

7

1

.单词及内部表示: 保留字和分界符采用一符一类

单词名称

类别编码

记忆符

单词值

BEGIN

END

FOR

DO

1

2

3

4

BEGINSY

ENDSY

FORSY

DOSY

-

-

-

-

IF

5

IFSY

-

THEN

ELSE

标识符

6

7

8

THENSY

ELSESY

IDSY

-

-

内部字符串

整数值

常数(整)

9

INTSY

:

10

11

12

13

14

15

16

COLONSY

PLUSSY

STARSY

COMSY

LPARSY

RPARSY

ASSIGNSY

-

-

-

-

-

-

-

+

*

,

(

)

:

=

北京航空航天大学计算机学院

1

8

2

.词法分析程序需要引用的公共（全局）变量和过程

名称

类别

功能

4

4

4

4

CHAR

TOKEN

GETCHAR

GETNBC

字符变量

字符数组

存放当前读入的字符

存放单词字符串

读字符过程 读字符到CHAR,移动指针

过程

反复调用GETCHAR,

直至CHAR进入一个非空白字符

CHAR与TOKEN连接

判断

4

4

CAT

ISLETTER 和

过程

布尔函数

过程

ISDIGIT

4

4

读字符指针后退一个字符

判断TOKEN中的字符串

是保留字, 还是标识符

字符串到数字的转换

出错处理

UNGETCH

RESERVE

布尔函数

函数

过程

4

4

ATOI

ERROR

北京航空航天大学计算机学院

1

9

3

、词法分析程序算法

S TA RT: TOKEN := ‘ ‘; /*置TOKEN为空串*/

GETCHAR; GETNBC;

CASE CHAR OF

‘

A’..’Z’: BEGIN

WHILE ISLETTER OR ISDIGET DO

BEGIN CAT; GETCHAR END;

UNGETCH;

C:= RESERVE;

IF C=0 THEN RETURN(‘IDSY’: TOKEN)

ELSE RETURN (C,-) /*C为保留字编码*/

END;

0’..’9’: BEGIN

WHILE DIGIT DO

BEGIN CAT; GETCHAR END;

‘

UNGETCH;

RETURN (‘INTSY’,ATOI)

END;

‘

+’ : RETURN(‘PLUSSY’,-) ;

北京航空航天大学计算机学院

2

0

‘

‘

‘

‘

‘

*’ : RETURN(‘STARSY’,-) ;

,’ : RETURN(‘COMMASY’,-) ;

(’ : RETURN(‘LPARSY’,-) ;

)’ : RETURN(‘RPARSY’,-) ;

:’ : BEGIN

GETCHAR;

if CHAR=‘=‘ THEN RETURN(‘ASSIGNSY’,-) ;

UNGETCH;

RETURN(‘COLONSY’,-) ;

END

END OF CASE;

ERROR;

GOTO START;

北京航空航天大学计算机学院

2

1

3

.5.1 正则表达式和正则集合的递归定义

有字母表, 定义在 上的正则表达式和正则集合递归定义如下:

1

2

3

. 和都是 上的正则表达式, 其正则集合分别为:{}和;

. 任何a  , a是 上的正则表达式,其正则集合为:{a};

. 假定U和V是  上的正则表达式, 其正则集合分别记为L(U)

和L(V), 那么U|V, U•V和U_*也都是 上的正则表达式, 其

正则集合分别为L(U) L(V)、 L(U) • L(V)和L(U)_*；

. 任何 上的正则表达式和正则集合均由1、2和3产生。

4

北京航空航天大学计算机学院

2

2

正则表达式中的运算符：

|

*

-----或（选择） • ----连接

或 { } ---重复 （） ----括号

运算符的优先级：

先*, 后• , 最后 |

• 在正则表达式中可以省略.

正则表达式相等 这两个正则表达式表示的语言相等

如：b{ab} = {ba}b

{a|b} = {{a} {b}} = (a*b*)*

北京航空航天大学计算机学院

2

3

例：设  = { a,b },下面是定义在上的正则表达式和正则集合

正则集合

正则表达式

ba*

a(a|b)*

(a|b)*(aa|bb)(a|b)*

北京航空航天大学计算机学院

2

4

正则表达式的性质：

设e1, e2和e3均是某字母表上的正则表达式, 则有:

单位正则表达式: 

e = e = e

交换律: e1 | e2 = e2 | e1

结合律: e1|(e2|e3) = (e1|e2)|e3

e1(e2e3) = (e1e2)e3

分配律: e1(e2|e3) = e1e2|e1e3

(e1|e2)e3 = e1e3|e2e3

此外: r_* = (r|)_* r_** =r_*

(r|s)_* = (r_*s_*)_*

北京航空航天大学计算机学院

2

5

正则表达式与3型文法等价

例如：

正则表达式：ba*

a(a|b)*

3

型文法： Z ::= Za|b

Z::=Za|Zb|a

例：

3

型文法

正则表达式

S::= aS|aB

B::= bC

aS|aba*a

ba*a

a*aba*a

C::= aC|a

a*a

北京航空航天大学计算机学院

2

6

3

.5.2 确定的有穷自动机（DFA）— 状态图的形式化

(Deterministic Finite Automata)

一个确定的有穷自动机（DFA）M是一个五元式:

M=(S, Σ，δ,s0, Z)

其中:

1

2

3

. S —有穷状态集

. Σ—输入字母表

. δ—映射函数(也称状态转换函数)

S×Σ→S

δ(s,a)=s’ , s, s’ ∈S, a∈Σ

4

5

. s0 —初始状态

. Z—终止状态集

s

0

∈S

ZS

北京航空航天大学计算机学院

2

7

例如: M:（{0,1,2,3},{a,b},δ，0，{3}）

δ（0，a）=1 δ（0，b）=2

δ（1，a）=3 δ（1，b）=2

δ（2，a）=1 δ（2，b）=3

δ（3，a）=3 δ（3，b）=3

状态转换函数δ可用一矩阵来表示：

输入

字符

所谓确定的状

态机，其确定

性都表现在状

态转换函数是

单值函数！

状态

a

b

0

1

2

3

1

2

3

1

3

2

3

3

北京航空航天大学计算机学院

2

8

DFA也可以用一状态转换图表示：

DFA的状态图表示：

a

a

1

2

start

0

b

a

3

a,b

b

b

北京航空航天大学计算机学院

2

9

DFA M所接受的符号串：

令α= a1a2¨¨¨an，α∈Σ，若^*δ(δ(¨¨ δ(s0, a1),a2)¨¨），

an-1）,an) = Sn ,且Sn ∈Z，则可以写成δ(s0, α)= Sn,我们称α可为

M所接受。

δ(s0, a1)= S1

换言之：若存在一条

初始状态到某一终止

状态的路径，且这条

路径上能有弧的标记

符号连接成符号串α，

则称α为DFA M（接受）

识别。

δ(s1, a2)= S2

…

……

δ(sn-2, an-1)= Sn-1

δ(sn-1, an)= Sn

DFA M所接受的语言为：L(M)={α|δ(s0, α)= Sn , Sn∈Z}

北京航空航天大学计算机学院

3

0

3

.5.3 不确定的有穷自动机(NFA)

(Nondeterministic Finite Automata)

若δ是一个多值函数，且输入可允许为ε，则有穷自动机是不确定的,

即在某个状态下，对于某个输入字符存在多个后继状态。

ꢀ

从同一状态出发，有以同一字符标记的多条边，或者有

以ε标记的特殊边的自动机。

北京航空航天大学计算机学院

3

1

NFA的形式定义为:

一个非确定的有穷自动机NFA M’是一个五元式:

NFA M’=(S, Σ∪{ε}, δ, s0, Z)

其中 S—有穷状态集

Σ∪{ε}—输入符号加上ε,

即自动机的每个结点所射出的弧可以是Σ中的一个字符或是ε

s0—初态

s

0

∈S

Z—终态集

δ—转换函数

ZS

S×Σ∪{ε} →2_S

(2_S --S的幂集—S的子集构成的集合）

北京航空航天大学计算机学院

3

2

NFA M’所接受的语言为:

L(M’)={α|δ(S0,α)=S’ S’∩Z≠Φ}

例：NFA M’=({1,2,3,4},{a,b,c} ∪{ε},δ,1,{4})

北京航空航天大学计算机学院

3

3

上例题相应的状态图为：

a

b

a

2

start

ε

4

1

c

a 3

c

M’所接受的语言（用正则表达式） R=aa*b|ac*c|ε

北京航空航天大学计算机学院

3

4

3

.5.4 NFA的确定化

已证明：不确定的有穷自动机与确定的有穷自动机从功能

上来说是等价的，也就是说能够从：

NFA M ’^{构造成一个}DFA M

使得 L(M)=L(M’)

北京航空航天大学计算机学院

3

5

为了使得NFA确定化，首先给出两个定义：

定义1、集合I的ε-闭包：

令I是一个状态集的子集，定义ε-closure（I）为：

1

2

）若s∈I，则s∈ε-closure（I）；

）若s∈I，则从s出发经过任意条ε弧能够到达的任何

状态都属于ε-closure（I）。

状态集ε-closure（I）称为I的ε-闭包。

可以通过一例子来说明状态子集的ε-闭包的构造方法

北京航空航天大学计算机学院

3

6

ε

例：

2

3

4

6

5

a

如图所示的状态图：

令I={1}，

1

ε

a

求ε-closure（I）=？

a

根据定义：

ε-closure（I）= {1，3}

北京航空航天大学计算机学院

3

7

定义2: 令I是NFA M’的状态集的一个子集, a∈Σ

定义: I_a=ε-closure(J)

其中J = ∪δ(s,a)

S∈I

-- J是从状态子集I中的每个状态出发,经过标记为a的弧而

达到的状态集合。

-

- I_a是状态子集,其元素为J中的状态,加上从J中每一个

状态出发通过ε弧到达的状态。

同样可以通过一例子来说明上述定义,仍采用前面给定的

状态图为例

北京航空航天大学计算机学院

3

8

例：令 I={1}

I_a =ε-closure(J)

=

=

=

ε-closure(δ（1，a））

ε-closure({2，4}）

{2，4，6}

根据定义1，2，可以将上述的M’确定化（即可构造出状态

转换矩阵）

北京航空航天大学计算机学院

3

9

例：有NFA M’

I=ε-closure({1})={1,4}

I_a=ε-closure(δ(1,a)∪δ(4,a))

a

b

a

2

=

=

=

ε-closure({2,3}∪φ）

ε-closure ({2,3})

{2,3}

start

ε

1

4

c

a 3

I_b= ε-closure(δ(1,b)∪δ(4,b))

c

=

=

ε-closure(φ）

φ

I_c= ε-closure(δ(1,c)∪δ(4,c))

=

φ

I={2,3}, I ={2},I ={4},I ={3,4}…

a

b

c

北京航空航天大学计算机学院

4

0

I

I_a

1,4} {2,3} φ

2,3} {2} {4}

2} {2}

I_b

I_c

{

{

{

{

{

φ

{3,4}

{4} φ

4} φ

φ

φ

φ

3,4} φ

{3,4}

北京航空航天大学计算机学院

4

1

将求得的状态转换矩阵重新编号

DFA M状态转换矩阵：

符号

a

b

_

c

状态

_

0

1

2

3

4

1

2

2

3

3

4

_

_

_

_

_

_

4

北京航空航天大学计算机学院

4

2

DFA M的状态图：

{2,3}

a

c

{1,4}

1

start

0

4

b

3

a

c

{3,4}

a

2

{2}

{4}

b

注意：包含原初始状态1的状态子集为DFA M的初态

包含原终止状态4的状态子集为DFA M的终态。

北京航空航天大学计算机学院

4

3

3

.5.5 正则表达式与DFA的等价性

定理：在Σ上的一个子集V ( VΣ_* ）是正则集合，当且仅当

存在一个DFA M，使得V=L(M)

V是正则集合，

R是与其相对应的正则表达式  DFA M

V=L(R)

L(M)=L(R)

所以 正则表达式R  NFA M’  DFA M

L(R) = L(M’) = L(M)

证明: 根据定义。

北京航空航天大学计算机学院

4

4

start

start

start

a

a

φ

φ

正则表达式 ε

正则集合 {ε}

{

a}

N(s)

ε

ε

R=s|t NFA(R):

start

x

x

y

y

ε

ε

ε

ε

N(t)

N(t)

ε

R=st NFA(R):

start ε

N(s)

x

R=s_* NFA(R):

start

ε

ε

N(s) y

ε

北京航空航天大学计算机学院

4

5

3

.6 词法分析程序的自动生成器—LEX（LEXICAL）

LEX的原理：

正则表达式与DFA的等价性

根据给定的正则表达式自动生成相应的词法分析程序。

LEX的功能：

LEX源程序

S.P.(字符串)

LEX 词法分析程序L

S.P.单词(符号串)

L

北京航空航天大学计算机学院

4

6

3

.6.1 LEX源程序

一个LEX源程序主要由三个部分组成:

1

2

3

. 辅助定义式

. 识别规则

. 用户子程序

各部分之间用%%隔开

北京航空航天大学计算机学院

4

7

辅助定义式是如下形式的LEX语句：

D

D

1

2

R

R

1

2

∶

∶

D

n

R

n

其中：

R1,R2，……，Rn 为正则表达式。

D1,D2，……，Dn 为正则表达式名字，称简名。

北京航空航天大学计算机学院

4

8

例：标识符： letter→A|B|¨¨¨|Z

digit →0|1| ¨¨¨|9

iden →letter(letter|digit)_*

带符号整数：integer→digit (digit)_*

sign →+| - |ε

sign_integer →sign integer

北京航空航天大学计算机学院

4

9

识别规则：是一串如下形式的LEX语句：

P

P

1

{A1}

{A2}

2

∶

∶

P

m

{Am}

P

i

：定义在Σ∪{D1,D2,¨¨Dn}上的正则表达式，也称词形。

{Ai}：Ai为语句序列，它指出，在识别出词形为Pi的单词以

后，词法分析器所应作的动作。

其基本动作是返回单词的类别编码和单词值。

北京航空航天大学计算机学院

5

0

下面是识别某语言单词符号的LEX源程序：

例：LEX 源程序

AUXILIARY DEFINITIONS /*辅助定义*/

letter  A|B|¨¨|Z

digit  0|1|¨¨|9

%

%

RECOGNITION RULES

/*识别规则*/

1

2

3

.BEGIN

.END

{RETURN(1,─) }

{RETURN(2,─) }

{RETURN(3,─) }

.FOR

北京航空航天大学计算机学院

5

1

4

5

6

7

8

9

.DO

{RETURN(4,─) }

{RETURN(5,─) }

{RETURN(6,─) }

{RETURN(7,─) }

{RETURN(8,TOKEN) }

{RETURN(9,DTB }

{RETURN(10,─) }

{RETURN(11,─) }

{RETURN(12,─) }

.IF

.THEN

.ELSE

.letter(letter |digit)_*

.digit(digit)_*

1

0. :

1. +

2. “*”

1

1

北京航空航天大学计算机学院

5

2

1

1

1

1

1

3. ,

{RETURN(13,─) }

{RETURN(14,─) }

{RETURN(15,─) }

4. “（”

5. “）”

6. :=

{RETURN(16,─) }

{RETURN(17,─) }

7. =

北京航空航天大学计算机学院

5

3

3

.6.2 LEX的实现

LEX的功能是根据LEX源程序构造一个词法分析程序，

该词法分析器实质上是一个有穷自动机。

LEX生成的词法分析程序由两部分组成:

状态转换矩阵(DFA)

词法分析程序

控制执行程序

∴

LEX的功能是根据LEX源程序生成状态转换矩阵和控制程序

北京航空航天大学计算机学院

5

4

LEX的工作过程：

·

¨

·

扫描每条识别规则Pi，构造相应的不确定有穷自动机Mi

将各条规则的有穷自动机Mi合并成一个新的NFA M

¨确定化

NFADFA

生成该DFA的状态转换矩阵和控制执行程序

北京航空航天大学计算机学院

5

5

LEX二义性问题的两条原则：

1

.最长匹配原则

P

j

P

i

在识别单词过程中，有一字符串 x x x x x

根据最长匹配原则，应识别为这是

P

k

一个符合Pk规则的单词，而不是Pj和Pi规则的单词。

2

.优先匹配原则

如有一字符串，有两条规则可以同时匹配时，那么用规则

序列中位于前面的规则相匹配，所以排列在最前面的规则优先

权最高。

北京航空航天大学计算机学院

5

6

P

1

例：字符串·¨begin·¨

P

8

根据原则，应该识别为关键字begin，所以在写LEX源程序

时应注意规则的排列顺序。另要注意的是，优先匹配原则

是在符合最长匹配的前提下执行的。

可以通过一个例子来说明这些问题：

北京航空航天大学计算机学院

5

7

start

a

例： LEX源程序

a { }

1

2

4

8

start a

b

b

3

7

5

6

abb { }

a

b

start

b

^a*^bb

*

{ }

一.读LEX源程序，分别生成NFA，用状态图表示为：

a

二.合并成一个NFA：

1

3

7

2

4

8

ε

start ε

a

b

b

0

5

6

a

ε

b

b

北京航空航天大学计算机学院

5

8

三.确定化 给出状态转换矩阵

状态

a

b 到达终态所识别的单词

初态

{2,4,7} {8}

{0,1,3,7}

终态 {2,4,7}

{7}

8} φ

7} {7}

{5,8}

{8}

{8}

{6,8}

a

*

{

a_* bb

终态

{

*

终态

终态

{5,8} φ

{6,8} φ

a bb

*

{8}

abb

在此DFA中 初态为{0,1,3,7}

终态为{2,4,7},{8},{5,8},{6,8}

北京航空航天大学计算机学院

5

9

读入字符 进入状态

开始 {0,1,3,7}

词法分析程序的分析过程

令输入字符串为aba…

a

{2,4,7}

(1) 吃进字符ab

(2) 按反序检查状态子集

检查前一次状态是否含有原

b {5,8}

a 无后继状态(退

掉输入字符a)

NFA的终止状态

·即检查{5,8},含有终态8，因此断定所识别的单词ab是属于

a*bb*中的一个。

··若在状态子集中无NFA的终态，则要从识别的单词再退掉

一个字符(b)，然后再检查上一个状态子集。

··若一旦吃进的字符都退完，则识别失败，调用出错程序，

一般是跳过一个字符然后重新分析。（应打印出错信息）

·

北京航空航天大学计算机学院

6

0

三点说明：

1

) 以上是LEX的构造原理，虽然是原理性的，但据此就

不难将LEX构造出来。

2

) 所构造出来的LEX是一个通用的工具，用它可以生成

各种语言的词法分析程序，只需要根据不同的语言书

写不同的LEX源文件就可以了。

3

) LEX不但能自动生成词法分析器，而且也可以产生多

种模式识别器及文本编辑程序等。

北京航空航天大学计算机学院

6

1

正则文法

1

5

2

6

4

3

NFA

DFA

正则表达式

最小化

北京航空

6

2

（

1）有穷自动机正则文法

算法:

t

A

B

1

2

3

.对转换函数f(A,t)=B，可写成一个产生式:A→tB

.对可接受状态Z,增加一个产生式:Z→ε

.有穷自动机的初态对应于文法的开始符号(识别符号）,

有穷自动机的字母表为文法的终结符号集。

北京航空航天大学计算机学院

6

3

a

例:给出如图NFA等价的正则文法G

start

a

b

C

A

B

a

G=（{A，B，C，D}，{a，b}，P，A）

b

b

其中P: A aB

→

D

A→bD

B→bC

b

C aA

→

C bD

→

→

C ε

D→aB

D→bD

D ε

→

北京航空航天大学计算机学院

6

4

（

2）正则文法有穷自动机M

算法:

1

2

.字母表与G的终结符号相同；

.为G中的每个非终结符生成M的一个状态,G的开始符号S

是开始状态S;

3

4

.增加一个新状态Z,作为NFA的终态；

.对G中的形如A→tB,其中t为终结符或ε,A和B为非终结

符的产生式,构造M的一个转换函数f(A,t)=B；

5

.对G中的形如A→t的产生式,构造M的一个转换函数

f(A,t)=Z。

北京航空航天大学计算机学院

6

5

例:求与文法G[S]等价的NFA

G[S]: S→aA|bB|ε

A→aB|bA

B→aS|bA|ε

b

A

a

a

求得：

b

start

b

S

B

a

ε

ε

Z

北京航空航天大学计算机学院

6

6

（

3）正则式有穷自动机

语法制导方法

.(a)对于正则式φ,所构造NFA:

1

x

x

y

y

ε

(b)对于正则式ε,所构造NFA:

(c)对于正则式a,a∈Σ,则NFA:

a

x

y

北京航空航天大学计算机学院

6

7

2

.若s,t为Σ上的正则式,相应的NFA分别为N(s)和N(t);

(a)对于正则式R=s|t, NFA(R)

ε

N(s)

N(t)

ε

ε

x

y

ε

(b)对正则式R=st, NFA(R)

ε

ε

ε

N(s)

N(t)

x

y

或:

x N(s) N(t) y

北京航空航天大学计算机学院

6

8

(c)对于正则式R=s_*, NFA(R)

ε

ε

ε

x

N(s) y

ε

(d)对R=(s),与R=s的NFA一样.

北京航空航天大学计算机学院

6

9

*

例:为R=(a|b) abb构造NFA N,使得L(N)=L(R)

a

从左到右分解R,令r1=a,第一个a,则有 2

3

b

令r2=b,则有 4

5

a

令r3= r1 |r2,则有

ε

ε

ε

ε

2

4

3

5



1

6

b

北京航空航天大学计算机学院

7

0

令r4= r3* 则有:

ε

a

ε

ε

ε

ε

2

4

3

5

ε

ε



0

1

6

7

b

ε

令r5=a,

令r6=b

令r7=b

令r8= r5 r6

令r9= r8 r7 则有

a

b

b

 7

8

9

10

北京航空航天大学计算机学院

7

1

令r10= r4 r9 则最终得到NFA N:

ε

a

ε

ε

ε

ε

2

4

3

5

ε

ε a b b

7 8 9 10



0

1

6

b

ε

分解R的方法有很多种,下面给出另一种分解方式和所构成的NFA

北京航空航天大学计算机学院

7

2

(a|b)*

abb







(a)

(b)

x

x

x

i

y

j

a|b

ε ε

abb

abb

i

y

y

a

ε ε

i

j

(c)

(d)

b

a

ε ε

a

b

b



x

i

j

k

l

y

b

北京航空航天大学计算机学院

7

3

（

4）有穷自动机正则式R

算法:

1

)在M上加两个结点x,y,从x结点用ε弧到M的所

有初态,从M的所有终态用ε到y结点形成与M等

价的M’,M’只有一个初态x和一个终态y。

)逐步消去M’中的所有结点,直至剩下x和y结点,在

消结过程中,逐步用正则式来记弧,其消结规则如

下:

2

R

1

R

2

2 3

RR

1 2

1

2

3

.对于

代之为

1

1 3

R

1

2 代之为 1 ^R1|R2 2

.对于 1

R

2

R

2

.对于

代之为

R

1

R

3

2 3

R1R_2*R3

1

1

3

北京航空航天大学计算机学院

7

4

a,b

a,b

例:M:

start

a

a

0

3

4

b

1

b

2

a,b

a,b

解: (1)加x,y

a

a

3

1

4

a,b

0

ε

ε

y

x

ε

b

2

b

a,b

北京航空航天大学计算机学院

7

5

(2)消除M中的所有结点

a|b

aa(a|b) *

4

a|b

a|b

aa ε

x

0

y

x

0

y

ε

ε

bb ε

2

bb(a|b) *

a|b

(a|b)*(aa|bb)(a|b)*

x

y

北京航空航天大学计算机学院

7

6

（

5）正则文法正则式

利用以下转换规则,直至只剩下一个开始符号定义的产

生式,并且产生式的右部不含非终结符。

规则 文法产生式 正则式

规则1 A→xB,B→y A=xy

规则2

规则3

A→xA|y

A=x_*y

A→x,A→y A=x|y

北京航空航天大学计算机学院

7

7

例:有文法G[s]

S→aA|a,

A→aA|dA|a|d

于是: S=aA|a

A=(aA|dA)|(a|d)A=(a|d)A|(a|d)

由规则二: A=(a|d)*(a|d)

代入:S=a(a|d)*(a|d)|a

于是:S=a((a|d)*(a|d)|ε)

北京航空航天大学计算机学院

7

8

（

6）正则式正则文法

算法:

1

) 对任何正则式r,选择一个非终结符S作为识别符号,

并产生产生式 S→r

2

) 若x,y是正则式,对形为A→xy的产生式,重写为

A→xB B→y,其中B为新的非终结符,B∈Vn

同样: 对于 A→x*y  A→xA A→y

A→x|y  A→x A→y

例:将R=a(a|d)*转换成相应的正则文法

解:1) S→a(a|d)*

3

) S→aA

A→(a|d)A

A→ε

4) S→aA

A→aA|dA

A→ε

2

) S→aA

A→(a|d)*

北京航空航天大学计算机学院

7

9

补充: DFA的简化(最小化)

“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”

一个有穷自动机是化简的 它没有多余状态并且它的状态

中没有两个是互相等价的。

一个有穷自动机可以通过消除多余状态和合并等价状态

而转换成一个最小的与之等价的有穷自动机

北京航空航天大学计算机学院

8

0

定义：

(1) 有穷自动机的多余状态：从该自动机的开始状态出发,任

何输入串也不能到达那个状态

0

1

例:

画状态图可

以看出s4,s6,s8

为不可达状

态应该消除

s

s

s

s

s

s

s

s

s

0

1

2

3

4

5

6

7

8

s

s

s

s

s

s

s

s

s

1

s

s

s

s

s

s

s

s

s

5

0

1

2

2

5

5

3

8

0

3

7

5

7

6

1

0

1

6

s

s

s

s

s

s

0

1

2

3

5

7

s

s

s

s

s

s

1

s

s

s

s

s

s

5

2

2

5

3

0

7

5

7

1

1

北京航空航天大学计算机学院

8

1

(2)等价状态 状态s和t的等价条件是:

1

2

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

不接受状态。

)蔓延性条件：对于所有输入符号,状态s和t必须

转换到等价的状态里。

对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同

的后继，则称s，t是等价的。

（任何有后继的状态和任何无后继的状态一定不等价）

有穷自动机的状态s和t不等价,称这两个状态是可区别的。

北京航空航天大学计算机学院

8

2

“

分割法”：把一个DFA(不含多余状态)的状态分割成一些

不相关的子集，使得任何不同的两个子集状态

都是可区别的，而同一个子集中的任何状态都

是等价的。

b

例:最小化

a

a

6

4

a

a

a

b

start

7

1

5

a

b

a

b

b

b

2

3

b

北京航空航天大学计算机学院

8

3

解:

(一)区分终态与非终态

a

6

7

b 区号

区号

a

6

7

b

3

3

1

2

3

3

1

2

1

1

3

4

1

4

5

6

3

3

4

1

4

5

6

3

2

5

6

7

4

5

6

7

4

1 2

1 3

7

4

2

7

4

2

北京航空航天大学计算机学院

8

4

区号

区号

a

6

7

b

3

3

a

1 6

2 7

b

3

3

1

2

1

1

3

4

1

4

5 2

6 3

3 1

4 4

5 2

6 3

4

5

6

7

4

3

5 7

6 4

3

1

1 4

5

7

4

2

7 4

2

北京航空航天大学计算机学院

8

5

将区号代替状态号得:

a

b

b

a

a

5

a

1

2

3

4

5

5

1

3

5

3

2

4

5

2

1

3

a

b

1

a

b

b

2

4

b

北京航空航天大学计算机学院

8

6

•

•

•

语法分析的功能、基本任务

自顶向下分析法

自底向上分析法

北京航空航天大学计算机学院

1

4.1 语法分析概述

功能：根据文法规则，从源程序单词符号串中识别出语法

成分，并进行语法检查。

基本任务：识别符号串S是否为某语法成分。

两大类分析方法：

自顶向下分析

自底向上分析

北京航空航天大学计算机学院

2

自顶向下分析算法的基本思想为：

+

若Z  S 则 S  L(G[Z]) 否则 S  L(G[Z])

G[Z]

s 主要问题:

Ø 左递归问题

§ 主要方法:

•

•

递归子程序法

LL分析法

Ø 回溯问题

北京航空航天大学计算机学院

3

自底向上分析算法的基本思想为：

+

若Z  S

则 S L(G[Z]) 否则 S  L(G[Z])

G[Z]

s 主要问题:

§ 主要方法:

•

•

算符优先分析法

LR分析法

Ø 句柄的识别问题

北京航空航天大学计算机学院

4

4.2 自顶向下分析

4

.2.1 自顶向下分析的一般过程

给定符号串S，若预测是某一语法成分，则可根据该

语法成分的文法,设法为S构造一棵语法树，

若成功,则S最终被识别为某一语法成分,即

SL(G[Z])，其中G[Z]为某语法成分的文法

若不成功, 则 SL(G[Z])

•

可以通过一例子来说明语法分析过程

北京航空航天大学计算机学院

5

例：

S = cad

G[Z]:

分析过程是设法建立一

棵语法树,使语法树的末端结

点与给定符号串相匹配。

Z∷ =cAd

A∷ =ab|a

求解 SL(G[Z]) ?

Z

1

2

. 开始:令Z为根结点

·

Z

. 用Z的右部符号串去匹配输入串

·

完成一步推导ZcAd

检查, c-c匹配

c A d

A是非终结符,将匹配任务交给A

北京航空航天大学计算机学院

6

Z

·

3

. 选用A的右部符号串匹配输入串

A有两个右部,选第一个

c A d

完成进一步推导Aab

检查,a-a匹配,b-d不匹配(失败)

但是还不能冒然宣布SL(G[Z])

a b

Z

4

. 回溯 即砍掉A的子树

改选A的第二右部

·

Aa 检查 a-a匹配

d-d匹配

c A d

a

建立语法树,末端结点为cad,与输入cad相匹配,

建立了推导序列 ZcAdcad

∴

cadL(G(Z))

北京航空航天大学计算机学院

7

自顶向下分析方法特点:

1

2

. 分析过程是带预测的，对输入符号串要预测属于什么

语法成分，然后根据该语法成分的文法建立语法树。

. 分析过程是一种试探过程，是尽一切办法(选用不同

规则) 来建立语法树的过程, 由于是试探过程, 难免

有失败, 所以分析过程需进行回溯, 因此也称这种方法

是带回溯的自顶向下分析方法。

3

. 最左推导可以编写程序来实现, 但带溯的自顶向下分

析方法在实际上价值不大, 效率低。

北京航空航天大学计算机学院

8

4

.2.2 自顶向下分析存在的问题及解决方法

1

、 左递归文法：

有如下文法：

令U是文法的任一非终结符，文法中有规则

+

U∷ =U¨¨或者U U¨¨

这个文法是左递归的。

自顶向下分析的基本缺点是：

不能处理具有左递归性的文法

为什么？

北京航空航天大学计算机学院

9

如果在匹配输入串的过程中，假定正好轮到要用非终结

符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配，

为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下

去将无法终止。

如果文法具有间接左递归，则也将发生上述问题，只不

过环的圈子兜得更大。

要实行自顶向下分析，必须要消除文法的左递归，下面

将介绍直接左递归的消除方法，在此基础上再介绍一般左递

归的消除方法。

北京航空航天大学计算机学院

1

0

消除直接左递归

方法一，使用扩充的BNF表示来改写文法

例：(1) E∷ =E+T|T  E∷ =T{+T}

(2) T∷ =T*F|T/F|F  T ∷ =F{*F|/F}

a. 改写以后的文法消除了左递归。

b. 可以证明，改写前后的文法是等价的，表现在

L(G改前) = L(G改后)

如何改写文法能消除左递归，又前后等价，

可以给出两条规则:

北京航空航天大学计算机学院

11

规则一（提因子）

若：U∷ =xy|xw|….|xz

则可改写为：U∷ =x(y|w|….|z)

若：y=y y , w=y w

1

2

1 2

则 U∷ =x(y (y |w )|….|z)

1

2

2

若有规则：U∷ =x|xy

则可以改写为：U∷ =x(y|ε)

注意：不应写成U∷ =x(ε|y)

使用提因子法，不仅有助于消除直接左递归，而且有

助于压缩文件的长度，使我们能更有效地分析句子。

北京航空航天大学计算机学院

1

2

规则二

若有文法规则：U∷ =x|y|……|z|Uv

其特点是：具有一个直接左递归的右部并位于最后，

这表明该语法类U是由x或y……或z其后随有零个

或多个v组成。

UUv  Uvv  Uv vv  ……

∴

可以改写为U∷ =(x|y|……|z){v}

通过以上两条规则，就能消除文法的直接左递归，

并保持文法的等价性。

北京航空航天大学计算机学院

1

3

方法二，将左递归规则改为右递归规则

规则三

若：P∷ =P| 

则可改写为：P ∷ =  P’

P’ ∷ = P’| ε

北京航空航天大学计算机学院

1

4

例1 E∷ =E+T|T

右部无公因子，所以不能

用规则一。

例2 T∷ =T*F|T/F|F

T∷ =T(*F|/F) | F 规则一

T∷ =F|T(*F|/F)

为了使用规则二，

令E∷ =T|E+T

T∷ =F{(*F|/F)} 规则二

即T∷ =F{*F|/F}

∴

由规则二可以得到

E∷ =T{+T}

右递归：

T ::= FT’

T’ ::= *FT’ | /FT’ | ε

北京航空航天大学计算机学院

1

5

消除一般左递归

一般左递归也可以通过改写文法予以消除。

消除所有左递归的算法：

1

. 把G的非终结符整理成某种顺序A1，A2，……An ，使得：

A

1

::= δ1|δ2|……δk

::= A1 r……

::= A2u |A1v…..

A

A

2

3

…

….

北京航空航天大学计算机学院

1

6

2

. For i:=1 to n do

begin

for j :=1 to i-1 do

把每个形如Ai∷ =Ajr的规则替换成

∷ =(δ1|δ2|……|δk) r ,

A

i

其中Aj ∷ =δ1|δ2|……|δk是当前全部Aj 的规则;

消除Ai规则中的直接左递归

end

3

. 化简由2得到的文法即可。

北京航空航天大学计算机学院

1

7

例：文法G[s]为

S ∷ = Qc|c

Q ∷ = Rb|b

R ∷ = Sa|a

该文法无直接左递归，但有间接左递归

+

SQc Rbc Sabc

∴ S Sabc

R∷ =Sa|a

Q∷ =Rb|b

S∷ =Qc|c

非终结符顺序重新排列

北京航空航天大学计算机学院

1

8

1

2

3

4

5

. 检查规则R是否存在直接左递归 R∷ =Sa|a

. 把R代入Q的有关选择，改写规则Q

. 检查Q是否存在直接左递归

Q∷ =Sab|ab|b

. 把Q代入S的右部选择

. 消除S的直接左递归

S∷ =Sabc|abc|bc|c

S∷ =(abc|bc|c){abc}

北京航空航天大学计算机学院

1

9

最后得到文法为:

S∷ =(abc|bc|c){abc}

Q∷ =Sab|ab|b

R∷ =Sa|a

可以看出其中关于Q和R的规则是多余的规则

∴经过压缩后 S∷ =(abc|bc|c){abc}

可以证明改写前后的文法是等价的

应该指出,由于对非终结符的排序不同,最后得到的文法在形

式上可能是不一样的,但是不难证明它们的等价。

北京航空航天大学计算机学院

2

0

2

、回溯问题

什么是回溯?

分析工作要部分地或全部地退回去重做叫回溯。

造成回溯的条件：

文法中，对于某个非终结符号的规则其右部

有多个选择，并根据所面临的输入符号不能准确

地确定所要的选择时，就可能出现回溯。

回溯带来的问题：

严重的低效率，只有在理论上的意义而无实际意义

北京航空航天大学计算机学院

2

1

效率低的原因



1

FIRST(α1)

1

2

) 语法分析要重做

FIRST(α2)

U



2

) 语义处理工作要推倒重来

FIRST(α2)

设文法G（不具左递归性），U Vn

U::=  |  | 



3

1

2

3

[

定义] FIRST(αi) = {a | αi^*

 a…, a Vt }

为避免回溯，对文法的要求是:

FIRST(αi) ∩ FIRST(αj)=φ (ij)

北京航空航天大学计算机学院

2

2

消除回溯的途径：

.改写文法

对具有多个右部的规则反复提取左因子

1

例1 U∷ =xV|xW

改写为U∷ =x(V|W)

更清楚地表示为：

U∷ =xZ

U, V, W∈Vn, x∈V_t+

注意：问题到此并没有结束，还需要

进一步检查V和W的首符号是否相交

若V∷ =ab|cd FIRST(V) = {a,c}

W∷ =de|fg FIRST(W) = {d,f}

只要不相交就可以根据输入符号确定

目标，若相交，则要代入，并再次提

取左因子。如：V::= ab w::= ac

Z∷ =V|W

则：Z::= a (b|c)

北京航空航天大学计算机学院

2

3

例2：文法G[<程序>]

<

<

<

程序> ∷ = <分程序>| <复合语句>

分程序>∷ = begin<说明串>；<语句串> end

复合语句>∷ = begin<语句串> end

FIRST(<分程序>) = {begin }

FIRST(<复合语句>) = {begin }

改写文法：

<

程序> ∷ = begin （<说明串>；<语句串> end |

语句串> end ）

<

引入 <程序*>

<

<

程序> ∷ = begin <程序*>

程序*> ∷ = <说明串>；<语句串> end | <语句串> end

北京航空航天大学计算机学院

2

4

<

<

程序> ∷ = begin <程序*>

程序*> ∷ = <说明串>；<语句串> end | <语句串> end

对于：<程序*>

FIRST( <说明串>；<语句串> end)

=

{real, integer, boolean, array, function, procedure }

FIRST( <语句串>end )

{标识符，goto, begin, if, for}

=

不相交。

北京航空航天大学计算机学院

2

5

2

.超前扫描

当文法不满足避免回溯的条件时，即各选择的首符号相

交时，可以采用超前扫描的方法，即向前侦察各输入符

号串的第二个、第三个符号来确定要选择的目标

这种方法是通过向前多看几个符号来确定所选择的目

标，从本质上来讲也有回溯的味道，因此比第一种方

法费时，但是假读仅仅是向前侦察情况，不作任何语

义处理工作。

北京航空航天大学计算机学院

2

6

例：

<

<

<

程序> ∷ = <分程序>| <复合语句>

分程序>∷ = begin<说明串>；<语句串> end

复合语句>∷ = begin<语句串> end

这两个选择的首符号是相交的，故读到begin时并不能确定

该用哪个选择，这时可采用向前假读进行侦察，此例题只

需假读一次就可以确定目标。

因为<说明串>的首符集为{real，integer，……，procedure}

而<语句串>的首符集为{标识符，if ，for，……，begin}

∴只要超前假读得到的是“说明”的首符，便是第一个选择；

若是“语句”的首符，就是第二个选择。

北京航空航天大学计算机学院

2

7

文法的两个条件

为了在不采取超前扫描的前提下实现不带回溯的自顶向

下分析，文法需要满足两个条件：

1、文法是非左递归的；

2、 对文法的任一非终结符，若其规则右部有多个选择时， 各选择

所推出的终结符号串的首符号集合要两两不相交。

[

定义] 设文法G（不具有左递归性），UVn

U::=  |  | 

1

2

3

*

FIRST(αi) = {a | αi  a…, a Vt }

为避免回溯，对文法的要求是:

FIRST(αi) ∩ FIRST(αj)=φ (ij)

在上述条件下，就可以根据文法构造有效的、不带回溯的

自顶向下分析器。

北京航空航天大学计算机学院

2

8

4

.2.3 递归子程序法（递归下降分析法）

具体做法：对语法的每一个非终结符都编一个分析程序，

当根据文法和当时的输入符号预测到要用某个非终结符

去匹配输入串时，就调用该非终结符的分析程序。

下面通过举例说明如何根据文法构造该文法的

语法分析程序

北京航空航天大学计算机学院

2

9

如文法G[Z]: Z ::= UV

U ::= ….

V ::= ….

Z的分析程序

U的分析程序

V的分析程序

U

V

注：消除左递归后，可有其它递归：

U ::= …U…

U ::= …W…

W::= …U…

北京航空航天大学计算机学院

3

0

例：文法G[Z]

Z∷ =‘(’U‘)’|aUb

U∷ =dZ|Ud|e

1

.检查并改写文法

改写后无左递归且首符集不相交：

Z∷ =‘ (’U‘) ’|aUb

U∷ =(dZ|e){d}

{

{

(}∩{a}=φ

d}∩{e}=φ

2

.检查文法的递归性

+

Z¨·U¨·¨·Z¨·

U¨·Z¨·¨·U¨·

∴Z¨·Z¨·

+

∴U¨·U¨·

因此，Z和U的分析程序要编成递归子程序

北京航空航天大学计算机学院

3

1

3

.算法框图

非终结符号的分析子程序的功能是：

用规则右部符号串去匹配输入串。

以下是以框图形式给出的两个子程序:

北京航空航天大学计算机学院

3

2

入口

F

F

F

error

(sym)=‘(’

(sym) =‘a’

Y

T

读符号

读符号

U

U

F

error

(sym) =‘)’

T

(sym) =‘b’

T

读符号

出口

北京航空航天大学计算机学院

3

3

入口

F

F

error

(sym)=‘d’

(sym) =‘e’

Y

T

读符号

读符号

Z

(sym) =‘d’

T

F

读符号

出口

北京航空航天大学计算机学院

3

4

说明

要注意子程序之间的接口,在程序编制时进入某个非终结

•

符的分析程序时其所要分析的语法成分的第一个符号已

读入sym中。

递归子程序法对应的是最左推导过程

北京航空航天大学计算机学院

3

5

4

.2.4 用递归子程序法构造语法分析程序的例子

文法: <语句>∷ = <变量>∶ =<表达式>

IF <表达式> THEN <语句>

IF <表达式> THEN <语句> ELSE <语句>

|

|

<

<

<

<

变量>∷ = i | i ‘[’<表达式>‘]’

表达式>∷ = <项>| <表达式> + <项>

项>∷ = <因子>| <项>* <因子>

因子>∷ = <变量>| ‘(’<表达式>‘)’

改写文法: <语句>∷ = <变量>∶ =<表达式>

|

IF<表达式>THEN<语句>[ELSE <语句>]

<

<

<

<

变量>∷ = i[‘[’<表达式>‘]’]

表达式>∷ = <项>{+<项>}

项>∷ = <因子>{*<因子>}

因子>∷ = <变量>|‘(’<表达式>‘)’

北京航空航天大学计算机学院

3

6

语法分析程序所要调用的子程序:

nextsym: 词法分析程序, 每调用一次读进一个单词,

单词的类别码放在sym中。

error:

出错处理程序。

北京航空航天大学计算机学院

3

7

PROCEDURE state;

IF sym =‘IF’ THEN

/*语句分析子程序*/

BEGIN nextsym; expr;

IF sym≠‘THEN’ THEN error

ELSE BEGIN nextsym; state;

IF sym= ‘ELSE’

THEN BEGIN

nextsym;

state;

END

END

END

ELSE BEGIN var;

IF sym≠‘∶ =’

THEN error

ELSE BEGIN

nextsym;

expr;

END

END

北京航空航天大学计算机学院

3

8

PROCEDURE var;

IF sym ≠‘i’ THEN error

ELSE BEGIN nextsym;

IF sym=‘[’ THEN

BEGIN nextsym;

expr;

/*变量*/

IF sym ≠‘]’

THEN error

ELSE nextsym;

END

END

北京航空航天大学计算机学院

3

9

<语句>∷ = <变量>∶ =<表达式>

|

IF<表达式>THEN<语句>[ELSE <语句>]

<

<

<

<

变量>∷ =i[‘[’<表达式>‘]’]

表达式>∷ =<项>{+<项>}

项>∷ =<因子>{*<因子>}

因子>∷ =<变量>|‘(’<表达式>‘)’

PROCEDURE expr;

BEGIN term;

/*表达式*/

WHILE sym=‘+’ DO

BEGIN nextsym;

term;

END

END;

北京航空航天大学计算机学院

4

0

PROCEDURE term;

BEGIN factor;

/*项*/

WHILE sym=‘*’ DO

BEGIN nextsym; factor END

END;

PROCEDURE factor;

BEGIN

/*因子*/

IF sym=‘(’ THEN

BEGIN nextsym; expr;

IF sym ≠‘)’

THEN error

ELSE nextsym

END

ELSE var;

END

北京航空航天大学计算机学院

4

1

4

.2.5 LL分析法

LL－自左向右扫描、自左向右地分析和匹配输入串。



分析过程表现为最左推导的性质。

1

、LL分析程序构造及分析过程

输入串

#

由三部分组成:

分析表

执行程序

符号栈

#

执行程序 (总控程序）

符号栈 （分析栈）

分析表

北京航空航天大学计算机学院

4

2

在实际语言中，每一种语法成分都有确定的左右界

符，为了研究问题方便，统一以‘＃’表示。

（

1）、分析表：二维矩阵M

A∷ =αi

αi∈V*

A ∈Vn

M[A,a]= 或

error

a ∈ Vt or #

北京航空航天大学计算机学院

4

3

M[A,a] = A∷ =αi

表示当要用A去匹配输入串时，且当前输

入符号为a时，可用A的第i个选择去匹配。

*

即 当αi≠ε时，有αi a…;

当αi＝ε时，则a为A的后继符号。

M[A,a] = error

表示当用A去匹配输入串时，若当前输入符

号为a，则不能匹配，表示无Aa…,或a不是A的

*

后继符号。

北京航空航天大学计算机学院

4

4

（

2）符号栈: 有四种情况

•

开始状态

xxxxxx#

符号栈

#

E

E#

a

•

工作状态

X



i

X::=

a……#

查分析表得：

X ∈Vn, M[X,a] = X∷ =αi

X⁺ a…

符号栈

#

…..X

X….#

X ∈Vt, X = a

北京航空航天大学计算机学院

4

5

a

•

出错状态

X error

a……#

查分析表得：

X ∈Vn, M[X,a] = error

无X⁺ a…

符号栈

#

…..X

X….#

X ∈Vt, X  a

•

结束状态

#

符号栈

#

#

北京航空航天大学计算机学院

4

6

a……#

符号栈

#

…..X

（

3）执行程序

X….#

执行程序主要实现如下操作:

1

2

. 把#和文法识别符号E推进栈, 读入下一个符号，

重复下述过程直到正常结束或出错。

. 测定栈顶符号X和当前输入符号a,执行如下操作:

(1) 若X=a=#，分析成功，停止。E匹配输入串成功。

(2) 若X=a≠#，把X推出栈，再读入下一个符号。

(3) 若X∈Vn，查分析表M。

北京航空航天大学计算机学院

4

7

(3) 若X∈Vn，查分析表M

a) M[X,a] = X∷ = UVW

#

…..X

#…..WVU

UVW….#

则将X弹出栈，将UVW压入

注：U在栈顶 （最左推导）

X….#

b) M[X, a] = error 转出错处理

c) M[X, a] = X::=ε，

a

—

a为X的后继符号

X

X::=UVW

则将X弹出栈 (不读下一符号)

继续分析。

北京航空航天大学计算机学院

4

8

例：文法G[E]

E ::= E +T | T

消除左递归

E ::= TE’

T ::= T * F | F

F ::= (E)|i

E ::= +TE’|ε

T ::= FT’

T’ ::= *FT’|ε

F ::= (E)|i

北京航空航天大学计算机学院

4

9

分析表

i

+

*

(

)

#

E E ::= T E '

E ::=

T E '

E '

E '::=

E '::=ε E '::=ε

T '::=ε T '::=ε

+

T E '

T T::= F T '

T '

T::=

FT '

T '::= T '::=

FT '

*

ε

F

F ::=

F ::= i

(E )

注：矩阵元素空白表示Error

北京航空航天大学计算机学院

5

0

输入串为: i+i*i#

步骤

符号栈

＃E

读入符号

剩余符号串

+i*i#

使用规则

1

2

3

4

5

6

7

.

.

.

.

.

.

.

E#

i

i

＃E’T

TE’#

+i*i#

E::=TE’

T::=FT’

F::= i

＃E’T’F FT’E’#

＃E’T’ i iT’E’#

＃E’T’ T’E’#

i

+i*i#

i

+i*i#

+

＋

＋

i*i#

i*i#

i*i#

(出栈，读下一个符号）

T::= ε

＃E’

E’#

＃E’T+ +TE’#

E’::=+TE’

北京航空航天大学计算机学院

5

1

步骤

符号栈

＃E’T

读入符号

剩余符号串

使用规则

8

9

1

.

i

*i#

*i#

*i#

i#

.

＃E’T’F

＃E’T’ i

＃E’T’

＃E’T’F*

＃E’T’F

＃E’T’ i

＃E’T’

＃E’

i

T::=FT’

F::= i

0.

i

11.

*

*

i

1

1

1

1

1

1

2.

3.

4.

5.

6.

7.

i#

T’::=*FT’

F::= i

#

i

#

#

#

#

T’::= ε

E’::= ε

＃

北京航空航天大学计算机学院

5

2

推导过程：

E  TE'  FT'E'  iT'E' iE'







i+TE'  i+FT'E'  i+iT'E'

i+i*FT'E'  i+i*iT'E'

i+i*iE'  i+i*i

最左推导。

北京航空航天大学计算机学院

5

3

2

、分析表的构造

设有文法G[Z]:

*

定义：FIRST(α)={a| αa…，a∈Vt}

α∈V_* , 若αε，则ε∈FIRST(α)

*

该集合称为α的头符号集合。

*

定义：FOLLOW(A)={a| Z…Aa…，a∈Vt}

A∈Vn , Z识别符号

该集合称为A的后继符号集合。

*

特殊地：若Z ...A 则 #∈FOLLOW(A)

北京航空航天大学计算机学院

5

4

构造集合FIRST的算法

设α=X X ...X ,

X ∈V V

t

1

2

n

i

n

求FIRST(α)=?

首先求出组成α的每一个符号X_i的FIRST集合

(1) 若Xi∈Vt，则 FIRST(Xi) = {Xi}

(2) 若Xi ∈Vn 且 Xi∷ =a…..|ε， a ∈Vt

则 FIRST(Xi)={a，ε}

北京航空航天大学计算机学院

5

5

(3) 若Xi ∈Vn 且Xi∷ =y1 y2 …yk，则按如下顺序计算FIRST(Xi)

FIRST(Xi)  FIRST(y1) –{ε}；

若ε∈FIRST(y1) 则将FIRST(y2)-{ε}加入FIRST(Xi)；

若ε∈FIRST(y1)

ε∈FIRST(y2) 则将FIRST(y3)-{ε}加入FIRST(Xi)

.

.......

若ε∈FIRST(yk-1) 则将FIRST(yk)-{ε}加入FIRST(Xi)

若ε ∈FIRST(y1) ～ FIRST(yk)

则将ε加入FIRST(Xi)

注意：要顺序往下做，一旦不满足条件，过程就要中断进行

得到FIRST(Xi)，即可求出FIRST(α)

北京航空航天大学计算机学院

5

6

2

.构造集合FOLLOW的算法

设S, A, B∈V_n ,

算法：连续使用以下规则，直至FOLLOW集合不再扩大

(1) 若S为识别符号,则把“#”加入FOLLOW(S)中

(2) 若A∷ =αBβ (β≠ε),则把FIRST(β)-{ε}加入FOLLOW(B)

*

(3) 若A∷ =αB 或A∷ =αBβ， 且βε则把FOLLOW(A)加

入FOLLOW(B)

注：FOLLOW集合中不能有ε

北京航空航天大学计算机学院

5

7

2

、构造分析表

基本思想是:

终结符号

当文法中某一非终结符

呈现在栈顶时,根据当前

的输入符号,分析表应指

示要用该非终结符的哪

一条规则去匹配输入串

(即进行一步最左推导)

非

终

结

符

号

根据这个思想, 不难把构造分析表算法构造出来!

北京航空航天大学计算机学院

5

8

算法：

设A∷ =αi为文法中的任意一条规则，a为任一终结符或#。

1

、若a ∈FIRST（αi ），则A::= αi ==> M[A,a]

表示：A在栈顶，输入符号是a，应选择αi 去匹配

、若αi =ε或αi ⁺ ε,而且a ∈FOLLOW（A），

则A::= αi ==>M[A,a]，表示A已经匹配输入串成功，

其后继符号终结符a由A后面的语法成分去匹配。

、把所有无定义的M[A,a]都标上error

2

3

北京航空航天大学计算机学院

5

9

例：G[E]分析表的构造

E∷ =TE’

E’∷ =+TE’|ε

T∷ =FT’

求FIRST ：

FIRST(F)={(,i}

T’∷ =*FT’|ε

F∷ =(E)|i

FIRST(T’)={*,ε}

FIRST(T)=FIRST(F)-{ε}={(,i}

FIRST(E’)={+,ε}

FIRST(E)= FIRST(T)-{ε}={(,i}

∴

FIRST(TE’)=FIRST(T)-{ε}={(,i}

FIRST(+TE’)={+}

FIRST(ε)={ε}

FIRST(FT’)= FIRST(F)-{ε}={(,i}

FIRST(*FT’)={*}

FIRST(（E）)={(}

FIRST(ε)={ε}

FIRST(i)={i}

北京航空航天大学计算机学院

6

0

E∷ =TE’

E’∷ =+TE’|ε

T∷ =FT’

T’∷ =*FT’|ε

F∷ =(E)|i

求FOLLOW

FOLLOW(E)={#, )} ∵因为E是识别符号∴#∈FOLLOW(E)

又F∷ =(E) ∴ )∈FOLLOW(E)

FOLLOW(E’)={#, )} ∵E∷ =TE’ ∴FOLLOW(E)加入

FOLLOW(E’)

FOLLOW(T)={+, ), #} ∵E’∷ =+TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T)

又E’ε，∴ FOLLOW(E’)加入FOLLOW(T)

FOLLOW(T’)= FOLLOW(T)= {+,),#}

∵T∷ =FT’ ∴ FOLLOW(T)加入FOLLOW(T’)

FOLLOW(F)={*, + , ), #} ∵T∷ =FT’ ∴ FOLLOW(F)=FIRST（T’）-{ε}

*

又T’ε∴ FOLLOW(T)加入FOLLOW(F)

北京航空航天大学计算机学院

6

1

构造分析表

i

+

*

(

)

#

E E::=TE’

E

E::=TE’

E’∷ =+TE’

E’∷ =εE’∷ =ε

T’∷ =εT’∷ =ε

’

T T::=FT’

T::=FT’

T

’

T’∷ =ε T’∷ =*FT’

F F∷ =i

F∷ =(E)

注意:用上述算法可以构造出任意给定文法的分析表,但不是所有

文法都能构造出上述那种形状的分析表即M[A,a]=一条的规则或

Error。对于能用上述算法构造分析表的文法称为LL(1)文法

北京航空航天大学计算机学院

6

2

3

、LL(1)文法

定义：一个文法G，其分析表M不含多重定义入口(即分

析表中无二条以上规则)，则称它是一个LL(1)文法.

定理：文法G是LL(1)文法的充分必要条件是：对于G的

每一个非终结符A的任意两条规则A::=α|β,下列条件成立：

1

2

、FIRST(α) ∩FIRST(β) = Ф

*

、若β==> ε, 则FIRST(α) ∩FOLLOW(A) = Ф

北京航空航天大学计算机学院

6

3

用此构造分析表的算法,可以构造任何文法的分析表,

但对于某些文法,有些M[A,a]中可能有若干条规则,这称

为分析表的多重定义或者多重入口。

可以证明: 如果G是左递归的,或者是二义性的文法,则至少有一

个多重入口。

U∷ =U…| a …

则有：FIRST(U…)∩FIRST(a…)≠φ

左递归:

∴

M[U,a]={U∷ =U…, U∷ =a…}

对文法所定义的某些句子存在着两个最左推导,

即在推导的某些步上存在多重定义,有两条规则

可用，所以分析表是多重定义的。

二义文法:

北京航空航天大学计算机学院

6

4

4

、LL分析的错误恢复----补充（不要求)

当符号栈顶的终结符和下一个输入符号不匹配,或栈

顶是非终结符A, 输入符号a,而M[A,a]为空白(即error)时,

分析发现错误。

错误恢复的基本思想是: 跳过一些输入符号,直到期望

的同步符号之一出现为止。

同步符号(可重新开始继续分析的输入符号)集合通

常可按以下方法确定:

北京航空航天大学计算机学院

6

5

1

2

) 把FOLLOW(A)的所有符号加入A的同步符号集合，跳过输

入符号直到出现FOLLOW(A)的元素, 便把A从栈中弹出,

继续往下分析。

) 为了避免仅按1)来确定同步符号集合会使跳读过多(如输入

串中缺少语句结束符号“;”)，可将程序高层语法结构(成分)的

开始符号(通常是关键词)加入到低层语法结构的同步集合中。

3

4

5

) 把FOLLOW(A)的符号加入A的同步集合中。

) 如果栈顶的非终结符号A可以产生空串,可以将A从栈中弹出。

) 如果终结符在栈顶而不能匹配,则可弹出该终结符,继续分析，

这好比把所有其他符号均作为该符号的同步集合元素。

北京航空航天大学计算机学院

6

6

4.3 自底向上分析

基本算法思想:

若采用自左向右的描述和分析输入串,那么自

底向上的基本算法是：

从输入符号串开始，通过重复查找当前句型的句

柄(最左简单短语)，并利用有关规则进行归约，若能

归约为文法的识别符号，则表示分析成功，输入符号

串是文法的合法句子，否则有语法错误。

北京航空航天大学计算机学院

6

7

分析过程是重复以下步骤：

1

、找出当前句型的句柄 x （或句柄的变形）

2

3

、找出以 x 为右部的规则 X::= x

、把 x 归约为X，产生语法树的一枝

关键：找出当前句型的句柄 x (或其变形），这不是很容易。

北京航空航天大学计算机学院

6

8

主要内容：

•

•

•

自底向上分析的一般过程（移进-归约分析）

算符优先分析法

LR分析法

北京航空航天大学计算机学院

6

9

4

.3.1 移进—归约分析（Shift-reduce parsing)

要点：建立符号栈，用来记录分析的历史和现状，

并根据所面临的状态，确定下一步动作是移

进还是归约。

输入串

#

符号栈

S.R.P

#

北京航空航天大学计算机学院

7

0

分析过程：把输入符号串按扫描顺序一一地移进

符号栈（一次移一个），检查栈中符号，当在栈顶的若

干符号形成当前句型的句柄时，就根据规则进行归约，

将句柄从符号栈中弹出，并将相应的非终结符号压入

栈内（即规则的左部符号），然后再检查栈内符号串是

否形成新的句柄，若有就再进行归约，否则移进符号。

分析一直进行到读到输入串的右界符为止。最后，若栈

中仅含有左界符号和识别符号，则表示分析成功，否则

失败。

北京航空航天大学计算机学院

7

1

例：G[S]:

S ∷ = aAcBe

A∷ = b

输入串为：

abbcde

A∷ = Ab

B∷ = d

输入串为abbcde，检查是否是该文法的合法句子：

若采用自底向上分析，即能否一步步归约当前句型的

句柄 ，最终归约到识别符号S。先设立一个符号栈，将

符号“#”作为待分析的符号串的左右分界符。

作为初始状态，先将符号串的左分界符推进符号栈，作

为栈底符号。

分析过程如下表:

北京航空航天大学计算机学院

7

2

步骤

符号栈

输入符号串

动作

1

#

abbcde#

准备,初始化

2

3

4

5

6

7

8

9

#a

#ab

bbcde#

bcde#

bcde#

cde#

cde#

de#

e#

移进

移进

#aA

归约(A∷ =b)

移进

#aAb

#aA

归约(A∷ =Ab)

移进

#aAc

#aAcd

#aAcB

#aAcBe

#S

移进

e#

归约(B∷ =d)

移进

10

#

11

#

归约(S∷ =aAcBe)

成功

12

#S

#

北京航空航天大学计算机学院

7

3

这一方法简单明了,不断地进行移进归约,关键是确定

当前句型的句柄。

说明: 1) 例子的分析过程是一步步地归约当前句型的句柄

S

该句子的唯一语法树为:

A

B

A

a b b c d e

北京航空航天大学计算机学院

7

4

注意两点：

（

1）栈内符号串 + 未处理输入符号串 = 当前句型

2）句柄都在栈顶

（

实际上，以上分析过程并未真正解决句柄的识别问题

北京航空航天大学计算机学院

7

5

2

) 未真正解决句柄的识别。

上述分析过程是怎样识别句柄的，主要看栈顶符号串

是否形成规则的右部。

这种做法形式上是正确的，但在实际上不一定正确。

举例的分析过程可以说是一种巧合。

因为不能认为: 对句型 xuy 而言

若有U∷ = u，即Uu 就断定u是简单短语，

*

u 就是句柄，而是要同时满足 Z xUy

北京航空航天大学计算机学院

7

6

4

.3.2 算符优先分析(Operator-Precedence Parsing)

1

) 这是一种经典的自底向上分析法，简单直观，并被广泛使

用，开始主要是对表达式的分析，现在已不限于此。可以

用于一大类上下无关的文法。

2

) 称为算符优先分析是因为这种方法是仿效算术式的四则运算

而建立起来的，作算术式的四则运算时，为了保证计算结果

和过程的唯一性，规定了一个统一的四则运算法则，规定运

算符之间的优先关系。

1

2

3

.乘除的优先级大于加减

.同优先级的运算符左大于右

.括号内的优先级大于括号外

运算法则:

于是： 4+8-6/2*3 运算过程和结果唯一

北京航空航天大学计算机学院

7

7

3

) 算符优先分析的特点:

仿效四则运算过程，预先规定相邻终结符之间的优

先关系，然后利用这种优先关系来确定句型的“句柄” ，

并进行归约。

4

) 分析器结构:

输入串

#

分析程序

符号栈

#

优先关系矩阵

北京航空航天大学计算机学院

7

8

例: G[E]

E∷ =E+E | E*E | (E) | i

Vt={+, *, (, ), i}

这是一个二义文法，要用算符优先法分析由该文法所确定的

语言句子， 如：i+i*i

(1) 先确定终结符之间的优先关系

优先关系的定义:

设 a, b 为可能相邻的终结符

定义: a =_. b

a的优先级等于b

a的优先级小于b

a的优先级大于b

.

a< b

.

a > b

北京航空航天大学计算机学院

7

9

1

) 例中文法终结符之间的优先关系可以用一个矩阵M来表示

b(右,栈外)

+

*

i

(

)

#

a(左,栈内)

.

. . . . .

+

>

<

<

<

>

>

.

. . . . .

*

i

>

>

<

<

>

>

.

.

^.> ^.

>

>

>

.

. . . .

(

<

<

<

<

=

.

.

^.> ^.

)

>

>

>

.

. . .

#

<

<

<

<

北京航空航天大学计算机学院

8

0

2

) 矩阵元素空白处表示这两个终结符不能相邻,故没有

优先关系

(2) 分析过程

算法:

i+i*i

当栈顶项(或次栈顶项)终结符的优先级大于

栈外的终结符的优先级，则进行归约，否则

移进。

北京航空航天大学计算机学院

8

1

E∷ =E+E | E*E | (E) | i

步骤

符号栈

输入串

i+i*i#

+i*i#

+i*i#

i*i#

优先关系

#<i

动作

移进

归约

移进

移进

归约

1

#

2

3

4

5

#i

i>+

#E

#<+

#E+

#E+i

+<i

*i#

i>*

6

7

8

#E+E

#E+E*

#E+E*i

*i#

i#

#

+<*

*<i

i>#

移进

移进

归约

9

#E+E*E

#E+E

#E

#

#

#

*>#

+>#

归约

归约

接受

10

11

分析过程是从符号串开始,根据相邻终结符之间的优先

关系确定句型的“句柄”,并进行归约,直到识别符号E,最

后分析成功: i+i*i∈L(G[E])

出错情况:

1

2

3

. 相邻终结符之间无优先关系

. 对双目运行符进行归约时,符号栈中无足够项

. 非正常结束状态

北京航空航天大学计算机学院

8

3

重要说明

(1) 上述分析过程不一定是严格的最左归约（即不一定是

规范归约）也就是每次归约不一定是归约当前句型的

句柄，而是句柄的变形，但也是短语。

(2) 文法的终结符优先关系可以用一个矩阵表示,也可以用

两个优先函数来表示：

f—栈内优先函数

g—栈外优先函数

若 a < b 则令 f(a) < g(b)

.

.

.

a = b

a > b

f(a) = g(b)

f(a) > g(b)

北京航空航天大学计算机学院

8

4

根据这些原则,构造出上述文法的优先函数:

算符优先函数值的确定方法

1

2

. 把各算符优先级由小到大定为j=0～n

#

（ + * ） i

0

0 1 2 3

. 对于各算符的优先顺序

若为左结合,则 f (op)=2j g (op)=2j-1

若为右结合,则 f (op)=2j g (op)=2j

设m>2n, 则 f (j) = f (i) = m+1

g (j) = g (i) = m，其他为0

f(#) = f(() = g(#) = g()) = 0

北京航空航天大学计算机学院

8

5

+

*

(

) i

0 5 5 0

6 0 6 0

#

f(栈内) 2 4

g(栈外) 1 3

f(+) > g(+)

f(+) < g(*)

f(+) < g(()

：

左结合

先乘后加

先括号内后括号外

：

北京航空航天大学计算机学院

8

6

特点:

(1) 优先函数值不唯一

(2) 优点：

•

节省内存空间

若文法有n个终结符，则关系矩阵为n₂

而优先函数为2n

•

易于比较：算法上容易实现,数与数比,不必

查矩阵。

(3) 缺点：可能掩盖错误。

北京航空航天大学计算机学院

8

7

(3) 可以设立两个栈来代替一个栈

运算对象栈(OPND)

运算符栈(OPTR)

优点：便于比较,只需将输入符号与运算符栈的

栈顶符号相比较

(4) 使用算符优先分析方法可以分析二义性文法所产生的语言

二义性文法按规范分析，其句柄不唯一

例: G[E]

这是一个二义性文法,

i+i*i有两棵语法树

E∷ =E+E|E*E|(E)|i

Vt={+, *, (, ), i}

北京航空航天大学计算机学院

8

8

E

E

5

5

E

+

E

E

*

E

4

3

1

4

E * E

E + E

i

i

2

3

1

2

i

i

i

i

按规范归约,句柄不唯一, E+E*i 所以整个归约过程就

不唯一,编译所得的结果也将不唯一。

北京航空航天大学计算机学院

8

9

4

.3.3 算符优先分析法的进一步讨论

三个问题:

(1) 算符优先文法(OPG)

(2) 构造优先关系矩阵

(3) 算符优先分析算法的设计

北京航空航天大学计算机学院

9

0

（

1）算符优先文法（OPG－Operator Precedence Grammar）

算符文法（OG）的定义

若文法中无形如U∷ = ·¨VW·¨的规则，这里V,W∈Vn

则称G为OG文法，也就是算符文法。

优先关系的定义

若G是一OG文法，a,b∈Vt , U,V,W∈Vn

分别有以下三种情况:

北京航空航天大学计算机学院

9

1

.

1

2

3

) a=b iff 文法中有形如 U∷ = ·¨ab·¨或U∷ = ·¨aVb·¨

的规则。

.

) a<b iff 文法中有形如 U∷ =·¨aW·¨的规则，其中

W b·¨或W Vb·¨ 。

+

+

.

) a>b iff 文法中有形如 U∷ =·¨Wb·¨的规则, 其中

+

+

W ·¨a或W ·¨aV 。

北京航空航天大学计算机学院

9

2

例：文法G[E]

E::= E + T | T

T::= T * F | F

F::= ( E ) | i

E::=E + T

E => E + T ∴ + >· +

T => T * F ∴ + <· *

T =>F =>( E ) ∴ + (

<

·

T =>F =>i ∴ + i

<

·

F::= ( E )

E => E + T ∴ + ·> )

∴

∴

( )

( <· +

=

·

北京航空航天大学计算机学院

9

3

算符优先文法（OPG）的定义

设有一OG文法，如果在任意两个终结符之间，至多只有

上述关系中的一种，则称该文法为算符优先文法(OPG)

对于OG文法的几点说明:

(1) 运算是以中缀形式出现的

(2) 可以证明，若文法为OG文法，则不会出现两个非

终结符相邻的句型。

(3) 算法语言中的表达式以及大部分语言成分的文法均

是OG文法

北京航空航天大学计算机学院

9

4

（

2）构造优先关系矩阵

.

•

求 “ = ” 检查每一条规则，若有U::=…ab…或

.

U::=…aVb…, 则 a=b

.

.

•

求“ < ”、“ > ” ，需定义两个集合

+

+

FIRSTVT( U ) = {b|Ub…或UVb…,b∈Vt, V∈Vn}

+

+

LASTVT( U ) = {a|U…a或U…aV,a∈Vt, V∈Vn}

北京航空航天大学计算机学院

9

5

.

.

•

求“ < ”、“ > ”:

若文法有规则

W∷ =...aU... ，对任何b, b∈FIRSTVT(U)

.

则有：a < b

若文法有规则

W∷ =...Ub... ，对任何a, a∈LASTVT(U)

.

则有：a > b

北京航空航天大学计算机学院

9

6

构造FIRSTVT(U)的算法

+

+

1

) 若有规则U∷ = b…或U∷ = Vb…(存在Ub…或UVb…)

则b∈FIRSTVT(U)

2

) 若有规则U∷ = V…且b∈FIRSTVT(V), 则b∈FIRSTVT(U)

+

+

+

说明:因为Vb…或VWb…, 所以有UV…b…或

UV… ⁺ Wb…

北京航空航天大学计算机学院

9

7

具体方法如下:

设一个栈S和一个二维布尔数组F

F[U,b]=TRUE iff b∈FIRSTVT(U)

PROCEDURE INSERT(U,b)

IF NOT F[U,b] THEN

BEGIN

F[U,b]:=TRUE;

把(U,b)推进S栈 /* b∈FIRSTVT(U) */

END

BEGIN {main}

FOR 每个非终结符号U和终结符b DO

F[U,b]:=FALSE;

FOR 每个形如U::=b…或U::=Vb… 的规则 DO

INSERT(U,b);

北京航空航天大学计算机学院

9

8

WHILE S栈非空 DO

BEGIN

把S栈的栈顶项弹出,记为 (V,b) /* b∈FIRSTVT(V)*/

FOR 每条形如U::=V…的规则 DO

INSERT (U,b); /* b∈FIRSTVT(U)*/

END OF WHILE

END

上述算法的工作结果是得到一个二维的布尔数组F,从F

可以得到任何非终结符号U的FIRSTVT

FIRSTVT(U) = { b | F[U,b] = TRUE }

北京航空航天大学计算机学院

9

9

构造LASTVT(U)的算法

1

2

. 若有规则U::=…a或U::=…aV,则a∈LASTVT(U)

. 若有规则U::=…V,且a∈LASTVT(V), 则a∈LASTVT(U)

设一个栈ST,和一个布尔数组B

PROCEDURE INSERT(U,a)

IF NOT B[U,a] THEN

BEGIN

B[U,a]::=TRUE; 把(U,a)推进ST栈;

END;

北京航空航天大学计算机学院

1

00

BEGIN

FOR 每个非终结符号U和终结符号a DO

B[U,a]:=FALSE;

FOR 每个形如U::=…a或U::=…aV的规则 DO

INSERT (U,a);

WHILE ST栈非空 DO

BEGIN

把ST栈的栈顶弹出,记为(V,a);

FOR 每条形如U::=…V的规则 DO

INSERT(U,a);

END OF WHILE;

END;

北京航空航天大学计算机学院

1

01

构造优先关系矩阵的算法

FOR 每条规则U::=x1x2…xn DO

FOR i:=1 TO n-1 DO

BEGIN

IF xi和xi+1均为终结符,THEN 置 xi=^. xi+1

IF i≤n-2，且xi和xi+2都为终结符号但

xi+1为非终结符号 THEN 置 xi=^.xi+2

IF xi为终结符号,xi+1为非终结符号 THEN

FOR FIRSTVT(xi+1)中的每个b DO

.

置xi<b

IF xi为非终结符号,xi+1为终结符号 THEN

FOR LASTVT(xi)中的每个a DO

置a>^. xi+1

END

北京航空航天大学计算机学院

1

02

（

3）算符优先分析算法的实现

先定义优先级，在分析过程中通过比较相邻运算符之

间的优先级来确定句型的“句柄”并进行归约。

[

定义] 素短语：文法G的句型的素短语是一个短语，

它至少包含有一个终结符号，并且除它自身以外不再

包含其他素短语。

北京航空航天大学计算机学院

1

03

例: 文法G[E]

E::=E+T|T

文法的语法树:

T::=T*F|F

F::=(E)|i

求句型T+T*F+i 的素短语

E

+

E

T

F

短语:T+T*F+i, T+T*F

T(最左), T*F, i

E + T

其中T不包含终结符,T是句柄

而T+T*F+i和T+T*F包含其他

素短语。

i

T T * F

只有T*F和i为素短语,其中T*F为最左素短语,而该句型句

柄为T。

北京航空航天大学计算机学院

1

04

句型：T + T + i

短语：T+T+i

T +T

T

i

句柄：T

素短语：T+T, i

北京航空航天大学计算机学院

1

05

算符优先分析法如何确定当前句型的最左素短语？

设有OPG文法句型为:

#

N1a1N2a2…NnanNn+1#

其中Ni为非终结符(可以为空), ai为终结符

定理：一个OPG句型的最左素短语是满足下列条件的

最左子串：aj-1Njaj…NiaiNi+1ai+1

其中 aj-1<_. aj

.

.

.

.

aj=aj+1, aj+1= aj+2 ,…, ai-2= ai-1, ai-1= ai

.

ai> ai+1

北京航空航天大学计算机学院

1

06

根据该定理,要找句型的最左素短语就是要找满足

上述条件的最左子串。

Njaj…NiaiNi+1

注意:出现在aj左端和ai右端的非终结符号一定

属于这个素短语,因为运算是中缀形式给

出的(OPG文法的特点)NaNaNaN NaWaN

例: 文法G[E]

E::=E+T|T

T::=T*F|F

F::=(E)|i

分析文法的句型T+T*F+i

北京航空航天大学计算机学院

1

07

步骤

句型

关系

. . . .

. . .

最左子串 归约符号

.

1

2

3

4

#T+T*F+i# #<+<*>+<i># T*F

T

E

F

E

.

#T+T+i#

#E+i#

#<+>+<i># T+T

.

. .

#<+<i>#

i

.

.

#E+F#

#<+>#

E+F

可以看出:

1

2

3

. 每次归约最左子串,确实是当前句型的

最左素短语(语法树）

. 归约的不都是真句柄（仅i归约为F是句柄，

但它是最左素短语)

. 没有完全按规则进行归约,因为素短语不一

定是简单短语

北京航空航天大学计算机学院

1

08

E

E

E

+

T

F

+

E

T

F

E + T

E

+

T

T * F

i

T

i

T

T

.

. . . .

. . . .

#

<+<*>+<i>#

#<+>+<i>#

E

E

+

T

F

E

+

T

E

FF

.

.

.

. .

i

#<+>#

#

<+<i>#

北京航空航天大学计算机学院

1

09

算符优先分析法的实现：

基本部分是找句型的最左子串（最左素短语）

并进行归约。

输入串

#

分析程序

符号栈

#

优先关系矩阵

当栈内终结符的优先级＜＝栈外的终结符的优先级时，移

进；栈内终结符的优先级＞栈外的终结符的优先级时，表

明找到了素短语的尾，再往前找其头，并进行归约。

北京航空航天大学计算机学院

110

4

.3.4 LR分析法

、概述

1

什么是LR分析：从左到右扫描(L)自底向上进行归约(R)

(是规范归约）, 是自底向上分析方法的高度概括和集中

历史 + 展望 + 现状 => 句柄

(1) LR分析法的优缺点:

1

2

3

4

5

) 适合文法类足够大

) 分析效率高

) 报错及时

) 可以自动生成

) 手工实现工作量大

北京航空航天大学计算机学院

111

(2) LR分析器有三部分: 状态栈 分析表 控制程序

输入串

#

状态栈：放置分析

器状态和文法符号。

状态栈

控制程序

#

分析表

分析表：由两个矩阵组成，其功能是指示分析器的动作，

是移进还是归约，根据不同的文法类要采用不同

的构造方法。

控制程序：执行分析表所规定的动作，对栈进行操作。

北京航空航天大学计算机学院

112

(3) 分析表的种类

a) SLR分析表(简单LR分析表)

构造简单,最易实现,大多数上下文无关文法都

可以构造出SLR分析表,所以具有较高的实用

价值。使用SLR分析表进行语法分析的分析器

叫SLR分析器。

b) LR分析表(规范LR分析表)

适用文法类最大,几乎所有上下文无关文法都能

构造出LR分析表, 但其分析表体积太大，实

用价值不大。

北京航空航天大学计算机学院

113

c) LALR分析表(超前LR分析表)

这种表适用的文法类及其实现上难易在上面

两种之间,在实用上很吸引人。

使用LALR分析表进行语法分析的分析器叫LALR分析器。

例：UNIX----YACC

文法规则文件

YACC源文件

某语言的

LALR分析器

YACC

北京航空航天大学计算机学院

114

(4) 几点说明

1

2

3

. 三种分析表对应三类文法

. 一个SLR文法必定是LALR文法和LR文法

. 仅讨论SLR分析表的构造方法

北京航空航天大学计算机学院

115

2

、LR分析

（1）逻辑结构

输入串：#a a ... a ... a #

1

2

i

n

状态栈

S x S x

分 状

析 态 LR分析器

动 转

作 移

表 表

#

......

x S

m m

0

1 1 2

控

制

程

序

北京航空航天大学计算机学院

116

S S ...... ^Sm

#

S x S x

......

x S

m m

0 1

0

1 1 2

#

x₁x₂..... x_m

S0,S1,…,Sm 状态

状态栈:

S0---初始状态

Sm---栈顶状态

栈顶状态概括了从分析开始到该状态的

全部分析历史和展望信息。

符号串: X X ..... X

m

1

2

为从开始状态(S0)到当前状态(Sm)所识别

的规范句型的活前缀。

北京航空航天大学计算机学院

117

规范句型: 通过规范归约得到的句型。

规范句型前缀: 将输入串的剩余部分与其连接起来就

构成了规范句型。

如： x₁x₂..... x a ... a 为规范句型

m

i

n

活前缀: 若分析过程能够保证栈中符号串均是规范句型

的前缀，则表示输入串已分析过的部分没有语

法错误，所以称为规范句型的活前缀。

北京航空航天大学计算机学院

118

规范句型的活前缀:

对于句型αβt， β表示句柄,如果αβ= u1u2…ur

那么符号串u1u2…ui(1≤i≤r)即是句型αβt的活前

缀

例: 有文法G[E]: E→T|E+T|E-T

T→i|(E)

拓广文法G’[S]: S→E#

E→T|E+T|E-T

T→i|(E)

句型E-(i+i) #

活前缀：E, E-, E-(, E-(i 是句型E-(i+i)# 的活前缀。

北京航空航天大学计算机学院

119

•

分析表

a. 状态转移表 (GOTO表)

GOTO表

符号

E T F i + * ( ) #

状态

S

S

S

:

0

1

2

是一个矩阵：

行---分析器的状态

列---文法符号

S

n

北京航空航天大学计算机学院

1

20

GOTO表

符号

E T F i + * ( ) #

状态

S

S

S

:

0

1

2

S

n

GOTO[Si-1, xi]=Si

Si-1---当前状态(栈顶状态)

xi--- 新的栈顶符号

Si----新的栈顶状态(状态转移)

#

S x S x x S x S

......

1 1 2 i-1 i-1 i i

0

Si需要满足条件是:

若X1 X2…. Xi-1是由S0到Si-1所识别的规范句型的

活前缀,则X1 X2…. Xi是由S0到Si所识别的规范句型

的活前缀。

北京航空航天大学计算机学院

1

21

通过对有穷自动机的了解, 可以看出:

状态转移函数GOTO是定义了一个以文法符

号集为字母表的有穷自动机，该自动机识别文法所

有规范句型的活前缀。

M=(S, V, GOTO, S0, Z )

xi-1

Si-1

S

2

x

2

x

i

S

1

x

1

S

i

S

0

北京航空航天大学计算机学院

1

22

b. 分析动作表(ACTION表)

ACTION表

输入符号a

状态s

+

*

i

( ) #

S

S

S

:

0

1

2

S

n

ACTION[Si,a] = 分析动作 a∈Vt

北京航空航天大学计算机学院

1

23

分析动作：

(1) 移进(shift)

ACTION[Si,a] = s

动作: 将a推进栈，并设置新的栈顶状态Sj

= GOTO[Si,a]，将指针指向下一个

输入符号

S

j

(2) 归约(reduce)

ACTION[Si,a] = r_d

d：文法规则编号 (d) A→β

动作: 将符号串β(假定长度为n)连同状态从栈内

弹出, 把A推进栈, 并设置新的栈顶状态Sj

S

j

= GOTO[Si-n,A]

北京航空航天大学计算机学院

1

24

(3) 接受(accept)

ACTION[Si,#]=accept

(4) 出错(error)

ACTION[Si,a]=error

北京航空航天大学计算机学院

1

25

控制程序: (Driver Routine)

1

2

、 根据栈顶状态和现行输入符号，查分析动

作表(ACTION表)，执行由分析表所规定

的操作；

、并根据GOTO表设置新的栈顶状态(即实现

状态转移)。

北京航空航天大学计算机学院

1

26

（

2） LR分析过程

例：文法G[E]

(1) E ::= E+T

(2) E ::= T

(3) T ::= T*F

(4) T ::= F

(5) F ::= (E)

(6) F ::= i

该文法是SLR文法,故可以构

造出SLR分析表(ACTION表

和GOTO表)

北京航空航天大学计算机学院

1

27

GOTO表

文法符号

状态

E

1

T

2

F

i

+

6

*

(

)

0

1

2

3

4

5

6

7

8

9

1

(S0)

(S1)

3

5

4

(S2)

(S3)

(S4)

(S5)

(S6)

(S7)

(S8)

(S9)

0(S10)

7

8

2

9

3

5

4

3

5

5

4

4

10

6

11

7

11(S11)

北京航空航天大学计算机学院

1

28

ACTION 表

GOTO 表

输入符号

状态

北京航空航天大学计算机学院

1

29

分析过程 i*i+i

步骤 状态栈

符号

＃

输入串

i*i+i#

*i+i#

*i+i#

*i+i#

i+i#

动作

初始化

1

2

3

4

5

6

7

＃0

＃0i5

＃i

S

＃0F3

＃0T2

＃0T2*7

＃F

＃T

＃T*

r6

r4

S

＃0T2*7i5 ＃T*i

＃0T2*7F10 ＃T*F

+i#

S

+i#

r6

北京航空航天大学计算机学院

1

30

8

9

＃0T2

#T

#E

+i#

+i#

i#

#

r3

＃0E1

r2

1

0

＃0E1+6

#E+

S

11

＃0E1+6i5 #E+i

＃0E1+6F3 #E+F

＃0E1+6T9 #E+T

S

1

2

3

4

5

#

r6

1

1

1

#

r4

＃0E1

#E

#E

#

r1

accept

北京航空航天大学计算机学院

1

31

由分析过程可以看到:

E

8

(1) 每次归约总是归约当前句型的句柄,是

规范归约。

E + T

7

5

(算符优先分析归约最左素短语)

T

F

4

6

i

T * F

(2) 分析的每一步栈内符号串均是规范句

型的活前缀,与输入串的剩余部分构成

规范句型。

2

3

i

F

1

i

北京航空航天大学计算机学院

1

32

3

、构造SLR分析表

构造LR分析器的关键是构造其分析表。

构造LR分析表的方法是:

（

1）根据文法构造识别规范句型活前缀的有穷

自动机DFA

（

2）由DFA构造分析表

北京航空航天大学计算机学院

1

33

(1) 构造DFA

DFA 是一个五元式

1

M=(S, V, GOTO, S0, Z)

S：有穷状态集

在此具体情况下，S = LR(0) ，项目集规范族。

项目集规范族：其元素是由项目所构成的集合。

V：文法字汇表

S0：初始状态 S₀∈S

北京航空航天大学计算机学院

1

34

GOTO: 状态转移函数

GOTO[Si,X]=Sj

S

i

,Sj∈S

S

i

,Sj为项目集合

X∈Vn∪Vt

表示当前状态Si面临文法符号为X时，应将状态转移到Sj

Z：终态集合 Z = S-{S0}

即除S0以外，其余全部是终态

构造DFA：

一、确定S集合，即LR（0）项目集规范族，

同时确定S₀

二、确定状态转移函数GOTO

北京航空航天大学计算机学院

1

35

2

构造LR（0）的方法

LR(0) 是DFA的状态集,其中每个状态又都是项目的集合。

项目:文法G的每个产生式(规则)的右部添加一个圆点

就构成一个项目。

例:产生式:A→XYZ

项 目: A→.XYZ

A→X.YZ

A→XY.Z

A→XYZ.

项目的直观意义: 指明在分

析过程中的某一时刻已经归

约的部分和等待归约部分。

产生式:A→ε

项 目: A→.

北京航空航天大学计算机学院

1

36

构造LR(0)的方法(三步)

) 将文法拓广

1

目的：使构造出来的分析表只有一个接受状态,这是

为了实现的方便。

方法：修改文法，使识别符号的规则只有一条。

G[E]

E→···

E→···

G'[E']

E'→E

E→···

E→···

拓广

·

··

·

··

L(G(E))=L(G'[E'])

北京航空航天大学计算机学院

1

37

2

) 根据文法列出所有的项目

3

) 将有关项目组合成集合，即DFA中的状态；

所有状态再组合成一个集合，即LR（0）项目集规范族

通过一个具体例子来说明LR(0)的构造以及DFA

的构造方法。

例：G[E]

E→E+T | T

T→T*F | F

F→(E) | i

北京航空航天大学计算机学院

1

38

1

2

将文法拓广为G’[E’]

(0) E’→E

(1) E→E+T

(2) E→T

(4) T→F

(5) F→(E)

(6) F→i

(3) T→T*F

列出文法的所有项目

(1) E’→.E

(2) E’→E.

(6) E→E+T. (11)T→T*.F (16)F→(.E)

(7) E→.T (12)T→T*F. (17)F→(E.)

(3) E→.E+T (8) E→T.

(13)T→.F

(18)F→(E).

(19)F→.i

(4) E→E.+T (9) T→.T*F (14)T→F.

(5) E→E+.T (10) T→T.*F (15)F→.(E) (20) F→i.

北京航空航天大学计算机学院

1

39

3

将有关项目组成项目集,所有项目集构成的集合即为LR(0)

为实现这一步，先定义：

•

•

项目集闭包closure

状态转移函数GOTO

北京航空航天大学计算机学院

1

40

A.项目集闭包closure的定义和计算:

令I是文法G’的任一项目集合，定义closure(I)为项目

集合I的闭包，可用一个过程来定义并计算closure(I)：

Procedure closure(I);

begin

将属于I的项目加入closure(I);

repeat

for closure(I)中的每个项目A→α.Bβ(B∈Vn) do

将B→.r(r∈V* )加入closure(I)

until closure(I)不再增大

end

北京航空航天大学计算机学院

1

41

B. 状态转移函数GOTO的定义:

GOTO(I,X) = closure(J)

I：项目集合

X：文法符号，X∈V

J：项目集合

J = { 任何形如A→αX.β的项目| A→α.Xβ∈I }

closure(J):项目集J的闭包, 仍是项目集合

所以,GOTO(I,X) = closure(J) 的直观意义是:

它规定了识别文法规范句型活前缀的DFA, 从状态

I(项目集)出发,经过X弧所应该到达的状态(项目集合)

北京航空航天大学计算机学院

1

42

例:

I={E’→E. , E→E.+T} 求GOTO(I , + ) =?

GOTO(I , +) = closure(J)

∵

∴

J = {E→E+.T}

GOTO(I , +) = {E→E+.T , T→.T*F , T→.F ,

F→.(E) , F→.i }

北京航空航天大学计算机学院

1

43

LR(0)和GOTO的构造算法:

G'→LR(0), GOTO

Procedure ITEMSETS(G')

begin

LR(0) := {closure({E'→.E})};

repeat

for LR(0)中的每个项目集I和G'的每个符号X do

if GOTO(I , X)非空,且不属于LR(0)

then 把GOTO(I , X)放入LR(0)中

until LR(0)不再增大

end

北京航空航天大学计算机学院

1

44

例:求G'[E']的LR(0)

G'[E']共有20个项目

V={E, T, F, i, +, *, (, )}

LR(0)={I0,I1,I2,…I11} 由12个项目集组成:

I

0

:

E'→.E

E→.E+T

E→.T

closure({E’→.E}) = I₀

T→.T*F

T→.F

F→.(E)

F→.i

GOTO(I0,E) = closure({E’→E.

E→E.+T})

I1: E'→E.

E→E.+T

=

I

1

北京航空航天大学计算机学院

1

45

I

2

:

E→T.

GOTO(I₀,T) = closure({E→T. T→T.*F}) = I₂

T→T.*F

T→F.

F→(.E)

E→.E+T

E→.T

T→.T*F

T→.F

GOTO(I0,F) = closure({T→F.}) = I3

GOTO(I0,() = closure({F→(.E)}) = I4

I

I

3

:

:

4

F→.(E)

F→.i

I5: F→i.

GOTO(I0,i) =closure({F→i.})= I5

GOTO(I0,*) =φ

GOTO(I0,+) =φ

GOTO(I0,)) =φ

北京航空航天大学计算机学院

1

46

I

6

:

E→E+.T

T→.T*F

T→.F

GOTO(I1,+) = closure({E→E+.T}) = I6

GOTO(I1,其他符号)为空

F→.(E)

F→.i

I

7

:

T→T*.F

F→.(E)

F→.i

GOTO(I2,*) = closure({T→T*.F}) = I7

GOTO(I2,其他符号)为空

GOTO(I3,所有符号)为空

北京航空航天大学计算机学院

1

47

I

8

:

F→(E.)

E→E.+T

GOTO(I4,E) = closure({F→(E.),E→E.+T}) = I8

GOTO(I4,T) = I2 ∈LR(0)

GOTO(I4,F) = I3 ∈LR(0)

GOTO(I4,() = I4 ∈LR(0)

GOTO(I4,i) = I5 ∈LR(0)

GOTO(I4,+) =φ

GOTO(I4,*) =φ

GOTO(I4,)) =φ

GOTO(I5,所有符号) =φ

I

9

:

E→E+T.

T→T.*F

GOTO(I6,T) = closure({E→E+T.,T→T.*F}) = I9

GOTO(I6,F) = I3

GOTO(I6,() = I4

GOTO(I6,i) = I5

北京航空航天大学计算机学院

1

48

I10:T→T*F. GOTO(I7,F) = closure({T→T*F .}) = I10

GOTO(I7,() = I4

GOTO(I7,i) = I5

I11:F→(E). GOTO(I8,)) =closure({F→(E) .}) = I11

GOTO(I8,+) = I6

GOTO(I9,*)= I7

GOTO(I10,所有符号) =φ, GOTO(I11,所有符号) =φ

北京航空航天大学计算机学院

1

49

3

构造DFA

M = (S, V, GOTO, S0, Z)

S = {I0, I1, I2, …, I11} = LR(0)

V = {+, *, i, (, ), E, T, F}

GOTO(Im , X) = In

S

0

= I0

Z = S-{I0} = {I1, I2, …, I11}

M的图解表示如下:

北京航空航天大学计算机学院

1

50

+

T

I

I

I

1

5

3

4

2

I

I

6

i

I

9

E

i

+

i

i

*

start

F

F

I

0

(

8

I11

(

F

I

(

)

E

T

I

7

I10

T

I

(

F

*

北京航空航天大学计算机学院

1

51

关于自动机的说明:

除I₀以外,其余状态都是终态,从I0到每一状态的每条

1

路径都识别和接受一个规范句型的活前缀

如对文法句子i+i*i 进行规范归约

所得到的规范句型的活前缀都可

以由该自动机识别,如:

I0~I1 识别规范句型的活前缀E(+i*i)

I0~I6 识别规范句型的活前缀E+(i*i)

I0~I7 识别规范句型的活前缀E+T*(i)

I0~I9 识别规范句型的活前缀E+T(*i)

I0~I10 识别规范句型的活前缀E+T*F

北京航空航天大学计算机学院

1

52

2

3

状态中每个项目对该状态能识别的活前缀都是

有效的。

有效项目定义:若项目A→β1 .β2 对活前缀αβ1

有效，其条件是存在规范推导

*

E’αAw  αβ1β2 w

其中α,β1,β2 ∈ V *, w ∈ Vt *

注意：项目中圆点前的符号串成为活前缀的后缀

有效项目能预测分析的下一步动作：

E→E+T. 表示已将输入串归约为E+T,下一步应

该将E+T归约为E

*

E’ (E)(E+T)

T→T.*F 表示已将输入串归约为T,下一步动作

是移进输入符号*

注意：经移进或归约后,在栈内仍是规范句型的活前缀

北京航空航天大学计算机学院

1

53

4

DFA中的状态,既代表了分析历史又提供了展望信息

每条规范句型的活前缀都代表了一个确定的

的规范归约过程,故由状态可以代表分析历史。

由于状态中的项目都是有效项目,所以提供了

下一步可能采取的动作。

历史+展望+现实 句柄

北京航空航天大学计算机学院

1

54

（

2）由DFA构造SLR分析表

*

GOTO表在求LR（0）时已求出

GOTO表

文法符号

E

1

T

2

F

3

i

5

+

*

(

4

)

状态

0

1

2

3

4

5

6

7

8

9

1

(S0)

(S1)

(S2)

(S3)

(S4)

(S5)

(S6)

(S7)

(S8)

(S9)

0(S10)

6

7

8

2

9

3

5

4

3

10

5

5

4

4

6

11

7

11(S11)

北京航空航天大学计算机学院

1

55

*

求ACTION表

设k为状态编号,E为原文法识别符号，

E’为扩充文法识别符号

1

、求出文法每个非终结符的FOLLOW集合

2

、若项目A→α.aβ∈k,且a ∈V_t ,则置

ACTION[k,a] = s (移进）

北京航空航天大学计算机学院

1

56

3

、若项目A→α.∈k, 那么对输入符号a,若

a∈FOLLOW(A),则置ACTION[k,a]=r_j

其中A→ α为文法G’的第j个产生式。

4

、若项目E’→E.∈k, 则置

ACTION[ k , # ] =accept

5

、ACTION表中不能用步骤2~4填入信息的

空白格，均置error

北京航空航天大学计算机学院

1

57

在状态中可有三种类型的项目,其中只有两种有移

进或归约动作:

A→α.aβ a∈Vt

A→α.

移进项目 分析动作:移进

归约项目 分析动作:归约

A→α.Bβ B∈Vn 待约项目 无动作

根据上述算法,可以构造出文法G’[E’]的ACTION

北京航空航天大学计算机学院

1

58

对文法G’[E’]

k=2 (I2)

有效项目 E→T.

k=1 (I1)

E’→E.

k=0 (I0)

E’→.E

T→T.*F

E→E.+T

E→.E+T

FOLLOW(E)={#, +, )} FOLLOW(E’)={#} E→.T

T→.T*F

T→.F

F→.(E)

F→.i

根据算法造出的ACTION表为:

北京航空航天大学计算机学院

1

59

ACTION表

输入符号a

状态s

i

+

*

(

)

#

0

1

2

3

4

5

6

S

5

S

4

S

6

accpet

r

2

S

7

r

2

r

2

7

8

9

1

0

1

1

北京航空航天大学计算机学院

1

60

两点说明:

1

. 由DFA构造出的SLR分析表,在造表时, 只需

向前看一个符号就能确定分析的动作是移进还

是归约，所以称为SLR(1)分析表，简称SLR分

析表，使用SLR分析表的分析器叫SLR分析器。

. 对文法G,若应用上述算法所造出的分析表

具有多重定义入口,分析动作不唯一, 则文法

G就不是SLR的，需要用别的方法来构造分析表。

2

北京航空航天大学计算机学院

1

61

复 习

+

自顶向下分析法 Z S

S∈L[Z]

语法分析方法:

+

自底向上分析法 SZ

(一) 自顶向下分析

概述自顶向下分析的一般过程

1

左递归问题 消除左递归的方法

存在问题

无回溯的条件

改写文法

回溯问题

超前扫描

北京航空航天大学计算机学院

1

62

两种常用方法:

2

a) 改写文法,消除左递归,回溯

b) 写递归子程序

(1) 递归子程序法

LL(1)分析器的逻辑结构及工作过程

LL(1)分析表的构造方法

1

2

3

.构造FIRST集合的算法

.构造FOLLOW集合的算法

.构造分析表的算法

(2) LL(1)分析法

LL(1)文法的定义以及充分必要条件

北京航空航天大学计算机学院

1

63

(二) 自底向上分析

归约过程:

(1)一般过程: 移进-归约过程

问题:如何寻找句柄

(2)算法:

i)算符优先分析法:

1

.分析器的构造,分析过程

根据算符优先关系矩阵来决定

是移进还是归约。

北京航空航天大学计算机学院

1

64

2

.算符优先法的进一步讨论

1

2

3

) 适用的文法类--------------引出的算符优先法的定义

) 优先关系矩阵的构造

) 什么是“句柄”,如何找

由句柄引出的最左素短语的概念。