山東理工大學(xué)編譯原理內(nèi)部自底而上語法分析市公開課金獎市賽課一等獎?wù)n件

/10/101第6章自底而上優(yōu)先分析引言介紹相關(guān)概念自下而上分析基本問題歸約規(guī)范歸約算符優(yōu)先分析算符優(yōu)先關(guān)系表結(jié)構(gòu)和分析過程小結(jié)作業(yè)課程目錄第1頁/10/102引言自下而上分析介紹相關(guān)概念短語、直接短語和句柄素短語和最左素短語利用語法樹尋找短語、句柄方法章節(jié)目錄第2頁/10/103自下而上分析介紹文法G：E→E+T|TT→T*F|FF→(E)|i輸入串：w=i*i+i最右推導(dǎo)EE+TFiTT*FiFi最左歸約E==>E+T==>E+F==>E+i==>T*F+i==>T*i+i==>F*i+i==>i*i+i==>T+i

輸入串最終能歸約到開始符號，說明輸入串是文法一個句子，分析成功結(jié)束。第3頁/10/104自下而上分析基本思想p102從輸入串出發(fā)，逐步進行歸約，直至歸約到文法開始符號，那么輸入串是文法句子，不然輸入串有語法錯誤或者說，從語法樹末端開始，步步向上歸約，修剪語法樹，直到只剩根結(jié)點歸約——用產(chǎn)生式左部替換右部關(guān)鍵——尋找每步句型中可歸約串尋找方式不一樣，分析方法不一樣效率更高，對語法限制更少節(jié)目錄第4頁/10/105相關(guān)概念ＳαＡ

δ

β短語

若Ｓ==*>αＡδ，且A==+>β，則稱

β是句型αβδ相對于非終止符號A短語。節(jié)目錄直接短語

若Ｓ*

αＡδ

且Aβ，則稱β是句型

αβδ相對于非終止符號A直接短語。句柄一個句型最左直接短語。

第5頁/10/106素短語最左素短語p115句型E+T*i最左素短語是：i句型E+T*i短語有三個：E+T*iT*ii其中：i是句型E+T*i素短語T*i不是句型E+T*i素短語E+T*i不是句型E+T*i素短語不滿足條件(3)，包含素短語i不滿足條件(3)，包含素短語i素短語(1)是一個短語(2)最少包含一個終止符(3)且除本身外不再包含其它素短語最左素短語

處于句型最左邊素短語節(jié)目錄第6頁/10/107利用語法樹尋找句型短語、句柄等句型η=E+T*iEE+TT*Fi尋找方法句型η語法樹有：n棵子樹——n個短語m棵直接子樹——m個直接短語最左直接子樹——句柄①②③3個短語1個直接短語i句柄iE+T*iT*ii只有父子兩代素短語i

最左素短語i

n個內(nèi)部節(jié)點——n棵子樹每顆子樹葉結(jié)點從左至右排列組成一個短語第7頁/10/108利用語法樹尋找短語、句柄舉例句型η=T+T*F+i語法樹例文法G[E]：E→E+T|TT→T*F|FF→(E)|iEE+TFiE+TT*FT①②③④⑤⑥句型η有6個短語：T+T*F+i是句型η相對于E1短語T+T*F是句型η相對于E2短語T是句型η相對于E4短語T*F是句型η相對于T5短語i，i是句型η相對于T3，F(xiàn)6短語3個直接短語：T,T*F，i句柄：T2個素短語：T*F，i最左素短語：T*F6個內(nèi)部節(jié)點——6棵子樹第8頁/10/109利用語法樹尋找短語、句柄課堂練習(xí)句型η=i1*i2+i3

語法樹8個內(nèi)部節(jié)點——8棵子樹句型η有8個短語：i1*i2+i3是句型η相對于E1短語i1*i2是句型η相對于E2,T4短語i1是句型η相對于T6，F(xiàn)8短語i2是句型η相對于F7短語i3是句型η相對于T3,F5短語例文法G[E]：E→E+T|TT→T*F|FF→(E)|i直接短語3個：i1,i2，i3句柄：i1素短語3個：i1,i2，i3

最左素短語：

i1

E1E2+T3F5T6*F7T4F8i2i3i1節(jié)目錄BEGIN第9頁/10/1010自下而上分析基本問題歸約與移進歸約法規(guī)范推導(dǎo)與規(guī)范歸約移進歸約分析器要處理基本問題?章節(jié)目錄第10頁/10/1011歸約與移進歸約法歸約推導(dǎo)逆過程當(dāng)Ａ→γ是文法Ｇ一個產(chǎn)生式，且α、β∈Ｖ*，則αγβ能直接歸約到αＡβ比如E+T==>E+T*F,那么E+T*F能夠歸約到E+T

移進歸約法把輸入符號一個一個地移進棧里，當(dāng)棧頂形成某個產(chǎn)生式一個候選式時，就把棧頂這一可歸約串替換成（歸約為）該產(chǎn)生式左部符號歸約舉例第11頁/10/1012移進歸約法舉例例文法G[S]S→aAcBeA→Ab|bB→d輸入串為：abbcdeSaAcBedAbb步驟棧輸入緩沖區(qū)動作0#abbcde#1#abbcde#2#abbcde#3#aAbcde#4#aAbcde#5#aAcde#6#aAcde#7#aAcde#8#aAcBe#9#aAcBe#10#S#分析成功結(jié)束移進a移進b歸約A→b移進b歸約A→Ab移進c移進d歸約B→d移進e歸約S→aAcBe接收棧中串+余留輸入串

=當(dāng)前句型棧頂可歸約串=當(dāng)前句型句柄語法樹分析過程說明最右推導(dǎo)：S==>aAcBe==>aAcde==>aAbcde==>abbcde

右句型中句柄后面只能出現(xiàn)終止符修剪語法樹當(dāng)前句型句柄第12頁/10/1013語法分析樹生成（輸出）abbcdeAABS1.A→b2.A→Ab3.B→d4.S→aAcBe例文法G[S]：S→aAcBeA→Ab|bB→d產(chǎn)生式序列：1.A→b2.A→Ab3.B→d4.S→aAcBe節(jié)目錄第13頁/10/1014規(guī)范推導(dǎo)與規(guī)范歸約規(guī)范推導(dǎo)——最右推導(dǎo)規(guī)范句型——假如文法G無二義性，由規(guī)范推導(dǎo)所得句型(也稱為右句型)規(guī)范歸約——規(guī)范推導(dǎo)逆過程，即最左歸約規(guī)范歸約實質(zhì)——在移進過程中，當(dāng)發(fā)覺棧頂展現(xiàn)句柄時就用對應(yīng)產(chǎn)生式左部符號進行替換對于規(guī)范句型來說，句柄后面不會出現(xiàn)非終止符，只能出現(xiàn)終止符節(jié)目錄第14頁/10/1015移進歸約分析器i＊i#＋Ｅ#移進歸約控制程序產(chǎn)生式序列

棧內(nèi)容+輸入緩沖區(qū)內(nèi)容＝#句型#分析過程中符號棧輸入串初態(tài)#w#………

終態(tài)#S#

分析成功分析棧輸入緩沖區(qū)第15頁/10/1016移進歸約分析器四種動作移進——把輸入串一個符號移進棧歸約——發(fā)覺棧頂展現(xiàn)可歸約串，將0個或多個符號從棧中彈出，將對應(yīng)產(chǎn)生式左部非終止符壓入棧接收——宣告最終分析成功犯錯——發(fā)覺棧頂內(nèi)容與輸入串相悖，分析工作無法正常進行，此時需要調(diào)用犯錯處理程序進行診察和校正，并對棧頂內(nèi)容和輸入符號進行調(diào)整第16頁/10/1017i1*i2+i3分析例文法G[E]E→E+T|TT→T*F|FF→(E)|i步驟棧輸入緩沖區(qū)動作0#i1*i2+i3#1#i1

*i2+i3#2#F*i2+i3#3#T*i2+i3#4#T*i2+i3#5#T*i2

+i3#6#T*F+i3#7#T+i3#8#E+i3#9#E+i3#10#E+i3

#預(yù)備移進i1歸約F→i歸約T→F移進*移進i2歸約F→i歸約T→T*F歸約E→T移進+移進i311#E+F

#12#E+T#13#E#14

歸約F→i歸約T→F歸約E→E+T接收EE+TFT*FTFi2i3i1分析過程中所用產(chǎn)生式序列即可表示語法分析輸出語法樹第17頁/10/1018對輸入串規(guī)范歸約分析步驟當(dāng)棧中符號棧頂部分還不能形成句柄時，進行移入操作一旦發(fā)覺棧頂部分形成了句柄時候，對該句柄進行歸約。將句柄出棧，然后將歸約得到非終止符號入棧假如輸入是句子，則棧中符號（從底到頂）和輸入緩沖區(qū)剩下符號組成句型第18頁/10/1019i1+i2*i3課堂練習(xí)例文法G[E]E→E+T|TT→T*F|FF→(E)|i步驟棧輸入緩沖區(qū)動作BEGIN0#i1+i2*i3#1#i1

+i2*i3#2#F+i2*i3#3#T+i2*i3#4#E+i2*i3#5#E+

i2*i3#6#E+i2*i3#7#E+F*i3#8#E+T*i3#9#E+T*i3#10#E+T*i3

#預(yù)備移進i1歸約F→i歸約T→F歸約E→T移進+移進i2歸約F→i歸約T→F移進*移進i311#E+T*F

#12#E+T#13#E#14

歸約F→i歸約T→T*F歸約E→E+T接收EE+TFTi1T*FFi3i2E+T不是當(dāng)前句型句柄，不能歸約，繼續(xù)移進歸約8次規(guī)范歸約節(jié)目錄第19頁/10/1020要處理基本問題怎樣找出能夠進行直接歸約

“可歸約串”？將找到“可歸約串”歸約到哪個非終止符號？怎樣決定什么時候移進，什么時候歸約？節(jié)目錄第20頁/10/10216.3算符優(yōu)先分析p106算符優(yōu)先分析介紹相關(guān)定義算符文法算符優(yōu)先關(guān)系算符優(yōu)先文法算法優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表結(jié)構(gòu)FRISTVT集合和LASTVT集合計算算符優(yōu)先分析算法小結(jié)章節(jié)目錄第21頁/10/1022算符優(yōu)先分析介紹是一個自下而上語法分析法優(yōu)點：簡單、有效、易于手工實現(xiàn)借助于定義算符之間某種優(yōu)先關(guān)系，尋找“可歸約串”進行歸約尤其有利于表示式分析，但只適合于一類不大文法——算法優(yōu)先文法比如：E+T*F只需要知道*優(yōu)先級高于+，就能夠知道T*F是“可歸約串”廣義講，文法中終止符號即為算符節(jié)目錄舉例:i+i*i第22頁/10/1023算法優(yōu)先分析相關(guān)定義算符文法算符優(yōu)先關(guān)系算符優(yōu)先文法算法優(yōu)先關(guān)系表節(jié)目錄第23頁/10/1024算符文法OG—OperaterGrammer

p107定義：假如文法Ｇ中不存在P→…QR…產(chǎn)生式，其中Q，R∈VN，則稱G為算符文法特點：文法G中任一產(chǎn)生式右部不含兩個非終止符相鄰情況舉例G1(E):E→EAE|(E)|iA→+|*G1不是OG改造為G1’(E):E→E+E|E*E|(E)|iG1’是OG文法G(E)：

E→E+T|TT→T*F|FF→(E)|iG是OG小節(jié)目錄第24頁/10/1025算符優(yōu)先關(guān)系終止符a和b之間三種優(yōu)先關(guān)系表示a<ba優(yōu)先級低于ba=ba優(yōu)先級等于ba>ba優(yōu)先級高于b假如a，b存在優(yōu)先關(guān)系，則a,b是在句型中為相鄰一對終止符，且a一定在b左邊第25頁/10/1026算符優(yōu)先關(guān)系a=bp108設(shè)G為不含ε產(chǎn)生式OG，對于任何a、b∈VT，P、Q、R∈VN，定義：a=b

當(dāng)且僅當(dāng)G中含有形如P→…ab…或P→…aQb…產(chǎn)生式 P…aδb

…其中δ=ε或Q因a，b同時歸約，故a與b優(yōu)先級相同F(xiàn)（

E

）（=）注意：若a，b存在優(yōu)先關(guān)系，則a，b在句型中為相鄰一對終止符，且a一定位于b左邊

第26頁/10/1027算符優(yōu)先關(guān)系a<bp108a<b

當(dāng)且僅當(dāng)G中含有形如P→…aR…產(chǎn)生式，而R=+>b…

或R=+>Qb…其中δ=ε或Q因b先于a被歸約故a優(yōu)先級低于bP…

a

R

…b是由R能推出首遇終止符EE+TT*Fi+<**<i...δb

…第27頁/10/1028算符優(yōu)先關(guān)系a>bp108

a>b

當(dāng)且僅當(dāng)G中含有形如P→…Rb…產(chǎn)生式，而R=+>…a

或R=+>…aQ其中δ=ε或Q因a先于b被歸約故a優(yōu)先級高于bP…

R

b

…a是由R能推出終遇終止符...…

aδEE+TT*FiTF*>+i>*小節(jié)目錄第28頁/10/1029算符優(yōu)先文法p109定義假如不含ε產(chǎn)生式算符文法Ｇ中，若任意兩個終止符之間至多有一個優(yōu)先關(guān)系存在，則稱G為算符優(yōu)先文法OPG—OperatorPrecedenceGrammar注意允許b>c,c>b例+>-，->+不允許b>c,b<c,b=c中任意兩個同時存在b=c不一定c=b例（=），）≠(要求若S=+>a…或S=+>Ra…,則#<a

若S=+>…a或S=+>…aR,則a>#小節(jié)目錄第29頁/10/1030算符優(yōu)先關(guān)系表定義一個算符優(yōu)先文法G終止符之間優(yōu)先關(guān)系能夠用一個矩陣來表示，該矩陣稱為該文法優(yōu)先關(guān)系表用矩陣M表示優(yōu)先關(guān)系表其中(1)a,b∈VT或#。

(2)若a與#存在優(yōu)先關(guān)系，則有

M(#，a)=<M(a，#)=>

M(a，b)=>當(dāng)a>b<當(dāng)a<b

=當(dāng)a=b空白其它(a與b匹配有錯誤)第30頁/10/1031表示式文法算符優(yōu)先關(guān)系表p111表6.5

算符優(yōu)先文法能夠確保優(yōu)先關(guān)系表不含多重入口

(1)相同終止符之間未必是=例+>+，*>*(2)假如有a<b，未必有b>a例+>)，而)>+(3)a，b之間未必一定存在優(yōu)先關(guān)系比如i與i，)與(，不可能相鄰(與#，#與），括號不匹配

+*i()#+><<<>>*>><<>>i>>>>(<<<<=)>>>>#<<<<=b所面臨輸入符號a棧頂終止符小節(jié)目錄第31頁/10/1032算符優(yōu)先關(guān)系表結(jié)構(gòu)FRISTVT集合和LASTVT集合定義FRISTVT集合和LASTVT集合計算算符優(yōu)先關(guān)系表結(jié)構(gòu)結(jié)構(gòu)算法舉例節(jié)目錄第32頁/10/1033FIRSTVT和LASTVT集合定義p109關(guān)于文法G中每個非終止符P：

FIRSTVT(P)={a|P+a…，或者P+Qa…，

a∈VT且Q∈VN}

含義：由P往下推導(dǎo)全部可能出現(xiàn)首個終止符比如：有F→(E)|i

，則(，i∈FIRSTVT(F)

有E→E+T，則EE+T，+∈FIRSTVT(E)

LASTVT(P)={a|P+…a，或者P+…aQ,

a∈VT且Q∈VN}

含義：由P往下推導(dǎo)全部可能出現(xiàn)最終一個終止符比如：有F→(E)|i

，則)，i∈LASTVT(F)

有E→E+T，則EE+T，+∈LASTVT(E)第33頁/10/1034怎樣計算算符優(yōu)先關(guān)系p109-110

=關(guān)系直接看產(chǎn)生式右部，若出現(xiàn)了

A→…ab…或A→…aPb…，則a=b

<關(guān)系若A→…aP…,則b∈FIRSTVT(P),a<b

>關(guān)系若A→…Pb…,則a∈LASTVT(P),a>b小節(jié)目錄第34頁/10/1035集合FIRSTVT(P)算法p111連續(xù)使用下面兩條規(guī)則，直到FIRSTVT(P)不再擴大為止若有P→a…或P→Qa…,則a∈FIRSTVT(P)若a∈FIRSTVT(Q)，且有P→Q…，則a∈FIRSTVT(P)

即FIRSTVT(Q)加入FIRSTVT(P)

文法G[E’]：

E’→#E#E→E+T|T

T→T*F|F

F→(E)|iFIRSTVT(E’)={#}FIRSTVT(F)={(,i}FIRSTVT(T)={*,(,i}FIRSTVT(E)={+,*,(,i}第35頁/10/1036集合LASTVT(P)算法

連續(xù)使用下面兩條規(guī)則，直到LASTVT(P)不再擴大為止若有P→…a或P→…aQ,則a∈LASTVT(P)若a∈LASTVT(Q)，且有P→…Q，則a∈LASTVT(P)

即把LASTVT(Q)中加入LASTVT(P)中

文法G[E’]：

E’→#E#E→E+T|T

T→T*F|FF→(E)|iLASTVT(E’)={#}LASTVT(F)={),i}LASTVT(T)={*,),i}LASTVT(E)={+,*,),i}第36頁/10/1037計算FIRSTVT(P)和LASTVT(P)課堂練習(xí)FIRSTVT(E’)={#}FIRSTVT(P)={(，i}FIRSTVT(F)={↑，(，i}FIRSTVT(T)={*，↑，(，i}FIRSTVT(E)={+，*，↑，(，i}文法G為：E’→#E#E→E+T|T T→T*F|FF→P↑F|PP→(E)|i

BEGINLASTVT(E’)={#}LASTVT(P)={)，i}LASTVT(F)={↑，)，i}LASTVT(T)={*，↑，)，i}LASTVT(E)={+，*，↑，)，i}小節(jié)目錄第37頁/10/1038算符優(yōu)先表結(jié)構(gòu)算法計算每個非終止符PFIRSTVT(P)和LASTVT(P)確定算符優(yōu)先關(guān)系，結(jié)構(gòu)文法算符優(yōu)先表若有A→…ab…或A→…aPb…，則a=b若有A→…aP…,對b∈FIRSTVT(P),則a<b若有A→…Pb…,對a∈LASTVT(P),則a>b把全部沒有定義M(a，b)標(biāo)上“犯錯標(biāo)志”第38頁/10/1039優(yōu)先表結(jié)構(gòu)舉例拓廣G[E’]

(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→iFIRSTVT(E’)={#}FIRSTVT(E)={+,*,(,i}FIRSTVT(T)={*,(,i}FIRSTVT(F)={(,i}LASTVT(E’)={#}LASTVT(E)={+,*,),i}LASTVT(T)={*,),i}LASTVT(F)={),i}+*i()#+*i()#1)=關(guān)系(0)#=#(5)(=)==2）<關(guān)系找形如：A→…aP…(0)#E，則#<FIRSTVT(E)<<<<(1)+T，則+<FIRSTVT(T)<<<(3)*F，則*<FIRSTVT(F)<<(5)(E，則(<FIRSTVT(E)<<<<3）>關(guān)系找形如：A→…Pa…(0)E#，則LASTVT(E)>#>>>>(1)E+，則LASTVT(E)>+>>>>(3)T*，則LASTVT(T)>*>>>(5)E)，則LASTVT(E)>)>>>>4)表中空白格表示對應(yīng)終止符對沒有優(yōu)先關(guān)系小節(jié)目錄第39頁/10/1040算符優(yōu)先分析算法p114算符優(yōu)先分析舉例算符優(yōu)先分析動作算符優(yōu)先分析算法算符優(yōu)先分析與規(guī)范歸約差異節(jié)目錄第40頁/10/1041i1*i2+i3分析過程例文法G[E]E→E+T|TT→T*F|FF→(E)|iEE+TFT*FTFiii步驟棧a輸入串b動作1#

i*i+i##<i

移進i2#i

*i+i#i>*

歸約F→i3#F*i+i##<*移進*4#F*

i+i#*<i移進i5#F*i

+i#i>+歸約F→i6#F*F+i#*>+歸約T→T*F7#T+i##<+移進+8#T+

i#+<i移進i9#T+i

#

i>#歸約F→i10#T+F#

+>#歸約E→E+T11#E#

#=#接收結(jié)構(gòu)歸約第41頁/10/1042算符優(yōu)先分析中可歸約串p114對于算符優(yōu)先文法，句型普通形式為：

#N1a1N2a2…NnanNn+1#

其中ai是終止符，Ni是可有可無非終止符，任何兩個終止符之間至多有一個非終止符一個算符優(yōu)先文法G任何句型最左素短語是滿足以下條件最左子串Njaj…NiaiNi+1

：

aj-1<aj

aj=aj+1，…

，ai-1=ai

ai>ai+1比如句型#i+i*i#

因為#<i

i>+

所以i是最左素短語小節(jié)目錄第42頁/10/1043算符優(yōu)先分析動作移進當(dāng)棧頂終止符＜或＝當(dāng)前輸入符號時歸約當(dāng)棧頂終止符＞當(dāng)前輸入符號時，在棧中尋找最左素短語進行歸約接收當(dāng)棧頂終止符＝當(dāng)前輸入符號＝‘#’

時，分析成功結(jié)束犯錯當(dāng)棧頂終止符與當(dāng)前輸入符號沒有優(yōu)先關(guān)系時第43頁/10/1044i1+i2*i3課堂練習(xí)例文法G[E]E→E+T|TT→T*F|FF→(E)|i步驟棧a輸入串b動作BEGIN1#

i+i*i##<i

移進i2#i

+i*i#i>+

歸約F→i3#F+i*i##<+移進+4#F+

i*i#+<i移進i5#F+i

*i#i>*歸約F→i6#F+F*i#+<*移進*7#F+F*

i#*<i移進i8#F+F*i

#

i>#歸約F→i9#F+F*F#

*>#歸約T→T*F10#F+T#

+>#歸約E→E+T11#E#

#=#接收歸約5次結(jié)構(gòu)歸約小節(jié)目錄第44頁/10/1045算符優(yōu)先分析算法把句型最左素短語歸約到一個非終止符，該非終止符是一個產(chǎn)生式左部符號，此產(chǎn)生式右部和最左素短語組成以下一一對應(yīng)關(guān)系：自左至右，終止符對終止符，非終止符對非終止符，對應(yīng)終止符相同，對應(yīng)非終止符能夠不相同——結(jié)構(gòu)歸約非規(guī)范歸約：不是嚴(yán)格最左歸約算