編譯原理實驗2

1、4第二章語法分析器構(gòu)造我們采用一種最為常用的語法分析器─LR分析器。LR分析器的構(gòu)造主要是指上下文無關(guān)文法的自下而上分析程序的自動構(gòu)造。從實踐角度出發(fā)，我們采用手工方法來設(shè)計LR分析器。LR系指“自左向右掃描和自下而上進(jìn)行歸約”。大多數(shù)用上下文無關(guān)文法描述的程序語言都可用LR分析器予以識別。LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)其中的任何錯誤，并能準(zhǔn)確地指出出錯地點。一個LR分析器包括兩部分，一個總控（驅(qū)動）程序和一張分析表。注意，所

2、有LR分析器的總控程序都是一樣的，只是分析表各有不同。因此，產(chǎn)生器的主要任務(wù)就是產(chǎn)生分析表。21LR分析器基本知識我們知道，規(guī)范歸約（最左歸約，即最右推導(dǎo)的逆過程）的關(guān)鍵問題是尋找句柄。LR方法的基本思想是：在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約出的整個符號串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來的可能碰到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時，我們希望能夠根據(jù)所記載的“歷史”和“展望

3、”以及“現(xiàn)實”的輸入符號等三方面的材料，來確定棧頂?shù)姆柺欠駱?gòu)成相對某一產(chǎn)生式的句柄。一個LR分析器實質(zhì)上是一個帶先進(jìn)后出存貯器（棧）的確定有限狀態(tài)自動機。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”。分析棧（先進(jìn)后出存貯器）用來存放狀態(tài)。棧里的每個狀態(tài)概括了從分析開始直到某一歸約階段的全部“歷史”和“展望”資料。任何時候，棧頂?shù)臓顟B(tài)都代表了整個的歷史和已推測出的展望。LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決

4、定的。為了有助于明確歸約手續(xù)，我們把已歸約出的文法符號串也同時放在棧里。于是，棧的結(jié)構(gòu)可看成圖21所示的結(jié)構(gòu)。TOPsmYsm1X..…….……s0#圖21分析棧示意棧的每一項內(nèi)容包括狀態(tài)s和文法符號X兩部分。（sO，#）為分析開始前預(yù)先放入棧里的初始狀態(tài)和句子括號。棧頂狀態(tài)為sm，符號串X1X2…Xm是至今已移進(jìn)歸約出的文法符號串。6有活前綴。這個NFA的每個狀態(tài)就是一個“項目”。而文法G每一個產(chǎn)生式的右部添加一個圓點稱為G的一個LR

5、（0）項目（簡稱項目）。例如產(chǎn)生式A→XYZ對應(yīng)有四個項目：A→XYZA→XYZA→XYZA→XYZ但是產(chǎn)生式A→ε只對應(yīng)一個項目A→。一個項目指明了在分析過程的某時刻我們看到產(chǎn)生式多大一部分。我們可以使用這些項目狀態(tài)構(gòu)造一個NFA，用來識別一個文法的所有活前綴。使用子集方法把識別活前綴的NFA確定化，使之成為一個以項目集合為狀態(tài)的DFA（確定有限自動機），這個DFA就是建立LR分析算法的基礎(chǔ)。構(gòu)成識別一個文法活前綴的DFA的項目集（狀

6、態(tài)）的全體稱為這個文法的LR（0）項目集規(guī)范族。這個規(guī)范族提供了建立一類LR（0）和SLR（簡單LR）分析器的基礎(chǔ)。注意，凡園點在最右端的項目，如A→α，稱為一個“歸約項目”；對文法的開始符號S′的歸約項目，如S′→α稱為“接受”項目。形如A→αaβ的項目，其中a為終結(jié)符，稱為“移進(jìn)”項目；形如A→αBβ的項目，其中B為非終結(jié)符，稱為“待約”項目。221LR（0）項目集規(guī)范族的構(gòu)造我們采用ε_CLOSURE（閉包）的方法來構(gòu)造一個文法G

7、的LR（0）項目集規(guī)范族。首先，為了使“接受”狀態(tài)易于識別，總是將文法G進(jìn)行拓廣。假定文法G是一個以S為開始符號的文法，我們構(gòu)造一個G′，它包含了整個G并引進(jìn)了一個不出現(xiàn)在G中的非終結(jié)符S′，同時加進(jìn)了一個新產(chǎn)生式S′→S，而這個S′是G′的開始符號，我們稱G′是G的拓廣文法。由于會有一個僅含項目S′→S的狀態(tài)，這就是唯一的“接受”態(tài)。假定I是文法G′的任一項目集，定義和構(gòu)造I的閉包CLOSURE（I）的方法是：（1）I的任何項目都屬于

8、CLOSURE（I）；（2）若A→αBβ屬于CLOSURE（I），那么對任何關(guān)于B的產(chǎn)生式B→γ，項目B→γ也屬于CLOSURE（I）（設(shè)A→αBβ的狀態(tài)為i，則i到所有含B→γ的狀態(tài)都有一條ε?。唬?）重復(fù)執(zhí)行上述兩步驟直至CLOSURE（I）不再增大為止。在構(gòu)造CLOSURE（I）時，請注意一個重要的事實，那就是對任何非終結(jié)符B，若某個圓點在左邊的項目B→γ進(jìn)入到CLOSURE（I），則B的所有其它圓點在左邊的項目B→β也將進(jìn)入同