編譯原理實驗指導(dǎo)書

1、編譯原理實驗指導(dǎo)書、八前言編譯原理是計算機專業(yè)的主干課和必修課， 由于這門課程相對 抽 象且內(nèi)容較復(fù)雜， 一直是比較難學(xué)的一門課程。 在編譯原理的學(xué) 習過 程中，實驗非常重要，只有通過上機實驗，才能使學(xué)生比照擬抽 象的 課程內(nèi)容產(chǎn)生一個具體的感性認識。本書實驗環(huán)境主要為 C 環(huán)境，在 C 環(huán)境下手動生成詞法分析器及語法分析器， 通過這些實驗，能使學(xué)生對這些部份的工作機理有一個詳細的了解。由于這門課實驗難度較大，所以希望在實驗前學(xué)生要做好預(yù)習工 作。在上機前寫好實驗預(yù)習報告。目錄實驗一 手工生成 PL/0 語言詞法分析器 1實驗二 用算符優(yōu)先分析法進行表達式分析 5實驗一 手工生成 PL/0 語

2、言詞法分析器實驗名稱：手工生成 PL/0 語言詞法分析器實驗?zāi)康模壕幹埔粋€讀單詞過程， 從輸入的源程序中， 識別出各個具有獨立意義的單詞， 即根本保 留 字、標識符、常數(shù)、運算符、 分隔符五大類。 并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。遇到錯誤時可顯示 “ Error ，然后跳過錯誤局部繼續(xù)顯示實驗原理：詞法分析過程1 、 PL/0 的詞法分析程序 Getsym 圖 1是一個獨立的過程，它把輸入的字符串形式的源程序分割成一個個單詞符號。為此 PL/0 編譯程序設(shè)置了三個全程量的公用單元如下：Sym ：存放每個單詞的類別，用內(nèi)部編碼形式表示；Id :存放用戶所定義的標識符的值，即標識符字

3、符串的機內(nèi)表示；Num ：存放用戶定義的數(shù)。如果我們把根本字、 運算符、界符稱為語言固有的單詞， 而對標識符、 常數(shù)稱為用戶定 義 的單詞，那么經(jīng)詞法分析程序分出的單詞，對固有的單詞只給出類別存放在sym 中，而 對用戶定義的單詞標識符或常數(shù)既給出類別又給值，其類別存放在sym 中，值放在 id 或 num 中，全部單詞種類由編譯程序定義的純量類型sumbol 給出，也可稱為語法的詞匯表。如下面提到的 ifsym ， thensym ， ident ， number 均屬 symbol 中的元素。因此詞法分析程序 Getsym 將完成以下任務(wù):濾空格: 空格在詞法分析時是一種不可缺少的界符，

4、而在語法分析時那么是無用的， 必須 濾 掉； 1 識別保存字:設(shè)有一張保存字表。對每個字母打頭的字母、數(shù)字串要查此表。假設(shè)查到那么為保存字，將對應(yīng)的類別放在 sym 中，如 IF 對應(yīng)值 IFSYM ， THEN 對應(yīng) 為 THENSYM 。假設(shè)查不到，那么認為是用戶定義的標識符； 2 識別標識符:對用戶定義的標識符將 IDENT 放在 SYM 中，標識符本身的值放在ID 中； 3 拼數(shù):當所取單詞是數(shù)字時，將數(shù)的類別 NUMBER 放在 SYM 中，數(shù)值本身的值 存放 在 NUM 中； 4 拼復(fù)合詞:對兩個字符組成的算符，如 >=， :=， <=等單詞，識別后將類別送 SYM中；

5、 5 輸出源程序:邊讀入字符邊輸出可輸出在文件中 。 由于一個單詞往往是由一個或 幾個字符組成的，所以在詞法分析過程Getsym 中又定義了一個取字符過程 GETCH 見圖 2，由詞法分析需要取字符時調(diào)用。；EK H的值迭K<10fK*-K+iAK i CHGETCH三 1DENT保存字?NUMSYM < * Nl'MBER!把謹字符轉(zhuǎn)檢成對應(yīng) 單惻成祈復(fù)臺單詞. 將其類SYM P引莊保陌字類2、GETCH所用單元說明：CH :存放當前讀取的字符，初值為空；LINE :為一維數(shù)組，其數(shù)組元素是字符，界對為1 : 80。用于讀入一行字符的緩沖區(qū)。LL和CC為計數(shù)器，初值為 0

6、 ;GETSYM流程圖的工作單元說明：A :一維數(shù)組，數(shù)組元素為字符，界對 1 :10 ；ID ：同 A ；WORD :保存字表，一維數(shù)組，數(shù)組元素為以字符為元素的一維數(shù)組，界對為1： 13，查找方式采用二分法。圖2取字符過程 GETCH實驗步驟：一準備：1閱讀課本有關(guān)章節(jié)，花一周時間明確語言的語法，寫出根本保存字、識符、常數(shù)、運算符標分隔符和程序例。2.初步編制好程序。3.準備好多組測試數(shù)據(jù)。二上課上機：將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試 通過。三程序要求：程序輸入/輸出例如：如源程序為 C語言。輸入如下一段：mai nint a,b;a = 10;b = a +

7、20;要求輸出如右圖。要求： 識別保存字：if、int、for、while、do、return、break、continue其他的都識別為標識符；常數(shù)為無符號整形數(shù)；運算符包括：+、-、*、/、=、V、 =、v =、!=分隔符包括：，、；、估計實驗時間：1.課余準備15小時；2.上機二次4小時；3.完成實驗報告 5小時。(2 ,ma in)(5,( “)(5,)“)(5, “)(1 , int )(2, a)(5,，)(2, b)(5,;)(2, a)以上為參考，具體可自行增刪。實驗成果：1. 程序源代碼 以報告形式提交 ；2. 已經(jīng)測試通過的測試數(shù)據(jù) 3 組全部存在一個文本文件中附在報告后面

8、，以 輸入 / 輸出 /第二組輸入 /輸出 /第三組輸入 /輸出 的順序存放 ；3. 實驗報告：1功能描述：該程序具有什么功能？2程序結(jié)構(gòu)描述：函數(shù)調(diào)用格式、參數(shù)含義、返回值描述、函數(shù)功能；函數(shù)之間的 關(guān)系圖、程序總體執(zhí)行流程圖參考課本第二章 。 3 實驗過程記錄：出錯次數(shù)、出錯嚴重程度、解決方法摘要。4實驗總結(jié)：你在編程過程中花時多少？多少時間在紙上設(shè)計？多少時間上機輸入 試？多少時間在思考問題？遇到了哪些難題？你是怎么克服的？你對你的程序的評 獲有哪些？第一組調(diào)用和調(diào)？你的收實驗二用算符優(yōu)先分析法進行表達式分析實驗名稱： 用算符優(yōu)先法進行表達式分析實驗?zāi)康?了解用算符優(yōu)先分析法進行語法分析

9、的方法。實驗要求從鍵盤輸入表達式， 利用算符優(yōu)先分析法求出其值，如輸入表達式有錯， 那么給出報錯提 示表達式以；結(jié)尾。例：以于如下的輸入表達式串：13+5*4 ;那么應(yīng)給出結(jié)果為 33。實驗原理我們要分析的表達式滿足下面的算符優(yōu)先矩陣0 201+-/()+>><<<>>->><<<>>>>>><>>/>>>><>>(<<<<<=)>>>>>><<<

10、;<<=實驗步驟 為實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧。一個叫做OPTR，用以存放運算符，一個叫OPND,用以存放操作數(shù)或結(jié)果。算法描述如下：1 首先置操作數(shù)棧為空棧，將表達式起始符；作為運算符棧的棧底元素。2 依次讀入表達式中每個單詞，假設(shè)是操作數(shù)那么進OPND棧，假設(shè)是運算符那么轉(zhuǎn)3。3 將此運算符 0 1與 OPTR棧頂元素0 2進行比較， 即查上表，假設(shè)e > 0 ,貝y： 0!進棧，轉(zhuǎn)2。假設(shè)e 1 e,如ei為；，貝扮析成功，否那么optr棧頂元素出棧，并轉(zhuǎn)。假設(shè) 01< e那么,出棧 OPND棧頂元素至 b，又出棧其棧頂元素至 a，出棧 OPTR棧頂元

11、素 至t，進行運算r=a t b (t為運算符)，并將結(jié)果r存入棧OPND后轉(zhuǎn) 。假設(shè)0!和0 2之間無優(yōu)先關(guān)系，那么報錯。源程序提示利用以前實驗生成的 Getsym ()進行單詞識別，并自組織工程文件，關(guān)于算符優(yōu)先算法要用到的部份函數(shù)提示如下。1 一些自定義的變量和函數(shù)的聲明#defi ne MAX 255SY MBOLtitle7= PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN,SEMICOLON;用來將相應(yīng)的種別碼與數(shù)組下標進行映射char oo77= '>','>','<','<

12、','<','>','>',r>''<* '>I r I 5 J J 1 J 1y y i jiI)!11P>' »>f>、叩專I】JP1 TT fl'v','v','v','v','v','!','='表!'示兩算符無優(yōu)先; /算符優(yōu)先矩陣，其中int Op關(guān)系MAX;/操作數(shù)棧 SYMBOL OPTRMAX; / 算符棧i

13、nt topd,topr;兩棧的指針 void PushOp nd (int a);int PopOp nd (void);int EmptyOp nd (void);int GetTopOp nd (void);void PushOptr (S YMBOL a);SY MBOL PopOptr (void);int EmptyOptr (void);SY MBOL GetTopOptr (void);/上面為棧函數(shù)int Positio n(SY MBOL c);/將c映射至數(shù)組下標int IsOp nd(S YMBOL c);判斷c是否是操作數(shù)int lsOptr(S YMBOL c);判斷c是否是操作符char Precede(S YMBOL c1,S YMBOL c2);查算符優(yōu)先矩陣，求出c1和c2之間的優(yōu)先矩陣int Operate(i nt a,i nt b,S YMBOL o);求出a o bchar First();/算符優(yōu)先分析函數(shù)2 部份函數(shù)實現(xiàn)的源代碼(略)實驗成果：1. 程序源代碼(以報告形式提交)；2. 已經(jīng)測試通過的測試數(shù)據(jù)3組(全部存在一個文本文件中附在報告后面，以“第一組輸入/輸出/第二組輸入/輸出/第三組