編譯原理課程設(shè)計(jì)終結(jié)版(共34頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 基于算符優(yōu)先分析方法 的表達(dá)式語法分析器 年 級： 2007班 級： 級計(jì)算機(jī)科學(xué)與技術(shù) 4班組 長： 劉思佳組 員： 歐 垚 毛群暉 袁小仨 徐碧紅 鄧文杰 孫苗苗 頓 碩 伍小軍 曾 潔 孫 梁 吉順昌指導(dǎo)老師： 段明秀二二二二二二年二月二十二日目 錄00814.1第一版測試2152233專心-專注-專業(yè)前 言1摘要編譯原理是計(jì)算機(jī)專業(yè)的一門重要專業(yè)課，旨在介紹編譯程序構(gòu)造的一般原理和基本方法。內(nèi)容包括語言和文法、詞法分析、語法分析、語法制導(dǎo)翻譯、中間代碼生成、存儲管理、代碼優(yōu)化和目標(biāo)代碼生成。編譯原理是計(jì)算機(jī)專業(yè)設(shè)置的一門重要的專業(yè)課程。雖然只有少數(shù)人從事編譯

2、方面的工作，但是這門課在理論、技術(shù)、方法上都對學(xué)生提供了系統(tǒng)而有效的訓(xùn)練，有利于提高軟件人員的素質(zhì)和能力。算符優(yōu)先分析法是一種簡單直觀、特別方便于表達(dá)式分析，易于手式實(shí)現(xiàn)的方法。算符優(yōu)先法只考慮算符（廣義為終結(jié)符號）之間的優(yōu)先關(guān)系，它是一種自底向上的歸約過程，但這種歸約未必嚴(yán)格按照句柄歸約。它是一種不規(guī)范歸約法。算符優(yōu)先分析法的關(guān)鍵是比較兩個(gè)相繼出現(xiàn)的終結(jié)符號的優(yōu)先級而決定應(yīng)采取的動作。要完成算符間的優(yōu)先級比較，就要先定義各種可能出相繼出現(xiàn)的運(yùn)算符的優(yōu)先級，并將其表示成矩陣形式，在分析過程中通過查詢矩陣元素而得出算符間的優(yōu)先關(guān)系。2問題描述給出該文法E # E #E E + Q | QQ Q

3、- T | TT T * F | FF F/ MMM M PPP ( E )i用算符優(yōu)先分析法實(shí)現(xiàn)對表達(dá)式的計(jì)算。3項(xiàng)目開發(fā)平臺語言：Java開發(fā)平臺：MyEclipse第1章 課程設(shè)計(jì)計(jì)劃1.1組員與工作分配組長：劉思佳資料組：毛群暉，鄧文杰，曾潔代碼組：劉思佳，孫梁，孫苗苗，頓碩測試組：歐垚，吉順昌，徐碧紅，袁小仨，伍小軍1.2課程計(jì)劃表1.2.1 課程設(shè)計(jì)計(jì)劃清單序號內(nèi)容需求計(jì)劃時(shí)間實(shí)際時(shí)間狀態(tài)1問題定義對課程設(shè)計(jì)要求分析6月15日6月15日已完成2查詢資料對課程設(shè)計(jì)做必要的資料查詢6月16日-6月17日6月17日已完成3概要設(shè)計(jì)確定課程設(shè)計(jì)的總體框架與分包6月18日6月18日已完成4詳

4、細(xì)設(shè)計(jì)具體分析設(shè)計(jì)每個(gè)類與接口6月19日-6月20日6月20日已完成5編碼實(shí)現(xiàn)程序6月21日6月21日已完成6測試并修改測試程序BUG并進(jìn)行修改6月22日-6月26日6月26日已完成1.3資源需求 表1.3.1開發(fā)資源序號資源作用占用時(shí)間當(dāng)前可用狀態(tài)獲得途徑1MyEclipse平臺設(shè)計(jì)平臺貫穿整個(gè)設(shè)計(jì)階段可用網(wǎng)上下載第2章 功能需求分析2.1 功能需求清單表2.1.1 需求清單功能編號功能名稱備注1鍵盤輸入用戶能從鍵盤輸入字符串2表達(dá)式切分切分算術(shù)表達(dá)式，結(jié)果存入字符串?dāng)?shù)組，如： 字符串：1.5+3*2# 將被切分為 1.5,+,3,*,2,#3掃描表達(dá)式檢測是否符合給定的文法4出錯處理不符合

5、文法的給出錯誤提示5計(jì)算表達(dá)式合法的算術(shù)表達(dá)式將計(jì)算出結(jié)果6輸出將計(jì)算結(jié)果輸出給用戶第3章 設(shè)計(jì)、分析與編碼3.1 總體設(shè)計(jì)3.1.1 模塊劃分該語法分析器可分為以下幾個(gè)主要模塊：1. 詞法分析并計(jì)算模塊其中應(yīng)有一個(gè)操作符棧和一個(gè)操作數(shù)棧，用于分析輸入的文法和句子，并提供方法檢驗(yàn)該表達(dá)式是否為給出的文法，如果是則運(yùn)算出結(jié)果，否則提示錯誤2. 算符優(yōu)先表構(gòu)建模塊用于構(gòu)建輸入文法的算符優(yōu)先表，并對其中的算符優(yōu)先表進(jìn)行各種操作。3. 輸入功能模塊提供從鍵盤輸入功能。3.1.2程序分包c(diǎn)om.op.core 該包下為核心類，完成核心功能com.op.util 該報(bào)為工具包，包含一些輸入，字符串處理等程

6、序之間應(yīng)該保持低耦合，高內(nèi)聚。包之間的依賴關(guān)系為core->util,核心包依賴于util， util不依賴其他包。3.2 詳細(xì)設(shè)計(jì) 3.2.1 類圖com.op.core.OperatorPrority類：該類為核心類，實(shí)現(xiàn)所有核心功能。com.op.core.ProrityTable類：該類為存放算符優(yōu)先級表，以及對算符優(yōu)先級表查詢等操作。com.op.core.StringUtil類：該類實(shí)現(xiàn)必要的字符串操作。com.op.core.IOUtil類：該類實(shí)現(xiàn)輸入輸出等常用操作類之間的依賴關(guān)系：OperatorPriority將依賴于其他三個(gè)類，而其他的類互不依賴。輸入待分析的表達(dá)式

7、切分表達(dá)式掃描表達(dá)式中的項(xiàng)是否為運(yùn)算符優(yōu)先級是否大于操作符棧棧頂元素優(yōu)先級YY當(dāng)前操作符進(jìn)入操作符棧N是否小于操作符棧棧頂元素優(yōu)先級操作數(shù)棧彈出兩個(gè)元素，操作符棧彈出一個(gè)元素，進(jìn)行運(yùn)算，計(jì)算結(jié)果存入操作數(shù)棧Y 符號棧彈出棧頂元素N壓入操作數(shù)棧是否為#N入口出口N3.3 程序流程圖3.4 分析與編碼實(shí)現(xiàn)3.4.1表達(dá)式文法GE構(gòu)造算符優(yōu)先關(guān)系表計(jì)算算符優(yōu)先只針對于終結(jié)符，終結(jié)符之間的優(yōu)先關(guān)系有三種，在計(jì)算優(yōu)先關(guān)系之前我們先定義兩個(gè)集合，對于任意兩個(gè)終結(jié)符（a,b）FIRSTVT（B）=b|B=>b或B=>Cb,其中表示V中的符號串。LASTVT（B）=a|B=>a或B=>

8、aC三種優(yōu)先關(guān)系： （1）等于關(guān)系:可直接查看產(chǎn)生式的右部,對如下形式的產(chǎn)生式A->ab A-> aBb則有a=b成立。 （2）小于關(guān)系：求出每個(gè)非終結(jié)符B的FIRSTVT（B），觀察如下形式的產(chǎn)生式A->aB對每一bFIRSTVT(B)有ab成立 （3）大于關(guān)系：計(jì)算每個(gè)非終結(jié)符B的LASTVT（B），觀察如下形式的產(chǎn)生式A->Bb對每一aLASTVT(B)有ab成立關(guān)系表：通常用矩陣的形式存放文法中各種可能的優(yōu)先關(guān)系。大小：矩陣是n×n的，其中n是文法中終結(jié)符的個(gè)數(shù)。表達(dá)式文法G E：E # E #E E + Q | QQ Q - T | TT T * F

9、 | FF F/ MMM M PPP ( E )i根據(jù)上面的規(guī)則手工構(gòu)造上述文法的算符優(yōu)先表如下：+-*/（）i#+-*/（=）i#=代碼清單package com.op.core;public class PriorityTable private static char table = / + * / i ( ) # '>', '<', '<', '<', '<', '>', '>', '<' , / + '

10、>', '>', '>', '<', '<', '>', '>', '<' , / * '>', '>', '>', '<', '<', '>', '>', '<' , / / '>', '>', '&g

11、t;', '$', '$', '>', '>', '>' , / i '<', '<', '<', '<', '<', '=', '$', '<' , / ( '>', '>', '>', '$', '$', '>&#

12、39;, '>', '>' , / ) '<', '<', '<', '<', '<', '$', '=', '<' , / # '>', '>', '>', '<', '<', '>', '>', '<' , /

13、; / 算符優(yōu)先表/* * 判斷一個(gè)符號在算符優(yōu)先表中位置 * * param c * return */private static int judgePriority(char c) int priority = 0;switch (c) case '+':priority = 0;break;case '*':priority = 1;break;case '/':priority = 2;break;case 'i':priority = 3;break;case '(':priority = 4;brea

14、k;case ')':priority = 5;break;case '#':priority = 6;break;case '':priority = 7;break;return priority;/* * 判斷兩個(gè)算術(shù)符的優(yōu)先級 * * param m * 為符號棧的棧頂元素 * param n * 為當(dāng)前輸入算術(shù)符 * return */public static char getPriority(char m, char n) return PriorityTable.tablejudgePriority(m)judgePriority

15、(n);3.4.2 根據(jù)算符優(yōu)先表用棧結(jié)構(gòu)來實(shí)現(xiàn)算符優(yōu)先分析設(shè)置兩個(gè)棧：存放運(yùn)算符的OPTR棧和存放操作數(shù)或運(yùn)算結(jié)果的OPND棧。具體算法描述如下：（1）首先置操作數(shù)OPND棧為空棧，將#入運(yùn)算符OPTR棧。（2）依次讀入表達(dá)式中每個(gè)單詞，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則轉(zhuǎn)（3）。（3）當(dāng)前設(shè)讀入的運(yùn)算符為2，查找算符優(yōu)先關(guān)系表，比較2與OPTR棧頂元素1 ：若1<2,則2進(jìn)OPTR棧，轉(zhuǎn)（2）； 若12, 如2為#，則分析成功，否則OPTR棧頂元素1出棧，并轉(zhuǎn)（2）；若12，則出棧OPND棧頂元素存放到b，又出棧其新棧頂元素存放到a，再出棧OPTR棧頂元素至t，進(jìn)行運(yùn)算r=a t

16、 b (t為運(yùn)算符)，并將結(jié)果r存入棧OPND后轉(zhuǎn)（2）；（4） 若1和2之間無優(yōu)先關(guān)系，則報(bào)錯。YNYNYNYNYNYNNYYN置初值K：=1，SK：=#當(dāng)前輸入符讀入aSK VTJ:=kJ:=k-1Sj>aSK <a?Q:= SjJ:=j-1Sj-1 VTJ:=j-2Sj<QSj = a ?Sj =#檢查是否正常結(jié)束K:=k+1Sk = a出錯出錯結(jié)束Sj+1SK歸約為NK:=j+1 SK:=N分析歸約流程圖在分析過程中，利用分析棧存放已識別的那部分句型，而句型的其余部分由剩余輸入串組成，通過比較棧頂符號和下一個(gè)輸入符號之間的關(guān)系，如果是小于或等于則將輸入串一次逐個(gè)存入符

17、號棧中，直到遇到棧頂符號的優(yōu)先關(guān)系大于下一個(gè)待輸入符號為止，此時(shí)可以判別棧頂符號是否為句柄尾符號。如果是句柄尾，則沿棧頂向下，在棧內(nèi)尋找句柄頭（利用文法的某條規(guī)則），然后把它們彈出棧，并代之以歸約后的非終結(jié)符。這樣就完成了一次歸約過程。代碼清單package com.op.core;import java.math.BigDecimal;import java.util.Stack;import com.op.util.StringUtil;import com.op.util.IOUtil;public class OperatorPriority private Stack<Char

18、acter> optrStack; /符號棧private Stack<Float> opndStack; /操作數(shù)棧private String input; /待分析的算術(shù)表達(dá)式/* * 構(gòu)造函數(shù) * param input */public OperatorPriority(String input) super();optrStack = new Stack<Character>();opndStack = new Stack<Float>();optrStack.push('#');this.input = input;/*

19、* 操作兩個(gè)數(shù) * param a 操作數(shù)1 * param b 操作數(shù)2 * param op 操作符 * return 運(yùn)算結(jié)果 */public float operateTwoNum(float a, float b, char op) BigDecimal da = new BigDecimal(Float.toString(a); BigDecimal db = new BigDecimal(Float.toString(b); switch (op) case '*':return da.multiply(db).floatValue();case '+&

20、#39;:return da.add(db).floatValue();case '-':return db.subtract(da).floatValue();case '/':return db.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue(); /除不盡的情況取7位精確值。case '':return db.pow(int)a).floatValue();return 0;/* * 判斷是否為操作符 * param ch 被判斷字符 * return 布爾值 */public boolea

21、n isOperator(char ch) if (ch = '+' | ch = '-' | ch = '*' | ch = '/' | ch = '('| ch = ')' | ch = '#'|ch='')return true;elsereturn false;/* * 掃描字符串，判斷是否對應(yīng)文法，并計(jì)算出結(jié)果 * return 計(jì)算結(jié)果 * throws Exception 如果不符合文法，或者除數(shù)等于0，都將拋出異常 */public String sc

22、anner() throws Exception int postion = 0; / 字符串上指示的指針char operator = 0; / 操作符float a = 0, b = 0; / 操作數(shù)String exp = StringUtil.splitExp(input);while (true) / 判斷是否為運(yùn)算符if (exppostion.length()=1&&isOperator(exppostion.charAt(0) / 需要進(jìn)行運(yùn)算符的比較if (!optrStack.isEmpty() if (PriorityTable.getPriority(o

23、ptrStack.peek().charValue(),exppostion.charAt(0) = '<')optrStack.push(exppostion.charAt(0);else if (PriorityTable.getPriority(optrStack.peek().charValue(), exppostion.charAt(0) = '>') a = opndStack.pop();b = opndStack.pop();operator = optrStack.pop().charValue();opndStack.push(

24、operateTwoNum(a, b, operator);continue; else if (PriorityTable.getPriority(optrStack.peek().charValue(), exppostion.charAt(0) = '=') optrStack.pop();if (exppostion.charAt(0) = '#') return opndStack.pop().toString(); elseoptrStack.push( exppostion.charAt(0);/ 為運(yùn)算數(shù)時(shí)else opndStack.push(

25、Float.valueOf(exppostion).floatValue();postion+;if (postion >= exp.length)break;throw new Exception();/* * 程序入口，啟動函數(shù) * param args */public static void main(String args) OperatorPriority op = new OperatorPriority(IOUtil.getStringFromKeyBoard(); /實(shí)例化 構(gòu)造函數(shù)參數(shù)從鍵盤獲得try System.out.println("您輸入的表達(dá)式:

26、" + op.input + "=" + op.scanner(); catch (Exception e) / TODO Auto-generated catch block/e.printStackTrace();System.out.println("您輸入的表達(dá)式" + op.input + "有誤!");3.4.3 輔助工具類設(shè)計(jì)a. 通過鍵盤輸入表達(dá)式。程序清單package com.op.util;import java.io.BufferedReader;import java.io.IOException;

27、import java.io.InputStreamReader;public class IOUtil /* * 得到從鍵盤輸入的字符串 * return 字符串 */ public static String getStringFromKeyBoard() try BufferedReader reader=new BufferedReader(new InputStreamReader(System.in); System.out.print("請輸入一個(gè)表達(dá)式以#號結(jié)束："); String str=reader.readLine(); /獲取字符串 / Syste

28、m.out.println("您輸入的字符串是："+str); return str; catch (IOException e) e.printStackTrace(); return null; b. 字符串處理類將從鍵盤輸入的字符串表達(dá)式進(jìn)行簡單的切分，存入字符串?dāng)?shù)組。這個(gè)類是為了在掃描表達(dá)式時(shí)能對其中的操作數(shù)與操作符進(jìn)行方便的操作。程序清單package com.op.util;import java.util.Vector;public class StringUtil /* * 切分算術(shù)表達(dá)式，結(jié)果存入字符串?dāng)?shù)組，如： 字符串：1.5+3*2# 將被切分為 1.

29、5,+,3,*,2,# * param str * return */public static String splitExp(String str) Vector<String> v = new Vector<String>();int beginIndex = 0;for (int i = 0; i < str.trim().length(); i+) if (str.charAt(i) > 32 && str.charAt(i) < 48&&str.charAt(i)!=46)|str.charAt(i)=94)

30、 if(beginIndex!=i)v.add( str.substring(beginIndex, i);v.add( String.valueOf(str.charAt(i);beginIndex = i + 1;if(beginIndex!=str.length()v.add(str.substring(beginIndex, str.length();String result=new Stringv.size();for(int i=0;i<v.size();i+)resulti=v.get(i);return result;第4章 測試用例及程序截圖本次設(shè)計(jì)經(jīng)過三次測試形成最

31、終版本4.1第一版測試1、如果正確輸入表達(dá)式應(yīng)能正確得出結(jié)果當(dāng)輸入10+15*4#后，預(yù)計(jì)結(jié)果為70，實(shí)際結(jié)果為：70.0之所以會出現(xiàn)70.0是因?yàn)檩敵鼋Y(jié)果的精度不一樣。提示“請按任意鍵繼續(xù)”，當(dāng)按下任意鍵時(shí)，退出了程序。程序應(yīng)該跳到開始處，提醒用戶再次輸入表達(dá)式并以#號結(jié)束。2、如果輸入一個(gè)錯誤的表達(dá)式應(yīng)能給出錯誤信息從圖中所輸入的表達(dá)式跟文法進(jìn)行分析可以得出10不是文法的句子，故輸出的結(jié)果為：您輸入的表達(dá)式10+*15+有誤！3、對負(fù)號的處理經(jīng)過對文法的分析并沒有對負(fù)數(shù)的處理，在這里他會認(rèn)為是減號，而在減號的左邊缺少一個(gè)元素，故輸出的結(jié)果為：您輸入的表達(dá)式（-10）*2有誤！4、對于單個(gè)的

32、整數(shù)5、測試除法優(yōu)先操作測試結(jié)果與預(yù)計(jì)的結(jié)果不符合，經(jīng)過分析得出，之所以上圖的結(jié)果會是11是因?yàn)樗乃惴ú襟E為：（1）、2*4=8 （2）、（6/2）=3 （3）、3/2=1 （4）、8+3*1=11 在這里出現(xiàn)了兩個(gè)錯誤：第一個(gè)錯誤在計(jì)算整數(shù)除的時(shí)候3/2=1出現(xiàn)錯誤；第二個(gè)錯誤為在計(jì)算（6/2）*3/2的問題上出現(xiàn)處理錯誤，他這里計(jì)算除法優(yōu)先于乘法運(yùn)算了，在乘法與除法之間的優(yōu)先為誰先出現(xiàn)就先計(jì)算誰。正確的算法為：（1）、2*4=8 （2）、（6/2）=3 （3）、3*3=9 （4）、9/2=4.5 （5）、8+4.5=12.56、乘方的測試測試結(jié)果與預(yù)計(jì)的結(jié)果不符合，經(jīng)過對文法的分析得出此

33、語句為方法的句子，這時(shí)可以確定為在編寫程序代碼時(shí)沒有完成此功能。7、對于不是方法句子的表達(dá)式情況下8、在輸入時(shí)不加“#”測試報(bào)告測試人姓名：測試組測試時(shí)間：2010/6/20錯誤個(gè)數(shù)：0序號路徑輸入預(yù)計(jì)輸出實(shí)際結(jié)果1.如果正確輸入表達(dá)式應(yīng)能正確得出結(jié)果10+15*4#7070.02.如果輸入一個(gè)錯誤的表達(dá)式應(yīng)能給出錯誤信息10+*15+#給出錯誤提示您輸入的表達(dá)式10+*15+有誤！3對負(fù)號的處理（-10）*（-5）#給出錯誤提示您輸入的表達(dá)式（-10）*（-5）有誤!4對于單個(gè)的整數(shù)10#1010.05測試除法優(yōu)先操作2*4+（6/2）*3/2#12.5116對乘方的測試27#128您輸入的

34、表達(dá)式27有誤!7多“（“括號的情況下（9-6）*3#給出錯誤提示您輸入的表達(dá)式（9-6）*3有誤!8輸入時(shí)沒有輸入“#“號3+4+5錯誤提示您輸入的表達(dá)式3+4+5有誤!本次測試中發(fā)現(xiàn)設(shè)計(jì)中并未涉及到乘方運(yùn)算，且除法運(yùn)算的并非是自左向右而是自右向左的，且除法運(yùn)算優(yōu)先級大于乘法運(yùn)算，需作修改維護(hù)4.2第二版測試根據(jù)第一版中的問題進(jìn)行測試測試報(bào)告測試人姓名：測試組測試時(shí)間：2010/6/28錯誤個(gè)數(shù)：6序號任務(wù)輸入預(yù)計(jì)輸出實(shí)際結(jié)果1.對于單個(gè)的浮點(diǎn)數(shù)10#101.02.浮點(diǎn)運(yùn)算 1+2*3/6213測試除法優(yōu)先操作2*4+（6/2）*3/2#12.512.54對乘方的測試27#128您輸入的表達(dá)式27有誤!1、對于版本1中沒有解決的問題己經(jīng)解決了，主要是對浮點(diǎn)數(shù)的處理。2針對于符點(diǎn)操作與浮點(diǎn)優(yōu)先測試3、針對乘除法優(yōu)先操作的測試4、針對乘方問題的測試，依舊沒有解決需要進(jìn)一步改進(jìn)程序1110987654321輸入待分析的表達(dá)式切分表達(dá)式掃描表達(dá)式中的項(xiàng)是否為運(yùn)算符優(yōu)先級是否大于操作符