基于表達(dá)式計(jì)算器的編譯原理課程設(shè)計(jì)

1、*工程學(xué)院編譯原理課程設(shè)計(jì)i果程i殳計(jì)題目表達(dá)式計(jì)算器姓 名：*院（系）:計(jì)算機(jī)科學(xué)與工程學(xué)院專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)084班學(xué) 號(hào)：200810214415 指導(dǎo)教師:*役計(jì)日期:2010年12月26日目錄表達(dá)式計(jì)算器11. 需求分析11.1. 總述12. 概要設(shè)計(jì)12.1. 開發(fā)環(huán)境122總體設(shè)計(jì)22.2.1. 模塊結(jié)構(gòu)圖22.2.2. 模塊說明22.2.3. 界面設(shè)計(jì)33. 詳細(xì)設(shè)計(jì)43.1. 詞法分析模塊: 43.1.1. 詞法分析簡(jiǎn)介： 43.1.2. 詞法分析模塊的設(shè)計(jì)及實(shí)現(xiàn)432語(yǔ)法分析模塊11321.語(yǔ)法分析簡(jiǎn)介113.22語(yǔ)法分析器的實(shí)現(xiàn)113.3 文法分析19.1 文法分

2、析器生成工具yacc194 測(cè)試分析215課程總結(jié)246 .參考文獻(xiàn)25農(nóng)達(dá)式計(jì)算器1. 需求分析1.1 總述計(jì)算器是我們經(jīng)常使用的小工具，它能幫我們對(duì)數(shù)據(jù)進(jìn)行冇效的 運(yùn)算，如通過四則運(yùn)算能實(shí)現(xiàn)對(duì)輸入數(shù)據(jù)的加減乘除。本課程設(shè)計(jì)結(jié) 合了編譯原理屮的詞法分析、語(yǔ)法分析及語(yǔ)義分析方法，給出了表達(dá) 式計(jì)算器的系統(tǒng)設(shè)計(jì)過程，并在VC+6.0中使用面向?qū)ο蟮募夹g(shù)實(shí) 現(xiàn)了計(jì)算器。1.2 功能要求計(jì)算器的功能要求如下：可以支持加（ +）、減（）、乘（*）、除 （/）運(yùn)算,如3+45*2/2;支持括號(hào)運(yùn)算,如（4+5） *5/8；判斷用戶 輸入的表達(dá)式是否正確，如3+丄3是一個(gè)錯(cuò)誤的表達(dá)式，在計(jì)算時(shí)將 提示錯(cuò)誤

3、；用戶輸入表達(dá)式后，按下等號(hào)按鈕執(zhí)行計(jì)算。2. 概要設(shè)計(jì)2.1. 開發(fā)環(huán)境開發(fā)平臺(tái)：Windows XP +VC+6.0開發(fā)語(yǔ)言：C+2.2. 總體設(shè)計(jì)程序在VC+6.0中使用面向?qū)ο蟮募夹g(shù)實(shí)現(xiàn)了計(jì)算器。模塊設(shè)計(jì)2.2.1. 模塊結(jié)構(gòu)圖圖1.程序模塊圖2.2.2. 模塊說明計(jì)算器分為三個(gè)功能模塊：（1）詞法分析模塊：對(duì)輸入的表達(dá)式從左到右掃描，識(shí)別出表 達(dá)式屮的單詞（包括運(yùn)算符和運(yùn)算數(shù)），若單詞的構(gòu)成不符合詞法規(guī) 則（運(yùn)算符和運(yùn)算數(shù)的構(gòu)成規(guī)則），則報(bào)錯(cuò)并停止計(jì)算。（2）語(yǔ)法分析模塊：將單詞分解為各類語(yǔ)法短語(yǔ)，若存在不符 合規(guī)則的語(yǔ)法短語(yǔ)，則報(bào)錯(cuò)并停止計(jì)算。(3) 計(jì)算模塊：對(duì)符合語(yǔ)法規(guī)則的語(yǔ)法

4、短語(yǔ)進(jìn)行計(jì)算，若計(jì)算 不能進(jìn)行，則報(bào)錯(cuò)并停止計(jì)算。計(jì)算器的三個(gè)功能模塊中語(yǔ)法分析模塊起到了核心作用，如圖1 所示。223.界面設(shè)計(jì)圖2表達(dá)式計(jì)算器3 詳細(xì)設(shè)計(jì)3.1. 詞法分析模塊：其詞法分析器調(diào)用接口為lex()3.1.1 詞法分析簡(jiǎn)介：詞法分析是編譯原理程序的第一階段，其任務(wù)是：從左至右逐個(gè) 字符地對(duì)源程序掃描和分解，識(shí)別出一個(gè)個(gè)的單詞(如標(biāo)志符、常量、 運(yùn)算符、界符等)，并判斷單詞的構(gòu)成是否符合詞法規(guī)則?？梢允褂?上下文無關(guān)文法來描述詞法規(guī)則，使用有限口動(dòng)機(jī)來識(shí)別單詞。3.1.2. 詞法分析模塊的設(shè)計(jì)及實(shí)現(xiàn)lex工具的基本使用方法和工作原理：Lex工具是一種詞法分析程序生成器，它可以根擁

5、詞法規(guī)則說明書的 要求來生成單詞識(shí)別程序，由該程序識(shí)別出輸入文本中的各個(gè)單詞。一般可以分為 定義部分X規(guī)則部分X用戶子程序部分。其屮規(guī)則部分是必須的，定義和用戶子程序 部分是任選的。(1) 定義部分定義部分起始于%符號(hào),終止于%符號(hào)，其間可以是包括include語(yǔ)句、聲明語(yǔ)句在內(nèi)的C語(yǔ)句。這部分跟普通C程序開頭沒什么區(qū)別。%#include "stdio.h"int linenum;%(2) 規(guī)則部分規(guī)則部分起始丁%符號(hào)，終止于%符號(hào)，其間則是詞法規(guī)則。詞法規(guī)則由模式和動(dòng)作兩部分組成。模式部分可以由任意的正則表達(dá)式組成，動(dòng)作部分 是由C語(yǔ)言語(yǔ)句組成，這些語(yǔ)句用來對(duì)所匹配的模

6、式進(jìn)fj湘應(yīng)處理。需要注意的是，lex將識(shí)別出來的單詞存放在yytextf字符數(shù)據(jù)小，因此該數(shù)組的內(nèi)容就代表了所識(shí)別出來的單詞的內(nèi)容。類似yytext這些預(yù)定義的變量函數(shù)會(huì)隨著后而內(nèi)容展開一一介紹。動(dòng)作部分如果冇多行執(zhí)行語(yǔ)句，也可以用括起來。%titleshowtitle();n0-9 +:%sn，z, yytext);1i nenum+;printf (z，Tnt0-9*0-9 +printf("Float : %srT,yytext);a-zA-Z a-zA-ZO-9* printf (/zVar : %snz，, yytext);+-*/%printf (/z0p: %snz，

7、, yytext);printf ('"Unknown : %cn", yytext0);%A.規(guī)則部分的正則表達(dá)式規(guī)則部分是Lex描述文件中最為復(fù)雜的一部分，下面列出些模式部分的正則表達(dá)式字符含義：A-Z, 0-9, a-z構(gòu)成模式部分的字符和數(shù)字。指定范圍。例如：a-z指從a到z之間的所冇字符。轉(zhuǎn)義元字符。用來覆蓋字符在此表達(dá)式中定義的特殊意義，只取字符的本身。表示一個(gè)字符集合。匹配括號(hào)內(nèi)的任意字符。如果第i個(gè)字符是那么它表示否定模式。例如：abC匹配a, b,和C的任何一個(gè)。表刀I否立。*匹配0個(gè)或者多個(gè)上述模式。+匹配1個(gè)或者多個(gè)上述模式。9匹配0個(gè)或1個(gè)上

8、述模式。$作為模式的最后一個(gè)字符時(shí)匹配一行的結(jié)尾。表示一個(gè)模式可能出現(xiàn)的次數(shù)。例如：A1,3表示A可能出現(xiàn)1次或3次。a-z 5表示長(zhǎng)度為5的，由a-z組成的字符。此外，還可以表示預(yù)定義的變量。匹配任意字符，除了 no()將一係列常規(guī)表達(dá)式分組。如：Letter(Letter|Digit)1表達(dá)式間的邏輯或。"一些符號(hào)字符的字面含義。元字符具有。如：相當(dāng)于*。/向前匹配。如果在匹配的模式中的廠后跟有后續(xù)表達(dá)武,只匹配模版中7前面的部分。如：模式為ABC/D 輸入 ABCD,吋ABC會(huì)匹配ABC/D,而D會(huì)匹配相應(yīng)的模式。輸入ABCE的話，ABCE就不會(huì)去匹配ABC/D0B.規(guī)則部分的

9、優(yōu)先級(jí)規(guī)則部分貝有優(yōu)先級(jí)的概念，先舉個(gè)簡(jiǎn)單的例子:%#include "stdio.h"%n*Aprintf (/z0NEnz/);AAprintf (z，TW0n，z);AAAAprintf("THREEn)；;%此時(shí)，如果輸入內(nèi)容：root local host liweitest# cat filel.txtAAAAAAArootlocalhost liweitest# . /parser < filel. txtTHREETWOONELex分析詞法時(shí)，是逐個(gè)字符進(jìn)行讀取，口上而下進(jìn)行規(guī)則匹配的，讀取到第一個(gè)A字符時(shí)，遍歷后發(fā)現(xiàn)三個(gè)規(guī)則皆匹配成功，Le

10、x會(huì)繼續(xù)分析下去，讀至第五個(gè)字符時(shí)，發(fā)現(xiàn)AAAA只有一個(gè)規(guī)則可用，即按行為進(jìn)行處理，以此類推?？梢奓ex會(huì)選擇最長(zhǎng)的字符匹配規(guī)則。如果將規(guī)則AAAAprintfCTHREEnz/)；改為AAAAAprintfCTIIREEn，z);./parser < filel. txt 輸出結(jié)果為:THREETWO(3) 用戶子程序部分最后一個(gè)%后面的內(nèi)容是用戶子程序部分，可以包含用C語(yǔ)言編寫的子程序，而這些子程序可以用在前面的動(dòng)作中，這樣就可以達(dá)到簡(jiǎn)化編程的II的。這里9需要注意的是，當(dāng)編譯時(shí)不帶T1選項(xiàng)時(shí)，是必須加入main函數(shù)和yywrap（yywrap將下后面說明）。如:%showt it

11、le()printf (z，Lex Examplenz，);int main()1inenumO;yylexO ; /* 進(jìn)行 Lex 分析 */printf CAnLine Count: %dn，z, linenum);return 0;int yywrap ()return 1;io3.2. 語(yǔ)法分析模塊3.2.1. 語(yǔ)法分析簡(jiǎn)介語(yǔ)法分析的任務(wù)是：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則, 把單詞串分解成各類語(yǔ)法短語(yǔ)(如句子、程序、表達(dá)式等)，從而確 定整個(gè)輸入串的結(jié)構(gòu)是否正確?？墒褂蒙舷挛臒o法文法描述語(yǔ)法規(guī) 則，算符優(yōu)先分析法是一種語(yǔ)法分析方法，它特別適合分析各類表達(dá) 式。3.2.2. 語(yǔ)

12、法分析器的實(shí)現(xiàn)(1) 產(chǎn)生式：(0)S, -E E-E+TET T-T*FT-F(5) F- (E)(6) F-*i E-E-T T-T/Fii（2）得出LR分析表:狀態(tài)ACTIONGOTO1+*/()#ETF0S5S41231S6S7ACC2r2r2S8S9r2r23r4r4r4r4r4r44S5S410235r6r6r6r6r6r66S5S41137S5S41238S5S4139S5S41410S6S7S1511rlrlS8S9rlrl12r7r7S8S9r7r713r3r3r3r3r3r314r8r8r8r8r8r815r5r5r5r5r5r5（3）代碼實(shí)現(xiàn)：嚴(yán)以下變量用于語(yǔ)法分析*/終

13、結(jié)符符號(hào)表Vvt=” i”,$INT,”+”,$PLUS,”“,$MINUS,”*“,$MUL,”廠,$DIV,” (”,$LPAR.”)”,$RPAR,”#”,$END非終結(jié)符符號(hào)表V vn=” E”,$E,” F”,$F；文法的產(chǎn)生式集合P pset=1 ,$E, $E,$PLUS,$T,() ,/E>E+T2, $E,$E,$MINUS,$T,0,3, $E,$T,0,0.0,4, $T,$T,$MUL,$F,(),5, $T,$T,$DIV,$F,0,6, $T,$F,0,0,0,7, $F, $LPAR,$E,$RPAR,0,& $F,$INT.0,0,0,0,0,()

14、；/action 表int action168 = iS+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK.BLANK,S+6,S+7,BLANK,BLANK.BLANK,BLANK,ACC,BLANK,R+3,R+3,S+&S+9,BLANK,R+3,R+3,BLANK.R+6.R+6.R+6.R+6,BLANK,R+6.R+6,14S+5,BLANK,BLANK,BLANK.BLANK,S+4.BLANK,BLANK,BLANK,R+&R+&R+&R+8,BLANK,R+&R+&S+5,BLANK,BLANK

15、,BLANK,BLANK,S+4,BLANK,BLANK,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,S+5,BLANK,BLANK、BLANK.BLANK,S+4.BLANK,BLANK,S+5,BLANK,BLANK,BLANK,BLANK,S+4,BLANK,BLANK,BLANK,S+6,S+7,BLANK,BLANK.BLANK,S+15,BLANK,BLANKR+l ,R+1 ,S+8,S+9,BLANK,R+l ,R+1,BLANK,R+2,R+2,S+8,S+9,BLANK,R+2.R+2,BLANK,R+4,R+4.R+4R+4,B

16、LANK,R+4R+4,BLANK,R+5,R+5R+5.R+5,BLANK,R+5,R+5,BLANK,R+7,R+7.R+7,R+7,BLANK,R+7.R+7；/Goto 表int go163 = /E,T,F123,BLANK,BLANK.BLANK,BLANK,BLANK.BLANK,BLANK,BLANK,BLANK,10,2,3,BLANK,BLANK,BLANK,BLANK J 1,3,BLANK, 12,3,BLANK,BLANK,13,BLANK,BLANK,14,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK,BLANK.BLANK,B

17、LANK,BLANK. BLANK,BLANK,BLANK.BLANK,BLANK,BLANK.BLANK；int SLR1()/SLR1 分析表入口int token;/輸入符號(hào)int s,e; /U態(tài)棧頂、符號(hào)棧頂元素ini *pipl;產(chǎn)生式右部、左部int act;/動(dòng)作分析棧rstack slrstack(256);slrstack.push(0, SEND);token = Lex();while(true)if (token = $UNKNOWN)ProcError();return FAIL;elseact = actionslrstack.top(s,e) token-1;i

18、f (act = BLANK)ProcError();return FAIL; else if (act = ACC)primf(”接受！ ”);return SUCCESS;else if (act < R)移入printf(n移入sn", vtftoken-1 .name);slrstack.push(act-S, token);token = Lex();else規(guī)約pr = psetact-R-l.right;pl = psetact-R-l.left;printfC'規(guī)約產(chǎn)生式:%s->", );while(*pr !

19、= 0)if (*pr >= 100)printf(H%s vn*pr-IOO.name);elseprintf("%s ", vt*);slrstack.pop(s, e);pr+;printf(nnM);s = goslrstack.top(s,e) pl -100;slrstack.push(s, pl);/if (act = BLANK)/if (token = $UNKN0WN)/while3.3文法分析.1文法分析器生成工具yacc簡(jiǎn)單來說,yacc(Yet Another Compiler-Compiler)就是編譯器的編 譯器。Yac

20、c是一-個(gè)通用的工具，能夠根據(jù)用戶指定的規(guī)則，生成一 個(gè)詞法分析程序。yacc能識(shí)別LALR且無歧義的文法，它的輸入是 詞法分析器的輸出。我們知道，生成詞法分析器是lex分內(nèi)的事，因 此lex和yacc常常珠聯(lián)璧合。先讓我們看一下yacc文件的格式。和前面介紹的lex的格式類 似：declarations聲明%rules規(guī)則%programs其它程序其屮聲明段聲明一些符號(hào)常量，可以為空。同lex樣，聲明段中可 以有出現(xiàn)在目標(biāo)C程序中的代碼,放在%-%中；還有一些yacc關(guān) 鍵詞可以指示出token的結(jié)介順序：% left左結(jié)合%right右結(jié)合%nonassoc不結(jié)合%token聲明token

21、俗話說“沒有規(guī)矩，不成方圓”。規(guī)則段描述規(guī)則，自然是重中之重To規(guī)則段的結(jié)構(gòu)是如下，A : BODY ;A表示非終結(jié)符名，BODY表示產(chǎn)生式和動(dòng)作，產(chǎn)生式包括非終結(jié)符和 終結(jié)符，終結(jié)符用''引用。一些轉(zhuǎn)義字符，比如'L等, 和C里而的表示是一樣的。動(dòng)作(action)則是在輸入被當(dāng)前規(guī)則識(shí)別 出來時(shí)而執(zhí)行的。動(dòng)作實(shí)際上就是C的代碼，寫在 屮。為了溝通 詞法分析器和動(dòng)作，yacc引入了形式變量，以$開頭。如果希望獲得 詞法分析器和前面的動(dòng)作返冋的值，我們可以使用$1,$2,。$丄表示一條規(guī)則右側(cè)第7個(gè)單元的值。比如冇這樣的一條規(guī)則,A : B C D ;C的返回值為$2, D為$3。依此類推。程序段放些其它的程序，也可以省略，連%都可以不要。連接時(shí)需要指定連接庫(kù)，gcc的參數(shù)為Ty。4 測(cè)試分析功能測(cè)試:圖2進(jìn)行加法運(yùn)算25盤表達(dá)式計(jì)算晉