編譯原理實(shí)驗(yàn)指導(dǎo)

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

2、時(shí)實(shí)驗(yàn)?zāi)康模菏煜ぴ闯绦蝾A(yù)處理的任務(wù)和要求。實(shí)現(xiàn)源程序輸入串中注釋、續(xù)行符的刪除，換行符和Tab的替換，大小寫字母變換，得到預(yù)處理后的文本串，為單詞識(shí)別做好準(zhǔn)備。實(shí)驗(yàn)內(nèi)容：1. 刪除注釋2. 刪除續(xù)行符以及后續(xù)換行符3. 將換行符和TAB統(tǒng)一替換為空格4. 將大寫字母變換為小寫字母，或者相反，以實(shí)現(xiàn)不區(qū)分大小寫5. 識(shí)別標(biāo)號(hào)區(qū)，識(shí)別續(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í)提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告（實(shí)驗(yàn)報(bào)告包括實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)

3、驗(yàn)結(jié)果、實(shí)驗(yàn)體會(huì)）。實(shí)現(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; /計(jì)數(shù)器 char old_c='0',cur_c; /前一個(gè)字符，當(dāng)前字符 bool in_comment=false; /false表示當(dāng)前字符未處于注釋中 while(cinf.read(&cur_c,sizeof(char) /從文件讀一個(gè)字符 switch(in_comment) case false: if(old_c='/' && cur_c='*') /進(jìn)入注釋 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; /保留前一個(gè)字符 /end of while bufi+='#' /在源程序詞尾加字符#實(shí)驗(yàn)二 簡單程序設(shè)計(jì)語言的詞法分析器實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)?zāi)康模赫莆赵~法分析器的原理將源程序預(yù)處理、狀態(tài)圖轉(zhuǎn)換等結(jié)合，建立簡單的程序設(shè)計(jì)語言詞法分析器實(shí)驗(yàn)內(nèi)容： 要求能對(duì)簡單程序設(shè)計(jì)語言進(jìn)行詞法分析，具體內(nèi)容如下：字符集 a.z, 0.9,+,=,*,;,(,),#若發(fā)現(xiàn)字符集之外的字符，即為非法字符，當(dāng)出現(xiàn)非法字符時(shí)終止詞法分析器的運(yùn)行。單詞集基本字：begin、end、integer、real標(biāo)

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

8、或多字符單詞。實(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í)提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告（實(shí)驗(yàn)報(bào)告包括實(shí)驗(yàn)?zāi)康摹?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會(huì)）。實(shí)現(xiàn)代碼：詞法分析有5個(gè)函數(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ù)，獲得一個(gè)單詞二元式 coutf<<t.code<<t<<t.val<<endl; while(t.code!=#cout<<”end of lexical analysis”<<endl;實(shí)驗(yàn)三 遞歸下降分析法實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)?zāi)康模赫莆者f歸下降語法分析的原理利用高級(jí)語言的遞歸過程為給定文法的每個(gè)非終結(jié)符構(gòu)造對(duì)應(yīng)的遞歸函數(shù)實(shí)驗(yàn)內(nèi)容：若文法不含左遞歸，并且每個(gè)非終結(jié)符的所有候選式的首符集都兩兩不相交，就有可能構(gòu)造一個(gè)不帶回溯的自上而下的語法分析程序。這

11、個(gè)分析程序是由一組遞歸過程（函數(shù)）組成的，每個(gè)過程（函數(shù)）對(duì)應(yīng)文法的一個(gè)非終結(jié)符。如果用某種高級(jí)語言寫出所有遞歸過程（函數(shù)），那就可以用這個(gè)高級(jí)語言的編譯系統(tǒng)產(chǎn)生整個(gè)分析程序。這個(gè)分析程序稱為遞歸下降分析器。 用類C語言為文法G的每個(gè)非終結(jié)符構(gòu)造對(duì)應(yīng)的遞歸函數(shù)。文法G如下所示：ETEE+TE|TFTT*FT|F(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í)提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告（實(shí)驗(yàn)報(bào)告包括實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會(huì)）。實(shí)現(xiàn)

12、代碼：假設(shè)源程序?yàn)椤?a+b)*c”，經(jīng)詞法分析，單詞二元式序列存放于文件lex_r.txt中。遞歸下降分析器從文件lex_r.txt讀入數(shù)據(jù)進(jìn)行處理。每次讀入的是單詞二元式，即單詞的種別(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;實(shí)驗(yàn)四 預(yù)測分析析法實(shí)驗(yàn)學(xué)時(shí)：4學(xué)時(shí)實(shí)

14、驗(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)行語法分析。文法G如下所示：ETEE+TE|TFTT*FT|F(E)|i|x|y預(yù)測分析法是一種不使用遞歸的語法分析方法，由一張分析表和一個(gè)控制程序構(gòu)成的。一、預(yù)測分析表的構(gòu)造產(chǎn)生式的一般形式為：A1|2|n|若當(dāng)前輸入符號(hào)t.codefirst(i)，則用Ai推導(dǎo)；若當(dāng)前輸入符號(hào)t.codefollow(A)，則用A推導(dǎo)；除此以外均為錯(cuò)誤。候選式的選取是由兩個(gè)要素決定的：一個(gè)是句型中的非終結(jié)符A，從它出發(fā)進(jìn)行最左推導(dǎo)；另一個(gè)是當(dāng)前輸入

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

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

17、tack棧，然后把產(chǎn)生式右部符號(hào)串按反序一一推進(jìn)stack棧。若右部符號(hào)串為空字，則意味著無任何文法符號(hào)進(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í)提交本次實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告（實(shí)驗(yàn)報(bào)告包括實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)實(shí)現(xiàn)過程、源程序、實(shí)驗(yàn)結(jié)果、實(shí)驗(yàn)體會(huì)）。實(shí)現(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按反序進(jìn)棧; top=top+k; 實(shí)驗(yàn)五 LR語法分析實(shí)驗(yàn)學(xué)時(shí)：2學(xué)時(shí)實(shí)驗(yàn)?zāi)康模?掌握LR語法分析的基本原理基本原理：把每個(gè)句柄的識(shí)別（產(chǎn)生式右部的符號(hào)串）過程劃分為若干狀態(tài)，每個(gè)狀態(tài)只識(shí)別句柄的一個(gè)符號(hào)，若干個(gè)狀態(tài)就可識(shí)別句柄左端的一部分符號(hào)。利用高級(jí)語言實(shí)現(xiàn)LR語法分析器實(shí)驗(yàn)內(nèi)容：文法：（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5）F(E)（6）F i假設(shè)分析表用二維數(shù)組M存儲(chǔ)，棧頂狀態(tài)用Stop表示，當(dāng)前輸入符號(hào)用t.code表示，控制程序的算法可歸納如下：(1) 移進(jìn)。若MStopt.c