1、學(xué)號(hào):E 專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)二班 姓名:楊雨露實(shí)驗(yàn)日期:2012/5/25 教師簽字: 成績(jī):編譯原理課程實(shí)驗(yàn)報(bào)告Word上實(shí)驗(yàn)四:LR分析 目 錄引言.1第一章 概述.2 1.1設(shè)計(jì)題目及內(nèi)容.2 1.2設(shè)計(jì)環(huán)境.2第二章 設(shè)計(jì)的基本原理.3 2.1 LR分析器的基本理.3 2.2 LR分析器工作過(guò)程算法.3 第三章 程序設(shè)計(jì).5 3.1總體方案設(shè)計(jì).5 3.2各模塊設(shè)計(jì).5 第四章 程序測(cè)試和結(jié)論以及心得. .7參考文獻(xiàn). 7 附錄 程序清單.8第一章 概述11設(shè)計(jì)題目及內(nèi)容設(shè)計(jì)題目：根據(jù)LR分析表構(gòu)造LR分析器內(nèi)容：已知文法G：(1)EE+T (2) ET (3) TT*F (4)

2、TF (5) F(E) (6) FILR分析表：狀態(tài)Action表GOTO表 a b c # S A B0S21231accept2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S99R2R2R2R2注：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分析器，并要求輸出LR工作過(guò)程。12設(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ì)的基本原理21 基本原理1.LR方法的基本思想： 在規(guī)范規(guī)約的

3、過(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)生式的句柄。2LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。3LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。4為清晰說(shuō)明LR分析器實(shí)現(xiàn)原理和模型： LR分析器的核心部分是一張分析表。這張分析表包括兩個(gè)部分，一是“動(dòng)作”（ACTION）表，另一是“狀態(tài)轉(zhuǎn)換”（GOTO）

4、表。他們都是二維數(shù)組。ACTION(s,a)規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。GOTO（s，X）規(guī)定了狀態(tài)s面對(duì)文法符號(hào)X（終結(jié)符或非終結(jié)符）時(shí)下一狀態(tài)是什么。顯然，GOTO(s，X)定義了一個(gè)以文法符號(hào)為字母表的DFA。 每一項(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 進(jìn)行規(guī)約。假若的長(zhǎng)度為r，規(guī)約的動(dòng)作是A，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r 變成棧頂狀態(tài)，然后把（Sm-r，A）的下一狀態(tài)s = GOTO(Sm-r,A)和文法符

5、號(hào)A推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著（= Xm-r+1Xm）已呈現(xiàn)于棧頂而且是一個(gè)相對(duì)于A的句柄。（3）接受宣布分析成功，停止分析器的工作。（4）報(bào)錯(cuò)發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。22 LR分析器工作過(guò)程算法描述一個(gè)LR分析器的工作過(guò)程可看成是棧里的狀態(tài)序列，已規(guī)約串和輸入串所構(gòu)成的三元式的變化過(guò)程。分析開始時(shí)的初始三元式為 （s0, #, a1a2an#）其中，s0為分析器的初態(tài)；為句子的左括號(hào)；a1a2an為輸入串；其后的為結(jié)束符（句子右括號(hào)）。分析過(guò)程每步的結(jié)果可表示為（s0s1sm， #X1X2Xm ai, ai+1an#）分析器的下一步動(dòng)作是由棧頂狀態(tài)s

6、m和現(xiàn)行輸入符號(hào)ai所唯一決定的。即，執(zhí)行ACTION（sm，ai）所規(guī)定的動(dòng)作。經(jīng)執(zhí)行每種可能的動(dòng)作之后，三元式的變化情形是：（1） 若ACTION（sm，ai）為移進(jìn)，且s = GOTO（sm，ai），則三元式變成： （s0s1sm s， #X1X2Xm ai, ai+1an#）（2） 若ACTION（sm，ai）= A,則按照產(chǎn)生式A進(jìn)行規(guī)約。此時(shí)三元式變?yōu)?（s0s1sm s， #X1X2Xm A, ai ai+1an#） 此處s = GOTO（Sm-r，A），r為的長(zhǎng)度， = Xm-r+1Xm。（3） 若ACTION（sm，ai）為“接受”，則三元式不再變化，變化過(guò)程終止，宣布分析成

7、功。（4） 若ACTION（sm，ai）為“報(bào)錯(cuò)”，則三元式的變化過(guò)程終止，報(bào)告錯(cuò)誤。一個(gè)LR分析器的工作過(guò)程就是一步一步的變換三元式，直至執(zhí)行“接受”或“報(bào)錯(cuò)”為止。 第三章 程序設(shè)計(jì)31總體設(shè)計(jì)方案建模（1）分析表建模： 構(gòu)造一個(gè)int 型二維數(shù)組table139,用于存放LR分析表。并初始化。作者這樣規(guī)定：011 表示 狀態(tài)sj，其中0對(duì)應(yīng)s0，1對(duì)應(yīng)s12126表示 規(guī)約rj，其中21對(duì)應(yīng)r1，22對(duì)應(yīng)r212表示 “接受”-1表示 規(guī)約出錯(cuò)，報(bào)錯(cuò)（2）棧建模： 建立一個(gè)int 型狀態(tài)棧，該棧為順序棧。 建立一個(gè)char型符號(hào)棧和一個(gè)char型輸入串棧，該棧為順序棧。（3）規(guī)約表達(dá)式建

8、模： 建立一個(gè)rule型結(jié)構(gòu)，成員變量為char型非終結(jié)符和int型表示規(guī)約第幾條表達(dá)式。程序設(shè)計(jì)關(guān)鍵注意環(huán)節(jié)（1）在輸入串(句子)輸入的過(guò)程中，涉及到一個(gè)壓棧的問(wèn)題。但是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲(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ò)程均采取自棧底到棧頂

9、的順序，而輸入串棧 symbol_instr(instr_p)則是采取自棧頂?shù)綏５椎捻樞蜉敵觥?2各模塊設(shè)計(jì)棧設(shè)計(jì)構(gòu)造一個(gè)int型“狀態(tài)棧”status和一個(gè)char型“符號(hào)輸入串?！?symbol_instr。該棧包括初始化該棧init_status()，壓棧push()，彈棧pop()，取棧頂元素get_top()，自棧底到棧頂遍歷元素out_stack1()和自棧頂?shù)綏５妆闅v元素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í)

10、現(xiàn)移進(jìn)規(guī)約動(dòng)作voidaction(status *status_p,symbol_instr *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)流程圖 初始化狀態(tài)棧，符號(hào)棧，輸入串棧輸入串各字符壓棧 求下一狀態(tài)符號(hào)ii = goto_char(status_p,instr_p)規(guī)約出錯(cuò)！異常中止！i = = -1 ?規(guī)約成功！退出i = = 12 ?規(guī)約動(dòng)作：1 求出i對(duì)應(yīng)規(guī)約規(guī)則右部字符串

11、長(zhǎng)度x = ri-21.y2 在符號(hào)棧和狀態(tài)棧中彈出x個(gè)字符。然后將該規(guī)約規(guī)則左部壓入輸入串棧i0 & i=11 移進(jìn)動(dòng)作：1 將現(xiàn)狀態(tài)i壓棧push(status_p,i)2 將當(dāng)前輸入串字符壓入符號(hào)棧a = pop(instr_p)push(symbol_p,a)打印該步工作過(guò)程 LR分析器設(shè)計(jì)流程圖 附錄 程序源代碼一：頭文件 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, -1,1, -1, -1,-1, -1,-1,12,-1,-1,-

12、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 rulechar x;int y;r6=E,3,E,1,T,3,T,1,F,3,F,1;/輸入字符char index_char9=i,+,*,(,),#,E,T,F;/獲取index_char9中元素的位置int get_index_char(ch

13、ar 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;int top;status;/初始化棧void init_stack(status *p)if( !p)printf(n初始化狀態(tài)棧出錯(cuò)!n);p-top = -1;/壓棧void push(status *p,int x)if(p-top top+;p-stackp-top = x;else printf(n狀態(tài)棧溢出

14、!n);/彈棧int pop(status *p)int x;if(p-top != 0)x = p-stackp-top;p-top-;return x;else printf(n狀態(tài)棧1空!n);return 0;/取棧頂元素int get_top(status *p)int x;if(p-top != -1)x = p-stackp-top;return x;else printf(n狀態(tài)棧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+)pri

15、ntf(%d,p-stacki);三：頭文件 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)棧出錯(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(sy

16、mbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;p-top-;return x;else printf(n符號(hào)棧1空!n);return 0;/取棧頂元素char get_top(symbol_instr *p)char x;if(p-top != -1)x = p-stackp-top;return x;else printf(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;

17、 itop;i+)printf(%c,p-stacki);/自棧頂?shù)綏５妆闅v棧元素void out_stack2(symbol_instr *p)int i;if(p-top top;i=0;i-)printf(%c,p-stacki);四：主程序：#includestatus_stack.h#includesymbol_instr_stack.h#includelr.h/打印LR分析器的工作過(guò)程void print(status *status_p,symbol_instr *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