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

第五章自下向上分析语法分析方法5.1自下向上分析概述5.2算符优先分析法5.3LR分析法概述5.4

LR（0）分析

5.5SLR（1）分析

5.6LR（0）分析

5.7LALR（1）分析5.8

二义性文法在LR分析中应用

第1页知识结构第2页5.1自下向上分析概述自下向上分析（移进－归约分析）：对输入符号串自左向右进行扫描，并将输入符逐一移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型句柄或可归约串时，就用该产生式左部非代替对应右部文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法开始符号时则为分析成功，也就确认输入串是文法句子关键问题:是寻找可归约串。对“可归约串”概念不一样定义，就形成了不一样自下而上分析方法。在算符优先分析法中我们用“最左素短语”来刻画“可归约串”，在“规范归约”中，则用“句柄”来刻画“可归约串”第3页例5.1设文法G[S]：（1）SaAcBe（2）Ab（3）AAb（4）Bd对输入串abbcde＃进行分析，检验它是否是G[S]句子：最右推导为规范推导自左向右归约过程也称规范归约对输入串abbcde最右推导是SaAcBeaAcdeaAbcdeabbcde第4页步骤符号栈输入符号串动作(1)#abbcde#移进(2)#abbcde#移进(3)#abbcde#归约(Ab)(4)#aAbcde#移进(5)#aAbcde#归约(AbA)(6)#aAcde#移进(7)#aAcde#移进(8)#aAcde#归约(Bd)(9)#aAcBe#移进(10)#aAcBe#归约(SaAcBe)(11)#S#接收第5页图5.1自底向上结构语法树过程

第6页77分析器结构:#分析程序优先关系矩阵#符号栈输入串5.2算符优先分析法算符优先分析就是预先要求运算符(确切地说是终止符)之间优先关系和结合性质，借助于这种优先关系来比较相邻运算符优先级，以确定句型可归约串并进行归约。注意：算符优先分析不是规范归约。第7页5.2.1算符优先文法定义算符文法（OG）定义：设有一文法G，假如G中没有形如A…BC…产生式，其中B和C为非终止符，则称G为算符文法（operatergrammar）(OG文法)第8页性质1在算符文法中任何句型都不包含两个相邻非终止符证实：用归纳法设γ是句型，SγS＝w0w1

…wn-1wn=γ推导长度为n，归纳起点n=1时，S=w0w1=γ即Sγ必存在产生式Sγ，而由算符文法定义，文法产生式中无相邻非终止符，显然满足性质1。假设n＞1，wn-1满足性质1。若wn-1=aAδ，A为非终止符。*第9页由假设a尾符号和δ首符号都不可能是非终止符，不然与假设矛盾。又若Aβ是文法产生式，则有wn-1wn=aβδ=γ而Aβ是文法原产生式不含两个相邻非终止符，所以aβδ也不含两个相邻非终止符。满足性质1，证毕。第10页性质2假如Ab(或bA)出现在算符文法句型γ中，其中A∈VN，b∈VT，则γ中任何含此b短语必含有A证实：用反证法因为由算符文法性质1知可有：

Sγ＝abAβ若存在Bab，这时b和A不一样时归约，则必有SBAβ，这么在句型BAβ中，存在相邻非终止符B和A，所以与性质1矛盾，证毕。***第11页

（1）ab当且仅当G中含有以下产生式A…ab…或A…aBb

…（2）ab当且仅当G中含有以下产生式A…aB…，且Bb…或BCb…（3）ab当且仅当G中含有以下产生式A…Bb…，且B…a或B…aC>.<.＝.++++优先关系定义：设G是一个不含ε产生式算符文法，a和b是任意两个终止符，A、B、C是非终止符，算符优先关系定义以下：第12页以上三种关系存在语法子树以下列图：第13页算符优先文法（OPG）定义：设有一不含ε产生式算符文法G，假如对任意两个终止符对a,b之间至多只有,,三种关系一个成立，则称G是一个算符优先文法（operatorprecedencegrammar）(OPG文法)>.<.＝.第14页比如：二义性文法EE+E|E-E|E*E|E/E|E↑E|(E)|i不是算符优先文法第15页5.2.2算符优先关系表结构1.定义：FIRSTVT和LASTVT集合：FIRSTVT(B)={b|Bb…或BCb…},其中…表示V*中符号串LASTVT(B)＝｛a|B…a或B…aC}++++第16页2.结构FIRSTVT集和LASTVT集算法：FIRSTVT集：①若有产生式Aa…或ABa…，则a∈FIRSTVT(A)，其中A、B为非终止符，a为终止符②若a∈FIRSTVT(B)且有产生式AB…则有a∈FIRSTVT(A)LASTVT集：①若有产生式A…a或A…aB，则a∈LASTVT(A)，其中A、B为非终止符，a为终止符②若a∈LASTVT(B)且有产生式A…B则有a∈LASTVT(A)第17页例5.2：（0）E`＃E＃（1）EE＋T（2）ET（3）TT*F（4）TF（5）FP↑F|P（6）P(E)（7）Pi第18页(1)计算FIRSTVT和LASTVT集合FIRSTVT集合FIRSTVT（E`）=FIRSTVT（E）＝FIRSTVT（T）＝FIRSTVT（F）＝FIRSTVT（P）＝｛＃｝｛+｝｛*｝｛↑｝｛(,i｝+｛(,i｝=｛↑，(,i｝+｛↑，(,i｝=｛*，↑，(,i｝+｛*，↑，(,i｝=｛+,*，↑，(,i｝第19页LASTVT集合LASTVT（E`）＝LASTVT（E）＝LASTVT（T）＝LASTVT（F）＝LASTVT（P）＝｛＃｝｛+｝{*}{↑}{)，i}+{)，i}={↑，)，i}+{↑，)，i}={*，↑，)，i}+{*，↑，)，i}={*，↑，)，i}第20页有了文法FIRSTVT集和LASTVT集，就能够结构文法优先关系表：FOR每个产生式AX1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终止符THEN置XiXi+1

IFi≤n-2且Xi和Xi+2都为终止符，但Xi+1为非终止符

THEN置XiXi+2IFXi为终止符，但Xi+1为非终止符THENFORFIRSTVT（Xi+1)中每个bDO置Xib

IFXi为非终止符，但Xi+1为终止符THENFORLASTVT（Xi)中每个aDO置aXi＋1END＝.＝.>.<.3.结构算符优先关系表第21页继续例5.2：关系：由产生式（0）、（6）可得：＃＃，（）FIRSTVT（E`）＝｛＃｝FIRSTVT（E）＝｛+，*，↑，(，i｝FIRSTVT（T）＝｛*，↑，(，i｝FIRSTVT（F）＝｛↑，(，i

｝FIRSTVT（P）＝｛(，i｝＝.＝.＝.第22页LASTVT（E`）＝｛＃｝LASTVT（E）＝｛＋，*，↑，），i｝LASTVT（T）＝｛*，↑，），i｝LASTVT（F）＝｛↑，)，i｝LASTVT（P）＝｛)，i｝关系：列出所给表示式文法中终止符在前非终止符在后全部相邻符号对，并确定相关算符关系#E则有：#FIRSTVT（E）+T则有：+FIRSTVT（T）*F则有：*FIRSTVT（F）↑F则有：↑

FIRSTVT（F）(E则有：(FIRSTVT（E）<.<.<.<.<.<.<.第23页③关系：列出所给表示式文法中非终止符在前终止符在后全部相邻符号对，并确定相关算符关系E#则有：LASTVT（E）#E+则有：LASTVT

（E）+T*则有：LASTVT

（T）*P↑则有：LASTVT

（P）↑E）则有：LASTVT

（E））>.>.>.>.>.>.>.第24页表示式文法算符优先关系表：+*↑i()#+*↑i()#＝.＝.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.第25页例5.3:对以下文法G:S’#S#PS|iSD(R)DiRR;P|P求出每个非终止符FIRSTVT集和LASTVT集，并结构算符优先关系矩阵。第26页文法G每个非终止符FIRSTVT集合FIRSTVT(S’)={#}FIRSTVT(P)={i,(}FIRSTVT(S)={(,i}FIRSTVT(D)={i}FIRSTVT(R)={;,(,I}文法G每个非终止符LASTVT集合LASTVT(S’)={#}LASTVT(P)={i,)}LASTVT(S)={)}LASTVT(D)={i}LASTVT(R)={;,),i}

第27页();i#();i#<.<.<.<.>.>.>.＝.＝.<.<.>.>.>.>.>.<.第28页例5.4:已知文法G[S]为算符优先文法，其规则为：SSaF|FFFbP|PPc|d求优先关系矩阵第29页解：每个非终止符FISRVT集合FIRSTVT(S)={c,d,a,b}FIRSTVT(F)={b,c,d}FIRSTVT(P)={c,d}每个非终止符LASTVT集合LASTVT(S)={a,b,c,d}LASTVT(F)={b,c,d}LASTVT(P)={c,d}因为SSaF则LASTVT(S)·>a且a<·FIRSTVT(F)则：a·>a,b·>a,c·>a,d·>a且a<·b,a<·c,a<·d因为FFbP;则LASTVT(F)>b且b<FIRSTVT(P)则:b>b,c>b,d>b且b<c,b<d第30页abcd#abcd#＝.<.<.<.<.>.>.>.>.<.<.<.>.>.>.<.<.>.>.>.>.优先关系矩阵：第31页

为了处理算符优先分析过程怎样寻找“可归约串”问题,将定义算符优先文法句型“最左素短语”这个概念。依据最左素短语定义我们能够结构算符优先分析算法（1）最左素短语定义设有文法G[S]，其句型素短语是一个短语，它最少包含一个终止符，并除本身外不包含其它素短语，最左边素短语称最左素短语5.2.3算符优先分析算法第32页（2）怎样寻找最左素短语？算符优先分析句型性质算符文法任何一个句型(括在两个#号之间）应为以下形式(性质1)#N1a1N2a2…NnanNn+1#其中Nk(1≤k≤n+1)为非终止符或空，ak(1≤k≤n)为终止符算符优先文法句型最左素短语NiaiNi+1ai+1...NjajNj+1满足：

aj-1aj

ajaj+1,…,ai-1aiaiai+1

(性质1,

性质2,

算符优先文法定义)>.＝.＝.<.第33页(3)查找最左素短语方法：

1)最左子串法

先找出句型中终止符由左至右满足aj-1<aj=aj+1=…=ai>ai+1最左子串。再检验文法每个候选式,看其是否满足:全部终止符由左至右排列恰为ajaj+1…ai,即终止符对应相等而非终止符仅对应位置相同。若存在这么候选式,则用该候选式进行归约。第34页

2)语法树法

先画出句型γ语法树,再找语法树中全部相邻终止符间优先关系。确定相邻终止符间优先关系标准:①语法树中同层优先关系为“=”;②不一样层时,层次在下优先级高,层次在上优先级低;③在句型γ两侧加上语句括号“#”,则有#<γ和γ>#。最终按最左素短语必须具备条件确定最左素短语。第35页例5.4:文法G[E]:E→E+T|TT→T*F|FF→(E)|i试确定F+T*i最左素短语。

解:画句型F+T*i语法树,依据语法树确定相邻终止符间优先关系如图,故最左素短语为i。注意:句柄为FE＋EE*TFTiF#＜＋＜*＜i＞#第36页比如，若表示式文法G[E]为：EE+T｜TTT*F｜FFP↑F｜PP（E）｜i现有句型#T+T*F+i#，它语法树如右：第37页它短语有：T+T*F+i相对于非终止符E短语T+T*F相对于非终止符E短语T相对于非终止符E短语T*F相对于非终止符T短语i相对于非终止符P,F,T短语由定义6.4知i和T*F为素短语，T*F为最左素短语第38页算符优先分析时语法树框架第39页

1k:=1;S[k]:=“#”/*k代表栈S使用深度*/2 do{3read(a);/*下一符号到*/4ifS[k]VT

thenj:=k;/*j指栈顶终止符*/

5

elsej:=k-1;6

whileS[j]>ado

/*找最左S[j]<…=…=S[k]>a*/7

{

do{

/*j从最左素短语末逐步移向首*/8 Q:=S[j];9if

S[j-1]VT

thenj:=j-110elsej:=j-211 }whileS[j]=Q;12将S[j+1]S[j+2]…S[k]归约到某个N;//13 k:=j+1;14 S[k]:=N;/*把N置于原S[j+1]位置*/15

}16 if(S[j]<aorS[j]=a)17

then{k:=k+1;S[k]:=a}/*若栈顶S[j]<a或=a则将a压栈*/18 elseerror19 }whilea!=“#”（3）算符优先分析算法：第40页例5.5文法G[E]及其优先关系如例5.4所表示,试给出输入串i+i*i算符优先分析过程。解:输入串i+i*i算符优先分析过程以下:符号栈输入串动作#i+i*i##<i#i+i*i##<i>+,用F→i归约#F+i*i##<+#F+i*i##<+<i#F+i*i#…+<i>*,用F→i归约#F+F*i##<+<*#F+F*i##<+<*<i#F+F*i#…*<i>#,用F→i归约#F+F*F#…+<*>#,用T→T*F归约#F+T##<+>#,用E→E+T归约#E##E#结束第41页比如对输入串i+i#，其规范过程以下表所表示：步骤栈剩下输入串句柄归约用产生式(1)#i+i#(2)#i+i#iPi(3)#P+i#PFP(4)#F+i#FTF(5)#T+i#TET(6)#E+i#(7)#E+i#(8)#E+i#iPi(9)#E+P#PFP(10)#E+F#FTF(11)#E+T#E+TEE+T(12)#E#接收第42页算符优先分析时语法树框架语法树第43页五.优先函数我们能够定义两个函数f，g满足以下条件：当ab则令f(a)=g(b)当ab则令f(a)<g(b)当ab则令f(a)>g(b)对f，g我们称它为优先函数，它值用整数表示，它结构方法：（1）由定义直接结构优先函数①对每个终止符a∈VT(包含＃号在内)令f(a)=g(a)=1(也能够是其它整数)＝.>.<.第44页②对每一终止符对逐一比较假如ab，而f(a)≤g(b)则令f(a)=g(b)+1假如ab，而f(a)≥g(b)则令g(b)=f(a)+1假如ab，而f(a)≠g(b)则令min{f(a),g(b)}=max{f(a),g(b)}重复②直到过程收敛。假如重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数＝.>.<.第45页+*↑i()#+*↑i()#＝.＝.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.比如：若已知表示式文法算符优先矩阵以下表所表示，按上述规则结构它优先函数fg第46页首先把全部f(a)，g(a)值置为1，如表6.9中初值（0次迭代）然后对算符优先关系矩阵逐行扫描，按前述步骤②规则修改函数f(a)，g(a)值，这是个迭代过程，一直进行到优先函数值再无改变为止第47页表示式文法优先函数计算过程：迭代次数+*↑i()#0fgfgfgfg111111111111112446161235551112335571712466611与第2次迭代结果相同第48页第一次迭代过程：#)(i↑*+#)(i↑*+＝.＝.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.fgg=1g=1g=1g=1g=1g=1g=1f=1f=1f=1f=1f=1f=1f=1f=2g=3g=3g=3g=3f=2f=4g=5g=5g=5f=2f=4

f=2f=4f=6g=2f=3f=4f=6第49页第二次迭代过程：#)(i↑*+#)(i↑*+＝.＝.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.fgg=2g=3g=5g=5g=5g=1g=1f=2f=4f=4f=6f=1f=6f=1f=

3g=

4f=

5g=

6g=

6g=

6f=

5f=

7f=

7第50页第三次迭代过程：#)(i↑*+#)(i↑*+＝.＝.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.fgg=2g=4g=6g=6g=6g=1g=1f=3f=5f=5f=7f=1f=7f=1第51页对优先函数每个元素值都增加同一个常数，优先关系不变，因而，对同一个文法优先关系矩阵对应优先函数不唯一也有一些优先关系矩阵中优先关系是唯一，却不存在优先函数，比如下面优先关系矩阵：abab>.＝.＝.＝.第52页（2）用关系图法结构优先函数①对全部终止符a(包含＃)用有下脚标fa，ga为结点名，画出2n个结点②若aiaj或aiaj，则从fai到gaj画一条箭弧若aiaj或aiaj，则从gai到faj画一条箭弧＝.>.<.＝.第53页③给每个结点赋一个数，此数等于从该结点出发所能抵达结点（包含该结点本身在内）个数。赋给结点fai数，就是函数f(ai)值，赋给gaj数，就是函数g(aj)值④对结构出优先函数，按优先关系矩阵检验一遍是否满足优先关系条件，若不满足时，则说明在关系图中存在3个或3个以上结点回路，不存在优先函数第54页例6.4若已知优先关系矩阵为表6.10:i*+#i*+#fg>.<.＝.<.<.>.<.<.>.>.>.<.>.>.>.第55页结构优先关系图以下列图：第56页由图6.11求得优先函数关系表:i*+#f6642g7532第57页例6.5优先关系矩阵为表6.12:abab>.＝.＝.＝.第58页则优先关系图为图6.10:第59页优先函数表为表6.13:abf44g44第60页优先函数分析即使占用空间少，但它有不可克服缺点：我们在利用优先关系矩阵进行优先分析时，当两个终止符对无优先关系情况时优先关系矩阵对应元素为犯错信息，而用优先函数进行优先分析时，对两个终止符对没有优先关系情况不能区分，因而犯错时不能准确地指犯错误位置比如：表示式i+i*i(i+i)#，按算符优先矩阵i与(无优先关系，当归约分析到N+N*i时，能即时发觉错误，而用优先函数分析则此时发觉不了错误，直到归约到N+N*NN时，才能由两非终止符相邻出现而发觉错误，因而不能准确指犯错误位置第61页六.算符优先分析法不足因为算符优先分析法去掉了单非终止符之间归约，尽管在分析过程中，当决定是否为句柄时采取一些检验办法，但仍难完全防止把错误句子得到正确归约思索：输入串能正确进行归约，那它是文法句子吗？第62页例6.6下述文法是一个算符优先文法，其产生式为：SS；D｜DDD（T）｜HHa｜（S）TT＋S｜S其中VN＝｛S,D,T,H｝,VT＝｛；,（,）,a,+},S为开始符号第63页对应算符优先关系矩阵为表6.14：;()a+#;()a+#<.＝.>.>.>.<.<.<.<.>.>.<.<.>.>.>.>.<.<.<.<.>.<.>.>.>.>.>.>.＝.第64页步骤符号栈当前符号剩下输入串移进或归约对输入串(a+a)#分析过程以下：(1)#(a+a)#移进(2)#（a+a)#移进(3)#（a+a)#归约(4)#（N+a)#移进(5)#（N+a)#移进(6)#（N+a)#归约(7)#（N+N)#归约(8)#（N)#移进(9)#（N)#归约(10)#N#分析成功第65页6.4经典例题及解答例题1已知布尔表示式文法G[B]:BBoT|TTTaF|FFnF|(B)|t|f1.G[B]是算符优先文法吗？2.若G[B]是算符优先文法，请给出输入串ntofat#分析过