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

1、編譯原理實驗指導(dǎo)書淘寶店530213目錄編譯原理課程實驗指導(dǎo)1實驗一 源程序預(yù)處理2實驗二 簡單程序設(shè)計語言的詞法分析器6實驗三 遞歸下降分析法9實驗四 預(yù)測分析法13實驗五 LR語法分析17記住淘寶店5302131編譯原理課程實驗指導(dǎo)一、課程實驗方案1 實驗教學目標與基本要求（1）通過實習具有開發(fā)基本的詞法分析和語法分析算法的能力。（2）了解詞法分析和語法分析的工作原理和特點（3）掌握課本所介紹的編譯算法的原理和實現(xiàn)2 實驗環(huán)境介紹實驗主要以程序設(shè)計實現(xiàn)各種教學課堂中講過的圖形算法為主。程序設(shè)計設(shè)計語言主要以Visual C+語言為實驗平臺。3 課程實驗內(nèi)容實驗一 源程序預(yù)處理實驗學時：2學

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

3、驗結(jié)果、實驗體會）。實現(xiàn)代碼：#include<fstream.h>#include<iostream.h># include<conio.h>void pro_process(char *);void main( )/定義掃描緩沖區(qū)char buf4048='0' /緩沖區(qū)清0/調(diào)用預(yù)處理程序pro_process(buf);/在屏幕上顯示掃描緩沖區(qū)的內(nèi)容cout<<buf<<endl;void pro_process(char *buf) ifstream cinf("source.txt",i

4、os:in); int i=0; /計數(shù)器 char old_c='0',cur_c; /前一個字符，當前字符 bool in_comment=false; /false表示當前字符未處于注釋中 while(cinf.read(&cur_c,sizeof(char) /從文件讀一個字符 switch(in_comment) case false: if(old_c='/' && cur_c='*') /進入注釋 i-; /去除已存入掃描緩沖區(qū)的字符/ in_comment=true; else if(old_c='

5、' && cur_c='n') /發(fā)現(xiàn)續(xù)行 i-; /去除已存入掃描緩沖區(qū)的字符 else if(cur_c>='A' && cur_c<='Z') /大寫變小寫 cur_c+=32; if(cur_c='t' | cur_c='n') /空格取代tab換行 cur_c=' ' bufi+=cur_c; break; case true: if(old_c='*' && cur_c='/') /離開注

6、釋 in_comment=false; /end of switch old_c=cur_c; /保留前一個字符 /end of while bufi+='#' /在源程序詞尾加字符#實驗二 簡單程序設(shè)計語言的詞法分析器實驗學時：2學時實驗?zāi)康模赫莆赵~法分析器的原理將源程序預(yù)處理、狀態(tài)圖轉(zhuǎn)換等結(jié)合，建立簡單的程序設(shè)計語言詞法分析器實驗內(nèi)容： 要求能對簡單程序設(shè)計語言進行詞法分析，具體內(nèi)容如下：字符集 a.z, 0.9,+,=,*,;,(,),#若發(fā)現(xiàn)字符集之外的字符，即為非法字符，當出現(xiàn)非法字符時終止詞法分析器的運行。單詞集基本字：begin、end、integer、real標

7、識符：以字母開始的數(shù)字字母串無符號整常數(shù)無符號實常數(shù)運算符：+、*、+、=界符：,、;、(、)、#錯誤詞形：. （前后無數(shù)字字符的小數(shù)點） 單詞編碼基本字：begin(, “NUL”、end(), “NUL”、integer(a, “NUL”、real(c, “NUL”標識符：(i, 字符串)無符號整常數(shù)：(x, 字符串)無符號實常數(shù)：(y, 字符串)運算符；=(=, “NUL”)、+(+, “NUL”)、*(*, “NUL”)、+($, “NUL”)界符：,(, “NUL”)、;(;, “NUL”)、(,C, “NUL”) 、), NUL)、#(#, “NUL”)狀態(tài)轉(zhuǎn)換圖單詞分為單字符單詞

8、或多字符單詞。實驗步驟：（1）熟悉習教材關(guān)于詞法分析的原理。（2）依照教材關(guān)于詞法分析的算法，使用C/C+語言實現(xiàn)該算法。（3）調(diào)試、編譯、運行程序。實驗要求：在下次實驗時提交本次實驗的實驗報告（實驗報告包括實驗?zāi)康?、實驗?nèi)容、實驗實現(xiàn)過程、源程序、實驗結(jié)果、實驗體會）。實現(xiàn)代碼：詞法分析有5個函數(shù)構(gòu)成，即預(yù)處理函數(shù)pro_process、掃描函數(shù)scanner、拼接函數(shù)concat、查基本字表函數(shù)reserve和主函數(shù)main。#include <iostream.h>#include <fstream.h>#include <string.h>#incl

9、ude <stdlib.h>const short WORDLEN=20;struct code_valchar code; char valWORDLEN;void pro_process(char *);void concat(char ,char);char reserve(char);code_val scanner(char *);void main() char buf4048=0; pro_process(buf); cout<<buf<<endl; ofstream coutf(“Lex_r.txt”,ios:out); code_val t

10、; do t=scanner(buf); /調(diào)用一次scanner函數(shù)，獲得一個單詞二元式 coutf<<t.code<<t<<t.val<<endl; while(t.code!=#cout<<”end of lexical analysis”<<endl;實驗三 遞歸下降分析法實驗學時：2學時實驗?zāi)康模赫莆者f歸下降語法分析的原理利用高級語言的遞歸過程為給定文法的每個非終結(jié)符構(gòu)造對應(yīng)的遞歸函數(shù)實驗內(nèi)容：若文法不含左遞歸，并且每個非終結(jié)符的所有候選式的首符集都兩兩不相交，就有可能構(gòu)造一個不帶回溯的自上而下的語法分析程序。這

11、個分析程序是由一組遞歸過程（函數(shù)）組成的，每個過程（函數(shù)）對應(yīng)文法的一個非終結(jié)符。如果用某種高級語言寫出所有遞歸過程（函數(shù)），那就可以用這個高級語言的編譯系統(tǒng)產(chǎn)生整個分析程序。這個分析程序稱為遞歸下降分析器。 用類C語言為文法G的每個非終結(jié)符構(gòu)造對應(yīng)的遞歸函數(shù)。文法G如下所示：ETEE+TE|TFTT*FT|F(E)|i|x|y實驗步驟：（1）熟悉習教材關(guān)于語法分析的原理。（2）依照教材關(guān)于基于遞歸下降分析的算法，使用C/C+語言實現(xiàn)該算法。（3）調(diào)試、編譯、運行程序。實驗要求：在下次實驗時提交本次實驗的實驗報告（實驗報告包括實驗?zāi)康?、實驗?nèi)容、實驗實現(xiàn)過程、源程序、實驗結(jié)果、實驗體會）。實現(xiàn)

12、代碼：假設(shè)源程序為“(a+b)*c”，經(jīng)詞法分析，單詞二元式序列存放于文件lex_r.txt中。遞歸下降分析器從文件lex_r.txt讀入數(shù)據(jù)進行處理。每次讀入的是單詞二元式，即單詞的種別(code)和單詞的值(val)，而分析器僅使用單詞的種別。struct code_val char code; char val20; t;ifstream cinf(“l(fā)ex_r.txt”,ios:in);void E() T;E;void E() if(t.code= =+) cinf>>t.code>>t.val; T;E; void T() F;T;void T() if(t

13、.code= =*) cinf>>t.code>>t.val; F;T; void F() if(t.code= =() cinf>>t.code>>t.val; E; If(t.code= =) cinf>>t.code>>t.val; else if(t.code= =i | t.code= =x | t.code= =y) cinf>>t.code>>t.val;void main() cinf>>t.code>>t.val; E;實驗四 預(yù)測分析析法實驗學時：4學時實

14、驗?zāi)康模罕緦嶒灋榫C合性實驗，綜合了棧、表等內(nèi)容，其目的是在掌握棧、表以及預(yù)測分析法原理的基礎(chǔ)上，實現(xiàn)預(yù)測分析表的建立和控制程序。實驗內(nèi)容： 用類C語言為文法G進行語法分析。文法G如下所示：ETEE+TE|TFTT*FT|F(E)|i|x|y預(yù)測分析法是一種不使用遞歸的語法分析方法，由一張分析表和一個控制程序構(gòu)成的。一、預(yù)測分析表的構(gòu)造產(chǎn)生式的一般形式為：A1|2|n|若當前輸入符號t.codefirst(i)，則用Ai推導(dǎo)；若當前輸入符號t.codefollow(A)，則用A推導(dǎo)；除此以外均為錯誤。候選式的選取是由兩個要素決定的：一個是句型中的非終結(jié)符A，從它出發(fā)進行最左推導(dǎo)；另一個是當前輸入

15、符號t.code?？梢园焉鲜龇墙K結(jié)符A的產(chǎn)生式映射成矩陣M的一行，矩陣M以文法的非終結(jié)符為縱坐標（行），以文法的終結(jié)符為橫坐標（列）。矩陣元素MAx存放著一條關(guān)于A的產(chǎn)生式，指出當A面臨輸入符號x所應(yīng)采用的候選。若afirst(i)，則MAa=“Ai”；若bfollow(A)，則MAb=“A”。MAc中也可能存放一個“出錯標志”，指出A根本不該面臨輸入符號c，在矩陣M中“出錯標志”用空白表示。預(yù)測分析表M的構(gòu)造方法： 構(gòu)造所有候選式的first集，構(gòu)造所有的非終結(jié)符的follow集； 對于文法G的每個產(chǎn)生式A，執(zhí)行和； 對于每個終結(jié)符afirst()，把A加至MAa； 若first()，則對于

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

17、tack棧，然后把產(chǎn)生式右部符號串按反序一一推進stack棧。若右部符號串為空字，則意味著無任何文法符號進棧。實驗步驟：（1）熟悉習教材關(guān)于預(yù)測分析法的原理。（2）依照教材關(guān)于基于預(yù)測分析的語法分析算法，使用C/C+語言實現(xiàn)該算法。（3）調(diào)試、編譯、運行程序。實驗要求：在下次實驗時提交本次實驗的實驗報告（實驗報告包括實驗?zāi)康?、實驗?nèi)容、實驗實現(xiàn)過程、源程序、實驗結(jié)果、實驗體會）。實現(xiàn)代碼：void LL1() struct code_val Char code; char var20;t;ifstream cinf(“l(fā)ex_r.txt”,ios:in);char stack20=#,S; c

18、har X; int top=1;cinf>>t.code>>t.val;while(1) do x=stacktop-; switch(X) of case #: if(x=t.code) cout>>”Acc”; break; case XVT: if(X= =t.code) cout>>t.code>>t.val; case XVN: if(MXt.code=XX1X2Xk) X1X2Xk按反序進棧; top=top+k; 實驗五 LR語法分析實驗學時：2學時實驗?zāi)康模?掌握LR語法分析的基本原理基本原理：把每個句柄的識別（產(chǎn)生式右部的符號串）過程劃分為若干狀態(tài)，每個狀態(tài)只識別句柄的一個符號，若干個狀態(tài)就可識別句柄左端的一部分符號。利用高級語言實現(xiàn)LR語法分析器實驗內(nèi)容：文法：（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）F i假設(shè)分析表用二維數(shù)組M存儲，棧頂狀態(tài)用Stop表示，當前輸入符號用t.code表示，控制程序的算法可歸納如下：(1) 移進。若MStopt.c