lr分析器實(shí)驗(yàn)報(bào)告

1、第 1 頁(yè) 共 34 頁(yè)lr分析器實(shí)驗(yàn)報(bào)告.1第一章 概述.21.1設(shè)計(jì)題目及內(nèi)容.21.2設(shè)計(jì)環(huán)境.2第二章 設(shè)計(jì)的基本原理.32.1 LR 分析器的基本理.32.2 LR 分析器工作過(guò)程算法.3第 2 頁(yè) 共 34 頁(yè)第三章 程序設(shè)計(jì).53.1 總體方案設(shè)計(jì).53.2各模塊設(shè)計(jì).5第四章 程序測(cè)試和結(jié)論以及心得 . .7參考文獻(xiàn) .7附錄 程序清單.8第一章 概述1 1 設(shè)計(jì)題目及內(nèi)容設(shè)計(jì)題目： 根據(jù) LR 分析表構(gòu)造 LR 分析器 內(nèi)容：已知文法 G: (1)E - E+T第3頁(yè)共 34 頁(yè)(2)E - T(3)T T*FT - F(5) F - (E)(6) F TLR 分析表:狀態(tài)A

2、ction 表GOT(表abc#SAB0S21231accep t2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S9第4頁(yè)共 34 頁(yè)9R2R2R2R2注：sj 表示把下一狀態(tài) j 和現(xiàn)行輸入符號(hào) a 移進(jìn)棧rj 表示按第 j 個(gè)產(chǎn)生式進(jìn)行規(guī)約acc表示接受空格表示出錯(cuò)標(biāo)志，報(bào)錯(cuò)根據(jù)以上文法和 LR 分析表，構(gòu)造 LR 分析器，并要求輸出 程。1. 2 設(shè)計(jì)環(huán)境硬件設(shè)備：一臺(tái) PC 機(jī)軟件設(shè)備： Windows 2000/XP OS , VC+6.0實(shí)現(xiàn)語(yǔ)言：C 語(yǔ)言設(shè)計(jì)的基本原理2 1 基本原理LR 工作過(guò)第二章第 5 頁(yè) 共 34 頁(yè)1.LR 方法的基

3、本思想：在規(guī)范規(guī)約的過(guò)程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào) 串，即記住“歷史”，另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能碰到 的輸入符號(hào)，即對(duì)未來(lái)進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn) 于分析棧的頂端時(shí)，我們希望能夠根據(jù)記載的“歷史”和“展望”以 及“現(xiàn)實(shí)”的輸入符號(hào)等三個(gè)方面的材料，來(lái)確定棧頂?shù)姆?hào)串是否 構(gòu)成相對(duì)某一產(chǎn)生式的句柄。2. LR 分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器(棧)的確定有限狀態(tài)自動(dòng)機(jī)。3. LR 分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。4. 為清晰說(shuō)明 LR 分析器實(shí)現(xiàn)原理和模型：LR 分析器的核心部分是一張分析表。這張分析表包括兩個(gè)部分， 一是“動(dòng)作

4、” (ACTION 表，另一是“狀態(tài)轉(zhuǎn)換”(GOTO 表。他們 都是二維數(shù)組。 ACTION(s,a)規(guī)定了當(dāng)狀態(tài) s 面臨輸入符號(hào) a 時(shí)應(yīng)采 取什么動(dòng)作。GOTQs, X)規(guī)定了狀態(tài) s 面對(duì)文法符號(hào) X(終結(jié)符或 非終結(jié)符)時(shí)下一狀態(tài)是什么。顯然，GOTO(s X)定義了一個(gè)以文法符號(hào)為字母表的 DFA。第 6 頁(yè) 共 34 頁(yè)每一項(xiàng) ACTION(s，a) 所規(guī)定的動(dòng)作不外是下述四種可能之一：(1)移進(jìn)把(s, a)的下一個(gè)轉(zhuǎn)態(tài) s = GOTO(s, X)和 輸入符號(hào) a 推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。(2)規(guī)約指用某一產(chǎn)生式 A-B進(jìn)行規(guī)約。假若B的長(zhǎng)度為 r，規(guī)約的動(dòng)作是

5、 A,去除棧頂?shù)?r 個(gè)項(xiàng)，使?fàn)顟B(tài) Sm-r 變成棧 頂狀態(tài)，然后把(Sm-r，A)的下一狀態(tài) s = GOTO(Sm-r,A)和文法 符號(hào) A 推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著B(niǎo)(= Xm-r+1Xn)已呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于 A 的句柄。(3)接受宣布分析成功，停止分析器的工作。(4)報(bào)錯(cuò)發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。2 2 LR 分析器工作過(guò)程算法描述一個(gè) LR 分析器的工作過(guò)程可看成是棧里的狀態(tài)序列，已規(guī)約串和輸入串所構(gòu)成的三元式的變化過(guò)程。分析開(kāi)始時(shí)的初始三元式為( s0,#, a1a2 an#)其中，s0 為分析器的初態(tài)；#為句子的左括號(hào)；a1a2

6、.an 為輸入串；其后的為結(jié)束符(句子右括號(hào))。分析過(guò)程每步的結(jié)果可表示 為(s0s1.sm, #X1X2.Xm ai, ai+1 .an#) 分析第 7 頁(yè) 共 34 頁(yè)器的下一步動(dòng)作是由棧頂狀態(tài)sm和現(xiàn)行輸入符號(hào)ai所唯一決定 的。即，執(zhí)行 ACTION(sm，ai )所規(guī)定的動(dòng)作。經(jīng)執(zhí)行每種可能的 動(dòng)作之后，三元式的變化情形是：(1) 若 ACTION(sm，ai )為移進(jìn)，且 s = GOT(O sm，ai )，則三元 式變成：(s0s1 sm s, #X1X2.Xm ai, ai+1 an#)(2)若 ACTION(sm ai ) = A-B,則按照產(chǎn)生式 A-B進(jìn)行規(guī)約。 此時(shí)三元

7、式變?yōu)?s0s1.sm s, #X1X2.Xm A, ai ai+1 an#)此處 s = GOTO( Sm-r, A), r 為B的長(zhǎng)度，B= Xm-r+1 .Xm。( 3) 若 ACTION(sm, ai )為“接受”,則三元式不再變化,變化過(guò) 程終止,宣布分析成功。(4) 若 ACTION(sm, ai )為“報(bào)錯(cuò)”,則三元式的變化過(guò)程終止, 報(bào)告錯(cuò)誤。一個(gè) LR 分析器的工作過(guò)程就是一步一步的變換三元式，直至執(zhí)行“接受”或“報(bào)錯(cuò)”為止。第 8 頁(yè) 共 34 頁(yè)第 9 頁(yè) 共 34 頁(yè)第三章 程序設(shè)計(jì)3 1 總體設(shè)計(jì)方案第 10 頁(yè) 共 34 頁(yè)建模（1）分析表建模：構(gòu)造一個(gè) int 型

8、二維數(shù)組 table139, 用于存放 LR 分析表。 并初始化。作者這樣規(guī)定：011 表示 狀態(tài) sj，其中 0 對(duì)應(yīng) s0, 1 對(duì)應(yīng) si 2126表示 規(guī)約 rj，其中 21 對(duì)應(yīng) r1 , 22 對(duì)應(yīng)r2 12表示 “接受”-1表示 規(guī)約出錯(cuò)，報(bào)錯(cuò)（2）棧建模：建立一個(gè) int 型狀態(tài)棧，該棧為順序棧。建立一個(gè) char 型符號(hào)棧和一個(gè) char 型輸入串棧，該棧為順序棧。（3）規(guī)約表達(dá)式建模：建立一個(gè) rule 型結(jié)構(gòu)，成員變量為 char 型非終結(jié)符和 int 型表 示規(guī)約第幾條表達(dá)式。程序設(shè)計(jì)關(guān)鍵注意環(huán)節(jié)（ 1 ）在輸入串（句子）輸入的過(guò)程中，涉及到一個(gè)壓棧的問(wèn)題。但這樣第 1

9、1 頁(yè) 共 34 頁(yè)是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反， 需要先彈出的反而在棧底。 為了既要保證字符串輸入， 又要讓輸入的 字符串存儲(chǔ)順序與輸入的字符串相反。采取以下措施： 先將輸入的字符串壓入符號(hào)棧symbol 中，然后符號(hào)棧彈出的字 符再壓入輸入串棧 instr 中，這樣實(shí)現(xiàn)了輸入串的倒序存儲(chǔ)。( 2 ) 狀 態(tài) 棧 status_stack(status_p) 和 符 號(hào) 棧symbol_instr(symbol_p) 輸出(遍歷) 過(guò)程均采取自棧底到棧頂?shù)捻?序，而輸入串棧 symbol_instr(instr_p) 則是采取自棧頂?shù)綏５椎捻?序輸出。32 各模塊設(shè)

10、計(jì)棧設(shè)計(jì)構(gòu)造一個(gè) int 型“狀態(tài)棧” status 和一個(gè) char 型“符號(hào)輸入 串?！眘ymbol_instr 。該棧包括初始化該棧 init_status() ，壓棧 push() ，彈棧 pop() ，取 棧頂元素 get_top() ，自棧底到棧頂遍歷元素 out_stack1() 和自棧頂 到棧底遍歷元素 out_stack2() 。LR分析器工作過(guò)程算法設(shè)計(jì)構(gòu)造一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換int goto_char(status *status_p,symbol_instr *instr_p)構(gòu)造一個(gè)移進(jìn)規(guī)約函數(shù)實(shí)現(xiàn)移進(jìn)規(guī)約動(dòng)作voidaction(status *status

11、_p,symbol_instr第 12 頁(yè) 共 34 頁(yè)*symbol_p,symbol_instr *instr_p)構(gòu)造一個(gè)打印 LR 分析器的工作過(guò)程函數(shù)實(shí)現(xiàn)輸出void print(status *status_p,symbol_instr*symbol_p,symbol_instr *instr_p)第 13 頁(yè) 共 34 頁(yè)流程圖第 14 頁(yè)共 34 頁(yè)初始化狀態(tài)棧，符號(hào)棧, 輸入串棧_X_輸入串各字符壓棧求下一狀態(tài)符號(hào)ii = goto_char(status_p,i nstr_p)規(guī)約動(dòng)作：1.求出i對(duì)應(yīng)規(guī)約規(guī)則右部 字符串長(zhǎng)度x = ri-21.y2.在符號(hào)棧和狀態(tài)棧中彈出x

12、個(gè)字符。然后將該規(guī) 約規(guī)則左部壓入輸入串 棧i = = 12 ?i0 & i=11.規(guī)約出錯(cuò)！異 常中止！*規(guī)約成功！退 出移進(jìn)動(dòng)作：1.將現(xiàn)狀態(tài)i壓 棧LR分析器設(shè)計(jì)流程圖附錄push(status_p,i)2.將當(dāng)前輸入串字符壓入符號(hào)棧apop( in str_p)push(symbol_p,a)1f打印該步程工作過(guò)第 15 頁(yè) 共 34 頁(yè)程序源代碼一：頭文件 lr.h/LR 分析表#include#include/0-11 表示狀態(tài)結(jié)點(diǎn)， 2126 表示規(guī)約標(biāo)號(hào)，/-1 表示 error （出錯(cuò)）， 12 表示 acc （接受）int table107 = 2,-1,-1, -

13、1,1, -1, -1,-1, -1,-1,12,-1,-1,-1,-1,7,-1,-1,-1,3,5,-1,7,4,-1,-1,-1,8, 21,21,21,21,-1, -1,-1,6,-1,-1,-1,-1,-1,-1,23,23,23,23,-1,-1,-1,24,24,24,24,-1,-1,-1,-1,9,-1,-1,-1,-1,-1,22,22,22,22,-1,-1,-1/ 規(guī)約規(guī)則struct rule第 16 頁(yè) 共 34 頁(yè)char x;int y;r6=E,3,E,1,T,3,T,1,F,3,F,1;/ 輸入字符char index_char9=i,+,*,(,),#,

14、E,T,F;/ 獲取 index_char9 中元素的位置int get_index_char(char i)for(int j=0;j9;j+)if(index_charj = i)return j;return -1;二：頭文件 status_stack.h#include#include #define MAX 20typedef structint stackMAX;第 17 頁(yè) 共 34 頁(yè)int top;status;/ 初始化棧void init_stack(status *p)if( !p)printf(n 初始化狀態(tài)棧出錯(cuò) !n); p-top = -1;/ 壓棧void p

15、ush(status *p,int x)if(p-top top+;p-stackp-top = x;else printf(n 狀態(tài)棧溢出 !n);第 18 頁(yè) 共 34 頁(yè)/ 彈棧int pop(status *p)int x;if(p-top != 0)x = p-stackp-top;p-top-;return x;elseprin tf(n狀態(tài)棧 1 空!n);return 0;/ 取棧頂元素int get_top(status *p)int x;if(p-top != -1)第 19 頁(yè) 共 34 頁(yè)x = p-stackp-top;return x;elseprintf(n狀態(tài)棧

16、 2 空!n);return 0;/ 遍歷棧元素void out_stack(status *p)int i;if(p-top 0)printf(n 狀態(tài)棧 3 空!n);for(i=0; itop;i+)printf(%d,p-stacki);第 20 頁(yè) 共 34 頁(yè)三：頭文件 symbol_instr_stack.h#include#include#define MAX 20typedef structchar stackMAX;int top;symbol_instr;/ 初始化棧void init_stack(symbol_instr *p)if( !p)printf(n 初始化符號(hào)

17、棧出錯(cuò) !n);p-top = -1;/ 壓棧void push(symbol_instr *p,char x)if(p-top top+;p-stackp-top = x;else printf(n 符號(hào)棧溢出 !n);/ 彈棧char pop(symbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;p-top-;return x;elseprintf(n 符號(hào)棧 1 空 !n);return 0;第 22 頁(yè) 共 34 頁(yè)/ 取棧頂元素char get_top(symbol_instr *p)char x;if(p-top != -1)

18、第 23 頁(yè) 共 34 頁(yè)x = p-stackp-top;return x;elseprintf(n 符號(hào)棧 2 空 !n);return 0;/ 自棧底到棧頂遍歷棧元素void out_stack1(symbol_instr *p)int i;if(p-top 0)printf(n 符號(hào)棧 3 空!n);for(i=0; itop;i+)printf(%c,p-stacki);/ 自棧頂?shù)綏５妆闅v棧元素void out_stack2(symbol_instr *p)第 24 頁(yè) 共 34 頁(yè)int i;if(p-top top;i=0;i-)printf(%c,p-stacki);四：主程

19、序：#includestatus_stack.h#includesymbol_instr_stack.h#includelr.h/打印 LR 分析器的工作過(guò)程void print(status *status_p,symbol_instry = get_top(status_p);第 25 頁(yè) 共 34 頁(yè)*symbol_p,symbol_instr *instr_p)int i;out_stack(status_p);for(i=0;itop;i+)printf( );out_stack1(symbol_p);for(i=0;i=0 & i=21 & i=26)x = ri-21.y;for(j=0;jtop != 0)x = p