计算机课件计算机之编译原理cpl之自底向上优先分析算法

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

•自底向上优先分析思想概述

•简单优先分析法

•优先关系的含义

•简单优先文法的定义及操作步骤

•算符优先分析法

•算符优先分析法的定义

•算符优先关系表的构造

•优先函数

学习目标

•算符优先分析法是自下而上（自底向上）语法分析的一种，尤其

适应于表达式的语法分析，由于它的算法简单直观易于理解，因

此，也是学习其它自下而上语法分析的基础。通过本章学习应掌

握：

•对给定的文法能够判断该文法是否是算符文法

•对给定的算符文法能够判断该文法是否是算符优先文法

•对给定的算符文法能构造算符优先关系表，并能利用算符优先关

系表判断该文法是否是算符优先文法。

•能应用算符优先分析算法对给定的输入串进行移进■归约分析，

在分析的每一步能确定当前应移进还是归约，并能判断所给的输

入串是否是该文法的句子。

•了解算符优先分析法的优缺点和实际应用中的局限性。

知识点

•算符优先分析法的算法简单、直观、易于理解，所以通常作为学

习其它自下而上语法分析的基础。

•需复习有关语法分析的知识有：什么是语言、文法、句子、句型、

短语、简单短语、句柄、最右推导、规范归约基本概念。

•本章重难点

•算符文法的形式。

•对一个给定的算符文法能构造算符优先关系分析表，并能判别所

给文法是否为算符优先文法。

•分清规范句型的句柄和最左素短语的区别，进而分清算符优先归

约和规范归约的区别。（在分析过程中如何寻找可归约串）

•对一个给定的输入串能应用算符优先关系分析表给出分析（归约）

步骤，并最终判断所给输入串是否为该文法的句子。

语法分析

•推导——自顶向下的语法分析过程

•预测分析程序，递归下降分析法(最左推导)

•要求文法是LL(1)文法

•归约——自底向上的语法分析过程

•简单优先分析法，算符优先分析法

•LR分析法

自底向上的语法分析过程思想::

•自底向上语法分析过程是一个最左归约的过程

（规范推导的逆过程，亦称规范归约），从输入

串开始，朝着文法的开始符号进行归约，直到

到达文法的开始符号为止的过程。

•输入串在这里依然是指从词法分析器送来的单词符

号组成的二元式的有限序列。

•自底向上的下推自动机PDA

•工作方式：“移进-归约”方式

•对输入符号串自左向右进行扫描，并将输入符逐个移入一个后

进先出栈中，在移进过程中不断查看栈顶符号串，一旦串形成

某个句型的句柄时（该句柄对应某产生式的右部），就用该产生

式的左部非终结符代替相应右部的文法符号串（归约）。重复这

一过程直到归约到栈中只剩文法的开始符号时则为分析成功，

也就确认输入串是文法的句子。

•栈顶符号串是指：该符号串包含栈顶符号在内，并由栈中某个

符号为该符号串的头，栈顶符号为该符号串的尾，也可以只包

含一个符号。

•几点说明：

•初态时，栈内仅有栈底符号“毋，读头指在最左以

的单词符号上。

即初态为：栈输入

#W#

语法分析执行的动作：

•移进读入一个单词并压入栈内，读头后移；

•归约检查栈顶若干符号能否进行归约，若能，就以产

生式左部替代该符号串，同时输出产生式编号；

•识别成功移进-归约的结局是栈内只剩下栈底符号和文

法开始符号，读头也指向语句的结束符；

即:直至最终形成如下格局：

标输入

#S#

•识别失败

例6.1文法G[S]产生式如下：

①S—aAcBe②A—b③A—Ab(4

B->d

输入串abbcde是不是文法的句子？

SnaABenaAdenaAbcdenabbcde

S

naAcBe

naAcde

naAbcde

nabbcde

b

G[s]：①S—aAcBe②A—b③A->Ab④B—d

步骤栈输入动作输出带

(1)#abbcde#移进

(2)#abbcde#移进

(3)#abbcde#归约，A-b2

(4)粕Abcde#移进

(5)粕Ab[A—b?cde#归约，A-Ab2,3

(6)#aAIA>/\b?cde#移进

(7)#aAcde#移进

(8)粕Acde#归约，B-d2,3,4

(9)粕AcBe#移进

(10)#aAcBe#归约，SfaAcBe2,3,4,1

(11)#S*接受

没有语法树的提示，如何分析，如何归约？

1.优先分析器：简单优先分析法；算符优先分析

法。

2.LR分析器

6.1自底向上优先分析思想

优先分析法可分为简单优先分析法和算符优先分析法。

•简单优先分析法是对一个文法按一定原则求出该文法所有符号

（V集）之间的优先关系，按照这种关系确定归约过程中的句柄，

实际上，是一种规范归约。

•算符优先分析法的基本思想只考虑算符之间的优先关系，在归

约过程中，只要找到可归约串就归约，不考虑其是否为句柄，

因此，算符优先归约不是规范归约。

优先分析法基本思想

1.相邻文法符号之间的优先关系

在句型中，句柄内各相邻符号之间具有相同的优先级。相同优先级

用'工”表示。

由于句柄要先归约，所以规定句柄两端符号的优先级要比位于句柄

之外的相邻符号的优先级高。优先级低于表示为：优先级高

于表示为：

某句型中：M…NgV,Nj工...丁Nj…4

N^..Nj.^-Nj......Nj->Nj+1...Nn

2.句型中Nj……Nj是句柄，语法分析程序可以通过寻找

岫.产・岫和这两个关系来确定句柄的头尾，从

而确定句柄进行归约。

型吟"G[S]：S—>aBeB—>bc

abce#bee#

6.2简单优先分析法：：

•定义

•一个文法G,如果它不含£产生式,也不含任何右部

相同的不同产生式,并且它的任何符号对(X,Y),

X,Y£V或者没有关系，或者存在优先级相同或低于、

高于等关系之一，则这是一个简单优先文法。

•优先级的定义

•XY当且仅当G中含有形如P一…XY…

•X=Y当且仅当G中含有形如P—…XQ…，且Q+Y-

•X->Y当且仅当G中含有形如P—…QR…，且=>

Q-X,RY-(YeFIRST(R)),YeVTo

例6.2有文法G：S—bAb：：

A—(B|a：：

B—Aa)

解析根据优先级的定义，由文法产生式可求得

文法符号之间的优先关系如下：

1,求工关系：b=A,A=b,(三B,A=a,a=)

2,求v•关系：b<-(,b<-a,(<-A...

3.求:关系：)->b,a->b,),>a,a>a,B->a...

•关于"#”的说明：

•通常把读头下待分析的句子放在一对#的中间，小

志了句子的开始和结束。

■母子的开工*4旬子的结

始符号#..........#束符号

•对任何x,若文法开始符号S与x…,贝I」#v・x,若有

S当■・・・x,则x>#

#<■X..............X>>#

•为句子的开始符号、终结符号和句中符号添加优先

关系，使句子易于被识别处理。

•简单优先分析的思想

•简单优先矩阵：根据优先关系的定义，将文法中各文法符号

之间的这种关系用一矩阵表示，称作简单优先矩阵。

•PDA读入一个单词后，比较栈顶符号和该单词的优先级，若

栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级

高于或等于读入符号，则找句柄进行归约，找不到句柄就继

续读入。直到最后栈内只剩下开始符号，输入串读到“#"为

止，此时识别正确。

•简单优先分析法的优缺点

•优点：技术简单

•缺点：适用范围小；分析表尺寸过大。

6.3算符优先分析法

•算符优先分析的基本思想

•所谓算符优先分析法是仿效四则运算的计算过程而构造的一

种语法分析过程.

•特点

•简单直观，特别适用于表达式分析,易于手工实现，是自底向上

的归约过程，但可归约串不一定是规范句型的句柄，所以算

符优先归约不是规范归约。

•关键

•分析表只规定算符（广义为终结符）之间的优先关系，也就是

只考虑终结符之间的优先关系及结合性质，不考虑非终结符

之间的优先关系。

•例如，30*40-10+20的运算

G[E]:E^E+E|E-E|E*E|E/E|ETE|(E)|-E|id

•由于该文法是一个二义文法，它的句子往往有不同的规范推导和

归约，实际运算会得到不同结果，但按传统的习惯规定优先级和

结合律进行归约，优先级从高到低为：乘幕运算符，乘、除运算符

力口、减运算符；同级运算符服从左结合原则；有括号时，先括号

内后括号外。

•则文法的句子id+id—id*(id+id)的归约过程为：

(1)id+id-id*(id+id)设算数级别最高，最先归约

(2)E+id-id*(id+id)

(3)E+E-id*(id+id)十,■同级，先归约左边十号

(4)E-id*(id+id)

(5)E-E*(id+id)・，*不同级，先归约右边的*

(6)E-E*(E+id)

⑺E-E*(E+E)先算括号内，在算括号外

(8)E—E*(E)

(9)E-E*E先归约*,在归约十

(10)E-E

(11)E

1.这个归约过程是唯一的，运算结果亦是唯一的。

2.上述归约过程中起决定作用的是相邻两个终结符号之间的优先关系

一旦确定了这种优先关系，就可以借助这种关系去寻找可归约串并

进行归约。

•因此，算符优先分析法的关键是比较两个相继出现的终结

符的优先级而决定应采取的动作。

•需完成运算符间优先级的比较，可以先定义各种可能相继出

现的运算符的优先级并表示为矩阵的形式，使得能够在分析

中通过查询矩阵元素而得到算符之间的优先关系。

•对于任何两个可能相继出现的终结符号a与b,若具有以下

形式”…ab…”或“…aQb…”，其中Q为某非终结符，则a,b

之间的关系为：

•a<-b表示a的优先级低于b

•a=b表示a的优先级等于b

•a->b表示a的优先级大于b

•若a,b在任何情况下不可能相继出现，贝Ua,b无关系

表6.2优先关系表

+・*/id)#

+•>•><•<•<•<•<••>•>

・•>•><•<•<•<•<••>•>

*•>•>•>•><•<•<••>•>

/•>•>•>•><•<•<••>•>

•>•>•>•><•<­<••>•>

id•>•>•>•>•>•>•>

1r<•<•<•<•<•<•<•—

)•>•>•>•>•>•>•>

#<•<­<•<•<­<•<­

说明：

•上述表满足通常数学上的习惯约定，且附加一条约定：运算量

id的优先级高于算符。

•语句开始符号和结束符号“铲与终结符相继出现时，应该有

或以此保证语句先归约。

•(二)表示括号是成对归约的。

•算术关系二”和“〉”与优先关系具有十分不同的性质。例

如，并不一定意味着b>a,例如：+<-(,(<-+o终结

符所处的左右位置很重要。

•决定优先关系方法：

(a)直观方法：代数规则；

(b)对于一个无二义性文法，有机械方法。

•直观算符分析法对下推自动机的改进

•添加了一个下推栈：一个用于放操作数和运算结果；

一个用于放操作符（包括执括号）。

•算法概要

初始化（OPND='，QPTR=#，读头指向输入串第一个符号）

读入符号到sym,若sym是运算数，则入OPND栈，读头下移，若sym是符

号则查表比较OPTR栈顶6与sym的优先级：

当OPTR栈顶符号9二'（'andsym='）',6弹出，读头下移；

当遇到可归约串时（即OPTR栈顶符号串与读头下符号形成了一对＜・・・・・＞）,

OPND弹出栈顶两个元素g、TT2,OPTR弹出栈顶元素&将口华改的结果入

OPND栈，继续读下一个符号，直到OPTR栈底的‘#’遇到读头下的

分析完毕。

a+b……#添加一个下推栈的原因：

+i)*i#

推"----------直观算符优先控制

栈0------------------------------

"优先表（=,＜）E

(

OPND#+

E

OPTR把

例如，改进的PDA,句子a+b*c#的直观算符优先分析过程。

a+b*c#a+b*c#a+b*c#

initial#<•++<•*+<***•>#

a+b*c#

OPTR栈只剩一个#,

读头亦只剩一个#,

分析结束，

T2即是运算结果。

Tl=b*cT2=a+Tl

•直观算符分析法的优缺点

•优点

简单明了，易于手工实现，适于分析各种算术表达式

使用此算法可以很方便的把表达式翻译成目标指令，只要在归约

时把计算口力取值改成相应指令（&3,叫，丁）即可。

•缺点

算法采用两个下推栈，有时会将错误句子识别成合法句子，并且，

无法指出输入串中出错位置。

对于含有单目运算符的算术表达式不便处理

■比如负号，由于负号的优先级高于加减法，低于乘除法，但负号的形式

与减号相同，不容易识别。

分析句子：i[i2+i3*+i4分析句子:甲2+++++

回3*乜#用2+++++#

2"Tl=i+ii

T3=i4+T22

1+-

#

•以上介绍的是直观算符优先分析法，仅仅是为了易于理解算符

优先分析法的概念。

•直观算符优先分析法的关键是对一个给定文法G,人为地规定

其算符的优先顺序，即给出优先级别和同一个级别中的结合

注质。

•仍需要讨论的问题是：任意给定的一个文法如何按形式算法

的规则计算算符之间的优先关系。

定义6.1设有一文法G,如果G中没有形如A->g或形如A-...BC…的产

生式，其中B和C为非终结符，则称G为算符文法(Operater

Grammar：也称0G文法。

>理解：即算符文法G中没有右部为£或右部具有相邻非终结符号的产

生式。

>例如：表达式文法E-E+E|E*E|(E)|i,其中任何一个产生式

中都不包含两个非终结符相邻的情况，因此该文法是算符文

法。

>又例：E->EAE|(E)|-E|idA—+|—1*|/|T不是算符文法，

因右部EAE具有相邻的非终结符号。

>算符文法保证了两个运算符之间只有一个操作数。

定义6.2设G是一个不含8产生式的算符文法，a和b

是任意两个终结符，A、B、C是非终结符，算符优

先关系三、•>、v•定义如下：

•az：b当且仅当G中含有形如A一…ab…或A—>…aBb…

的产生式

•av・b当且仅当G中含有形如A一…aB…的产生式，且

B与b...或B当Cb...

•a・>b当且仅当G中含有形如A一…Bb…的产生式，且

...a或...aC

定义6.3设有一不含w产生式的算符文法G,如果对

任意两个终结符对(a,b)之间至多只有IZ?和v•三种

关系中的•种成立，则称G是一个算符优先文法

(OperatorPrecedenceGrammar),即OPG文法。

•算符优先文法是无二义性的。

(a)a^zb(b)a<-b(c)a・〉b

①amb则存在语法子树如图（a）

其中b为E或为B,这样a,b在同一句柄中同时归约所以优先级相同。

②avb则存在语法子树如图（b）

其中b为z或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。

③a>b则存在语法子树如图（c）。

其中6为£或为C,a、b不在同一句柄中，a先归约，所以a的优先性大于b。

算符优先关系表的构造r

・・

•0G和OPG定义的意义

•这两个定义相当于对文法的句型和可归约的短语做了如下

规定：

•设A〔A?…AgAA+1…An是文法G的一个句型，

•若A]£VN，则Ag,Ai+1eVT,即不允许出现相继两个非终

结符；

•若B〔B2…Bm是当前可归约短语，并可归约为Aj,则

B1B2…Bm中不能相继出现两个非终结符，且相邻的终结符

优先级全相等；

对于B1B2…Bm中首终结符b有AgV・b

对于以B2…Bm中的尾终结符b有b>Aj+i

•实际上，可归约短语是某产生式右部符号串，所以通过检

查G的每个产生式的候选式可以查找出任意优先级相同的终

结符序偶对；要找出满足v•关系和》关系的终结符序偶，就

要找出各非终结符Ai的首终结符集和尾终结符集。

构造过程::

•求各非终结符的首终结符集和尾终结符集：••

•FIRSTVT(B尸{b|B多b…或B与Cb…}

•LASTVT(B尸但旧二…a或Bm…aC}

•则算符文法中任何两个终结符对(a,b)之间的优先关系,

其算法依据如下：

•三关系

•可直接查看产生式的右部，对如下形式的产生式

A一…ab…，Af..aBb…，有a=b成立。

•v•关系

•求出每个非终结符B的FIRSTVT(B),在如下形式的产生式

A一…aB…中，对每一b£FIRSTVT(B),有b成立。

•＞关系

•计算每个非终结符B的LASTVT(B),在如下形式的产生式

A—…Bb…中，对每一a£LASTVT(B),有a〉b成立。

由定义6.2可有如下推论：

a)若有产生式A-a..,或A->Ba.・.，则a^FIRSTVT(A),其中A、B

为非终结符，a为终结符。

b)若a£FIRSTVT(B)且有产生式ATB…，则有a£FIRSTVT(A)。

例设文法G的产生式为：

S->aAcBeA->.Bb

右

A—bB—dabcde

(1)计算每个非终结符的左

FIRSTVT与LASTVT；a

(2)计算所有终结符之间的关系

(优先关系表)。b

解析FIRSTVT(S)={a}c

FIRSTVT(A)={b}

FIRSTVT(B)={d}d

LASTVT(S)={e}e

LASTVT(A)={b}

LASTVT(B)={d}

构造算法

1.构造集合FIRSTVT(P)的算法

•依据：定义和推论

1)若有产生式A-a・・,或A—Ba.・.，则a@FIRSTVT(A),其中A、

BeVN,aeVT

2)若a£FIRSTVT(B)且有产生式A—B…，则有

aeFIRSTVT(A).

•注：规则1是求A的首终结符a的关系；规则2是求A与产生式中

开头的非终结符B之间的关系。

•两个数据结构

®二维布尔矩阵F.行标为非终结符A,列标为终结符a；F[A,a]=true,

当且仅当a£FIRSTVT(A)。

栈STACK栈中动态存放曾在F[A,a]中为真的序偶对(A,a)。

1.构造集合FIRSTVT(P)的算法

•算法如下：

•初始化，将布尔矩阵中各元素置为false,栈为空；

按规则1,查看产生式，对于形如A-a…或A-Ba…的

产生式，置相应的[A,a]为true,并将序偶对(A,a)入栈；

•按规则2,对栈施加如下操作：

■弹出栈顶序偶对并记为(B,a),查看所有产生式，看有无形如

A—B…的产生式，若有,且a不属于FISRTVT(A)(即F[A,a]

为false),则将F[A,a]置为true,并把(A,a)入栈;

■重复3,直到栈空为止。

最后，在F[A,a]中，凡是true的元素即属于A的首终结符

集。

2.构造集合LASTVT(P)

LASTVT集的求解方法和FIRSTVT相似，不再赘述。

3.构造算符优先表算法

算法过程：

对每条产生式P—X1X2…Xndo

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

{ifX和X.均为终结符then优先表表中置*尸为+1；

ifi<n-2andXj^nXi+2^VTandXi+1eVNthen

{forFIRSTVT(X+i)中的每个ado

{优先表表中置Xj〈・a}}

ifX,£VN而Xj+i^VTthen

{forLASTVT(X)中的每个ado

{优先表表中置a>X+i}}

})

算符优先文法的另一个定义：

如果文法G按此算法构造出的优先分析表没有重定义项，则文法G是算符优先文法.

构造下面文法的算符优先表。

①S—ifEbthenEelseE②E-E+T|T

③T—T*F|F④F—i⑤E「＞b

解析

1）先求各非终结符的首终结符集和尾终结符集。为考虑语句

的开始和结束符号“#“，对文法拓广，加一个产生式S，T#S#

FISRTVT(S)={if}LASTVT(S)={else,+,*,i}

FISRTVT(Eb)={b}LASTVT(Eb)={b}

FISRTVT(E)={+,*,i}LASTVT(E)={+,*,i}

FISRTVT(T)={*,i}LASTVT(T)={*,i}

FISRTVT(F)={i}LASTVT(F)={i}

2）填写算符优先表

■

右+*

左ifthenelse1b#

if

then

else

+

*

■

1

b

#

2）填写算符优先表（参考）

■

右+*

左ifthenelse1b#

if=<■

then=<■<■<■

else<­<■<■■>

+■>■><-<■■>

*->■>■><■■>

■

1■>■>■>■>

b■>

#<■

算符优先分析法流程

if(a<-b)or(a=b)then

begin/*移进*/

把b推入栈中；

使ip前进到下一个符号；

end

ifa->bthen/*归约*/

repeat

从栈中弹出符号

until栈顶终结符号〈•最近弹出的终结符号

elseerror

算符优先文法的若干问题

1.优先表构造算法讨论

•构造优先表的算法仅仅反映文法符号间关系，并不反映

附加条件，对二义性文法构造算符优先表，可能会出现

多重定义项。

•二义性文法存在规范归约不唯一的句子。例如，

文法G[E]:E-E+E|E*E|(E)|id

句子id+id*id有二个不同的最右推导：

E=E+EE=>E*E

nE+E*E=>E*id

nE+E*id3=>E+E*id

nE+id2*id3=>E+id*id

nid1+id2*id3=>id1+id2*id3

句型E+E*id3中，句柄不唯一o

2.非规范分析

•规范归约：严格按照句柄进行归约，终结符和非终结符

一起考虑，只要栈顶形成句柄，不管句柄内是否包含终

结符都要进行归约。

例如，考虑非二义的表达式文法G[E]:

E—E+T|TT-T*F|FF->(E)|i,识别语句i+i*i的过程

•规范归约：

i+i*i#

F+i*i#

T+i*i#

E+i*i#

E+F*i#

E+T*i#

E+T*F#

E+T#

E#

算符优先分析：算符优先分析中，仅研究终结符之间的

优先关系，而不考虑非终结符之间的优先关系，但句柄

是由终结符和非终结符一起构成的，所以算符优先分析

相对来说是非规范的分析过程。

对上例的算符优先分析过程：

i+i*i#

E+i*i#

E+T*i#

E+T*F#

E+T*F#

E+T#

E#

在优先分析中，可归约的短语不再称为句柄，而称为最

左素短语。素短语是指这样一个短语，至少含有一个终

结符号，并且除自身之外不再含有任何更小的带有终结

符号的短语。

注：最左素短语是指处于句型最左边的那个素短语；算符优先文法

句型的最左素短语是唯一的。

文法G[E]:E-E+T|TT-T*F|FF一(E)|i,

写出句型#丁+丁*F+i#的素短语。

由定义可知，

短语有：T,T*F,i,T+T*F+i

素短语有：T*F,i

左素短语有：T*F