lR語法分析器設(shè)計(jì)

1、.LR分析程序設(shè)計(jì)1實(shí)驗(yàn)?zāi)康?（1）構(gòu)造LR 分析程序，利用它進(jìn)行語法分析，判斷給出的符號(hào)串是否為該文法識(shí)別的句子；（2）了解LR分析方法是嚴(yán)格的從左向右掃描，和自底向上的語法分析方法。2實(shí)驗(yàn)內(nèi)容和實(shí)驗(yàn)要求 (1)LR分析器能夠構(gòu)造來識(shí)別所有能用上下文無關(guān)文法寫的程序設(shè)計(jì)語言的結(jié)構(gòu)。(2)LR分析方法是已知的最一般的無回溯，移進(jìn)-歸約方法，它能夠和其他移進(jìn)-歸約方法一樣有效地實(shí)現(xiàn)。(3)LR方法能分析的文法類是預(yù)測(cè)分析法能分析的文法類的真超集。3 待分析的語法描述E-vI:TI-I,i|iT-r4算法描述4.1 LR分析法基本思想 LR分析法是一種能夠根據(jù)分析棧中的文法符號(hào)串（狀態(tài)）和向右順序

2、查看第k個(gè)輸入字符就能夠唯一確定LR（k）分析器的動(dòng)作是移進(jìn)還是用哪一條產(chǎn)生式歸約的分析方法。采用LR（0）分析法進(jìn)行本次實(shí)驗(yàn)，即無需向前查看輸入符號(hào)就能夠確定分析器的動(dòng)作。4.2實(shí)現(xiàn)方法LR（0）分析器由三個(gè)部分組成：(1)總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器總控程序都是相同的。(2)分析表，不同的文法分析表將不同，同一個(gè)文法采用的LR分析器不同時(shí)，分析表將不同，分析表又可以分為動(dòng)作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個(gè)部分，它們都可用二維數(shù)組表示。由于它是總控程序的依據(jù)，所以在程序的第一部分就已經(jīng)定義好。(3)分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分

3、析器的動(dòng)作就是由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。(4)LR分析器及時(shí)察覺語法錯(cuò)誤,快到自左向右掃描輸入的最大可能。為了使一個(gè)文法是LR的，只要保證當(dāng)句柄出現(xiàn)在棧頂時(shí)，自左向右掃描的移進(jìn)-歸約分析器能夠及時(shí)識(shí)別它便足夠了。當(dāng)句柄出現(xiàn)在棧頂時(shí)，LR分析器必須要掃描整個(gè)棧就可以知道這一點(diǎn)，棧頂?shù)臓顟B(tài)符號(hào)包含了所需要的一切信息。如果僅知道棧內(nèi)的文法符號(hào)就能確定棧頂是什么句柄。由于LR分析表的轉(zhuǎn)移函數(shù)本質(zhì)上就是這樣的有限自動(dòng)機(jī)，因?yàn)?，如果這個(gè)識(shí)別句柄的有限自動(dòng)機(jī)自底向上讀棧中的文法符號(hào)的話，它達(dá)到的狀態(tài)正是這時(shí)棧頂?shù)臓顟B(tài)符號(hào)所表示的狀態(tài)，所以，LR分析器可以從棧頂?shù)臓顟B(tài)確定它需要從棧中了解的一切。 4.3

4、算法分析 SP為棧指針，Si為狀態(tài)棧，Xi為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當(dāng)棧頂狀態(tài)為i，遇到當(dāng)前文法符號(hào)為X時(shí)應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。ACTIONi，a規(guī)定了棧頂狀態(tài)為i時(shí)遇到輸入符號(hào)a應(yīng)執(zhí)行。動(dòng)作有四種可能：(1)移進(jìn)：actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a(bǔ)移入到文法符號(hào)棧，其中i,j表示狀態(tài)號(hào)。(2)歸約：actioni，a=rk：當(dāng)在棧頂形成句柄時(shí)，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A-B的產(chǎn)生式，若B的長(zhǎng)度為R(即|B|=R)，則從狀態(tài)棧和文法符號(hào)棧中自頂向下去掉R個(gè)符號(hào)，即棧指針SP減去R，并把A移入文法符號(hào)棧內(nèi)，j=GOTOi,A

5、移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc:當(dāng)歸約到文法符號(hào)棧中只剩文法的開始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。(4)報(bào)錯(cuò):當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入端不是該文法能接受的符號(hào)串。5 總控程序框圖6程序清單和程序運(yùn)行結(jié)果 程序清單見磁盤 程序運(yùn)行結(jié)果如下：1 顯示所要分析的文法，并且輸入所要分析的句型：2.輸入所要分析的句型 （1）若所要分析的字符串不為該文法的句型，出錯(cuò)分析：例 若為iii#，則出錯(cuò)顯示如下：(2)若正確輸入該文法的句型如：vi,i:r#， 則分析結(jié)果如下： (3)選擇是否要繼續(xù)分析，若需要?jiǎng)t

6、選Y,若不需要，則選擇N，則退出程序。 7實(shí)驗(yàn)感想 這是在做課程設(shè)計(jì)之前的最后一個(gè)實(shí)驗(yàn)：自底向下的語法分析法。這種方法來分析的固定的文法，是可以凸現(xiàn)其通用性，雖然它沒有算符優(yōu)先分析方法效率那么高。但是由于算符優(yōu)先分析法是將當(dāng)前句型中的最左素短語而不是句柄（最左直接短語）作為規(guī)約的子串，省略了所有單非終極符產(chǎn)生式對(duì)應(yīng)的歸約步驟，因此在分析過程中，雖然采取了相應(yīng)的一些檢查措施，但仍然有可能將錯(cuò)誤的輸入符號(hào)串歸約為正確的句子。而且很多的程序設(shè)計(jì)語言的文法也很難滿足算符優(yōu)先文法的條件，所以它只能局限在表達(dá)式的語法分析中。但是對(duì)于LR分析法，其分析的過程更加符合程序設(shè)計(jì)語言文法的要求，這樣使之通用性加強(qiáng)。同樣在做這個(gè)實(shí)驗(yàn)的時(shí)候，發(fā)現(xiàn)由于在構(gòu)造goto表以及action表中的相關(guān)參數(shù)中，沒有非常的有條理這樣就導(dǎo)致了在程序分析過程中沒有得到非常整齊的界面。經(jīng)過定義循環(huán)變量控制空格符的多少，使表格輸出合理化。由于LR分析方法是可以有很多中形式的，雖然這次我只是選擇了其中的一種方法。但