语法之自下而上分析市公开课金奖市赛课一等奖课件

第五章语法分析-自下而上分析

自底向上分析方法是从输入符号串开始，查找当前句柄，并用产生式将它归约成对应非终止符号，最终归约为识别符号一个分析方法。(1)对输入符号串扫描，采取自左向右次序；(2)分析过程是自下而上进行(对语法树来说从末端结点开始，最终归约到根结点)；(3)每次归约是对最左简单短语(句柄)进行；(4)算法关键是确定最左简单短语；注意以下几点：重点掌握：

(1)素短语、最左素短语、算符文法、算符优先文法等概念及判断法；

(2)优先关系和优先函数概念及判断方法。第1页例：设有文法G:

SaAcBe

Ab

AAb

Bd

输入串:

abbcdeSaAcBeAbbd其推导与归约过程为（示范最左/右推导与归约）自下而上分析采取最左归约即规范归约。第2页5.1自底向上分析普通过程一、普通过程：普通自底向上分析法，也称为“移进—归约”法，其普通过程为:(1)设置一个存放符号栈称为符号栈，用于统计分析过程和确定下一步动作。(2)把输入符号按扫描次序逐一移进栈里(符号栈)，当栈顶符号组成符号串形成一个句柄时(恰好是某条产生式右部)，就进行归约。即把该符号串用与它对应产生式左部非终止符号代替，依然置于栈顶。(3)接着检验新栈顶，若形成新句柄，再进行归约，若没有形成新句柄，则从符号串中移进新符号。如此重复，直到整个输入符号串处理完成为止。(4)若最终栈底为识别符号，则表明所分析输入串正当，汇报分析成功；不然是不正当符号串，汇报犯错信息。第3页一、举例：设有文法G:

SaAcBe

Ab

AAb

Bd

输入串:

abbcde步骤符号栈内容输入符号串内容所做动作1#abbcde#“#”移进2#abbcde#a进栈—移进3#abbcde#b进栈—移进4#aAbcde#用Ab归约5#aAbcde#b进栈—移进6#aAcde#归约(AAb)7#aAcde#c进栈—移进8#aAcde#d进栈—移进9#aAcBe#归约(Bd)10#aAcBe#e进栈—移进11#S#归约12接收输入串，汇报成功！输入仍用#做为左右分界符，即#abbcde#，一步步归约当前句柄，归约目标为#S#第4页总结以上过程能够发觉：(1)在此算法中所归约短语都是最左简单短语，即为规范归约。(2)并没有彻底处理句柄识别问题。5#aAbcde#在上例中当进行完步骤5后，符号栈和剩下输入符号串内容为：即输入符号串已经归约为：#aAbcde#，依据上述算法，下一步Ab和b都能够归约(它们都在符号栈栈顶且有产生式AAb和Ab)。假若判b为句柄，则可把b归约为A，即符号串归约为：#aAAcde#。那么，后面工作不论怎样做，都无法归约成功。第5页以上问题我们从语法树角度看：最初输入符号串对应语法树为：SaAcBeAbbd当前句柄进行一次归约后语法树为：此时，Ab和d为句型aAbcde简单短语，Ab为句柄，所以不能归约b。可见，算法并没有提供识别真正句柄方法。所以，怎样找到当前句型句柄，是自底向上分析方法关键。

P85-88复习短语、句柄、规范归约等概念。第6页5.2算符优先分析法一、方法概述：

算符优先分析法是自底向上分析方法中一个，即使它不是规范归约，但它含有分析速度快，尤其适合表示式分析特点，因而得到普遍应用。在算术表示式运算过程中，为了确保计算过程和结果唯一性，要求了四则运算法则，实际上就是要求了运算之间优先次序，如：先乘除后加减；同级运算从左向右；有括号先做括号内运算；一目运算减(负号)优先级高于加减低于乘除。所谓算符优先分析法就是仿照上述算术四则运算运算过程，而设计一个语法分析方法。它首先要要求运算符之间优先关系，然后利用这种关系确定句型“句柄”，并进行归约。第7页比如：有文法G[E]：

EE+E|E-E|E*E|E/E|(E)|i并有输入串i+i-i*(i+i)这个文法是一个二义性文法，但若采取了四则运算法则，归约过程就唯一了。1i+i-i*(i+i)2E+i-i*(i+i)3E+E-i*(i+i)4E-i*(i+i)5E-E*(i+i)6E-E*(E+i)7E-E*(E+E)8E-E*(E)9E-E*E10E-E11E相邻终止符号优先关系，决定了归约次序，处理了句柄和二义性问题。第8页二、直观算符优先分析法：实际上，在真正算符优先分析方法中，需定义任意两个相继出现终止符号a和b之间优先关系(a与b之间可有一个非终止符)，一旦确定了这种优先关系，就能够用它来确定“句柄”进行归约。1.优先关系，两个相继出现终止符之间优先关系有三种：a优先级高于b记为:>.baa优先级等于b记为:.abab<.a优先级低于b记为:注意：与数学中<、=、>含义不一样，如：若有：ab<.，不一定有：>.ab但>.-+<+-.一样：，不一定有：.ab.ba.()但却没有.)(第9页2.优先关系矩阵，用矩阵表示终止符之间优先关系。比如，有文法G[E]：EE+E|E*E|(E)|i

VT={+,*,i,(,)}其优先关系矩阵为：右终止符

左终止符+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..行表示相邻两个终止符号中左边一个列表示相邻两个终止符号中右边一个两个终止符号若不可能在句型中相邻，则它们之间无优先关系运算符之间、括号之间、运算符和括号之间优先关系据四则运算法则确定，为了确保消去括号要求“(”和“)”优先关系相等对于i因为它表示基本运算量要首先计算，所以它优先级最高。“#”是作为输入串分界符，所以它优先级最低。第10页三、算符优先分析法1、方法概述：

算符优先分析法是自底向上分析方法中一个，即使它不是规范归约，但它含有分析速度快，尤其适合表示式分析特点，因而得到普遍应用。在算术表示式运算过程中，为了确保计算过程和结果唯一性，要求了四则运算法则，实际上就是要求了运算之间优先次序，如：先乘除后加减；同级运算从左向右；有括号先做括号内运算；一目运算减(负号)优先级高于加减低于乘除。所谓算符优先分析法就是仿照上述算术四则运算运算过程，而设计一个语法分析方法。它首先要要求运算符之间优先关系，然后利用这种关系确定句型“句柄”，并进行归约。第11页2、算符优先文法：1）算符文法：设有一个文法G，假如G中没有形如:U…VW…产生式，则称G为算符文法。或称为OG(OperaterGrammar)文法。2）OG文法中终止符号之间优先关系：设G是一个算符(OG)文法，a,bVT,U,V,WVN,则算符优先关系定义以下：(1).ab,当且仅当G中含有产生式:U…ab…或U…aVb…；ab<.(2),当且仅当G中含有产生式:U…aW…,且W+b…或W+Vb…;>.ba(3),当且仅当G中含有产生式:U…Wb…,且W+…a或W+…aV;a,b同时参加归约，把…ab…或…aVb…归约为Ub首先参加归约，把b…或Vb…归约为W后再将…aW…归约为Ua首先参加归约，把…a或…aV归约为W后再将…Wb…归约为U第12页从语法树角度说明以上定义：设有文法G[E]：

EE+E|E*E|(E)|i

并有符号串：i+(i*i)首先给出与符号串对应语法树：E+EEE()*EEiiiEE+E

E(E)

先归约(E)再归约E+E所以+<.(E(E)

(E)一起归约

‘(’和‘)’优先级一样所以(.)E(E)

EE*E

先归约E*E再归约(E)所以*>.)第13页3）算符优先文法：设有一个不含空产生式算符文法，假如在任意两个终止符号之间，至多只有一个优先关系成立，则称这么算符文法为算符优先文法(OperatorPrecedenceGrammar)，即OPG文法。举例：

例1，判断文法G[E]:EE+E|E*E|(E)|i

是否为OPG文法。因，EE+E

又有

EE*E所以*>.+而，EE*E

且EE+E所以*<.+可见，据算符文法中，终止符号优先关系定义，可求出*和+之间有两种不一样优先关系，所以G[E]不是算符优先文法。据算符文法定义，第14页例2，设有文法G[E]:

EE+T|T

TT*F|F

F(E)|i

问，是否为OPG文法。(1)文法中各产生式都不包含有相邻非终止符号，据算符文法定义，G[E]是算符文法；(2)判断终止符号之间优先关系由产生式F(E)

可知：>.)+.()因有产生式F(E)且：EE+T(+<.T+TT*F+T(*<.…i*F+T(i<.一样产生式F(E)

且：EE+TE+T*F>.)*E+T*i>.)i继续使用产生式和相关推导，能够确定其它优先关系。从而能够形成关系优先矩阵：+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..=(3)最终得出优先关系能够确认，任意两个终止符号之间至多只有一个优先关系，故为OPG文法。注：大多数程序设计语言表示式都是OPG文法。第15页3、结构优先关系矩阵：依据算符文法优先关系矩阵定义(或四则运算这么约定)能够人工结构优先关系矩阵，但这对于复杂文法是极难实现，下面我们寻找便于计算机自动实现结构算法。1）两个主要集合：(1)定义：FIRSTVT(U)={b|U+b…或U+Vb…,bVT,U,VVN}LASTVT(U)={a|U+…a或U+…aV,aVT,U,VVN}(2)求法(以FIRSTVT(U)为例说明)：在此过程中，要充分利用两条规则:若有产生式Ub…或UVb…,U,VVN,则bFIRSTVT(U)若有产生式UV…，且bFIRSTVT(V),

则bFIRSTVT(U)2）结构方法go22第16页为了算法实现，建立一个布尔数组F[U,a]用于存放FIRSTVT(U),若终止符aFIRSTVT(U),则F[U,a]=TRUE，不然F[U,a]=FALSE；另外还要建立一个工作栈STACK，初值为空。①数组元素初始化为FALSE(用0表示)；例2，设有文法G[E]:

EE+T|T

TT*F|F

F(E)|i

STACK+*()iETFF000000000000000②从文法中找出形如Ub…或UVb产生式，并使对应数组元素F[U,b]=TRUE(用1表示)；EE+T1TT*F1F(E)1Fi1③将F[U,b]值为真符号对<U,b>压入工作栈(次序任意)；F,(E,+T,*F,i③若工作栈不空，将栈顶项弹出，此项记为<V,b>,若文法中有形如：

UV…产生式，则bFIRSTVT(U)，此时，若数组中F[U,b]=FALSE,则令F[U,b]=TRUE,且将<U,b>压入STACK,此过程重复进行，直到栈空。1T,i1E,i1E,*1T,(1E,(FIRSTVT(E)={+,*,(,i}

FIRSTVT(T)={*,(,i}

FIRSTVT(F)={(,i}用类似算法能够求出LASTVT(U)第17页2.优先关系确定(P92)检验文法中每一条产生式，找出形如U…ab…或U…aVb…产生式，则满足优先关系ab;.ab<.若文法中有产生式U…aW…，且bFIRSTVT(W)，则ab若文法中有产生式U…Wb…，且aLASTVT(W)，则>.for每条产生式Ux1x2…xndo

begin

fori:=1ton-1do

begin

ifxi,xi+1VTthen置xixi+1

ifin-2且xi,xi+2VT,xi+1VN

then置xixi+2

ifxiVT,xi+1VN

thenforbFIRSTVT(xi+1)doxib

ifxiVN,xi+1VT

thenforaLASTVT(xi)doaxi+1

end

end>.<...第18页四、算符优先分析算法：1.素短语：

文法句型素短语是这么一个短语：它最少包含有一个终止符号，而且除它之外，不再包含其它素短语。例，设有文法G[E]:

EE+T|T

TT*F|F

F(E)|i

句型为T+T*F+i,要求找出其素短语。句型对应语法树为：EE+TE+TT*FTFi据语法树句型短语有：T（E)T*F(T)i(F,T)T+T*F(E)T+T*F+i(E)其中素短语有：T*Fi2.最左素短语：任意句型最左边素短语为该句型最左素短语。T*FT是句柄，但不是素短语最左素短语是当前归约对象第19页3.最左素短语特征：(1)算符文法句型普通形式：#N1a1N2a2……NnanNn+1#其中，NiVN,aiVT由n个终止符号组成，而每个相邻终止符号之间至多有一个非终止符。(2)定理：一个OPG文法句型最左素短语是满足以下条件最左子串：NjajNj+1aj+1……NiaiNi+1其优先关系为：ajaj+1,

aj+1aj+2,

……,ai-1ai...且aj-1

aj,

aiai+1>.<.将子串左右邻接符号一起考虑：aj-1NjajNj+1aj+1……NiaiNi+1ai+1它们优先关系表示为：.aj-1

aj

aj+1……aiai+1

.<..>.这个定理给出了依据句型之间终止符号优先关系判断最左素短语方法。Nj和Ni+1属于最左素短语aj-1和ai+1不属于最左素短语第20页例，有文法G[E]:

EE+T|T

TT*F|F

F(E)|i

已知优先关系矩阵为：+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..=要求用归约当前最左素短语方法分析句型T+T*F+i步骤句型优先关系最左素短语1#T+T*F+i#T*F2#T+T+i#T+T3#E+i#4#E+F#E+F5#E#归约符号TEFE确认！i#+*+i#<.<.>.>.<.#+#<.>.#++i#<.>.>.<.#+i#<.>.<.EE+TE+TT*FTFi归约过程语法树表示为：可见，素短语能够经过终止符号优先关系确认第21页另外，即使我们指出了每步归约对应非终止符号，但对于确定素短语并没相关系，它们只需参加对应运算，假如将读入非终止符号按次序放入对象栈中，每次归约(运算)结果也放入对象栈中，那么能够不考虑它们名字是什么，只需取栈顶内容参加运算即可。还能够看出，单个非终止符号归约在算法中省略了，所以不象规范归约那样对应真正语法树，实际上，这个过程只对应一棵语法树框架结构NNN+N+NN*Ni因为在分析过程中采取是自左向右扫描，所以先处理最左边素短语，即每次归约是当前最左素短语算符优先分析算法实现(P93)Exercises:P1332,3（1）、（2）第22页3.直观算符优先分析法分析过程：建立两个栈，运算符栈用于存放运算符，对象栈用来存放运算对象，‘#’仍作为输入串左右分界符；开始分析时，‘#’进入算符栈，对象栈为空，代表算符栈当前栈顶符号(=#)，a存放当前输入符号，算法描述以下：(1)当前输入符号送a;(2)若读入符号a为基本运算量i,则送对象栈并转(1);>.(3)若读入符号a为运算符,且算符栈栈顶元素a，则据EE1E2进行归约，其中E2和E1分别代表对象栈次栈顶(E2)和栈顶(E1)；并将结果E压入对象栈中，同时算符栈栈顶()弹出，重新执行(3)。(4)若读入符号a为运算符,且算符栈栈顶元素.a,则脱去括号，即弹出算符栈栈顶‘(’并放弃a(a中为‘)’)，然后转入(1)。(5)若<.a,则a入算符栈，成为算符栈新栈顶，转(1)；(6)若=a=‘#’,分析过程结束，对象栈中只有一项内容，即表示式结果。(7)若和a不存在优先关系，汇报犯错。第23页算符优先分析法深入讨论一、算符优先函数：1.引入，在实际算符优先分析中，普通不用文法优先关系矩阵，而是用两个优先函数f和g，即我们把每个终止符号与两个自然数f()和g()相对应，并满足以下条件：若1<.2则f(1)<g(2)若12则f(1)=g(2).若12则f(1)>g(2)>.f称为栈内优先函数(左)，

g称为栈外优先函数(右)。例:依据以上标准，文法

G[E]:EE+E|E*E|(E)|i

优先函数为:+*()i#f240550g136060+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..=是唯一吗?第24页2.使用优先函数优缺点:编程时便于比较运算,即用普通关系运算即可;比用文法优先关系矩阵节约内存，若有n个终止符号，优先关系矩阵占内存为(n+1)2，优先函数为2(n+1);原来不存在优先关系两个终止符号，变成可比较了，不易发觉语法错误．3.注意:算符优先方法中，应区分对待一目运算“减”和二目运算“减”，它们即使使用相同符号‘-’，但优先级不一样，可使用不一样符号代替一目运算“减”，即看成两种运算．+*()i#f240550g136060+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..=第25页４.优先函数结构方法——Floyd方法：在优先关系矩阵已知情况下，由定义结构优先函数：(1)对每个终止符号aVT(包含＃)，令f(a)=g(a)=k(k通常取1)(2)若>.ba，而当前f(a)g(b)，则令f(a)=g(b)+1.ab(4)若，而当前f(a)g(b)，则令f(a)=g(b)=max{f(a),g(b)}(3)若，而当前f(a)g(b)，则令g(b)=f(a)+1ab<.(5)重复(2)(3)(4)，直到满足优先关系(收敛)，若f(a)或g(b)中某个值大于2n(n为终止符号数)，仍没有收敛，则说明此文法没有算符优先函数。比如：为文法G[E]:EE+E|E*E|(E)|i

结构算符优先函数。第26页优先关系矩阵已知为：+*i()#+*i()#<.>.<.<.>.>.>.>.<.<.>.>.>.>.>.>.>.>.>.>.<.<.<.<.<.<.<.<..=(0)+*()i#f111111g111111迭代过程：+*()i#fg(1)+*()i#f241441g235151(2)+*()i#f351551g246161收敛！第27页5.3LR分析方法

LR分析法是一个有效自底向上语法分析技术，它能适合用于大部分上下文无关文法分析，普通叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是结构最右(Right)推导逆过程(规范归约)，括号中k是指在决定当前分析动作时向前看符号个数。LR分析法与其它语法分析方法相比，应用更广泛，含有更强吸引力，主要原因有：(1