lr分析器實驗報告

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

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

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

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

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

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

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

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

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

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

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

12、個字符。然后將該規(guī) 約規(guī)則左部壓入輸入串 棧i = = 12 ?i0 & i=11.規(guī)約出錯！異 常中止！*規(guī)約成功！退 出移進動作：1.將現(xiàn)狀態(tài)i壓 棧LR分析器設計流程圖附錄push(status_p,i)2.將當前輸入串字符壓入符號棧apop( in str_p)push(symbol_p,a)1f打印該步程工作過第 15 頁 共 34 頁程序源代碼一：頭文件 lr.h/LR 分析表#include#include/0-11 表示狀態(tài)結點， 2126 表示規(guī)約標號，/-1 表示 error （出錯）， 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 頁 共 34 頁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 頁 共 34 頁int top;status;/ 初始化棧void init_stack(status *p)if( !p)printf(n 初始化狀態(tài)棧出錯 !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 頁 共 34 頁/ 彈棧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 頁 共 34 頁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 頁 共 34 頁三：頭文件 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 初始化符號

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

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

19、序：#includestatus_stack.h#includesymbol_instr_stack.h#includelr.h/打印 LR 分析器的工作過程void print(status *status_p,symbol_instry = get_top(status_p);第 25 頁 共 34 頁*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