第4章(3)語法分析算符優(yōu)先

1、自下而上分析法的一般原理自下而上分析法的一般原理自下而上分析法的一般原理自下而上分析法的一般原理:編譯中存在著多種自下而上的分析法，編譯中存在著多種自下而上的分析法，但不管哪種自下而上的分析法都是但不管哪種自下而上的分析法都是按照移按照移進進歸約法的原理建立起來的一種語法分歸約法的原理建立起來的一種語法分析方法。析方法。自下而上分析法的一般原理自下而上分析法的一般原理$t1t3ti-1t2tntiti+1$S基本思想:符號?？梢?guī)約串$A自下而上分析法的一般原理自下而上分析法的一般原理例例1 設(shè)有文法設(shè)有文法GS: (1) S aAcBe(2) A b(3) A A b(4) B d 對輸入串對

2、輸入串a(chǎn)bbcde進行自下而上語法進行自下而上語法分析分析, 檢查該符號串是否該文法的正確檢查該符號串是否該文法的正確句子。句子。 S aAcBe(2) A b(3) A A b(4) B d 輸入串輸入串a(chǎn)bbcde 符號棧符號棧 輸入串輸入串$ abbcde$a bbcde$ab bcde$aA bcde$aAb cde$aA cde$aAc de$aAcd e$aAcB e$aAcBe $S $實現(xiàn)自下而上分析法的實現(xiàn)自下而上分析法的關(guān)鍵問題是如關(guān)鍵問題是如何精確定義可歸約串這個直觀概念，以何精確定義可歸約串這個直觀概念，以及怎樣識別及怎樣識別“可歸約串可歸約串”？自下而上分析法的一般原

3、理自下而上分析法的一般原理 自下而上分析法的一般原理自下而上分析法的一般原理 對對“可歸約串可歸約串”的的不同定義不同定義形成不同形成不同的自下而上的分析方法的自下而上的分析方法: : 在規(guī)范歸約分析法中，是用在規(guī)范歸約分析法中，是用句柄句柄來刻畫可來刻畫可歸約串歸約串 在算符優(yōu)先分析法中在算符優(yōu)先分析法中, ,是用是用最左素短語最左素短語來來刻畫可歸約串。刻畫可歸約串。4.4 算符優(yōu)先分析法算符優(yōu)先分析法方法概述方法概述1.1.算符優(yōu)先分析法算符優(yōu)先分析法所謂算符優(yōu)先分析法就是所謂算符優(yōu)先分析法就是仿照算術(shù)表仿照算術(shù)表達式的四則運算過程達式的四則運算過程而設(shè)計的一種語法分而設(shè)計的一種語法分析

4、方法。析方法。 這種分析方法首先要這種分析方法首先要規(guī)定運算符之間規(guī)定運算符之間( (確切地說終結(jié)符之間確切地說終結(jié)符之間) )的優(yōu)先關(guān)系和結(jié)合的優(yōu)先關(guān)系和結(jié)合性質(zhì)性質(zhì)，然后借助這種關(guān)系，然后借助這種關(guān)系，比較相鄰運算比較相鄰運算符的優(yōu)先級符的優(yōu)先級來確定句型的可歸約串并進行來確定句型的可歸約串并進行歸約。歸約。4.4.1 方法概述方法概述例如：文法例如：文法GE為：為：EE+E | E* *E | (E) | id這個文法是一個二義性文法，因而對這個文法是一個二義性文法，因而對句子句子id+id* *id有兩種不同的規(guī)范歸約，也有兩種不同的規(guī)范歸約，也就是在歸約過程中句型的句柄不唯一。就是在

5、歸約過程中句型的句柄不唯一。4.4.1 方法概述方法概述句子句子id+id* *id的兩種不同的規(guī)范歸約過的兩種不同的規(guī)范歸約過程如下：程如下：第一個規(guī)范歸約過程第一個規(guī)范歸約過程 (1) id + id * * id(2) E + id * * id(3) E + E * * id(4) E + E * * E(5) E + E(6) E 第二個規(guī)范歸約過程第二個規(guī)范歸約過程 id + id * * id(2) E + id * * id(3) E + E * * id(4) E * * id(5) E * * E(6) E4.4.1 方法概述方法概述分析上述歸約過程，句型分析上述歸約過程，

6、句型 E+E* *id : 在第一個規(guī)范歸約中在第一個規(guī)范歸約中id是它的句柄是它的句柄; 在第二個規(guī)范歸約中在第二個規(guī)范歸約中E+E是它的句柄是它的句柄。此現(xiàn)象是由于沒有定義運算符此現(xiàn)象是由于沒有定義運算符+和和* *的優(yōu)的優(yōu)先關(guān)系而引起的。先關(guān)系而引起的。 在第一個規(guī)范歸約中是假定在第一個規(guī)范歸約中是假定* *優(yōu)先于優(yōu)先于+, 所所以不能立即把以不能立即把E+E歸約為歸約為E ; 在第二個規(guī)范歸約中是假定在第二個規(guī)范歸約中是假定+ 優(yōu)先于優(yōu)先于* * , 因此必須先把因此必須先把E+E歸約為歸約為E。4.4.1 方法概述可見上述可見上述歸約過程中起決定作用的是歸約過程中起決定作用的是相鄰兩

7、個終結(jié)符號之間的優(yōu)先關(guān)系相鄰兩個終結(jié)符號之間的優(yōu)先關(guān)系。于。于是算符優(yōu)先分析法的關(guān)鍵在于用合適的是算符優(yōu)先分析法的關(guān)鍵在于用合適的方法去定義任何兩個可能相鄰出現(xiàn)的終方法去定義任何兩個可能相鄰出現(xiàn)的終結(jié)符號結(jié)符號a和和b之間的優(yōu)先關(guān)系。之間的優(yōu)先關(guān)系。4.4.1 方法概述2. 任何兩個相鄰終結(jié)符號a 和 b之間的優(yōu)先關(guān)系有三種： a b.a的優(yōu)先級高于的優(yōu)先級高于b 4.4.1 方法概述 通常表達式中運算符的優(yōu)先關(guān)系有b a.+ （.注意,優(yōu)先關(guān)系與出現(xiàn)的左右次序有優(yōu)先關(guān)系與出現(xiàn)的左右次序有關(guān)關(guān),這一點是不同于數(shù)學(xué)中的,和。但沒有而是有例如不一定有 a b.( + .+ （。（。 .4.4.1

8、方法概述 a b a b 優(yōu)先關(guān)系表算符優(yōu)先分析法借助優(yōu)先關(guān)系表尋找句型的可歸約串。.4.4.1 方法概述優(yōu)先關(guān)系表優(yōu)先關(guān)系表算符優(yōu)先分析算法算符優(yōu)先分析算法符號棧文法規(guī)則詞法分析后的單詞串輸出算符優(yōu)先文法的定義算符優(yōu)先文法的定義1.算符文法的定義設(shè)有文法G, 若G中沒有形如UVW的規(guī)則，其中V和W為非終結(jié)符，則稱G為算符文法，也稱OG文法。 也就是說，在算符文法中，任何一個規(guī)則右部都不存在兩個非終結(jié)符相鄰的情況。 設(shè)G是一個算符文法，a和b是任意兩個終結(jié)符，P、Q、R是非終結(jié)符，算符優(yōu)先關(guān)系 、 、 定義如下： .=.=.ab 當(dāng)且僅當(dāng)G中含有形如(1)Pab 或 PaQb的規(guī)則。2.定義任

9、意兩個終結(jié)符號之間的優(yōu)先 關(guān)系當(dāng)且僅當(dāng)G中含有形如(2)PaR的規(guī)則,ab.PRb3.3.算符優(yōu)先文法的定義算符優(yōu)先文法的定義設(shè)有一個設(shè)有一個不含不含規(guī)則的算符文法規(guī)則的算符文法G，如果，如果任意兩個終結(jié)符號對任意兩個終結(jié)符號對(a，b)在在 、 和和 三種關(guān)系中三種關(guān)系中只有一種關(guān)系成立只有一種關(guān)系成立，則稱，則稱G是是算符優(yōu)先文法，也稱算符優(yōu)先文法，也稱OPG文法。文法。 .又由于又由于EE* *E和和E+E* *E有有+ * *.E+E+ +E 即運算符+ +和*之間存在兩種不同的優(yōu)先關(guān)系，所以該表達式的文法僅是算符文法而不是算符優(yōu)先文法。 若算術(shù)表達式的文法為： E E + T | T

10、T T * F | FF (E) | id顯然,該算術(shù)表達式的文法是算符優(yōu)先文法。 算符優(yōu)先關(guān)系表的構(gòu)造算符優(yōu)先關(guān)系表的構(gòu)造 對算符優(yōu)先文法,根據(jù)優(yōu)先關(guān)系的定義,可按如下方法直接構(gòu)造優(yōu)先關(guān)系表。 首先對文法每個非終結(jié)符定義兩個集合：FIRSTVT(A)=b | A b或A Bb,bVT , BVN +LASTVT(A)=a | A a 或A aB, aVT, BVN + 使用這兩個集合，構(gòu)造文法的優(yōu)先關(guān)系表的算法如下： 輸入：算符優(yōu)先文法輸出：關(guān)于文法的優(yōu)先關(guān)系表方法：方法：1.為每個非終結(jié)符計算為每個非終結(jié)符計算FIRSTVT(A)和和LASTVT(A) 2 .2 .執(zhí)行程序執(zhí)行程序for

11、( 每個產(chǎn)生式每個產(chǎn)生式 Ax1x2xn )for ( i=1; i = n-1 ; i+ ) if ( xi和和xi+1均均 VT) 置置 xi xi+1= =. if ( i = n-2 且且 xi和和xi+2 都都 VT , 而而xi+1 VN ) 置置xi xi+2= =.if ( xiVT , xi+1VN )for ( FIRSTVT(xi+1)中的每個中的每個b)置置xi b;.3. 對對 FIRSTVT(S)中的所有中的所有b，置，置$ b;對對 LASTVT(S)中的所有中的所有a，置，置a $； .置置$ $。= =.（S為文法開始符號）為文法開始符號） .例例 設(shè)有表達式

12、的文法設(shè)有表達式的文法GE：E E + T | TT T * F | FF (E) | id構(gòu)造該文法的算符優(yōu)先關(guān)系表。構(gòu)造該文法的算符優(yōu)先關(guān)系表。 首先計算每個非終結(jié)符的首先計算每個非終結(jié)符的FIRSTVT和和LASTVT：FIRSTVT(A)=b | A b或或A Bb,bVT , BVN +LASTVT(A)=a | A a 或或A aB, aVT, BVN +EE + T | TTT * * F | FF(E) | id FIRSTVT LASTVT E T F * *, +, (, id * *, +, ), id * *, (, id * *, ), id (, id ), id

13、執(zhí)行算法，逐條掃描文法規(guī)則，因有執(zhí)行算法，逐條掃描文法規(guī)則，因有F(E)的規(guī)則，則有的規(guī)則，則有 ( )= =. + * * id ( ) $ + * * id ( ) $= =.+ T 尋找終結(jié)符在左邊，非終結(jié)符在右邊尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號對有的符號對有 則則+ FIRSTVT(T).* * F.則則* * FIRSTVT(F).則則( FIRSTVT(E)( E * *, (, id (, id * *, +, (, id + * * id ( ) $ + * * id ( ) $.則則LASTVT(T) * *T * *.則則LASTVT(E) )E )有有$ $;= =

14、.$ FIRSTVT(E); LASTVT(E) $.= =.= =.= =.EE + T | TTT * * F | FF(E) | id 本節(jié)完本節(jié)完 對于算符優(yōu)先分析法，它雖然是一種自下而上的語法分析方法，但它并不是一種規(guī)范歸約一種規(guī)范歸約的分析方法。 這是因為在算符優(yōu)先文法中，僅在終結(jié)符號之間定義優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，從而無法使用優(yōu)先關(guān)系表去識別由單個非終結(jié)符組成的可歸約串，這也就是說，算符優(yōu)先分析法不是用句柄來刻畫可歸約串，而是用最最左素短語左素短語來刻畫可歸約串的。1. 最左素短語最左素短語 所謂句型的所謂句型的素短語素短語是指這樣一種短是指這樣一種短語，它至少包含一

15、個終結(jié)符，并且除語，它至少包含一個終結(jié)符，并且除自身之外，不再包含其它的素短語。自身之外，不再包含其它的素短語。句型最左邊的素短語稱句型最左邊的素短語稱最左素短語最左素短語。例如，有文法例如，有文法 G E E E + T | T T T * * F | F F (E) | id 求該文法句型求該文法句型T + T * F + id的素短語和的素短語和最左素短語。最左素短語。首先給出句型首先給出句型T+T * *F + id的語法樹的語法樹, ,見見 下圖下圖: :其短語有：其短語有： T + T* *F + id T+T* *F T T* *F id由素短語定義可知由素短語定義可知T* *F

16、和和id是素短語。是素短語。 T* *F為最左素短語。為最左素短語。 注意注意：T是該句型的句柄，而不是素短語。是該句型的句柄，而不是素短語。 E E + TE + T F T T * F id2. . 識別句型最左素短語的方法識別句型最左素短語的方法 由算符文法的定義可知，算符優(yōu)先由算符文法的定義可知，算符優(yōu)先文法的任何句型都沒有相鄰的兩個非終文法的任何句型都沒有相鄰的兩個非終結(jié)符。結(jié)符。其句型總可以表示成：其句型總可以表示成：$ N1a1 N2a2 Nnan Nn+1$ 其中每個其中每個Ni為非終結(jié)符或空為非終結(jié)符或空, ai為終結(jié)符為終結(jié)符（1in）對算符優(yōu)先文法對算符優(yōu)先文法G有如下定

17、理：有如下定理： 一個算符優(yōu)先文法一個算符優(yōu)先文法G的任何句型的最左的任何句型的最左素短語是滿足下列條件的最左子串素短語是滿足下列條件的最左子串:Ni ai Ni+1 ai+1 aj Nj+1 ai-1 ai.需要指出的是出現(xiàn)在需要指出的是出現(xiàn)在ai左端的非終左端的非終結(jié)符結(jié)符Ni和和aj右端的非終結(jié)符右端的非終結(jié)符Nj+1是屬于素是屬于素短語的。短語的。 這是由于算符文法的任何句型中終這是由于算符文法的任何句型中終結(jié)符和非終結(jié)符相鄰時含終結(jié)符的短語結(jié)符和非終結(jié)符相鄰時含終結(jié)符的短語必含相鄰非終結(jié)符。必含相鄰非終結(jié)符。 對上述句型對上述句型 $ T+T* *F+id $ 寫成算符寫成算符優(yōu)先分

18、析形式為：優(yōu)先分析形式為：ai ai+1, , aj-1 aj= =.= =.aj aj+1 .ai-1 ai.$ N1a1N2a2N3a3a4$ 故由最左素短語定理有故由最左素短語定理有N2a2N3 即即T* *F 是是 最左素短語。最左素短語。 因有因有 $ + * * + id $.根據(jù)最左素短語的定理根據(jù)最左素短語的定理，最左素短語，最左素短語中的終結(jié)符號具有相同的優(yōu)先關(guān)系，并且，中的終結(jié)符號具有相同的優(yōu)先關(guān)系，并且，由于最左素短語中的符號是當(dāng)時最先要歸由于最左素短語中的符號是當(dāng)時最先要歸約的串，其優(yōu)先關(guān)系先于最左素短語之外約的串，其優(yōu)先關(guān)系先于最左素短語之外的符號，所以的符號，所以我

19、們使用一個用于存放文法我們使用一個用于存放文法符號的先進后出棧，并利用優(yōu)先關(guān)系表，符號的先進后出棧，并利用優(yōu)先關(guān)系表，可以確定最左素短語是否已形成來決定分可以確定最左素短語是否已形成來決定分析器的動作析器的動作。 3. 3. 算符優(yōu)先分析程序的設(shè)計算符優(yōu)先分析程序的設(shè)計基本思想基本思想: :$t1t3tj+1t2tjti+1tn$符號棧符號棧優(yōu)先關(guān)系優(yōu)先關(guān)系ti 尾尾頭頭最左素短語最左素短語3. 3. 算符優(yōu)先分析程序的設(shè)計算符優(yōu)先分析程序的設(shè)計 .= =.aj aj+1ai ai aj-1 aj=.=.返回圖下面給出算符優(yōu)先分析算法。 輸入：輸入符號串W和優(yōu)先關(guān)系表。 輸出：若W是正確的句子，則接收， 否則輸出錯誤信息。 方法：執(zhí)行下圖算法。棧置初值 K 1, SK $ 當(dāng)前輸入符號讀入aSK是終結(jié)符？j K Y j K1NS j 是終結(jié)符？Q S j , j j-1YS j+1SK是最左素短語K j+1 , SK NY. K=2 且 a =$?結(jié)束YNSK aK K+1YerrorNj j-1NS j a ?.S j a ? 或 S j a ?N.=.YS j Q?.= =.歸約id$移進$.歸約$.$=.結(jié)束$id+ id $移進.$ N+id $移進.歸約