1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理實驗書 2010年11月 實驗目錄： 適用專業(yè)及實驗總學時：2007級計算機科學與技術(shù)專業(yè)(軟件方向)，18學時。 任課教師： 黃玲 E-mail: huangl 恭喜你！你將進入非常重要的專業(yè)課程的實踐。編譯原理的知識影響到專業(yè)人員的素質(zhì)，除編譯程序外有大量專業(yè)工作與編譯技術(shù)相關(guān) 。你現(xiàn)在需要通過腳踏實地的實踐學習(很辛苦的！)，把自己的專業(yè)水平提高一個層次。你需要在實驗課前自己閱讀程序代碼，在實驗課中調(diào)試程序，實驗課后完成實驗報告（每一個實驗上交一份實驗報告），實驗報告必須闡述清楚你的所做的工作，內(nèi)容包含修改思路、關(guān)鍵修改代碼、運行結(jié)果、對運行結(jié)果的評價、

2、進一步改進的建議。最重要的是，通過實踐你可以獲得專業(yè)的能力和自信。加油！實驗1：詞法分析程序（3學時，第12周）一、實驗目的和內(nèi)容：1實驗目的：通過詞法分析程序，了解詞法分析的過程。2實驗內(nèi)容：用C實現(xiàn)對Pascal的子集程序設(shè)計語言的詞法識別。3實驗要求：要求修改文法和程序，增加浮點數(shù)處理功能。4. 實驗環(huán)境是Windows操作系統(tǒng)、Visual C+開發(fā)環(huán)境。二、未增加浮點數(shù)處理的原設(shè)計：1 程序設(shè)計語言的描述：<程序><程序首部><分程序>.<程序首部>PROGRAM <標識符><分程序><常量說明部分>

3、<變量說明部分><過程說明部分><復合語句><常量說明部分>CONST <常量定義>,<常量定義><常量定義>標識符=無符號整數(shù)<變量說明部分>VAR <變量定義>,<變量定義><變量定義>標識符,標識符:<類型><類型>INTEGER|LONG<過程說明部分><過程首部><分程序><過程首部><分程序><過程首部>PROCEDURE 標識符;|PROCEDURE 標識

4、符(標識符:<類型>);<語句><賦值語句>|<條件語句>|<當型循環(huán)語句>|<過程調(diào)用語句>|<讀語句>|<寫語句>|<復合語句>|<賦值語句>標識符:=<表達式><條件語句>IF <條件> THEN <語句><當型循環(huán)語句>WHILE <條件> DO <語句><過程調(diào)用語句>標識符|標識符(<表達式>)<讀語句>READ (標識符,標識符)<寫語句

5、>WRITE (<表達式>,<表達式>)<復合語句>BEGIN <語句><語句>END<條件><表達式><關(guān)系運算符><表達式>|ODD <表達式><表達式>+|-<項><加型運算符><項><項><因子><乘型運算符><因子><因子>標識符|無符號整數(shù)|(<表達式>)<加型運算符>+|-<乘型運算符>*|/<關(guān)系運算符&g

6、t;=|<>|<|<=|>|>=其中： < > 用左右尖括號括起來的符號串表示非終結(jié)符 定義為 表示該語法成分可以重復0n次 表示方括號內(nèi)為可選項，即0或1次2 程序設(shè)計語言單詞的內(nèi)部編碼：(35個終結(jié)符) 內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20=21<>22<23<=24>25>=26.27,28;29:30:=

7、31(32)33無符號整數(shù)34標識符35# 3下面是一個詞法分析程序，該程序能夠?qū)⒃闯绦?，也就是相?yīng)字符流轉(zhuǎn)換成內(nèi)碼，并輸出到文件。程序的執(zhí)行需要提供兩個參數(shù)，第一個參數(shù)是源程序文件名，第二個參數(shù)是存放分析結(jié)果的文件名，第二個參數(shù)可以省略，可由程序自動生成。Vc+6程序參數(shù)的設(shè)置方法：菜單project下子菜單settings中的debug選項卡下program arguments對話框中，輸入?yún)?shù)。如采用Visual Studio 2008開發(fā)環(huán)境，構(gòu)建控制臺應(yīng)用程序,參數(shù)設(shè)置:項目屬性-(活動debug模式)配置屬性-調(diào)試-命令參數(shù)，同時工作目錄為當前工程下debug 。 #include

8、 <stdio.h>#include <ctype.h>#include <string.h>#include <process.h>#define lenth1 15 /保留字表的長度#define lenth2 17 /運算符界符表長度struct char name21;int type;int addr;indent1000; /符號表struct stchar name21;int code;sym; /當前單詞FILE *f1,*f2;int line=1,row=1,val; /行號、列號、數(shù)字串的值char ch=' &#

9、39; /當前字符int lenth3=0; /符號表中實際的標識符個數(shù)void getsym();char getchr();void error(int);main(int argc,char *argv) char ft12,*fc; if (f1=fopen(argv1,"r")=NULL) /打開源程序文件 printf("can not open file.n");exit(0); if (argc<=2) /如果沒有提供第二個參數(shù) strcpy(ft,argv1);if (fc=strchr(ft,'.')!=NULL

10、) /如果第一個參數(shù)即源文件名，有后綴 .xxxstrcpy(fc,".mid"); /結(jié)果文件名：源文件名非后綴部分.midelsestrcat(ft,".mid"); /結(jié)果文件名：源文件名.mid else strcpy(ft,argv2); if (f2=fopen(ft,"w")=NULL) /打開結(jié)果文件 printf("cannot open file 2n"); exit(0); while (!feof(f1) /只要沒有遇到源文件的結(jié)尾，繼續(xù)循環(huán)。 getsym(); /獲取一個單詞放到sym

11、printf("%s %dn",,sym.code); /顯示當前單詞的名字及其內(nèi)碼 fprintf(f2,"%s %dn",,sym.code);/向輸出文件寫入：單詞名字 單詞內(nèi)碼 fclose(f1); fclose(f2);void getsym()static char alenth110="PROGRAM","CONST","VAR","INTEGER","LONG","PROCEDURE",

12、"IF","THEN","WHILE","DO","READ","WRITE","BEGIN","END","ODD"/保留字表static char dlenth23="+","-","*","/","=","<>","<","<="

13、,">",">=",".",",","",":",":=","(",")" /運算符界符表char str21;int i,n;while (isspace(ch) ch=getchr();if (isalpha(ch) /如果當前字符是字母,則后面幾行代碼就是識別標識符的自動機的實現(xiàn)n=0; while (isalpha(ch) | isalnum(ch) /當前字符是字母或者數(shù)字，繼續(xù)循環(huán) if (i

14、salpha(ch) ch=tolower(ch); if (n<20) strn+=ch; /構(gòu)造字符串 ch=getchr(); /從文件中讀取下一個字符 strn='0' for (i=0;i<lenth1;i+) /檢查當前符號串是否保留字 if (!strcmp(str,ai) break; /如果字符串已經(jīng)登記在保留字表，中斷循環(huán) if (i<lenth1) /如果該字符串是保留字，將當前單詞寫入sym strcpy(,ai);sym.code=i+1; else /該單詞不是保留字，而是標識符 for(i=0;i<lenth

15、3;i+) /在符號表里檢查是否已經(jīng)登記過該標識符 if (!strcmp(str,) break; /如果登記過，中斷循環(huán) if (i=lenth3) strcpy(,str);/如果沒有登記過該標識符,登記它到符號表。lenth3+; strcpy(,); /當前標識符寫入sym sym.code=34; else if (isalnum(ch) /如果當前字符是數(shù)字,則后面就是識別數(shù)字串的自動機的實現(xiàn) val=0;n=0; while (isalnum(ch) val=val*10+ch-0; sym

16、.namen+=ch; ch=getchr();n=0;sym.code=33; else /當前字符是運算符或者界符 if (ch='+' | ch='-' | ch='*' | ch='/' | ch='=' | ch='.' | ch=',' | ch='' | ch='(' | ch=')') str0=ch;str1='0'ch=getchr(); /從文件中讀入一個字符 for (i=0;i&

17、lt;lenth2;i+) /在運算符界符表查詢，是否有此ch字符if (!strcmp(str,di) strcpy(,str); /有， sym.code=i+16; else /處理符號<> < <= > >= : := n=0;if (ch='>' | ch=':') strn+=ch; if (ch=getchr()='=') / >=或:= strn+=ch; ch=getchr(); else if (ch='<') strn+=ch; ch=ge

18、tchr(); if (ch='=' | ch='>') / <=或<> strn+=ch; ch=getchr(); else if (ch=-1) strcpy(,""); sym.code=35; /#/else error(1); strn='0' /str為一個完整的單詞 for (i=0;i<lenth2;i+) /查運算符界符表，看是否有此符號串str if (!strcmp(str,di) strcpy(,str); sym.code=i+16; c

19、har getchr() char ch=fgetc(f1); if (ch='n') row=1; line+; else if (ch!=' ' && ch!='t') row+; return (ch);void error(int n) printf("%d error happens.n",n); exit(0);4. 詞法分析程序 getsym()流程圖讀入下一個字符到chch的符號是空格？ Y Nch的符號是字母？ 標識符或者保留字 Y ch的符號是字母或數(shù)字？ N N Ych的符號是字母？ N

20、Y將ch的字母變?yōu)樾懽帜笇h的符號加入到字符數(shù)組str尾讀入下一個符號到ch在str尾增加0,構(gòu)建一個字符串在保留字表a中查找str的位置ii<保留字表長度？ N Y 標識符 保留字登記單詞str到sym，內(nèi)碼i+1在標識符表查找str的位置ii為標識符表的末尾？ YN在標識符表末尾登記str標識符表長度加1結(jié)束登記str到sym,內(nèi)碼34ch是數(shù)字？ Y Nch是數(shù)字？ N Y轉(zhuǎn)化為數(shù)值讀入字符到ch登記當前單詞到sym，內(nèi)碼33。結(jié)束ch是+ - * / = . , ; ( ) 中的符號？ 單個運算符或界符為該符號構(gòu)造字符串str Y讀入下一個符號到ch N在運算符界符表d中查該

21、符號的位置i登記該符號到sym,內(nèi)碼i+16ch是>或者:嗎？構(gòu)造str并讀入符號到ch Y ch是=嗎？ N N >或： Y >=或:=構(gòu)造str并讀入符號到ch ch是<嗎？ Y構(gòu)造str并讀入符號到ch Nch是=或>嗎？ N < Y <=或<>構(gòu)造str并讀入符號到ch登記#到sym，內(nèi)碼35 在str末尾加0,構(gòu)建字符串在運算符界符表d查str位置i。查到？單詞str?登記str到sym,內(nèi)碼i+16 Y N結(jié)束三、增加浮點數(shù)功能時，可以使用下面的源程序作為詞法分析程序的輸入（當然，你也可以自己編寫各種源程序，以便測試程序。）詞法

22、分析程序輸出詞法分析結(jié)果。PROGRAM mypascal;CONST UNIT=100;VAR x:INTEGER,y:FLOAT;PROCEDURE subproc(i:INTEGER); BEGIN x:=i; END; BEGIN subproc(20); x:=x+UNIT; y=y*x+23.45;END.實驗2：語法分析-遞歸子程序法（3學時，第13周）一、實驗的目的和內(nèi)容：1目的：通過完成語法分析程序，了解語法分析的過程和作用。2實驗內(nèi)容：用遞歸子程序法實現(xiàn)對Pascal的子集程序設(shè)計語言的分析程序。分析程序?qū)υ闯绦虻膬?nèi)碼流進行分析，如果為文法定義的句子，則輸出“是”，否則輸出

23、“否”。3 實驗要求：要求修改文法和程序，增加浮點數(shù)處理功能。二、未增加浮點數(shù)處理功能的原設(shè)計：1改寫實驗一的未增加浮點數(shù)處理的文法，使其是LL(1)文法。改變后文法如下：<程序><程序首部><分程序>.<程序首部>PROGRAM <標識符><分程序><常量說明部分><變量說明部分><過程說明部分><復合語句><常量說明部分>CONST <常量定義><常量定義后綴>|<常量定義>標識符=無符號整數(shù)<常量定義后綴>,&

24、lt;常量定義><常量定義后綴> |<變量說明部分>VAR <變量定義><變量定義后綴> |<變量定義>標識符<標識符后綴>:<類型><標識符后綴>, 標識符<標識符后綴> |<變量定義后綴><變量定義><變量定義后綴> |<類型>INTEGER|LONG<過程說明部分><過程首部><分程序><過程說明部分后綴> |<過程首部>PROCEDURE 標識符<參數(shù)部分>

25、;<參數(shù)部分>(標識符:<類型>) |<過程說明部分后綴><過程首部><分程序><過程說明部分后綴> |<語句><賦值或調(diào)用語句>|<條件語句>|<當型循環(huán)語句>|<讀語句>|<寫語句>|<復合語句>|<賦值或調(diào)用語句>標識符<后綴><后綴>:=<表達式>|(<表達式>)|<條件語句>IF <條件> THEN <語句><當型循環(huán)語句>

26、WHILE <條件> DO <語句><讀語句>READ (標識符<標識符后綴>)<寫語句>WRITE (<表達式><表達式后綴>)<表達式后綴>, <表達式><表達式后綴>|<復合語句>BEGIN <語句><語句后綴>END<語句后綴> <語句><語句后綴>|<條件><表達式><關(guān)系運算符><表達式>|ODD <表達式><表達式>+&

27、lt;項><項后綴>|-<項><項后綴>|<項><項后綴><項后綴><加型運算符><項><項后綴>|<項><因子><因子后綴><因子后綴><乘型運算符><因子><因子后綴>|<因子>標識符|無符號整數(shù)|(<表達式>)<加型運算符>+|-<乘型運算符>*|/<關(guān)系運算符>=|<>|<|<=|>|>=2非終結(jié)

28、符和函數(shù)名對照表：（34個非終結(jié)符） 非終結(jié)符函數(shù)名非終結(jié)符函數(shù)名<程序>program<程序首部>proghead<分程序>block<常量說明部分>consexpl<常量定義>consdefi<變量說明部分>varexpl<常量定義后綴>conssuff<變量定義>vardefi<變量定義后綴>varsuff<過程說明部分>procdefi<類型>typil<過程首部>procedh<過程說明部分后綴>procsuff<賦值或調(diào)用

29、語句>assipro<語句>sentence<后綴>suffix<條件語句>ifsent<讀語句>read<當型循環(huán)語句>whilsent<標識符后綴>idsuff<寫語句>write<復合語句>compsent<表達式后綴>exprsuff<語句后綴>sentsuff<條件>conditio<項后綴>termsuff<表達式>express<項>term<因子后綴>factsuff<參數(shù)部分>ar

30、gument<因子>factor<加型運算符>aAddoper<乘型運算符>muloper<關(guān)系運算符>respoper3下面是一個遞歸子程序語法分析程序，程序的執(zhí)行需要提供一個參數(shù)：源程序文件名。該程序判斷給定的源程序語法是否正確。#include <stdio.h>#include <ctype.h>#include <string.h>#include <process.h>#define PROGRAM 1 /從這里開始宏定義終結(jié)符內(nèi)碼，為的是增加程序的易讀性#define CONST 2#

31、define VAR 3 #define INTEGER 4#define LONG 5#define PROCEDURE 6#define IF 7#define THEN 8#define WHILE 9#define DO 10#define READ 11#define WRITE 12#define BEGIN 13#define END 14#define ODD 15#define ADD 16#define SUB 17#define MUL 18#define DIV 19#define EQU 20#define NEQ 21#define LES 22#define LE

32、Q 23#define LAG 24#define GEQ 25#define DOT 26#define COM 27#define SEM 28#define COL 29#define ASS 30#define LBR 31#define RBR 32#define INT 33#define ID 34 /標識符內(nèi)碼#define EIN 35#define lenth1 15 /保留字表長度#define lenth2 17 /運算符界符長度struct char name21;int type;int addr;indent 1000; /符號表struct stchar nam

33、e21;int code;sym; /當前單詞int lenth=0;FILE* f1;int line=0,row=0,val;void getsym();char getchr();void error(int);void program();void proghead();void block();void consexpl();void consdefi();void varexpl();void conssuff();void vardefi();void varsuff();void procdefi();void typeil();void procedh();void proc

34、suff();void assipro();void sentence();void suffix();void ifsent();void read();void whilsent();void idsuff();void write();void compsent();void exprsuff();void sentsuff();void condition();void termsuff();void express();void term();void factsuff();void factor();void addoper();void muloper();void respop

35、er();void argument();char ch=' ' /當前字符int lenth3=0; /符號表中實際標識符個數(shù)void main(int argc,char* argv) if (f1=fopen(argv1,"r")=NULL) /打開源程序文件 printf("cannot open filen"); exit(0); getsym(); /獲取第一個單詞 program(); /程序的語法分析 printf("the program is rightn");/源程序正確 fclose(f1);v

36、oid program() /非終結(jié)符<程序>的分析程序：<程序>-><程序首部><分程序>. proghead(); /非終結(jié)符<程序首部>的分析程序 block(); /非終結(jié)符<分程序>的分析程序 if (sym.code=DOT) /DOT為.的內(nèi)碼表示，見文件首的宏定義。如果當前單詞是. getsym(); /讀取下一個單詞到sym else error(2);void proghead() /非終結(jié)符<程序首部>的分析程序：<程序首部>->PROGRAM 標識符；if(sym

37、.code=PROGRAM) getsym(); if (sym.code=ID) getsym(); if (sym.code=SEM) getsym(); else error(5); else error(4); elseerror(3);void block() /非終結(jié)符<分程序>的分析程序 consexpl(); varexpl(); procdefi(); compsent();void consexpl() /非終結(jié)符<常量說明部分>CONST <常量定義><常量定義后綴>|if (sym.code=CONST) /如果當前單詞不

38、是CONST,則是分支，什么事情都不做。 / CONST <常量定義><常量定義后綴> getsym(); consdefi(); conssuff(); if (sym.code=SEM) getsym(); else error(6);void consdefi() /非終結(jié)符<常量定義>if (sym.code=ID) getsym(); if (sym.code=EQU) getsym();if (sym.code=INT)getsym();elseerror(9); else error(8); elseerror(7);void conssuff

39、() /非終結(jié)符<常量定義后綴>，<常量定義><常量定義后綴>| if (sym.code=COM) getsym(); consdefi(); conssuff();/* if (sym.code=SEM) getsym(); else error(10); */void varexpl() /變量說明部分 if (sym.code=VAR) getsym();vardefi();varsuff(); void vardefi() /非終結(jié)符<變量定義>if (sym.code=ID) getsym(); idsuff(); if (sym.c

40、ode=COL) getsym(); typeil(); if (sym.code=SEM) getsym(); else error(12); else error(11);void varsuff() /非終結(jié)符<變量定義后綴>if (sym.code=ID) vardefi(); varsuff();void typeil() /非終結(jié)符<類型>if (sym.code=INTEGER|sym.code=LONG) getsym();else error(13);void procdefi() /非終結(jié)符<過程說明部分>if (sym.code=PRO

41、CEDURE) procedh(); block(); if (sym.code=SEM) getsym(); procsuff(); else error(14);void procedh() /非終結(jié)符<過程首部>if (sym.code=PROCEDURE) getsym(); if (sym.code=ID) getsym(); argument(); if (sym.code=SEM) getsym(); else error(16); else error(15);void argument() /非終結(jié)符<參數(shù)部分>if (sym.code=LBR) ge

42、tsym(); if (sym.code=ID) getsym(); if (sym.code=COL) getsym(); typeil(); if(sym.code=RBR) getsym(); else error(19); else error(18); else error(17);void procsuff() /非終結(jié)符<過程說明部分后綴>if (sym.code=PROCEDURE) procedh(); block(); if (sym.code=SEM) getsym(); procsuff(); else error(20);void assipro() /賦

43、值或調(diào)用語句 if (sym.code=ID) getsym();suffix(); else error(21);void sentence() /語句 if (sym.code=ID)assipro(); else if (sym.code=IF)ifsent(); else if (sym.code=WHILE)whilsent();else if (sym.code=READ)read();else if (sym.code=WRITE)write();else if (sym.code=BEGIN)compsent();void suffix() /非終結(jié)符<后綴>if

44、(sym.code=ASS) getsym(); express();elseif (sym.code=LBR) getsym(); express(); if (sym.code=RBR) getsym(); else error(22);void ifsent() /非終結(jié)符<條件語句>if (sym.code=IF) getsym(); condition(); if (sym.code=THEN) getsym(); sentence(); else error(24);elseerror(23);void whilsent() /while語句 if (sym.code=

45、WHILE) getsym();conditio();if (sym.code=DO) getsym(); sentence();else error(26); else error(25);void read() /非終結(jié)符<讀語句>if (sym.code=READ) getsym(); if (sym.code=LBR) getsym(); if (sym.code=ID) getsym(); idsuff(); if (sym.code=RBR) getsym(); else error(27); else error(30); else error(29); elseer

46、ror(28);void idsuff() /非終結(jié)符<標識符后綴>if (sym.code=COM) getsym(); if (sym.code=ID) getsym(); idsuff(); else error(31);void write() /寫語句 if (sym.code=WRITE) getsym();if (sym.code()=LBR) getsym(); express(); exprsuff(); if (sym.code=RBR) getsym() else error(34);else error(33); else error(32); void c

47、ompsent() /非終結(jié)符<復合語句>if (sym.code=BEGIN) getsym(); sentence(); sentsuff(); if (sym.code=END) getsym(); else error(36); elseerror(35);void exprsuff() /非終結(jié)符<表達式后綴> if (sym.code=COM) getsym(); express(); exprsuff();void sentsuff() /非終結(jié)符<語句后綴>if (sym.code=SEM) getsym(); sentence(); sen

48、tsuff();void condition() /非終結(jié)符<條件>if (sym.code=ODD) getsym(); express(); else express(); respoper(); express();void express() /非終結(jié)符<表達式>+<項><項后綴>|-<項><項后綴>|<項><項后綴>if (sym.code=ADD|sym.code=SUB) getsym();term();termsuff();void term() /非終結(jié)符<項> factor(); factsuff();void termsuff() /非終結(jié)符<項后綴>if (sym.code=ADD|sym.code=SUB) getsym(); factor(); factsuff();void factsuff() /非終結(jié)符<因子后綴>if (sym.code=MUL|sym.code=DIV) getsym(); factor(); factsuff();void facto