編譯原理課程設(shè)計基于表達式計算器

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

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

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

4、存在不符合規(guī)則的語法短語，則報錯并停止計算。（3）計算模塊：對符合語法規(guī)則的語法短語進行計算，若計算不能進行，則報錯并停止計算。計算器的三個功能模塊中語法分析模塊起到了核心作用，如圖1所示。2.2.3. 界面設(shè)計圖2表達式計算器3. 詳細設(shè)計3.1. 詞法分析模塊：其詞法分析器調(diào)用接口為lex()3.1.1. 詞法分析簡介：詞法分析是編譯原理程序的第一階段，其任務(wù)是：從左至右逐個字符地對源程序掃描和分解，識別出一個個的單詞（如標志符、常量、運算符、界符等），并判斷單詞的構(gòu)成是否符合詞法規(guī)則。可以使用上下文無關(guān)文法來描述詞法規(guī)則，使用有限自動機來識別單詞。3.1.2. 詞法分析模塊的設(shè)計及實現(xiàn)l

5、ex工具的基本使用方法和工作原理：lex工具是一種詞法分析程序生成器，它可以根據(jù)詞法規(guī)則說明書的要求來生成單詞識別程序，由該程序識別出輸入文本中的各個單詞。 一般可以分為。其中規(guī)則部分是必須的，定義和用戶子程序部分是任選的。(1)定義部分 定義部分起始于 % 符號，終止于 % 符號，其間可以是包括include語句、聲明語句在內(nèi)的c語句。這部分跟普通c程序開頭沒什么區(qū)別。% #include stdio.hint linenum;%(2) 規(guī)則部分 規(guī)則部分起始于%符號，終止于%符號，其間則是詞法規(guī)則。詞法規(guī)則由模式和動作兩部分組成。模式部分可以由任意的正則表達式組成，動作部分是由c語言語句組

6、成，這些語句用來對所匹配的模式進行相應(yīng)處理。需要注意的是，lex將識別出來的單詞存放在yytext字符數(shù)據(jù)中，因此該數(shù)組的內(nèi)容就代表了所識別出來的單詞的內(nèi)容。類似yytext這些預(yù)定義的變量函數(shù)會隨著后面內(nèi)容展開一一介紹。動作部分如果有多行執(zhí)行語句，也可以用括起來。%title showtitle();n linenum+;0-9+ printf(int : %sn,yytext);0-9*.0-9+ printf(float : %sn,yytext);a-za-za-za-z0-9* printf(var : %sn,yytext);+-*/% printf(op : %sn,yytext

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

8、$ 作為模式的最后一個字符時匹配一行的結(jié)尾。 表示一個模式可能出現(xiàn)的次數(shù)。 例如: a1,3 表示 a 可 能出現(xiàn)1次或3次。a-z5 表示長度為5的，由a-z組成的 字符。此外，還可以表示預(yù)定義的變量。 . 匹配任意字符，除了 n。( ) 將一系列常規(guī)表達式分組。如：letter(letter|digit)* | 表達式間的邏輯或。一些符號 字符的字面含義。元字符具有。如：* 相當于 *。/ 向前匹配。如果在匹配的模式中的/后跟有后續(xù)表達式， 只匹配模版中/前面的部分。如：模式為 abc/d 輸入 abcd， 時abc會匹配abc/d，而d會匹配相應(yīng)的模式。輸入abce的話， abce就不會

9、去匹配abc/d。b.規(guī)則部分的優(yōu)先級規(guī)則部分具有優(yōu)先級的概念，先舉個簡單的例子：%#include stdio.h%n ;a printf(onen);aa printf(twon);aaaa printf(threen);%此時，如果輸入內(nèi)容：rootlocalhost liweitest# cat file1.txtaaaaaaarootlocalhost liweitest# ./parser file1.txtthreetwoonelex分析詞法時，是逐個字符進行讀取，自上而下進行規(guī)則匹配的，讀取到第一個a字符時，遍歷后發(fā)現(xiàn)三個規(guī)則皆匹配成功，lex會繼續(xù)分析下去，讀至第五個字符時，

10、發(fā)現(xiàn)aaaa只有一個規(guī)則可用，即按行為進行處理，以此類推。可見lex會選擇最長的字符匹配規(guī)則。如果將規(guī)則aaaa printf(threen);改為aaaaa printf(threen);./parser e+t2,$e,$e,$minus,$t,0,3,$e,$t,0,0,0,4,$t,$t,$mul,$f,0,5,$t,$t,$div,$f,0,6,$t,$f,0,0,0,7,$f,$lpar,$e,$rpar,0,8,$f,$int,0,0,0,0,0,0;/action表int action168 = / i,+,-,*,/,(,),# s+5,blank,blank,blank,b

11、lank,s+4,blank,blank,blank,s+6,s+7,blank,blank,blank,blank,acc,blank,r+3,r+3,s+8,s+9,blank,r+3,r+3,blank,r+6,r+6,r+6,r+6,blank,r+6,r+6,s+5,blank,blank,blank,blank,s+4,blank,blank,blank,r+8,r+8,r+8,r+8,blank,r+8,r+8,s+5,blank,blank,blank,blank,s+4,blank,blank,s+5,blank,blank,blank,blank,s+4,blank,bla

12、nk,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,blank,r+1,r+1,s+8,s+9,blank,r+1,r+1,blank,r+2,r+2,s+8,s+9,blank,r+2,r+2,blank,r+4,r+4,r+4,r+4,blank,r+4,r+4,blank,r+5,r+5,r+5,r+5,blank,r+5,r+5,blank,r+7,r+7,r+7,r+7,

13、blank,r+7,r+7;/goto表int go163 = /e,t,f1,2,3,blank,blank,blank,blank,blank,blank,blank,blank,blank,10,2,3,blank,blank,blank,blank,11,3,blank,12,3,blank,blank,13,blank,blank,14,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank,blank;int slr1()/slr1分析

14、表入口int token;/輸入符號int s,e;/狀態(tài)棧頂、符號棧頂元素int *pr,pl;/產(chǎn)生式右部、左部int act;/動作/分析棧rstack slrstack(256);slrstack.push(0, $end);token = lex();while(true)if (token = $unknown)procerror();return fail;elseact = actionslrstack.top(s,e)token-1;if (act = blank)procerror();return fail;else if (act = acc)printf(接受！);r

15、eturn success;else if (act , );while(*pr != 0)if (*pr = 100)printf(%s , vn*);elseprintf(%s , vt*);slrstack.pop(s, e);pr+;printf(n);s = goslrstack.top(s,e)pl-100;slrstack.push(s, pl);/if (act = blank)/if (token = $unknown)/while3.3 文法分析.1 文法分析器生成工具yacc簡單來說，yacc(yet an

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

17、ight右結(jié)合%nonassoc不結(jié)合%token聲明token俗話說“沒有規(guī)矩，不成方圓”。 規(guī)則段描述規(guī)則，自然是重中之重了。規(guī)則段的結(jié)構(gòu)是如下，a : body ;a表示非終結(jié)符名，body表示產(chǎn)生式和動作。產(chǎn)生式包括非終結(jié)符和終結(jié)符，終結(jié)符用引用。一些轉(zhuǎn)義字符，比如r,n等，和c里面的表示是一樣的。動作(action)則是在輸入被當前規(guī)則識別出來時而執(zhí)行的。動作實際上就是c的代碼，寫在 中。為了溝通詞法分析器和動作，yacc引入了形式變量，以$開頭。如果希望獲得詞法分析器和前面的動作返回的值，我們可以使用$1,$2,。$i表示一條規(guī)則右側(cè)第i個單元的值。比如有這樣的一條規(guī)則，a : b

18、 c d ;c的返回值為$2，d為$3。依此類推。程序段放一些其它的程序，也可以省略，連%都可以不要。連接時需要指定連接庫，gcc的參數(shù)為-ly。4. .測試分析功能測試：圖2進行加法運算圖3表達式進行減法運算圖4表達式進行乘法運算圖5表達式進行除法運算圖6表達式進行四則運算圖7表達式進行括號優(yōu)先運算5 課程總結(jié)本課程設(shè)計基于程序設(shè)計語言的編譯原理，給出了表達式計算器的設(shè)計過程，并在vc+6.0下將其進行了實現(xiàn)。其中由于時間問題，在詞法分析與語義分析中分別運用了lex和yacc工具。所以本課程設(shè)計的核心內(nèi)容在于語法分析階段，語法分析采用自上而下分析法，確定相關(guān)的文法產(chǎn)生式，確定first和follow集合，對產(chǎn)生式進行移近和規(guī)約，構(gòu)造action和goto表，最后進行代碼的編寫。通過本