期末前一周老師發(fā)下來一批“編譯原理復(fù)習(xí)題LR分析練習(xí)題”看著滿屏帶點(diǎn)的產(chǎn)生式和狀態(tài)轉(zhuǎn)移宿舍里直接安靜了幾秒。背模板應(yīng)付詞法分析和LL(1)還行到了LR分析這里題目是真要你動手畫自動機(jī)、填分析表、正面對抗移進(jìn)-歸約沖突的。我花了兩天半把這類題目徹底啃了一遍這篇文章就是完整的復(fù)盤從為什么LR分析容易“看了答案也寫不出來”到項(xiàng)目集規(guī)范族怎么構(gòu)造、SLR(1)分析表怎么填、LR(1)和LALR到底在什么場合登場最后一并給出我自己的刷題順序和自檢清單。準(zhǔn)備期末、準(zhǔn)備考研復(fù)試、甚至打算補(bǔ)考重修的同學(xué)都可以直接照著這套方法論走。1. LR分析為什么最容易“看了答案也寫不出來”1.1 從一道練習(xí)題說起網(wǎng)上流傳的LR分析復(fù)習(xí)題題干通常很短但解題量非常大。常見的有這么幾個層次將文法轉(zhuǎn)換為增廣文法并對產(chǎn)生式編號寫出文法的所有LR(0)項(xiàng)目構(gòu)造LR(0)項(xiàng)目集規(guī)范族畫出識別活前綴的DFA計(jì)算FIRST集和FOLLOW集構(gòu)造SLR(1)分析表判斷該文法是否為SLR(1)文法如果不是分析沖突再嘗試用LR(1)或LALR處理。表面看是七步實(shí)際上是一個鏈條前一步錯一個點(diǎn)后面全部跟著亂。我見過不少同學(xué)拿答案對照時覺得“每一步都能看懂”但自己從頭寫就卡住。最常見的問題不是看不懂歸約而是不知道每一步里的細(xì)節(jié)該落在哪里。舉個例子項(xiàng)目集閉包計(jì)算時很多人會把點(diǎn)后面的非終結(jié)符的產(chǎn)生式漏掉填SLR分析表時歸約動作只寫了某個狀態(tài)忘了歸約應(yīng)該在哪些終結(jié)符上執(zhí)行。這些細(xì)節(jié)不是“懂不懂原理”的問題而是“有沒有形成規(guī)范工序”的問題。1.2 自底向上分析到底在干什么LR分析是自底向上的分析方向是“從輸入串一步步歸約回開始符號”?？梢园阉胂蟪煞聪蛲茖?dǎo)正向推導(dǎo)是從開始符號反復(fù)用產(chǎn)生式展開到句子而自底向上分析則是從句子開始不斷把句柄歸約成產(chǎn)生式左部最終回到開始符號。這里最關(guān)鍵的是“句柄”概念。分析器維護(hù)一個棧輸入符號按順序壓進(jìn)去當(dāng)棧頂一段符號串匹配到某個產(chǎn)生式的右部同時這個右部恰好是當(dāng)前最左歸約的位置就執(zhí)行一次歸約把這段右部彈出換成左部非終結(jié)符。什么時候移進(jìn)、什么時候歸約就是分析表說了算。分析表分為ACTION表和GOTO表ACTION負(fù)責(zé)看當(dāng)前狀態(tài)和當(dāng)前輸入終結(jié)符決定移進(jìn)、歸約、接受或報(bào)錯GOTO負(fù)責(zé)歸約之后根據(jù)新得到的非終結(jié)符跳轉(zhuǎn)狀態(tài)。LR這個名字里L(fēng)表示從左到右掃描輸入R表示構(gòu)造最右推導(dǎo)的逆過程也就是最左歸約。記住這個方向很重要因?yàn)樗鼪Q定了你每次歸約的都是當(dāng)前棧中最靠右的句柄而不是隨便找一個能匹配的產(chǎn)生式右部就歸約。2. 做題前的三板斧FIRST、FOLLOW和LR(0)項(xiàng)目集2.1 FOLLOW集SLR分析的“裁判”SLR(1)和LR(0)最大的區(qū)別就是SLR分析表在歸約時多了一個限制條件只有當(dāng)前輸入終結(jié)符屬于左部非終結(jié)符的FOLLOW集才允許執(zhí)行這條歸約。所以FOLLOW集算錯后面的沖突判斷、填表全都會跟著錯。FOLLOW集的定義是在規(guī)范推導(dǎo)過程中可能出現(xiàn)在某個非終結(jié)符之后的所有終結(jié)符集合。計(jì)算規(guī)則用得最多的有四條開始符號S的FOLLOW集中一定包含$若有產(chǎn)生式A → αBβ則把FIRST(β)中除ε之外的所有終結(jié)符放入FOLLOW(B)若產(chǎn)生式是A → αB也就是B后面沒有東西則FOLLOW(A)中的全部元素放入FOLLOW(B)若產(chǎn)生式A → αBβ且FIRST(β)包含ε則同樣要把FOLLOW(A)放入FOLLOW(B)。很多同學(xué)會忽略第四條。判斷“β能不能推導(dǎo)出空串”時不能光看β本身是不是ε還要看β里的非終結(jié)符是否都能推出ε。實(shí)際算的時候我習(xí)慣用迭代法先給每個非終結(jié)符建空集合把$放進(jìn)取FOLLOW(開始符號)然后反復(fù)掃所有產(chǎn)生式直到所有集合都不再變化為止。因?yàn)橛醒h(huán)依賴比如后面要講的某個經(jīng)典文法里FOLLOW(L)和FOLLOW(R)互相包含必須迭代到收斂只掃一遍很容易漏。2.2 項(xiàng)目與項(xiàng)目集閉包不要把“項(xiàng)目”想復(fù)雜LR(0)項(xiàng)目就是在產(chǎn)生式右部的某個位置加一個圓點(diǎn)表示“已經(jīng)看到了圓點(diǎn)前面的部分正在等待圓點(diǎn)后面的部分”。比如產(chǎn)生式E → E T可以產(chǎn)生四個項(xiàng)目E → · E T還沒看到任何右部符號屬于初始期待狀態(tài)E → E · T已經(jīng)看到E等待E → E · T已經(jīng)看到E等待TE → E T ·右部全部看到說明句柄已經(jīng)形成可以歸約。如果圓點(diǎn)在最后一個符號后面這個項(xiàng)目就叫歸約項(xiàng)目如果圓點(diǎn)后面是終結(jié)符叫移進(jìn)項(xiàng)目如果圓點(diǎn)后面是非終結(jié)符叫待約項(xiàng)目。還有一種是S → S ·叫接受項(xiàng)目。這樣分類不是考試為了考定義而是你后面填A(yù)CTION表時看到什么類型就知道該寫什么動作。項(xiàng)目集閉包的計(jì)算方法一句話就能說清從一個狀態(tài)的核心項(xiàng)目出發(fā)不停地看圓點(diǎn)后面的符號如果是非終結(jié)符B就把B的所有產(chǎn)生式寫成B → · γ 加進(jìn)這個狀態(tài)直到?jīng)]有新項(xiàng)目為止?？梢园阉斫鉃椤胺治銎饕呀?jīng)到達(dá)這個位置時所有可能接下來要匹配的產(chǎn)生式都提前列出來”。用生活類比就是你在排隊(duì)時不知道隊(duì)伍前面具體哪個窗口會開于是把所有可能窗口的業(yè)務(wù)都提前準(zhǔn)備好。2.3 把LR(0)自動機(jī)完整畫一遍極簡文法示范概念說太多沒用用一個極小文法把DFA畫一遍。文法GS → aS | b增廣文法為S → S S → aS S → b項(xiàng)目集I0是閉包{S → · S}展開后為I0: S → · S S → · aS S → · b從I0可以看到開始符號S說明S → S · 已經(jīng)形成這就是接受狀態(tài)I1?？吹絘移進(jìn)到I2看到b移進(jìn)到I3。I2: S → a · S S → · aS S → · b這里很典型點(diǎn)后面是S所以又把S的兩個產(chǎn)生式作為閉包項(xiàng)目加進(jìn)來。從I2繼續(xù)分析看到S轉(zhuǎn)移到I4看到a回到I2看到b進(jìn)入I3。I3: S → b ·歸約項(xiàng)目對應(yīng)歸約S → b。 I4: S → aS ·歸約項(xiàng)目對應(yīng)歸約S → aS。完整的狀態(tài)轉(zhuǎn)移可以這樣寫出來I0 --S-- I1I0 --a-- I2I0 --b-- I3I2 --S-- I4I2 --a-- I2I2 --b-- I3畫成圖就是一個典型的DFA。注意點(diǎn)和邊的含義邊上的符號就是項(xiàng)目集中圓點(diǎn)后面看到的那個符號轉(zhuǎn)過去之后圓點(diǎn)往右移一位再做閉包。這就是識別活前綴的自動機(jī)所有練習(xí)題的骨架都在這里。3. 完整推演算術(shù)表達(dá)式文法的SLR(1)分析表是怎么填出來的3.1 增廣文法與編號寫表的第一動作任何LR分析表練習(xí)題第一步永遠(yuǎn)是寫增廣文法并編號目的只有一個讓接受動作有一個唯一的歸約目標(biāo)。原開始符號E可能出現(xiàn)在其他產(chǎn)生式右部的后面不能直接用E歸約來代表“整個句子分析完了”所以引入E → E。增廣文法(0) E → E (1) E → E T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → id編號是為了在分析表里寫歸約動作時能直接寫r1、r2這樣的簡寫。如果編號亂了后面的表就沒法填。接下來算FOLLOW集這個文法的依賴關(guān)系雖然不復(fù)雜但很容易在FOLLOW(F)這塊翻車。先說結(jié)論FOLLOW(E) {$, , )} FOLLOW(T) {$, , ), *} FOLLOW(F) {$, , ), *}最容易被問到的點(diǎn)是FOLLOW(F)里的*哪來的?？串a(chǎn)生式T → T * FF位于右部末尾所以FOLLOW(T)里的符號都要放進(jìn)FOLLOW(F)。這一步是被忽略的高頻錯誤。很多人會想當(dāng)然地認(rèn)為FOLLOW(T)包含F(xiàn)OLLOW(F)方向正好反了終結(jié)符集合是從前面?zhèn)鬟f給末尾的非終結(jié)符不是從后面的F往前傳。3.2 項(xiàng)目集規(guī)范族構(gòu)造這11個狀態(tài)怎么來的全稱構(gòu)造會很長我把完整狀態(tài)轉(zhuǎn)移列出來。起點(diǎn)I0是閉包{E → · E}I0: E → · E E → · E T E → · T T → · T * F T → · F F → · (E) F → · id從I0看E到接受狀態(tài)附近I1: E → E · E → E · TI1的狀態(tài)比較特殊E → E · 是接受項(xiàng)目E → E · T 又允許繼續(xù)移進(jìn)這就是一個隨時可能觸發(fā)“接受還是繼續(xù)歸約”的狀態(tài)節(jié)點(diǎn)。這里是靠輸入符號來區(qū)分的只有當(dāng)前符號是$時才接受遇到就移進(jìn)。從I0看T得到I2I2: E → T · T → T · * F這里出現(xiàn)了移進(jìn)-歸約沖突候選E → T · 想歸約成ET → T · * F 想移進(jìn)*。SLR(1)的裁判方式是看當(dāng)前符號是否在FOLLOW(E)中。FOLLOW(E) {$, , )}不在其中所以面對時不會選擇歸約E → T只能選擇移進(jìn)。這就是SLR(1)消解沖突的標(biāo)準(zhǔn)流程。繼續(xù)完整列一遍所有狀態(tài)I3: T → F · I4: F → ( · E) E → · E T E → · T T → · T * F T → · F F → · (E) F → · id I5: F → id · I6: E → E · T T → · T * F T → · F F → · (E) F → · id I7: T → T * · F F → · (E) F → · id I8: F → (E ·) E → E · T I9: E → E T · T → T · * F I10: T → T * F · I11: F → (E) ·狀態(tài)轉(zhuǎn)移表如下當(dāng)前狀態(tài)輸入符號目標(biāo)狀態(tài)I0EI1I0TI2I0FI3I0(I4I0idI5I1I6I2*I7I4EI8I4TI2I4FI3I4(I4I4idI5I6TI9I6FI3I6(I4I6idI5I7FI10I7(I4I7idI5I8I6I8)I11I9*I7寫項(xiàng)目集規(guī)范族時最容易漏的是“同一個目標(biāo)狀態(tài)被多個來源復(fù)用”。比如I2既從I0看T得到也從I4看T得到I3既從I0看F得到也從I4看F得到。做題時寧可多花時間把每個狀態(tài)的來源標(biāo)出來后面檢查時能省很多事。3.3 填A(yù)CTION/GOTO表FOLLOW集在這里派上用場有了DFA和FOLLOW集填表就是機(jī)械工作。ACTION表看當(dāng)前狀態(tài)和輸入終結(jié)符GOTO表看歸約后得到非終結(jié)符時的跳轉(zhuǎn)。完整的ACTION表如下狀態(tài)id*()$0s5s41s6acc2r2s7r2r23r4r4r4r44s5s45r6r6r6r66s5s47s5s48s6s119r1s7r1r110r3r3r3r311r5r5r5r5GOTO表為狀態(tài)ETF01234823693710觀察狀態(tài)2的動作id和(列是空的因?yàn)闋顟B(tài)2下這兩個符號不可能出現(xiàn)遇到、)、$時歸約E → T遇到時移進(jìn)。這就是2.1里FOLLOW集發(fā)揮作用的地方。再看狀態(tài)9遇到、)、$歸約E → E T遇到移進(jìn)狀態(tài)10則統(tǒng)一歸約T → T * F因?yàn)镕OLLOW(T)里包含了所有可能到達(dá)這里的終結(jié)符。這里有個易錯點(diǎn)歸約動作的符號集合不是“這個狀態(tài)里所有可能看到的終結(jié)符”而是“這個狀態(tài)里歸約項(xiàng)目的左部FOLLOW集”。兩個集合在有些狀態(tài)下確實(shí)重合但絕不能混為一談。3.4 拿輸入串驗(yàn)證idid*id一步步走完填完表必須驗(yàn)證。我用idid*id完整走一遍狀態(tài)棧只寫編號符號棧也不省略步驟狀態(tài)棧符號棧輸入串動作10idid*id$s520 5idid*id$r6按GOTO(0,F)330 3Fid*id$r4按GOTO(0,T)240 2Tid*id$r2按GOTO(0,E)150 1Eid*id$s660 1 6Eid*id$s570 1 6 5Eid*id$r6按GOTO(6,F)380 1 6 3EF*id$r4按GOTO(6,T)990 1 6 9ET*id$s7100 1 6 9 7ET*id$s5110 1 6 9 7 5ET*id$r6按GOTO(7,F)10120 1 6 9 7 10ET*F$r3按GOTO(6,T)9130 1 6 9ET$r1按GOTO(0,E)1140 1E$acc每一步的歸約動作都要先彈出右部長度個狀態(tài)再查GOTO表。比如第12步歸約T → T * F右部長度是3彈出9、7、10三個狀態(tài)回到6再查GOTO(6,T)9。這一步非常容易寫錯因?yàn)閺棾鰻顟B(tài)數(shù)量是按右部符號數(shù)算的和棧里實(shí)際壓了幾個狀態(tài)必須嚴(yán)格對應(yīng)。4. 沖突處理SLR(1)翻車的經(jīng)典案例與LR(1)/LALR的真身4.1 一個讓SLR(1)失效的文法算表達(dá)式文法雖然能用SLR(1)處理但只是“能處理”而已不能體現(xiàn)SLR的局限。真正讓SLR(1)當(dāng)場翻車的經(jīng)典文法長這樣S → L R | R L → * R | id R → L增廣文法編號后(0) S → S (1) S → L R (2) S → R (3) L → * R (4) L → id (5) R → L算FOLLOW集時要小心循環(huán)依賴。FOLLOW(S)初始為{$}由S → L R得到FOLLOW(L)至少含由S → R得到FOLLOW(R)含$由R → LFOLLOW(R)要放入FOLLOW(L)由L → * RFOLLOW(L)要放入FOLLOW(R)。迭代收斂后FOLLOW(L) {, $} FOLLOW(R) {, $}構(gòu)造LR(0)項(xiàng)目集只挑沖突狀態(tài)看。I0閉包I0: S → · S S → · L R S → · R L → · * R L → · id R → · L從I0看L得到I2: S → L · R R → L ·問題來了這個狀態(tài)里當(dāng)前符號如果等于一方面S → L · R 需要移進(jìn)另一方面R → L · 可以歸約成R。SLR(1)判斷歸約R → L是否可行要看當(dāng)前符號是否在FOLLOW(R)中?？蒄OLLOW(R) {, $}正好在里面于是SLR(1)裁定“既可以移進(jìn)也可以歸約R → L”沖突無法消解。注意這不是文法本身二義造成的。這個文法是明確的、無二義的它只是LR(1)文法不是SLR(1)文法。SLR用了全局的FOLLOW集來判斷歸約條件而這個全局信息太粗糙了。4.2 LR(1)項(xiàng)目里的“前瞻符號”怎么救場LR(1)項(xiàng)目把歸約條件做得更精細(xì)形式是[A → α · β, a]其中a表示當(dāng)前必須看到的前瞻終結(jié)符。用人話說SLR(1)判斷“R → L · 能不能歸約”時問的是“R后面可能跟著哪些符號”答案是{, $}LR(1)判斷同樣的歸約時問的是“在當(dāng)前這個狀態(tài)下真正能讓R后面出現(xiàn)的符號有哪些”答案往往比FOLLOW集更小。在I0中做LR(1)閉包前瞻會這樣傳播[S → · S, $] [S → · L R, $] [S → · R, $] [L → · * R, ] [L → · id, ] [R → · L, $]注意L的項(xiàng)目lookahead來自S → L RL后面直接跟著所以是R的項(xiàng)目來自S → RR后面是$所以是$。從I0看L后得到[S → L · R, $] [R → L ·, $]這時[R → L ·, $]的lookahead是$不是{, $}。于是狀態(tài)里遇到時只允許移進(jìn)遇到$時才允許歸約R → L沖突被干凈利落地消解了。這就是LR(1)比SLR(1)更強(qiáng)大的根本原因每個項(xiàng)目記住了自己真正需要的前瞻符號而不是引用全局FOLLOW集。閉包計(jì)算LR(1)前瞻時規(guī)則是如果有項(xiàng)目[A → α · Bβ, a]則對B的產(chǎn)生式B → · γ其lookahead要從FIRST(βa)取。也就是說把“β后面再跟上a”里能推出的第一個終結(jié)符作為新項(xiàng)目的前瞻。這個細(xì)節(jié)是LR(1)題目的重災(zāi)區(qū)容易漏掉的是β能推導(dǎo)出ε的情況。4.3 LALR合并什么時候能省什么時候不能省LR(1)自動機(jī)狀態(tài)數(shù)可能遠(yuǎn)大于LR(0)為了控制規(guī)模考試?yán)镞€有LALR。LALR的做法是把“同心項(xiàng)目集”合并也就是去掉lookahead之后核心相同的LR(1)項(xiàng)目集合并成一個。一般情況下如果LR(1)分析表沒有沖突合并后的LALR不會產(chǎn)生移進(jìn)-歸約沖突但可能產(chǎn)生歸約-歸約沖突。原因是兩組不同lookahead的歸約項(xiàng)目在合并后lookahead取并集原本不重疊的歸約條件可能互相重疊。做題時只需要記住合并之后一定要重新檢查歸約-歸約沖突。有些教材習(xí)題會在合并后的狀態(tài)里放兩個歸約項(xiàng)目它們的lookahead恰好重疊于是一個狀態(tài)里出現(xiàn)“同一輸入符號對應(yīng)兩個不同歸約動作”LALR就不成立。這種題考查的正是對“同心合并取并集”的深刻理解而不只是會不會合并。5. 復(fù)習(xí)策略與刷題自檢清單5.1 推薦刷題順序同樣是練習(xí)題順序不對會浪費(fèi)大量時間。我的建議是先從小文法啃起不要一上來就做綜合大題。第一步挑選只含兩三個產(chǎn)生式的極簡文法反復(fù)練LR(0)項(xiàng)目集閉包和DFA構(gòu)造目標(biāo)是閉包無遺漏第二步挑一個不含沖突的小文法完整填SLR分析表并跑輸入串重點(diǎn)感受ACTION和GOTO的協(xié)作關(guān)系第三步用算術(shù)表達(dá)式文法這類帶少量沖突但能被SLR消解的文法練FOLLOW集消解沖突第四步用S → L R | R那類SLR(1)失效的文法練LR(1)項(xiàng)目和LALR合并。順序的邏輯是每一層都建立在前一層的計(jì)算能力上。如果FOLLOW集一算就算錯直接去做LR(1)前瞻傳播就是空中樓閣。5.2 閱卷老師最喜歡扣分的六個細(xì)節(jié)結(jié)合我做題和改卷的經(jīng)驗(yàn)下面這六個細(xì)節(jié)出現(xiàn)的頻率最高每一項(xiàng)都值得考前專門檢查細(xì)節(jié)錯誤表現(xiàn)正確做法增廣文法忘了加S → S任何LR題先加增廣產(chǎn)生式再編號閉包完整性漏掉點(diǎn)后非終結(jié)符的產(chǎn)生式看到點(diǎn)后是B必須把B的所有產(chǎn)生式寫成B → · γFOLLOW循環(huán)依賴只掃一遍就結(jié)束迭代到集合不再變化必要時寫兩輪歸約符號集合把所有終結(jié)符都填進(jìn)歸約動作只填左部FOLLOW集內(nèi)的終結(jié)符LR(1)前瞻傳播只復(fù)制上層產(chǎn)生式的全局FOLLOW用FIRST(βa)逐項(xiàng)計(jì)算LALR歸約沖突合并后不再檢查歸約-歸約沖突合并后逐個歸約項(xiàng)目檢查lookahead是否有重疊我自己的經(jīng)驗(yàn)是步驟越機(jī)械化越容易因?yàn)椤笆只眮G分。每次寫完閉包先數(shù)一遍項(xiàng)目數(shù)再數(shù)一遍轉(zhuǎn)移邊數(shù)兩個數(shù)對不上基本就是漏閉包了。5.3 我的考前自檢清單答題字符串寫作模板化之后我每次交卷前會按下面的清單快速過一遍產(chǎn)生式編號從0開始了嗎增廣產(chǎn)生式編號是0嗎每個項(xiàng)目集的閉包里是否遺漏了“點(diǎn)后非終結(jié)符”的新增產(chǎn)生式DFA的每條邊上轉(zhuǎn)移符號是否都是項(xiàng)目里圓點(diǎn)后面的那個符號GOTO表里歸約后要壓入的狀態(tài)是否按“彈出右部長度個狀態(tài)后再查表”得到SLR判斷沖突時歸約條件用的是左部FOLLOW集還是當(dāng)前狀態(tài)下所有符號LR(1)項(xiàng)目的lookahead是否逐項(xiàng)目計(jì)算過FIRST(βa)而不是直接復(fù)制上一層的集合如果做了LALR合并合并后的狀態(tài)是否存在兩個歸約項(xiàng)目共用同一個lookahead這套清單看著簡單但真能攔住絕大多數(shù)低級錯誤。我刷完一份復(fù)習(xí)題后隔一天再拿清單復(fù)盤每次都能抓到至少一個當(dāng)初沒發(fā)現(xiàn)的筆誤。這也是我把這類題目從“會做”變成“穩(wěn)做”的關(guān)鍵一步。最后再分享一個小技巧。做題時我會把每個項(xiàng)目集的“核”先圈出來也就是最初從上一個狀態(tài)轉(zhuǎn)移過來的那些項(xiàng)目閉包新增的項(xiàng)目不作特殊標(biāo)記只是排在后面對齊。這樣返工檢查時只看每組的核是否對得上轉(zhuǎn)移邊就夠不用把整頁閉包重算一遍。復(fù)習(xí)本身也是同樣的道理先把框架核對清楚再去摳細(xì)節(jié)LR分析的所有練習(xí)到最后拼的就是這種有條不紊的工序感。