目錄引言..............................................................1第一章概述....................................................21.1設(shè)計(jì)題目及內(nèi)容.............................................21.2設(shè)計(jì)環(huán)境...................................................2第二章設(shè)計(jì)的基本原理..........................................32.1LR分析器的基本理..........................................32.2LR分析器工作過(guò)程算法......................................3第三章程序設(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 (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→I LR分析表：狀態(tài)ACTION(動(dòng)作)GOTO(轉(zhuǎn)換)I+*()#ETF0S5S41231S6Acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R5注：sj 表達(dá)把下一狀態(tài)j和現(xiàn)行輸入符號(hào)a移進(jìn)棧 rj 表達(dá)按第j個(gè)產(chǎn)生式進(jìn)行規(guī)約 acc 表達(dá)接受 空格表達(dá)出錯(cuò)標(biāo)志，報(bào)錯(cuò) 根據(jù)以上文法和LR分析表，構(gòu)造LR分析器，并規(guī)定輸出LR工作過(guò)程。1．2設(shè)計(jì)環(huán)境： 硬件設(shè)備：一臺(tái)PC機(jī) 軟件設(shè)備：Windows/XPOS，VC++6.0 實(shí)現(xiàn)語(yǔ)言：C語(yǔ)言二設(shè)計(jì)的基本原理2．1基本原理：1．LR措施的基本思想： 在規(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ì)上是一種帶先進(jìn)后出存儲(chǔ)器（棧）確實(shí)定有限狀態(tài)自動(dòng)機(jī)。3．LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。4．為清晰闡明LR分析器實(shí)現(xiàn)原理和模型： LR分析器的關(guān)鍵部分是一張分析表。這張分析表包括兩個(gè)部分，一是“動(dòng)作”（ACTION）表，另一是“狀態(tài)轉(zhuǎn)換”（GOTO）表。他們都是二維數(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（終止符或非終止符）時(shí)下一狀態(tài)是什么。顯然，GOTO(s，X)定義了一種以文法符號(hào)為字母表的DFA。 每一項(xiàng)ACTION(s，a)所規(guī)定的動(dòng)作不外是下述四種也許之一： （1）移進(jìn) 把（s，a）的下一種轉(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)和文法符號(hào)A推進(jìn)棧。規(guī)約動(dòng)作不變化現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著β（=Xm-r+1…Xm）已展現(xiàn)于棧頂并且是一種相對(duì)于A的句柄。 （3）接受 宣布分析成功，停止分析器的工作。 （4）報(bào)錯(cuò) 發(fā)現(xiàn)源程序具有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。2．2LR分析器工作過(guò)程算法描述： 一種LR分析器的工作過(guò)程可當(dāng)作是棧里的狀態(tài)序列，已規(guī)約串和輸入串所構(gòu)成的三元式的變化過(guò)程。分析開(kāi)始時(shí)的初始三元式為 (s0,#,a1a2……an#)其中，s0為分析器的初態(tài)；＃為句子的左括號(hào)；a1a2……an為輸入串；其后的＃為結(jié)束符（句子右括號(hào)）。分析過(guò)程每步的成果可表達(dá)為 （s0s1……sm，#X1X2……Xmai,ai+1……an#）分析器的下一步動(dòng)作是由棧頂狀態(tài)sm和現(xiàn)行輸入符號(hào)ai所唯一決定的。即，執(zhí)行ACTION（sm，ai）所規(guī)定的動(dòng)作。經(jīng)執(zhí)行每種也許的動(dòng)作之后，三元式的變化情形是：若ACTION（sm，ai）為移進(jìn)，且s=GOTO（sm，ai），則三元式變成：（s0s1……sms，#X1X2……Xmai,ai+1……an#）若ACTION（sm，ai）={A→β},則按照產(chǎn)生式A→β進(jìn)行規(guī)約。此時(shí)三元式變?yōu)椋╯0s1……sms，#X1X2……XmA,aiai+1……an#） 此處s=GOTO（Sm-r，A），r為β的長(zhǎng)度，β=Xm-r+1……Xm。若ACTION（sm，ai）為“接受”，則三元式不再變化，變化過(guò)程終止，宣布分析成功。若ACTION（sm，ai）為“報(bào)錯(cuò)”，則三元式的變化過(guò)程終止，匯報(bào)錯(cuò)誤。一種LR分析器的工作過(guò)程就是一步一步的變換三元式，直至執(zhí)行“接受”或“報(bào)錯(cuò)”為止。三程序設(shè)計(jì)3．1總體設(shè)計(jì)方案：1．建模： （1）分析表建模： 構(gòu)造一種int型二維數(shù)組table[13][9],用于寄存LR分析表。并初始化。作者這樣規(guī)定： 0～11表達(dá)狀態(tài)sj，其中0對(duì)應(yīng)s0，1對(duì)應(yīng)s1…… 21～26 表達(dá)規(guī)約rj，其中21對(duì)應(yīng)r1，22對(duì)應(yīng)r2…… 12 表達(dá)“接受” -1 表達(dá)規(guī)約出錯(cuò)，報(bào)錯(cuò) （2）棧建模： 建立一種int型狀態(tài)棧，該棧為次序棧。 建立一種char型符號(hào)棧和一種char型輸入串棧，該棧為次序棧。 （3）規(guī)約體現(xiàn)式建模： 建立一種rule型構(gòu)造，組員變量為char型非終止符和int型表達(dá)規(guī)約第幾條體現(xiàn)式。2．程序設(shè)計(jì)關(guān)鍵注意環(huán)節(jié)： （1）在輸入串(句子)輸入的過(guò)程中，波及到一種壓棧的問(wèn)題。不過(guò)輸入串壓入的字符次序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲(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ù)拇涡颍斎氪畻ymbol_instr(instr_p)則是采用自棧頂?shù)綏５椎拇涡蜉敵觥?．2各模塊設(shè)計(jì)：1．棧設(shè)計(jì)： 構(gòu)造一種int型“狀態(tài)?！眘tatus和一種char型“符號(hào)－輸入串?！眘ymbol_instr。該棧包括初始化該棧init_status()，壓棧push()，彈棧pop()，取棧頂元素get_top()，自棧底到棧頂遍歷元素out_stack1()和自棧頂?shù)綏５妆闅v元素out_stack2().2．LR分析器工作過(guò)程算法設(shè)計(jì)： 構(gòu)造一種狀態(tài)轉(zhuǎn)換函數(shù)實(shí)現(xiàn)實(shí)狀況態(tài)轉(zhuǎn)換intgoto_char(status*status_p,symbol_instr*instr_p) 構(gòu)造一種移進(jìn)－－規(guī)約函數(shù)實(shí)現(xiàn)移進(jìn)規(guī)約動(dòng)作voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)構(gòu)造一種打印LR分析器的工作過(guò)程函數(shù)實(shí)現(xiàn)輸出voidprint(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p)3．流程圖： 初始化狀態(tài)棧，符號(hào)棧，輸入串棧初始化狀態(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)作：求出i對(duì)應(yīng)規(guī)約規(guī)則右部字符串長(zhǎng)度x=r[i-21].y在符號(hào)棧和狀態(tài)棧中彈出x個(gè)字符。然后將該規(guī)約規(guī)則左部壓入輸入串棧i>0&&i<=11移進(jìn)動(dòng)作：將現(xiàn)實(shí)狀況態(tài)i壓棧push(status_p,i)將目前輸入串字符壓入符號(hào)棧a=pop(instr_p)push(symbol_p,a)打印該步工作過(guò)程LR分析器設(shè)計(jì)流程圖四程序測(cè)試和成果以及心得1．測(cè)試成果：見(jiàn)附錄通過(guò)測(cè)試，輸入多種各樣的對(duì)的句子，均能對(duì)的規(guī)約。并且，輸入錯(cuò)誤的句子，也能對(duì)的報(bào)錯(cuò)。2．心得：附錄程序源代碼：四：主程序：#include"status_stack.h"#include"symbol_instr_stack.h"#include"lr.h"http://打印LR分析器的工作過(guò)程voidprint(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p){ inti; out_stack(status_p); for(i=0;i<20-status_p->top;i++) printf(""); out_stack1(symbol_p); for(i=0;i<20;i++) printf(""); out_stack2(instr_p); printf("\n");}//狀態(tài)轉(zhuǎn)換函數(shù)intgoto_char(status*status_p,symbol_instr*instr_p){ charx; inty,z; x=get_top(instr_p); y=get_top(status_p); z=get_index_char(x); returntable[y][z];}//移進(jìn)－－規(guī)約函數(shù)voidaction(status*status_p,symbol_instr*symbol_p,symbol_instr*instr_p){ inti,j,x; chara; i=goto_char(status_p,instr_p); //規(guī)約出錯(cuò) if(i==-1) printf("\n===============規(guī)約出錯(cuò)!================\n"); //規(guī)約成功 if(i==12) printf("\n===============規(guī)約成功!================\n"); //移進(jìn)動(dòng)作 if(i>=0&&i<=11) { push(status_p,i); a=pop(instr_p); push(symbol_p,a); print(status_p,symbol_p,instr_p); action(status_p,symbol_p,instr_p); } //規(guī)約動(dòng)作 if(i>=21&&i<=26) { x=r[i-21].y; for(j=0;j<x;j++) { pop(status_p); pop(symbol_p); } push(instr_p,r[i-21].x); action(status_p,symbol_p,instr_p); }}intmain(){ charx; //分派空間 status*status_p; symbol_instr*symbol_p,*instr_p; status_p=(status*)malloc(sizeof(status)); symbol_p=(symbol_instr*)malloc(sizeof(symbol_instr)); instr_p=(symbol_instr*)malloc(sizeof(symbol_instr)); //初始化各棧 init_stack(status_p); init_stack(symbol_p); init_stack(instr_p); //壓進(jìn)棧初始元素 push(s