編譯原理第08章

1、第八章第八章 自自下下而而上上語法分析語法分析u概述概述u算符優(yōu)先分析法算符優(yōu)先分析法uLR分析法分析法語法分析語法分析 編譯理論中，語法分析是對高級語編譯理論中，語法分析是對高級語言的言的語法單位語法單位的結(jié)構(gòu)進(jìn)行分析。的結(jié)構(gòu)進(jìn)行分析。 語法單位結(jié)構(gòu)可以用語法單位結(jié)構(gòu)可以用上下文無關(guān)文上下文無關(guān)文法法來描述，而來描述，而下推自動(dòng)機(jī)下推自動(dòng)機(jī)可用于識別可用于識別上下文無關(guān)文法所描述的語言。上下文無關(guān)文法所描述的語言。 上下文無關(guān)文法及下推自動(dòng)機(jī)是語上下文無關(guān)文法及下推自動(dòng)機(jī)是語法分析的法分析的理論基礎(chǔ)理論基礎(chǔ)。語法分析語法分析 對無關(guān)文法對無關(guān)文法G=(VT，VN，S，P)及符號串及符號串w

2、w，判斷，判斷w w是否是文法是否是文法G的的一個(gè)合法一個(gè)合法句子句子。即即 S= S=* *w w ？ 語法分析的方法通常有兩類：語法分析的方法通常有兩類： 自上而下自上而下(自頂向下自頂向下)的分析方法的分析方法 自下而上自下而上(自底向上自底向上)的分析方法的分析方法 語法分析方法的分類語法分析方法的分類自上而下自上而下的語法分析分析過程分析過程 從文法開始符出發(fā)，能否找到一個(gè)從文法開始符出發(fā)，能否找到一個(gè)最左推導(dǎo)最左推導(dǎo)序列，使得序列，使得S=*w 或者從根結(jié)點(diǎn)或者從根結(jié)點(diǎn)S開始，能否構(gòu)造一開始，能否構(gòu)造一棵棵語法樹語法樹，使得該語法樹的葉結(jié)點(diǎn)自，使得該語法樹的葉結(jié)點(diǎn)自左至右的連接正好

3、是左至右的連接正好是w自上而下自上而下的語法分析具體方法：具體方法： 遞歸下降法、預(yù)測分析法遞歸下降法、預(yù)測分析法前提條件：前提條件： 提取公共左因子提取公共左因子 消除消除左遞歸左遞歸u缺陷：效率低；只適合部分文法缺陷：效率低；只適合部分文法自下而上自下而上的語法分析分析過程分析過程 從從w出發(fā)，能否找到一個(gè)出發(fā)，能否找到一個(gè)最左規(guī)約最左規(guī)約（最右推導(dǎo)的逆過程）序列，逐步向（最右推導(dǎo)的逆過程）序列，逐步向上規(guī)約，直至文法的開始符上規(guī)約，直至文法的開始符S； 或者對生成或者對生成w的語法樹，按最左規(guī)約的語法樹，按最左規(guī)約對語法樹進(jìn)行剪枝，能否最后只剩下對語法樹進(jìn)行剪枝，能否最后只剩下根結(jié)點(diǎn)根結(jié)

4、點(diǎn)S。第一節(jié)第一節(jié) 概述概述自下而上分析：自下而上分析： 從從輸入串輸入串出發(fā)，尋找出發(fā)，尋找歸約歸約序列，序列， 逐步進(jìn)行歸約，直至逐步進(jìn)行歸約，直至開始符號開始符號S方法：方法： 基于基于下推自動(dòng)機(jī)下推自動(dòng)機(jī)(利用符號棧利用符號棧 ) 移進(jìn)移進(jìn)-歸約歸約方法方法:移進(jìn)移進(jìn)-歸約歸約 (0) 初始：桟為空，輸入指針指向初始：桟為空，輸入指針指向第一個(gè)輸入符號；第一個(gè)輸入符號； (1) 將當(dāng)前輸入符號將當(dāng)前輸入符號移進(jìn)移進(jìn)棧中，輸棧中，輸入指針指向下一個(gè)輸入符號；入指針指向下一個(gè)輸入符號； ( 2) 如果棧頂（一個(gè)或多個(gè)符號）如果棧頂（一個(gè)或多個(gè)符號）形成某個(gè)非終結(jié)符號的形成某個(gè)非終結(jié)符號的候

5、選式；候選式；轉(zhuǎn)向轉(zhuǎn)向(3);否則，轉(zhuǎn)向（否則，轉(zhuǎn)向（1） (3)進(jìn)行進(jìn)行歸約歸約: 將候選式出桟；將候選式出桟； 歸約后的非終結(jié)符號歸約后的非終結(jié)符號移進(jìn)移進(jìn)棧；棧； 轉(zhuǎn)向（轉(zhuǎn)向（2）(4)重復(fù)進(jìn)行上述過程，直到輸入重復(fù)進(jìn)行上述過程，直到輸入串掃描結(jié)束串掃描結(jié)束(以以#作為結(jié)束標(biāo)記作為結(jié)束標(biāo)記)。 （分析結(jié)束分析結(jié)束） 語法分析結(jié)果語法分析結(jié)果如果棧內(nèi)只剩下如果棧內(nèi)只剩下開始符號開始符號S，則，則 輸入串是文法句子；輸入串是文法句子； 否則，否則， 輸入串不是句子。輸入串不是句子。例例8-1文法文法G： SSAS Sb AccA Aa輸入串輸入串bccab的歸約過程為：的歸約過程為：bScS

6、ccSaccSAccSASbASSASSG(S)： SSAS Sb AccA Aa輸入串輸入串bccab#符號棧符號棧b Scca AAb SS歷史記錄歷史記錄SbAaAccASb SSAS歸約系列歸約系列 bccab=Sccab=SccAb=SAb=SAS3.句柄：句柄： 一個(gè)句型的一個(gè)句型的最左直接短語最左直接短語。4.素短語素短語: 是是短語短語，至少包含一個(gè)，至少包含一個(gè)終結(jié)符終結(jié)符,且且不再含更小的素短語不再含更小的素短語5.最左素短語最左素短語: 句型中最左的素短語。句型中最左的素短語。例例: G(E) EE+T|T TT*F|F F(E)|I求求T*F+i的的短語短語、直接短語、

7、句柄、直接短語、句柄 EE+TT+TT*F+TT*F+FT*F+i T*F+i是關(guān)于是關(guān)于E的短語的短語 T*F是關(guān)于是關(guān)于E的短語的短語 句型句型：推導(dǎo)樹的葉結(jié)點(diǎn)自左至右連接：推導(dǎo)樹的葉結(jié)點(diǎn)自左至右連接短語短語：子樹的邊緣是相對于根的短語：子樹的邊緣是相對于根的短語直接短語直接短語：有且僅有兩層的子樹的邊：有且僅有兩層的子樹的邊緣是相對于根的直接短語緣是相對于根的直接短語句柄句柄：位于最左的有且僅有兩層的子：位于最左的有且僅有兩層的子樹的邊緣樹的邊緣推導(dǎo)樹確定短語推導(dǎo)樹確定短語EET+TTFFi*例例: G(E) EE+T|T TT*F|F F(E)|I求求T*F+i的短語、直接短語、句柄的

8、短語、直接短語、句柄 SaAcBe AAb|b Bd abbcde的的LR和算符優(yōu)先和算符優(yōu)先分析過程分析過程例例: LR和算符優(yōu)先和算符優(yōu)先分析一致分析一致SabbcdeaAbcdeaAcdeaAcBeSaSaAcBeAAb|bBd AcBeAbdb EE+TT TT*FF F(E) i i+i*i的的LR分析過程分析過程(按按句柄句柄歸約歸約)例例: G(E)i+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TEEET+FTii*FTiF共共8步歸約步歸約例例 : G(E) EE+TT TT*FF F(E) i i+i*i的的算符優(yōu)先分析算符優(yōu)先分析過程（按照過程（

9、按照最左素短語最左素短語進(jìn)行歸約）進(jìn)行歸約）EET+FTii*FTiFi+i*iF+i*iF+F*iF+F*FF+TE共共5步歸約步歸約注意：注意： 按最左素短語歸約是按最左素短語歸約是結(jié)構(gòu)歸約：結(jié)構(gòu)歸約： 處于棧頂待歸約的最左素短語與對處于棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)生式在應(yīng)的產(chǎn)生式在結(jié)構(gòu)上一致結(jié)構(gòu)上一致 即長度一致即長度一致, 對應(yīng)的對應(yīng)的終結(jié)符終結(jié)符一致一致 而非終結(jié)符可以不一致。而非終結(jié)符可以不一致。 回顧：素短語必須含有終結(jié)符回顧：素短語必須含有終結(jié)符!按最左素短語進(jìn)行歸約按最左素短語進(jìn)行歸約優(yōu)點(diǎn)優(yōu)點(diǎn) 按照最左素短語進(jìn)行的歸約按照最左素短語進(jìn)行的歸約 省略省略了了A 的產(chǎn)生式的使

10、用。的產(chǎn)生式的使用。其中：其中： VN+ (非終結(jié)符號串非終結(jié)符號串) 效率較高效率較高按最左素短語進(jìn)行歸約按最左素短語進(jìn)行歸約缺點(diǎn)缺點(diǎn) 并不是任何文法都可以按照最并不是任何文法都可以按照最左素短語進(jìn)行歸約。左素短語進(jìn)行歸約。 例如：例如： S AB A a B b對于串對于串a(chǎn)b的分析的分析 按最左素短語進(jìn)行歸約按最左素短語進(jìn)行歸約缺點(diǎn)缺點(diǎn)只有只有部分文法可以進(jìn)行算符優(yōu)部分文法可以進(jìn)行算符優(yōu)先分析先分析思考思考算符優(yōu)先分析的算符優(yōu)先分析的條件條件? 在算術(shù)表達(dá)式中，有運(yùn)算符號的在算術(shù)表達(dá)式中，有運(yùn)算符號的優(yōu)先級和結(jié)合性的規(guī)定。優(yōu)先級和結(jié)合性的規(guī)定。 算符優(yōu)先分析法算符優(yōu)先分析法就是就是仿效仿

11、效表達(dá)式表達(dá)式的的計(jì)算過程計(jì)算過程而設(shè)計(jì)的。而設(shè)計(jì)的。 第二節(jié)第二節(jié) 算符優(yōu)先分析法算符優(yōu)先分析法使用終結(jié)符號之間的使用終結(jié)符號之間的歸約順序歸約順序進(jìn)行語法分析。進(jìn)行語法分析。一、算符優(yōu)先文法一、算符優(yōu)先文法1. 算符文法算符文法 上下文無關(guān)文法上下文無關(guān)文法G如果沒有形如如果沒有形如 P 或或 P. . .QR. . .的產(chǎn)生式，則稱的產(chǎn)生式，則稱G為為算符文法算符文法。對算符文法對算符文法G, a,b VT 定義定義(1)a=b G有有P. . .ab. . . 或或 P. . .aQb. . .(2)ab G有有P. . .Qb. . . 且且Q+. . .a 或或Q+aR2. 相鄰相

12、鄰2個(gè)個(gè)終結(jié)符終結(jié)符之間優(yōu)先關(guān)系定義之間優(yōu)先關(guān)系定義(1)a=b P.ab.或或P.aQb.PbaQ推廣推廣u一個(gè)候選式中的所有終結(jié)符的優(yōu)一個(gè)候選式中的所有終結(jié)符的優(yōu)先關(guān)系都相等先關(guān)系都相等 (2)ab G中有中有P.Qb. 且且Q+.a或或Q+aRPabQLASTVT集合集合LASTVT(Q) =a|Q+.a 或或 Q+aR a VT,R VN3. 算符優(yōu)先文法算符優(yōu)先文法 若算符文法若算符文法G的終結(jié)符的終結(jié)符a、b之間之間的優(yōu)先關(guān)系的優(yōu)先關(guān)系 至多只有至多只有=、中的中的一個(gè)一個(gè)或者或者 終結(jié)符終結(jié)符a、b之間之間沒有優(yōu)先關(guān)系沒有優(yōu)先關(guān)系 則則G稱為稱為算符優(yōu)先文法算符優(yōu)先文法。 最左素

13、短語的判定最左素短語的判定 句型的一般形式為：句型的一般形式為： #N1a1N2a2NnanNn+1# 最左素短語是滿足條件的最左素短語是滿足條件的最左最左子串子串NjajNj+1NiaiNi+1條件：條件： aj-1ai+1Pai+1QNiaiNi+1 NjajNj+1aj-1 棧頂待歸約的最左素短語與對應(yīng)棧頂待歸約的最左素短語與對應(yīng)的產(chǎn)生式的產(chǎn)生式 結(jié)構(gòu)一致結(jié)構(gòu)一致 即長度一致即長度一致, 對應(yīng)的終結(jié)符一致對應(yīng)的終結(jié)符一致而非終結(jié)符可以不一致。而非終結(jié)符可以不一致。歸約最左素短語的方法歸約最左素短語的方法-結(jié)構(gòu)歸約結(jié)構(gòu)歸約 根據(jù)優(yōu)先關(guān)系的定義，可以得到根據(jù)優(yōu)先關(guān)系的定義，可以得到終結(jié)符之間

14、的所有優(yōu)先關(guān)系。終結(jié)符之間的所有優(yōu)先關(guān)系。G（E）: EE+T|T TT*F|F F(E)|i+*ii()#=算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表思考思考u特殊符號特殊符號#的優(yōu)先關(guān)系如何確定的優(yōu)先關(guān)系如何確定?對文法進(jìn)行改造，得：對文法進(jìn)行改造，得：G（S）: S #E# EE+T|T TT*F|F F(E)|i(1)相同終結(jié)符的優(yōu)先關(guān)系未必是相同終結(jié)符的優(yōu)先關(guān)系未必是=(2)有有aa(3)a、b之間未必一定有優(yōu)先關(guān)系之間未必一定有優(yōu)先關(guān)系 注意注意思考思考 兩個(gè)終結(jié)符之間若沒有優(yōu)先關(guān)系兩個(gè)終結(jié)符之間若沒有優(yōu)先關(guān)系 則表示則表示?二二. 算符優(yōu)先分析算法算符優(yōu)先分析算法 設(shè)設(shè)a為棧頂終結(jié)符為棧頂終結(jié)

15、符初始化初始化: #棧棧a=b=#ab歸約歸約最左素短語最左素短語:最左素短語出棧最左素短語出棧, 左部符號入棧左部符號入棧b入棧入棧結(jié)束結(jié)束出錯(cuò)出錯(cuò)YNYYNN讀一符號讀一符號bk:=1; Sk:=#;repeat a:=下一輸入符號；下一輸入符號； if Sk VT then j:=k else j:=k-1; while Sja do begin repeat Q:=Sj; if Sj-1 VT then j:=j-1 else j:=j-2 until SjQ; 把把Sj+1Sk歸約為某個(gè)歸約為某個(gè)N; k:=j+1; Sk:=N end of while; if Sja or Sj=

16、a then begin k:=k+1; Sk:=a end else erroruntil a=#; EE+TT TT*FF F(E) i i+i*i的分析過程的分析過程例例 G(E)步驟步驟1234567891011下推棧下推棧輸入串輸入串動(dòng)作動(dòng)作#i+i*i#+, 用用Fi歸約歸約#F +i*i#+, 移進(jìn)移進(jìn)+#F+ i*i#+*, 用用Fi歸約歸約#F+F *i#+*, 移進(jìn)移進(jìn)*#F+F* i#*#, 用用Fi歸約歸約*#, 用用TT*F歸約歸約+#, 用用EE+T歸約歸約結(jié)束結(jié)束#F+F*F#F+T#EEET+FTii*FTiFi+i*iF+i*iF+F*iF+F*FF+TE (

17、1)FIRSTVT集集FIRSTVT(P)= a|P+a 或或 P+Qa三、優(yōu)先關(guān)系表的構(gòu)造三、優(yōu)先關(guān)系表的構(gòu)造若若Pa或或PQa 則則 a FIRSTVT(P)若若PQ 則則 FIRSTVT(Q) FIRSTVT(P)直至直至FIRSTVT(P)不再增大。不再增大。 (2)LASTVT集集LASTVT(P)= a|P+.a 或或 P+aQ若若P.a或或PaQ 則則 a LASTVT(P)若若P.Q 則則 LASTVT(Q) LASTVT(P)直至直至LASTVT(P)不再增大。不再增大。例例 G(E) EE+TT TT*FF F(E) iETFFIRSTVTLASTVT( i + *( i)

18、 i + *) i *) i( i *（3）求）求FIRSTVT集的矩陣規(guī)則集的矩陣規(guī)則若若Pa 或或 PQa 則則MP,a:=1若若PQ 則對所有的則對所有的MQ,a=1置置MP,a:=1重復(fù)上述兩步，直到矩陣不再變化重復(fù)上述兩步，直到矩陣不再變化(4)求求LASTVT集的矩陣規(guī)則集的矩陣規(guī)則若若Pa 或或 PaQ 則則MP,a:=1;若若PQ 則對所有的則對所有的MQ,a=1置置MP,a:=1重復(fù)上述兩步，直到矩陣不再變化重復(fù)上述兩步，直到矩陣不再變化例例 G(E) EE+TT TT*FF F(E) iFIRSTVTLASTVTE ET TF FETF * i （ ） * i （ ） *

19、i （ ）11111 11 1 111111 11 1 1FOR 每條產(chǎn)生式每條產(chǎn)生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和和Xi+1均為終結(jié)符均為終結(jié)符 THEN Xi= Xi+1; /ab IF i=n-2 且且 Xi和和Xi+2均為終結(jié)符均為終結(jié)符 但但 Xi+1 VN THEN Xi=Xi+2; /aQb (5)構(gòu)造優(yōu)先關(guān)系表的算法構(gòu)造優(yōu)先關(guān)系表的算法IF Xi=a VT, Xi+1=Q VN /aQ THEN b FIRSTVT(Q) abEND例例 G(E) EE+TT TT*FF F(E) iETFFIRSTVTLASTVT( i +

20、 *( i) i + *) i *) i( i *+*ii()#=算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表u如果一個(gè)文法是算符優(yōu)先文法，則如果一個(gè)文法是算符優(yōu)先文法，則 對應(yīng)的算符優(yōu)先關(guān)系表沒有沖突對應(yīng)的算符優(yōu)先關(guān)系表沒有沖突u也是判斷文法是否為算符優(yōu)先文法也是判斷文法是否為算符優(yōu)先文法的方法的方法 第三節(jié)第三節(jié) LR分析法分析法一一. LR(K) 分析法分析法 LR分析法分析法從左向右從左向右掃描輸入串掃描輸入串 分析分析棧中符號棧中符號及及向前搜索向前搜索K個(gè)輸入符號個(gè)輸入符號 以確定是否已在棧頂形成以確定是否已在棧頂形成句柄句柄 從而決定應(yīng)采取的動(dòng)作。從而決定應(yīng)采取的動(dòng)作。LR(K)分析法分析法 只

21、考慮只考慮K=0、1的情況。的情況。s0sm-1smaia1驅(qū)動(dòng)程序驅(qū)動(dòng)程序其組成為其組成為: :棧棧, ,控制程序控制程序, ,分析表分析表, ,輸入串輸入串輸入串輸入串分析棧分析棧輸出輸出actiongoto分析表分析表.存放存放狀態(tài)狀態(tài) 初始時(shí)初始時(shí),置初始狀態(tài)置初始狀態(tài)0; 棧里的每個(gè)狀態(tài)棧里的每個(gè)狀態(tài)概括概括了從分析開了從分析開始到此時(shí)已進(jìn)行的分析工作。始到此時(shí)已進(jìn)行的分析工作。1. 1. 分析棧分析棧包括包括action和和goto兩個(gè)子表兩個(gè)子表 (1)actions,a 在狀態(tài)在狀態(tài)s下下, 當(dāng)前輸入符號為當(dāng)前輸入符號為a時(shí)時(shí) 應(yīng)采取的分析動(dòng)作應(yīng)采取的分析動(dòng)作: 移進(jìn)移進(jìn), 歸

22、約歸約,接收接收, 出錯(cuò)出錯(cuò)。 2. 分析表分析表(2) gotos,X表表 狀態(tài)及非終結(jié)符的二維矩陣狀態(tài)及非終結(jié)符的二維矩陣 在狀態(tài)在狀態(tài)s下下, 歸約后的符號歸約后的符號X的的對應(yīng)應(yīng)該入棧的對應(yīng)應(yīng)該入棧的狀態(tài)狀態(tài)。 (0)S E (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)FiLR分析表為分析表為例例 G0(E)11LR分析表分析表狀狀態(tài)態(tài)012345678910actiongotoi+*()ETFs5s4123s6accr2s7r2r2r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5

23、r5r5 (1) actions,a=sj 則將狀態(tài)則將狀態(tài)j移進(jìn)移進(jìn)棧頂棧頂, 輸入指針指向下一輸入符號輸入指針指向下一輸入符號;3. 控制程序的工作控制程序的工作- actions,a(2) actions,a=rj 按第按第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式A歸約歸約 分析棧棧頂上托分析棧棧頂上托| |個(gè)狀態(tài)出棧個(gè)狀態(tài)出棧, 目前目前 棧頂?shù)臓顟B(tài)為棧頂?shù)臓顟B(tài)為i, 則根據(jù)則根據(jù)i及及A, 查查goto表表, gotoi,A=k, 則將狀態(tài)則將狀態(tài)k壓入分析棧棧頂。壓入分析棧棧頂。(3)actions,a=acc, 則結(jié)束分析則結(jié)束分析,輸入串被輸入串被接收接收。(4)若若actions,a或或gotos

24、,A為為空空 轉(zhuǎn)轉(zhuǎn)出錯(cuò)出錯(cuò)處理程序。處理程序。123456789分析棧分析棧符號棧符號棧輸入串輸入串動(dòng)作動(dòng)作(i+i*i)移進(jìn)移進(jìn) +i*i)移進(jìn)移進(jìn)00,40,4,5 i+i*i)歸約歸約0,4,3 +i*i)歸約歸約0,4,2 +i*i)歸約歸約0,4,8 +i*i)移進(jìn)移進(jìn)0,4,8,6 i*i)移進(jìn)移進(jìn)0,4,8,6,5 *i)歸約歸約0,4,8,6,3 *i)歸約歸約例例: (i+i*i)的分析過程（不使用符號棧）的分析過程（不使用符號棧）101112131415161718190,4,8,6,9*i)移進(jìn)移進(jìn)0,4,8,6,9,7 i)移進(jìn)移進(jìn)0,4,8,6,9,7,5 )歸約歸約

25、0,4,8,6,9,7,10 )歸約歸約0,4,8,6,9 )歸約歸約0,4,8 )移進(jìn)移進(jìn)0,4,8,11 歸約歸約0,3 歸約歸約0,2 歸約歸約0,1 接受接受(續(xù)表續(xù)表)123456789分析棧分析棧符號棧符號棧輸入串輸入串動(dòng)作動(dòng)作(i+i*i)移進(jìn)移進(jìn),(,i +i*i)移進(jìn)移進(jìn)00,40,4,5,( i+i*i)歸約歸約0,4,3,(,F +i*i)歸約歸約0,4,2,(,T +i*i)歸約歸約0,4,8,(,E +i*i)移進(jìn)移進(jìn)0,4,8,6,(,E,+ i*i)移進(jìn)移進(jìn)0,4,8,6,5,(,E,+,i *i)歸約歸約0,4,8,6,3,(,E,+,F *i)歸約歸約例例:

26、(i+i*i)的分析過程的分析過程(使用符號棧使用符號棧)101112131415161718190,4,8,6,9,(,E,+,T*i)移進(jìn)移進(jìn)0,4,8,6,9,7,(,E,+,T,* i)移進(jìn)移進(jìn)0,4,8,6,9,7,5,(,E,+,T,*,i )歸約歸約0,4,8,6,9,7,10,(,E,+,T,*,F )歸約歸約0,4,8,6,9,(,E,+,T )歸約歸約0,4,8,(,E )移進(jìn)移進(jìn)0,4,8,11,(,E,) 歸約歸約0,3,F 歸約歸約0,2,T 歸約歸約0,1,E 接受接受(續(xù)表續(xù)表)EET+FTii*FTiF(i+i*i)(F+i*i)(T+i*i)(E+i*i)(E

27、+F*i)(E+T*i)(E+T*F)(E+T)(E)FTESF()S4. 幾種幾種LR分析法及其比較分析法及其比較 LR(0)、 SLR(1) LR(1)、 LALR(1) 分析能力，分析能力， LR(1)最強(qiáng)，最強(qiáng)，LALR(1)次之，次之， LR(0)最弱。最弱。LOOKAHEADScent 它們的它們的分析表的形式分析表的形式和和控制程控制程序序都是相同的都是相同的 差別在于差別在于分析表的內(nèi)容分析表的內(nèi)容。LR分析表可能存在沖突分析表可能存在沖突 在狀態(tài)在狀態(tài)S下，當(dāng)前輸入符為下，當(dāng)前輸入符為a時(shí)，時(shí)，采取的分析動(dòng)作有移進(jìn)和歸約。采取的分析動(dòng)作有移進(jìn)和歸約。 LR分析表在某些狀態(tài)下的

28、動(dòng)作分析表在某些狀態(tài)下的動(dòng)作既有移進(jìn)又有歸約既有移進(jìn)又有歸約 或有兩個(gè)以上或有兩個(gè)以上不同的歸約不同的歸約移進(jìn)移進(jìn)-歸約歸約或或歸約歸約-歸約歸約沖突。沖突。 LR(0)采取簡單的方法構(gòu)造分析采取簡單的方法構(gòu)造分析表，分析表不大，分析簡單，但表，分析表不大，分析簡單，但只對無沖突的文法有效。只對無沖突的文法有效。 SLR(1) 可以解決一類文法的沖突，可以解決一類文法的沖突，分析能力強(qiáng)于分析能力強(qiáng)于LR(0)，而分析表大，而分析表大小與小與LR(0)相同。相同。 LR(1) 則采取精確的辦法解決一則采取精確的辦法解決一大類文法的沖突，分析能力最強(qiáng)，大類文法的沖突，分析能力最強(qiáng)，但分析表大了很多

29、。但分析表大了很多。 LALR(1)則是在則是在SLR(1)和和LR(1)之間的折衷，但分析表的大小與之間的折衷，但分析表的大小與SLR(1)相同。相同。二二.LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族1. 活前綴活前綴: 規(guī)范句型規(guī)范句型的不含句柄之后任何的不含句柄之后任何符號的一個(gè)符號的一個(gè)前綴前綴若若A是文法的產(chǎn)生式是文法的產(chǎn)生式,且有且有 S* A 則則的任何前綴都是規(guī)范句型的任何前綴都是規(guī)范句型的的活前綴，包括活前綴，包括 、 和和 RR 活前綴活前綴 不含句柄的任何符號不含句柄的任何符號, 期待期待符符號串號串 入棧入棧 活前綴活前綴只含句柄的真前綴，即只含句柄的真前綴，即 已已經(jīng)入棧，經(jīng)

30、入棧，期待期待 入棧入棧 活前綴活前綴已含句柄的全部符號已含句柄的全部符號 ，表，表明產(chǎn)生式明產(chǎn)生式A的右部符號的右部符號已經(jīng)入已經(jīng)入棧，應(yīng)將棧，應(yīng)將歸約為歸約為A活前綴與句柄活前綴與句柄之間的三種關(guān)系之間的三種關(guān)系 句柄句柄是第是第3類活前綴的類活前綴的后綴后綴 若能識別一個(gè)文法的若能識別一個(gè)文法的所有活前綴所有活前綴（包括第（包括第3類活前綴）類活前綴）, 也就能識別文法的所有句柄。也就能識別文法的所有句柄?；钋熬Y的識別過程：活前綴的識別過程： - - :在產(chǎn)生式右部添加一個(gè)圓點(diǎn)在產(chǎn)生式右部添加一個(gè)圓點(diǎn) 如如A、A 、A歸約歸約項(xiàng)目項(xiàng)目:形如形如A 移進(jìn)移進(jìn)項(xiàng)目項(xiàng)目:形如形如A a a V

31、T待約待約項(xiàng)目項(xiàng)目:形如形如A B B VN接受接受項(xiàng)目項(xiàng)目:形如形如S S為開始符號為開始符號2. 項(xiàng)目及分類項(xiàng)目及分類3. 拓廣文法拓廣文法 增加產(chǎn)生式增加產(chǎn)生式SS SS 唯一的接受項(xiàng)目唯一的接受項(xiàng)目文法所有產(chǎn)生式的項(xiàng)目有文法所有產(chǎn)生式的項(xiàng)目有:1.S E 2.SE 3.E E+T 4.EE +T 5.EE+ T 6.EE+T 7.E T 例如例如, 文法文法 SE EE+T|T TT*F|F F(E)|i8.ET 9.T T*F10.TT *F11.TT* F12.TT*F 13.T F14.TF 15.F (E) 16.F( E) 17.F(E ) 18.F(E) 19.F i20.

32、Fi (1)對于項(xiàng)目對于項(xiàng)目A , 如果有如果有 S * A則稱則稱A 對活前綴對活前綴有效。有效。即即 到達(dá)項(xiàng)目到達(dá)項(xiàng)目A 時(shí)時(shí), 已識別出已識別出, 希望繼續(xù)識別希望繼續(xù)識別 串。串。 5. 項(xiàng)目的有效性項(xiàng)目的有效性有效性有效性AX 對對 有效有效AX 對對有效有效AX對對X有效有效AX對對X 有效有效 (2) A Br對活前綴對活前綴有效有效 則則B 對活前綴對活前綴也有效也有效 期待期待B的入棧的入棧， 實(shí)際是期待實(shí)際是期待串入棧串入棧 歸約為歸約為B后后 出棧，而出棧，而B入棧入棧對某個(gè)活前綴有效的項(xiàng)目可對某個(gè)活前綴有效的項(xiàng)目可能不止一個(gè)能不止一個(gè)AX 對對 有效有效AX 對對有效有

33、效AX對對X有效有效AX對對X 有效有效注意：注意： 后若為非終結(jié)符后若為非終結(jié)符 則還有有效項(xiàng)目則還有有效項(xiàng)目 對活前綴對活前綴 有效的項(xiàng)目的有效的項(xiàng)目的集合集合-對對 的的有效項(xiàng)目集有效項(xiàng)目集。對活前綴對活前綴有效的項(xiàng)目的有效的項(xiàng)目的集合集合-對對的的有效項(xiàng)目集有效項(xiàng)目集。對活前綴對活前綴 有效的項(xiàng)目的有效的項(xiàng)目的集合集合-對對 的的有效項(xiàng)目集有效項(xiàng)目集。(3)有效項(xiàng)目集有效項(xiàng)目集: (4)LR(0)項(xiàng)目集規(guī)范項(xiàng)目集規(guī)范族族: 文法文法G所有所有有效項(xiàng)目集組成的集合有效項(xiàng)目集組成的集合設(shè)設(shè)I是文法是文法G的一個(gè)的一個(gè)LR(0)項(xiàng)目集項(xiàng)目集,(1)對對i I,都有都有i closure(I)

34、;(2)若若AB closure(I), 且且B為文法為文法G的一個(gè)產(chǎn)生式的一個(gè)產(chǎn)生式, 則則B closure(I)； (3)重復(fù)重復(fù)(2)直至直至closure不再增大。不再增大。6. closure(I)go(I,X) =closure(AX |A XI) A X 對對有效有效 AX對對X有效有效7. go(I,X) 設(shè)設(shè)X VTVN 狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)go(I，X) u將圓點(diǎn)逐步向右移動(dòng)將圓點(diǎn)逐步向右移動(dòng) 分別得到分別得到對對 、 有效的項(xiàng)目集有效的項(xiàng)目集 u文法所有的項(xiàng)目集組成了項(xiàng)目集文法所有的項(xiàng)目集組成了項(xiàng)目集規(guī)范簇規(guī)范簇u對于不同的產(chǎn)生式，對應(yīng)對于不同的產(chǎn)生式，對應(yīng) 、 各

35、不相同各不相同 begin C:=closure(S S) repeat for C中每一項(xiàng)目集中每一項(xiàng)目集I和和X do if go(I,X)不空不空 且且 go(I,X) C then 把把go(I,X)加入加入C中中 until C不再增大不再增大end8. LR(0)項(xiàng)目集規(guī)范族的構(gòu)造項(xiàng)目集規(guī)范族的構(gòu)造例 SBB BaB Bb拓廣后的文法拓廣后的文法 0. SS 1. SBB 2. BaB 3. Bb所有項(xiàng)目如下：所有項(xiàng)目如下：1.SS 6. BaB2. SS 7. BaB3. SBB 8. BaB4. SBB 9. Bb5. SBB 10. BbLR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族I0

36、=closure(SS) =SS , SBB , BaB , Bbgo(I0,S)=closure(SS)=SS=I1go(I0,B)=SBB , BaB , Bb=I2go(I0,a)=BaB,BaB,Bb=I3go(I0,b)=Bb=I4go(I2,B)=SBB=I5go(I2,a)=BaB , BaB , Bb=I3go(I2,b)=Bb=I4go(I3,B)=BaB=I6go(I3,a)=BaB , BaB , Bb=I3go(I3,b)=Bb=I4至此至此C中的項(xiàng)目集數(shù)已不再增加中的項(xiàng)目集數(shù)已不再增加故故LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族C為為I0，I1，I6(1)C=I0,I1,I

37、n, Ii對應(yīng)狀態(tài)對應(yīng)狀態(tài)i, I0=closure(SS)為唯一初態(tài)為唯一初態(tài)三三. LR(0)分析表的構(gòu)造分析表的構(gòu)造(2)對每個(gè)對每個(gè)Ii若若AaIi, 且且go(Ii,a)=Ij, 則則 actioni,a=sj若若AIi, A為第為第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式, 則則 b VT #, actioni,b=rj若若SSIi, 則則actioni,#=acc (i=1)(3)若若ABIi, 且且go(Ii,B)=Ij 則則gotoi,B=j(4)凡不能應(yīng)用規(guī)則凡不能應(yīng)用規(guī)則(2)、(3) 表項(xiàng)均為表項(xiàng)均為“錯(cuò)誤錯(cuò)誤”分析表如圖分析表如圖8-16所示。所示。P190(0)SE(1)EE+TT(2)

38、TT*FF(3)F(E)i例例: 文法文法I0=closure(S S) SE, EE+T, ET, TT*F, TF, F(E), F iI1=go(I0,E)=closure(SE , EE +T) SE , EE +T I2=go(I0,T)= )=closure(ET , TT *F) ET , TT *F(0)SE(1)EE+TT(2)TT*FF(3)F(E)i移進(jìn)移進(jìn)-歸約沖突歸約沖突移進(jìn)移進(jìn)-歸約沖突歸約沖突I3=go(I0,F) TF I4=go(I0,( ) F( E), EE+T, ET, TT*F, TF, F(E), F iI5=go(I0,i) F i (0)SE(1)EE+TT(2)TT*FF(3)F(E)iI6=go(I1,+) EE+ T, TT*F, TF, F(E), F iI7=go(I2,*) TT* F,