1、編譯原理實(shí)驗(yàn)指導(dǎo)書指導(dǎo)老師:職稱：目錄編譯原理課程實(shí)驗(yàn)指導(dǎo)i 實(shí)驗(yàn)一源程序預(yù)處理2 實(shí)驗(yàn)二簡單程序設(shè)計語言的詞法分析器6 實(shí)驗(yàn)三遞歸下降分析法9 實(shí)驗(yàn)四預(yù)測分析法9 實(shí)驗(yàn)五lr語法分析13編譯原理課程實(shí)驗(yàn)指導(dǎo)一、課程實(shí)驗(yàn)方案1實(shí)驗(yàn)教學(xué)目標(biāo)與基本要求(1) 通過實(shí)習(xí)具有開發(fā)基本的詞法分析和語法分析算法的能力。(2) 了解詞法分析和語法分析的t作原理和特點(diǎn)(3) 掌握課本所介紹的編譯算法的原理和實(shí)現(xiàn)2實(shí)驗(yàn)環(huán)境介紹實(shí)驗(yàn)主要以程序設(shè)計實(shí)現(xiàn)各種教學(xué)課堂中講過的圖形算法為主。程序設(shè)計設(shè)計語言主要以visual c+語言為實(shí)驗(yàn)平臺。3課程實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)一源程序預(yù)處理實(shí)驗(yàn)學(xué)時：2學(xué)時實(shí)驗(yàn)?zāi)康模菏煜ぴ闯绦蝾A(yù)處理的

2、任務(wù)和要求。實(shí)現(xiàn)源程序輸入串中注釋、續(xù)行符的刪除，換行符和tab的替 換，大小寫字母變換，得到預(yù)處理后的文本串，為單詞識別做好準(zhǔn) 備。實(shí)驗(yàn)內(nèi)容：1. 刪除注釋2. 刪除續(xù)行符以及后續(xù)換行符3. 將換行符和tab統(tǒng)一替換為空格4. 將大寫字母變換為小寫字母，或者相反，以實(shí)現(xiàn)不區(qū)分大小 寫5. 識別標(biāo)號區(qū)，識別續(xù)行標(biāo)志。實(shí)驗(yàn)步驟：（1）熟悉教材關(guān)于詞法分析中預(yù)處理的原理。（2）依照教材關(guān)于源程序預(yù)處理的算法，使用c/c+語言或其它語 言實(shí)現(xiàn)該算法。（3）調(diào)試、編譯、運(yùn)行程序。實(shí)驗(yàn)要求：在下次實(shí)驗(yàn)時提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報告（實(shí)驗(yàn)報告包括實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會）。實(shí)

3、現(xiàn)代碼：# include<fstream.h>#include<iostream.h># include<conio.h>void pro_process(char *);void main()定義掃描緩沖區(qū)char bufi4048=0'緩沖區(qū)清 0調(diào)用預(yù)處理程序pro_process(buf)；在屏幕上顯示掃描緩沖區(qū)的內(nèi)容cout«buf«endl;void pro_process(char *buf)int i=0;ifstream cinf(nsource.txtn,ios:in);計數(shù)器char old_c=0cur_

4、c;前一個字符，當(dāng)前字符bool in_comment=false;/false表示當(dāng)前字符未處于注釋中從文件讀一個字符while(cinfread (&cur_c,sizeof(char)switch(in_comment) case false:if(old_c=7, && cur_c=,*) 進(jìn)入注釋 i-； 去除已存入掃描緩沖區(qū)的字符' in_comment=true;else if(old_c=! && cur_c=nf) /發(fā)現(xiàn)續(xù)行 i-； /去除已存入掃描緩沖區(qū)的字符' else if(cut_c>-a，&&a

5、mp; cujcv二z) /大寫變小寫 cur_c+=32;if(cur_c=t, ii cur_c=n!) 空格取代 tab 換行 cur_c+=*bufi+=cur_c;break;case true:if(old_c='*1 && cur_c=7*) 離開注釋 in_comment=false;/end of switchold_c=cur_c;保留前一個字符/end of whilebufi+=,#1;在源程序詞尾加字符#實(shí)驗(yàn)二簡單程序設(shè)計語言的詞法分析器實(shí)驗(yàn)學(xué)時：2學(xué)時實(shí)驗(yàn)?zāi)康模赫莆赵~法分析器的原理將源程序預(yù)處理、狀態(tài)圖轉(zhuǎn)換等結(jié)合，建立簡單的程序設(shè)計語言 詞法

6、分析器實(shí)驗(yàn)內(nèi)容：要求能對簡單程序設(shè)計語言進(jìn)行詞法分析，具體內(nèi)容如下：字符集若發(fā)現(xiàn)字符集之外的字符，即為非法字符，當(dāng)出現(xiàn)非法字符時終 止詞法分析器的運(yùn)行。單詞集基本字：begin > end> integer> real標(biāo)識符：以字母開始的數(shù)字字母串無符號整常數(shù)無符號實(shí)常數(shù)運(yùn)算符：+、*、+、=界符：八；、（、）、#錯誤詞形：.（前后無數(shù)字字符的小數(shù)點(diǎn)）單詞編碼基本字：begin（6 “nulj、end（9 “nul"、integer（4a “nul"、 real（6c “nul"標(biāo)識符：（t,字符串）無符號整常數(shù)：（丈，字符串）無符號實(shí)常數(shù)：（v

7、，字符串）運(yùn)算符;=（6= “nulj、+（'+', “nul"）、*（詠,“nulj、+（$, “nulj界符：,（；nul） ;（：nulj、（,c,nulj、），nul'）、#（#, “nul"）狀態(tài)轉(zhuǎn)換圖單詞分為單字符單詞或多字符單詞。實(shí)驗(yàn)步驟：（1）熟悉習(xí)教材關(guān)于詞法分析的原理。（2）依照教材關(guān)于詞法分析的算法，使用c/c+語言實(shí)現(xiàn)該算法。（3）調(diào)試、編譯、運(yùn)行程序。實(shí)驗(yàn)耍求：在下次實(shí)驗(yàn)時提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報告（實(shí)驗(yàn)報告包括實(shí)驗(yàn)?zāi)?的、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會）。實(shí)現(xiàn)代碼：詞法分析有5個函數(shù)構(gòu)成，即預(yù)處理函數(shù)pro

8、_process掃描函數(shù)scanner拼接函數(shù)concat查基本字表函數(shù)reserve和主函數(shù)main。#include <iostream.h>#include <fstream.h>#include <string.h>#include <stdlib.h>const short wordlen=20;struct code_valchar code; char valfwordlen;void pro_process(char *);void concat(char j,char);char reserve(charj);code_val

9、scanner(char *);void main()char buf4048=t0,);pro_process(buf);cout«buf«endl;ofstream coutfc'lex_r.txfios:out);code_val t;do t=scanner(buf); /調(diào)丿u次scanner函數(shù)，獲得一個單詞二元式 coutf«t.codc«,l,«t.val«cndl; while(t.code!=：'#'cout«end of lexical analysis,«endl;實(shí)

10、驗(yàn)三 遞歸下降分析法實(shí)驗(yàn)學(xué)時：2學(xué)時實(shí)驗(yàn)?zāi)康模赫莆者f歸下降語法分析的原理利用高級語言的遞歸過程為給定文法的每個非終結(jié)符構(gòu)造對應(yīng) 的遞歸函數(shù) 實(shí)驗(yàn)內(nèi)容：若文法不含左遞歸，并且每個非終結(jié)符的所有候選式的首符集都 兩兩不相交，就有可能構(gòu)造一個不帶回溯的自上而下的語法分析程 序。這個分析程序是由一組遞歸過程（函數(shù)）組成的，每個過程（函 數(shù)）對應(yīng)文法的一個非終結(jié)符。如果用某種高級語言寫出所有遞歸過 程（函數(shù)），那就可以用這個高級語言的編譯系統(tǒng)產(chǎn)生整個分析程序。 這個分析程序稱為遞歸下降分析器。用類c語言為文法g的每個非終結(jié)符構(gòu)造對應(yīng)的遞歸函數(shù)。 文法g如下所示：e-te，ej+te%t->ft，t

11、'f *ft'ief- （e） | i | x | y實(shí)驗(yàn)步驟：(1) 熟悉習(xí)教材關(guān)于語法分析的原理。(2) 依照教材關(guān)于基于遞歸下降分析的算法，使用c/c+語言實(shí)現(xiàn) 該算法。(3) 調(diào)試、編譯、運(yùn)行程序。實(shí)驗(yàn)要求：在下次實(shí)驗(yàn)時提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報告(實(shí)驗(yàn)報告包括實(shí)驗(yàn)?zāi)?的、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會)。實(shí)現(xiàn)代碼:假設(shè)源程序?yàn)椤?a+b)*c”,經(jīng)詞法分析，單詞二元式序列存放于 文件 lex_r.txt 中。遞歸下降分析器從文件lex_r.txt讀入數(shù)據(jù)進(jìn)行處理。每次讀入的 是單詞二元式，即單詞的種別(code)和單詞的值(val),而分析器僅使 用單詞

12、的種別。struct code_valchar code; char val20;t；ifstream cinf(44lex_r.txfios:in);void e()t;e,void e'()if(t.code=二'+') cinf»t.code»t.val;t;e，;void t()ft;void t'()if(t.code= ='*') ci nf»t .code» t. val;f;t'void f()if(t.code=,(<) cinf>>t.code»t.v

13、al;e;if(t.code= =')') cinf»t.code»t.val;else if(t.code=二'iti t.code=二'xti t.code= ='y") ci nf»t.code»t.val;void main()ci nf»t. code»t.val;e;實(shí)驗(yàn)四預(yù)測分析析法實(shí)驗(yàn)學(xué)時：4學(xué)時實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)為綜合性實(shí)驗(yàn)，綜合了棧、表等內(nèi)容，其目的是在掌握棧、 表以及預(yù)測分析法原理的基礎(chǔ)上，實(shí)現(xiàn)預(yù)測分析表的建立和控制程 序。實(shí)驗(yàn)內(nèi)容：用類c語言為文法g進(jìn)行語法分析。

14、文法g如下所示：ete，e'f+te%tft't'f *ft'lwff (e) | i | x | y預(yù)測分析法是一種不使用遞歸的語法分析方法，由一張分析表和 一個控制程序構(gòu)成的。一、預(yù)測分析表的構(gòu)造產(chǎn)生式的一般形式為：a->aila2l i anle若當(dāng)前輸入符號t.codeefirst(aj),則用af®推導(dǎo)；若當(dāng)前輸入符號 t.codeefollow(a),貝用aw推導(dǎo)；除此以外均為錯誤。候選式的選 取是由兩個耍素決定的：一個是句型中的非終結(jié)符a,從它出發(fā)進(jìn)行 最左推導(dǎo)；另一個是當(dāng)前輸入符號t.code?？梢园焉鲜龇墙K結(jié)符a的 產(chǎn)生式映射成

15、矩陣m的一行，矩陣m以文法的非終結(jié)符為縱處標(biāo)(行)，以文法的終結(jié)符為橫坐標(biāo)(列)。矩陣元素max存放著一 條關(guān)于a的產(chǎn)生式，指出當(dāng)a面臨輸入符號x所應(yīng)采用的候選。若 aefirst(ai),則 maa=如；若 befollow(a),則 mab=mac中也可能存放一個“出錯標(biāo)志”，指出a根本不該 血臨輸入符號c,在矩陣m中“出錯標(biāo)志”用空白表示。預(yù)測分析表m的構(gòu)造方法：%1 構(gòu)造所有候選式的first集，構(gòu)造所有的非終結(jié)符的follow集；%1 對于文法g的每個產(chǎn)生式a-a,執(zhí)行和；%1 對于每個終結(jié)符ae first(a),把a(bǔ)a加至maa；%1 若sfirst(a),則對于每個終結(jié)符bwf

16、ollow(a),把a(bǔ)_a加至mab；%1 把所有未定義的mac標(biāo)上“出錯標(biāo)志”。二、預(yù)測分析控制程序設(shè)置一個棧stack,用于存放文法符號。初始時，棧底先放一個然后放進(jìn)文法開始符號s。預(yù)測分析控制程序任何時刻的動作，都按照棧頂符號x和當(dāng)前輸入符號t.code進(jìn)行，控制程序每次執(zhí)行下述3種可能的動作之一：%1 若x和t.code均為則分析成功，輸入串為合法句子，終止分析過程。%1 若x是終結(jié)符，并ilx和t.code相等，表示期望的終結(jié)符號和輸 入符號相等。讓x出stack棧，并輸入下一個單詞二元式。%1 若x是非終結(jié)符，則查預(yù)測分析表。若mxt.code存放著關(guān)于x 的一個產(chǎn)生式，那么，讓x

17、出stack棧，然后把產(chǎn)生式右部符號串 按反序一一推進(jìn)stack棧。若右部符號串為空字£,則意味著無任 何文法符號進(jìn)棧。實(shí)驗(yàn)步驟：(1) 熟悉習(xí)教材關(guān)于預(yù)測分析法的原理。(2) 依照教材關(guān)于基于預(yù)測分析的語法分析算法，使用c/c+語言 實(shí)現(xiàn)該算法。(3) 調(diào)試、編譯、運(yùn)行程序。實(shí)驗(yàn)要求：在下次實(shí)驗(yàn)時提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報告(實(shí)驗(yàn)報告包括實(shí)驗(yàn)?zāi)?的、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會)。實(shí)現(xiàn)代碼：void ll1()struct codc_val char code; char var20j;t;ifstream cinfc'lex_匚txfios:in);cha

18、r slack20='#','s' char x; int top= 1; ci nf»t> code> >t. val;while(l) do x=stacktop; switch(x) of case #:if(x=t.code) cout»acc; break;case x wvt：if(x= =t.code) coul»t codc»l .val; case x wvn： if(mxt.code=x->x1x2-xk) x】x2xk按反序進(jìn)棧； top=top+k;實(shí)驗(yàn)五lr語法分析實(shí)驗(yàn)學(xué)時：2學(xué)時實(shí)驗(yàn)?zāi)康模赫莆誰r語法分析的基本原理基本原理：把每個句柄的識別(產(chǎn)生式右部的符號串)過程劃分 為若干狀態(tài)，每個狀態(tài)只識別句柄的一個符號，若十個狀態(tài)就叫識別 句柄左端的-部分符號。利用高級語言實(shí)現(xiàn)lr語法分析器實(shí)驗(yàn)內(nèi)容：文法：(0) s->e(1) e-e+t(2) e-t(3) tt*f(4) tf(5) f-(e)(6) f i假設(shè)分析表用二維數(shù)組m存儲，棧頂狀態(tài)用stop表示，當(dāng)前輸入符 號用t. code表示，控制程序的算法可歸納如下：(1) 移進(jìn)。若mslopt. code=sj,說明句柄尚未完成，應(yīng)執(zhí)行移進(jìn)