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

1、編譯原理實(shí)驗(yàn)指導(dǎo)書適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 網(wǎng)絡(luò)工程 軟件工程物聯(lián)網(wǎng)工程編寫者：編譯原理課程組修訂時(shí)間:2015年9月一、 課程的教學(xué)目標(biāo)本課程融驗(yàn)證性實(shí)驗(yàn)與創(chuàng)新設(shè)計(jì)實(shí)驗(yàn)于一體，使學(xué)生把構(gòu)造程序語言編譯系統(tǒng)的基本原理和技術(shù)應(yīng)用于實(shí)踐，掌握設(shè)計(jì)和構(gòu)造程序語言編譯系統(tǒng)的工作框架和開發(fā)實(shí)現(xiàn)過程，增強(qiáng)學(xué)生開發(fā)較大型系統(tǒng)軟件的能力。通過對一個(gè)常用高級程序設(shè)計(jì)語言的簡單語言子集編譯系統(tǒng)中詞法分析、語法分析、語義處理模塊的設(shè)計(jì)、開發(fā)，掌握實(shí)際編譯系統(tǒng)的核心結(jié)構(gòu)、工作流程及其實(shí)現(xiàn)技術(shù)，獲得分析、設(shè)計(jì)、實(shí)現(xiàn)編譯程序等方面的實(shí)際操作能力，增強(qiáng)設(shè)計(jì)、編寫和調(diào)試程序的能力。通過開源編譯器分析、編譯過程可視化等擴(kuò)展實(shí)

2、驗(yàn)，促進(jìn)學(xué)生增強(qiáng)復(fù)雜系統(tǒng)分析、設(shè)計(jì)和實(shí)現(xiàn)能力，鼓勵(lì)學(xué)生創(chuàng)新意識和能力。二、 實(shí)驗(yàn)內(nèi)容本課程的實(shí)驗(yàn)內(nèi)容分為三個(gè)實(shí)驗(yàn)項(xiàng)目，詞法分析程序設(shè)計(jì)與實(shí)現(xiàn)、語法分析程序設(shè)計(jì)與實(shí)現(xiàn)、語義處理程序設(shè)計(jì)與實(shí)現(xiàn)，總的實(shí)驗(yàn)學(xué)時(shí)為30課時(shí)，各項(xiàng)實(shí)驗(yàn)學(xué)時(shí)分配表如表1。表1：各項(xiàng)實(shí)驗(yàn)學(xué)時(shí)分配表實(shí)驗(yàn)項(xiàng)目實(shí) 驗(yàn) 內(nèi) 容參考實(shí)驗(yàn)課時(shí)數(shù)1、詞法分析程序設(shè)計(jì)與實(shí)現(xiàn)構(gòu)造具有關(guān)鍵字、運(yùn)算符、標(biāo)識符、無符號常數(shù)等單詞的詞法分析程序。輸入由符合及不符合規(guī)定單詞類別結(jié)構(gòu)的各類單詞組成的源程序。輸出單詞串的二元式編碼（CLASS，VALUE）。102、語法分析程序設(shè)計(jì)與實(shí)現(xiàn)將詞法分析程序輸出的單詞串作為輸入，針對常見的表達(dá)式、賦值語句、條件語句

3、、循環(huán)語句等語法成分，選擇有代表性的語法分析方法，如遞歸下降法、算符優(yōu)先分析、LL(1)、LR等方法之一，設(shè)計(jì)實(shí)現(xiàn)相應(yīng)的語法分析程序。103、語義分析程序設(shè)計(jì)與實(shí)現(xiàn)對各語法單位增加語義子程序，將表達(dá)式或可執(zhí)行語句翻譯為四元式序列輸出，并能進(jìn)行錯(cuò)誤檢查與處理，將錯(cuò)誤信息輸出。10合計(jì)30每個(gè)實(shí)驗(yàn)項(xiàng)目包括基本實(shí)驗(yàn)部分和擴(kuò)展實(shí)驗(yàn)兩部分。各實(shí)驗(yàn)項(xiàng)目的基本實(shí)驗(yàn)部分要求每個(gè)同學(xué)完成，擴(kuò)展實(shí)驗(yàn)部分供實(shí)踐能力較強(qiáng)的學(xué)生選做。三、實(shí)驗(yàn)要求1、 每次實(shí)驗(yàn)前學(xué)生應(yīng)詳細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書，做好實(shí)驗(yàn)的設(shè)計(jì)和準(zhǔn)備工作。2、 獨(dú)立完成實(shí)驗(yàn)，程序書寫符合程序書寫規(guī)范，積極配合實(shí)驗(yàn)進(jìn)度檢查和演示。3、 按要求完成實(shí)驗(yàn)報(bào)告。不接受不

4、完整的實(shí)驗(yàn)報(bào)告或者說明與程序、運(yùn)行結(jié)果不符合的作業(yè)。4、 實(shí)驗(yàn)報(bào)告電子版實(shí)驗(yàn)報(bào)告和源程序在最后一次機(jī)時(shí)后的一周內(nèi)上交。每人上交一個(gè)壓縮文件，其命名格式為“學(xué)號_姓名.rar”（“組長學(xué)號_姓名.rar”），內(nèi)含實(shí)驗(yàn)報(bào)告和一個(gè)命名為“源程序”的文件夾，其中包括一個(gè)說明文件和源程序，說明文件描述程序運(yùn)行環(huán)境和使用方法，源程序應(yīng)是經(jīng)過調(diào)試、測試成功的程序，并應(yīng)有相應(yīng)的注釋、運(yùn)行環(huán)境和使用方法簡介。四、 實(shí)驗(yàn)報(bào)告每個(gè)人針對所完成的實(shí)驗(yàn)內(nèi)容撰寫實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告主要包括三方面內(nèi)容：1、實(shí)驗(yàn)設(shè)計(jì)：實(shí)驗(yàn)采用的實(shí)現(xiàn)方法和依據(jù)，如描述語言的文法及其機(jī)內(nèi)表示，詞法分析的單詞分類碼表、狀態(tài)轉(zhuǎn)換圖或狀態(tài)矩陣等，語法分

5、析中用到的分析表或優(yōu)先矩陣等，語法制導(dǎo)翻譯中文法的拆分和語義動(dòng)作的設(shè)計(jì)編寫等；具體的設(shè)計(jì)結(jié)果，應(yīng)包括整體設(shè)計(jì)思想和實(shí)現(xiàn)算法，程序結(jié)構(gòu)的描述，各部分主要功能的說明，以及所用數(shù)據(jù)結(jié)構(gòu)的介紹等。2、程序代碼：實(shí)驗(yàn)實(shí)現(xiàn)的核心代碼源程序清單，要求符合常規(guī)的程序書寫風(fēng)格，有詳細(xì)的注釋。3、實(shí)驗(yàn)結(jié)果分析：自行編寫若干源程序作為測試用例，對所生成的編譯程序進(jìn)行測試（編譯程序的輸入與輸出以文件的形式給出）；運(yùn)行結(jié)果分析（至少包括一個(gè)正確和一個(gè)錯(cuò)誤單詞或語句的運(yùn)行結(jié)果）；以及改進(jìn)設(shè)想等。五、考核評價(jià)方法成績采用五級分制，根據(jù)實(shí)驗(yàn)完成情況、實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)過程表現(xiàn)、成果演示情況等方面綜合評定。進(jìn)行擴(kuò)展實(shí)驗(yàn)，按照完成情

6、況加分。實(shí)驗(yàn)一 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康耐ㄟ^編寫和調(diào)試一個(gè)詞法分析程序，掌握在對程序設(shè)計(jì)語言的源程序進(jìn)行掃描的過程中，將字符流形式的源程序轉(zhuǎn)化為一個(gè)由各類單詞序列的詞法分析方法。二、基本實(shí)驗(yàn)內(nèi)容與要求假定一種高級程序設(shè)計(jì)語言中的單詞主要包括五個(gè)關(guān)鍵字begin、end、if、then、else；標(biāo)識符；無符號常數(shù)；六種關(guān)系運(yùn)算符；一個(gè)賦值符和四個(gè)算術(shù)運(yùn)算符，試構(gòu)造能識別這些單詞的詞法分析程序（各類單詞的分類碼參見表1）。輸入：由符合和不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序文件。輸出：把所識別出的每一單詞均按形如（CLASS，VALUE）的二元式形式輸出，并將結(jié)果放到某個(gè)文件

7、中。對于標(biāo)識符和無符號常數(shù)，CLASS字段為相應(yīng)的類別碼的助記符；VALUE字段則是該標(biāo)識符、常數(shù)的具體值；對于關(guān)鍵字和運(yùn)算符，采用一詞一類的編碼形式，僅需在二元式的CLASS字段上放置相應(yīng)單詞的類別碼的助記符，VALUE字段則為“空”。要求：1、上機(jī)前完成詞法分析程序的程序流圖，并選擇好相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。2、用于測試掃描器的實(shí)例源文件中至少應(yīng)包含兩行以上的源代碼。3、對于輸入的測試用例的源程序文件，詞法正確的單詞分析結(jié)果在輸出文件中以二元式形式輸出，錯(cuò)誤的字符串給出錯(cuò)誤提示信息。例如，若輸入文件中的內(nèi)容為：“if myid=1.5E2+100 then x:=y”，則輸出文件中的內(nèi)容應(yīng)為：（I

8、F， ）（ID，myid）（GE， ）（UCON，0.015）（PL， ）（UCON，100）（THEN， ）（ID，x）（IS， ）（ID，y）三、實(shí)現(xiàn)方法1、一般實(shí)現(xiàn)方法說明詞法分析是編譯程序的第一個(gè)處理階段，可以通過兩種途徑來構(gòu)造詞法分析程序。其一是根據(jù)對語言中各類單詞的某種描述或定義（如BNF），用手工的方式（例如可用C語言）構(gòu)造詞法分析程序。一般地，可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，該狀態(tài)矩陣連同控制程序一起便組成了編譯器的詞法分析程序；也可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序。構(gòu)造詞法分析程序的另外一種途徑是所謂的詞法分析程序的自動(dòng)生成，即首先用正規(guī)式對語言中的各類

9、單詞符號進(jìn)行詞型描述，并分別指出在識別單詞時(shí)，詞法分析程序所應(yīng)進(jìn)行的語義處理工作，然后由一個(gè)所謂詞法分析程序的構(gòu)造程序?qū)ι鲜鲂畔⑦M(jìn)行加工。如美國BELL實(shí)驗(yàn)室研制的LEX就是一個(gè)被廣泛使用的詞法分析程序的自動(dòng)生成工具?？偟膩碚f，開發(fā)一種新語言時(shí)，由于它的單詞符號在不停地修改，采用LEX等工具生成的詞法分析程序比較易于修改和維護(hù)。一旦一種語言確定了，則采用手工編寫詞法分析程序效率更高。本實(shí)驗(yàn)建議使用手工編寫的方法。在一個(gè)程序設(shè)計(jì)語言中，一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖，然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖，即得到了一個(gè)有限自動(dòng)機(jī)，再進(jìn)行必要的確定化和狀態(tài)數(shù)最

10、小化處理，最后添加當(dāng)進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)所需執(zhí)行的語義動(dòng)作，就可以據(jù)此構(gòu)造詞法分析程序了。1、單詞分類為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，我們假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識符；在源程序的輸入文本中，關(guān)鍵字、標(biāo)識符、無符號常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運(yùn)算符以及賦值符，則至少須用一個(gè)空白字符加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標(biāo)識符的識別統(tǒng)一進(jìn)行處理。即每當(dāng)開始識別一個(gè)單詞時(shí)，若掃視到的第一個(gè)字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依次進(jìn)行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個(gè)盡可能長的字母數(shù)字字符串，然后以此字

11、符串查所謂保留字表（此保留字表要事先造好），若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識符。表1 語言中的各類單詞符號及其分類碼表單詞符號類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IFthen4THENelse5ELSE標(biāo)識符6ID字母打頭的字母數(shù)字串無符號常數(shù)7UCON機(jī)內(nèi)二進(jìn)制表示8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI采用上述策略后，針對表1中的部分單詞可以參考圖1和程序1，用C語言編寫出符合以上幾項(xiàng)要求的一個(gè)掃描器程序。2、詞法分析器的設(shè)計(jì)圖1 識別表I所列語言中的部分單詞的

12、DFA及相關(guān)的語義過程圖1中所出現(xiàn)的語義變量及語義函數(shù)的含義和功能說明如下：函數(shù)GETCHAR：每調(diào)用一次，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量ch，然后把掃描指示器前推一個(gè)字符位置。字符數(shù)組TOKEN：用來依次存放一個(gè)單詞詞文中的各個(gè)字符。函數(shù)CAT：每調(diào)用一次，就把當(dāng)前ch中的字符拼接于TOKEN中所存字符串的右邊。函數(shù)LOOKUP：每調(diào)用一次，就以TOKEN中的字符串查保留字表，若查到，就將相應(yīng)關(guān)鍵字的類別碼賦給整型變量c；否則將c置為零。函數(shù)RETRACT：每調(diào)用一次，就把掃描指示器回退一個(gè)字符位置（即退回多讀的那個(gè)字符）。函數(shù)OUT：一般僅在進(jìn)入終態(tài)時(shí)調(diào)用此函數(shù)，調(diào)用的形

13、式為OUT(c，VAL)。其中，實(shí)參c為相應(yīng)單詞的類別碼助記符；實(shí)參VAL為TOKEN（即詞文）或?yàn)榭沾?。函?shù)OUT的功能是，在送出一個(gè)單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個(gè)程序。3、詞法分析程序的實(shí)現(xiàn)程序1 根據(jù)圖1編寫的掃描器# include # include # include # define ID 6# define INT 7# define LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20；extern int lookup (char*);e

14、xtern void out (int, char*);extern report_error (void);void scanner_example (FILE *fp)char ch; int i, c;ch=fgetc (fp);if (isalpha (ch) /*it must be a identifer!*/TOKEN0=ch; ch=fgetc (fp); i=1;while (isalnum (ch)TOKENi=ch; i+；ch=fgetc (fp);TOKENi= 0fseek(fp,-1,1); /* retract*/c=lookup (TOKEN);if (c=0

15、) out (ID,TOKEN); else out (c, )；elseif(isdigit(ch)TOKEN0=ch; ch=fgetc(fp); i=1;while(isdigit(ch)TOKENi=ch; i+;ch=fgetc(fp);TOKENi= 0；fseek(fp,-1,1);out(INT,TOKEN);elseswitch(ch)case : ch=fgetc(fp);if(ch=)out(LE, );else if(ch=) out (NE, );elsefseek (fp,-1,1);out (LT, );break;case =: out(EQ, ); break

16、;case : ch=fgetc(fp);if(ch=)out(GE, );elsefseek(fp,-1,1);out(GT, );break;default: report_error( ); break;return; 程序1中所用的若干函數(shù)以及主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。例如：/* 建立保留字表 */#define MAX_KEY_NUMBER 20 /*關(guān)鍵字的數(shù)量*/#define KEY_WORD_END “waiting for your expanding” /*關(guān)鍵字結(jié)束標(biāo)記*/char *KeyWordTableMAX_KEY_NUMBER=“

17、begin”,“end”, “if”, “then”, “else”, KEY_WORD_END;/* 查保留字表，判斷是否為關(guān)鍵字 */int lookup (char *token)int n=0;while (strcmp(KeyWordTablen, KEY_WORD_END) /*strcmp比較兩串是否相同，若相同返回0*/if (!strcmp(KeyWordTablen, token) /*比較token所指向的關(guān)鍵字和保留字表中哪個(gè)關(guān)鍵字相符*/return n+1; /*根據(jù)單詞分類碼表I，設(shè)置正確的關(guān)鍵字類別碼，并返回此類別碼的值*/break;n+;return 0;

18、/*單詞不是關(guān)鍵字，而是標(biāo)識符*/4、無符號常數(shù)的識別注意按照本實(shí)驗(yàn)題目的具體要求，需要將圖1和程序1中整常數(shù)的識別擴(kuò)展為無符號常數(shù)，以滿足題目的要求。關(guān)于無符號數(shù)的文法可參見圖2，表2和程序2。描述無符號數(shù)的右線性文法G1如下：無符號數(shù) d余留無符號數(shù)無符號數(shù) 小數(shù)部分無符號數(shù) d余留無符號數(shù) d余留無符號數(shù)余留無符號數(shù) 十進(jìn)小數(shù)余留無符號數(shù) E指數(shù)部分余留無符號數(shù) d余留無符號數(shù) 十進(jìn)小數(shù) E指數(shù)部分十進(jìn)小數(shù) d十進(jìn)小數(shù)十進(jìn)小數(shù) d小數(shù)部分 d十進(jìn)小數(shù)小數(shù)部分 d指數(shù)部分 d余留整指數(shù)指數(shù)部分 +整指數(shù)指數(shù)部分 -整指數(shù)指數(shù)部分 d整指數(shù) d余留整指數(shù)整指數(shù) d余留整指數(shù) d余留整指數(shù)余留

19、整指數(shù) d圖2所示為上述文法的狀態(tài)轉(zhuǎn)換圖，其中編號0、1、2、6分別代表非終結(jié)符號、及。圖2 文法G1的狀態(tài)轉(zhuǎn)換圖無符號數(shù)識別中的語義處理方法見嵌入了語義動(dòng)作的狀態(tài)矩陣表2，其功能是在掃描源程序字符串的過程中，把識別出的字符串形式的無符號數(shù)的值，逐步轉(zhuǎn)換為相應(yīng)的二進(jìn)制整數(shù)（ICON）或二進(jìn)制浮點(diǎn)數(shù)（FCON）的內(nèi)部形式。（注：考慮能否采用C語言的庫函數(shù)實(shí)現(xiàn)此語義處理工作；是否可將無符號常數(shù)這一類單詞進(jìn)一步細(xì)分成整型常數(shù)和浮點(diǎn)型常數(shù)兩類單詞。）根據(jù)表2I所示的加入了語義過程說明的識別無符號數(shù)的狀態(tài)矩陣，編寫詞法分析程序，部分實(shí)現(xiàn)代碼如程序二所示。表2 包含語義處理過程的識別無符號數(shù)的狀態(tài)矩陣程序

20、2 單詞分類碼為UCON的無符號數(shù)的識別程序1 #include 2 #include 3 #include 45 #define DIGIT 16 #define POINT 27 #define OTHER 38 #define POWER 49 #define PLUS 510 #define MINUS 611 #define UCON 7 /Suppose the class number of unsigned constant is 712 #define ClassOther 20013 #define EndState -114 int w,n,p,e,d;15 int Cl

21、ass; /Used to indicate class of the word16 int ICON;17 float FCON;18 static int CurrentState; /Used to present current state, the initial value:01920 int GetChar (void);21 int EXCUTE (int,int)；22 int LEX (void)；23 int HandleOtherWord (void)24 return ClassOther;25 26 int HandleError (void)27 printf (

22、Error!n); return 0;2829 int GetChar (void)30 31 int c;32 c=getchar ( );33 if(isdigit(c) d=c-0;return DIGIT;34 if (c=.) return POINT;35 if (c=E|c=e) return POWER;36 if (c=+) return PLUS;37 if (c=-) return MINUS;38 return OTHER;39 40 int EXCUTE (int state, int symbol)41 42 switch (state)43 44 case 0:s

23、witch (symbol)45 46 case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;47 case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;48 default: HandleOtherWord( );Class=ClassOther;49 CurrentState=EndState;50 51 break;52 case 1:switch (symbol)53 54 case DIGIT: w=w*10+d;break; /CurrentState

24、=155 case POINT: CurrentState=2;break;56 case POWER: CurrentState=4;break;57 default: ICON=w;CurrentState=EndState;58 59 break；60 case 2:switch (symbol)61 62 case DIGIT: n+;w=w*10+d;break;63 case POWER: CurrentState=4;break;64 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;65 66 break;67 case 3

25、:switch (symbol)68 69 case DIGIT: n+;w=w*10+d;CurrentState=2;break;70 default: HandleError( )；CurrentState=EndState;71 72 break；73 case 4:switch (symbol)74 75 case DIGIT: p=p*10+d;CurrentState=6;break;76 case MINUS: e=-1;CurrentState=5;break;77 case PLUS: CurrentState=5;break;78 default: HandleError

26、( );CurrentState=EndState;79 80 break；81 case 5:switch (symbol)82 83 case DIGIT: p=p*10+d;CurrentState=6;break;84 default: HandleError( );CurrentState=EndState;85 86 break;87 case 6:switch (symbol)88 89 case: DIGIT:p=p*10+d;break;90 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;91 92 break;93

27、94 return CurrentState;95 96 int LEX (void)97 98 int ch;99 CurrentState=0;100 while (CurrentState!=EndState)101 102 ch=GetChar( );103 EXCUTE (CurrentState,ch);104 105 return Class;106 四、擴(kuò)展實(shí)驗(yàn)1、 對基本實(shí)驗(yàn)內(nèi)容進(jìn)行擴(kuò)充，在詞法分析過程中建立變量名表，以備后續(xù)的編譯過程查詢；擴(kuò)充關(guān)鍵字的數(shù)目、增加邏輯運(yùn)算符等單詞類別、將常數(shù)再細(xì)分成字符串常量、整型常量和實(shí)型常量等；添加詞法分析中單詞出錯(cuò)的位置和錯(cuò)誤類型，以及

28、刪除注釋部分等。2、 對基本實(shí)驗(yàn)內(nèi)容進(jìn)行擴(kuò)充，增加狀態(tài)轉(zhuǎn)換圖顯示、詞法分析過程的顯示等可視化展現(xiàn)功能。3、 研讀GCC，CLANG等開源編譯器的詞法分析部分，分析其程序結(jié)構(gòu)、實(shí)現(xiàn)方法、識別的單詞分類等。4、 其它自選題目。注意自選擴(kuò)展實(shí)驗(yàn)須經(jīng)過實(shí)驗(yàn)指導(dǎo)教師同意并備案。實(shí)驗(yàn)二 語法分析程序設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康娜芜x一種有代表性的語法分析方法，如算符優(yōu)先法、遞歸下降法、LL(1)、SLR(1)、LR(1)等，通過設(shè)計(jì)、編制、調(diào)試實(shí)現(xiàn)一個(gè)典型的語法分析程序，對實(shí)驗(yàn)一所得掃描器提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，實(shí)現(xiàn)并進(jìn)一步掌握常用的語法分析方法。二、基本實(shí)驗(yàn)內(nèi)容與要求選擇對各種常見高級程序設(shè)計(jì)語言

29、都較為通用的語法結(jié)構(gòu)算術(shù)表達(dá)式的一個(gè)簡化子集作為分析對象，根據(jù)如下描述其語法結(jié)構(gòu)的BNF定義G2，任選一種學(xué)過的語法分析方法，針對運(yùn)算對象為無符號常數(shù)和變量的四則運(yùn)算，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)語法分析程序。G2： | + | - | * | / | ()若將語法范疇、和分別用E、T、F和i代表，則G2可寫成：G2E：E T | E+T | E-T T F | T*F | T/F F i | (E)輸入：由實(shí)驗(yàn)一輸出的單詞串，例如：UCON，PL，UCON，MU，ID 輸出：若輸入源程序中的符號串是給定文法的句子，則輸出“RIGHT”，并且給出每一步分析過程；若不是句子，即輸入串有錯(cuò)誤，則輸出“ERROR

30、”，并且顯示分析至此所得的中間結(jié)果，如分析棧、符號棧中的信息等，以及必要的出錯(cuò)說明信息。要求:1、確定語法分析程序的流程圖，同時(shí)考慮相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，編寫一個(gè)語法分析源程序。2、將詞法、語法分析合在一起構(gòu)成一個(gè)完整的程序，并調(diào)試成功。3、供測試的例子應(yīng)包括符合語法規(guī)則的語句，及分析程序能判別的若干錯(cuò)例。對于所輸入的字符串，不論對錯(cuò)，都應(yīng)有明確的信息輸出。三、實(shí)現(xiàn)方法1、一般實(shí)現(xiàn)方法說明為了在對源程序的一遍掃描過程中，同時(shí)完成詞法和語法分析任務(wù)，應(yīng)注意首先修改實(shí)驗(yàn)一中的詞法分析程序，將它編寫為子程序的形式，以便供語法分析程序調(diào)用。另外，應(yīng)加強(qiáng)錯(cuò)誤檢查，對輸入符號串中的詞法、語法錯(cuò)誤，給出必要的說明

31、信息，盡可能多地、確切地指出錯(cuò)誤的位置、原因和性質(zhì)。例如，在詞法分析階段，對當(dāng)前正在處理的字符ch，可進(jìn)一步定義一些與該字符相關(guān)的信息row和col，即定義：char ch; /*The current character*/int row; /*The line number position of the current character*/int col; /*The column number position of the current character*/分別表示該字符所在的行和列，這些內(nèi)容在出錯(cuò)處理時(shí)用來提供和源程序位置相關(guān)的信息。2、 采用具有遞歸功能的高級語言編制遞歸下

32、降法的語法分析程序運(yùn)算對象i可以進(jìn)一步定義為變量、常數(shù)等，例如，此處將i定義為：i A|B|C|X|Y|Z利用擴(kuò)充的BNF消除G2E中E和T的直接左遞歸后，采用遞歸下降法分析上述算術(shù)表達(dá)式的框圖見圖3。其中ZC過程為總控程序，被設(shè)計(jì)成可以分析無窮多個(gè)算術(shù)表達(dá)式，主要完成：通知外界鍵入算術(shù)表達(dá)式。控制E過程分析算術(shù)表達(dá)式。根據(jù)分析結(jié)果之正誤，分別輸出不同的信息。E、T和F三個(gè)過程分別對應(yīng)、和三個(gè)產(chǎn)生式的處理。它們都利用到一個(gè)公共過程ADVANCE。ADVANCE過程負(fù)責(zé)從輸入字符串ST中取出下一個(gè)字符，并存入SYM中等待分析；然后再剔除ST中的首字符，這可通過挪動(dòng)字符串指針的辦法來實(shí)現(xiàn)（而實(shí)際上

33、是通過調(diào)用詞法分析程序來實(shí)現(xiàn)ADVANCE功能的）。變量TZ之值標(biāo)志分析的結(jié)果，表明表達(dá)式是否有錯(cuò)。圖3 遞歸下降法分析算術(shù)表達(dá)式的框圖(a) ZC過程 (b) E過程 (c) T過程 (d) F過程 (e) ADVANCE過程3、 基于預(yù)測分析法的語法分析程序參考教材P121例4.3，首先編寫無二義性的簡單算術(shù)表達(dá)式的文法(4.1)，并通過消除左遞歸對其進(jìn)行改寫得到文法(4.1)。然后求出如表4-1所示的各個(gè)FIRST集和FOLLOW集。再檢查是不是LL(1)文法，并按照LL(1)文法構(gòu)造如表4-2所示的預(yù)測分析表。最后根據(jù)預(yù)測分析器的工作流程，實(shí)現(xiàn)預(yù)測分析器的控制程序。4、 算符優(yōu)先分析法

34、的語法分析程序 如程序3所示。其中使用了分析棧stack，用來在分析過程中存放當(dāng)前句型的某一前綴，一旦句型的最左素短語在棧頂形成，便立即進(jìn)行歸約。程序3 算符優(yōu)先分析算法#define RIGHT 1#define ERROR 0#define MAXINPUT 300#define MAXSTACK 100#define STARTSYMBOL Sint stackMAXSTACK，aMAXINPUT; /* a is input line */int IsHigherThan (int, int); /* priority detection */int IsLowerThan (int,

35、 int); /* priority detection */int IsEqualTo (int, int); /* priority detection */int Reduce (int begin, int end, int len);int IsVt (int); /* determine if stack symbol is in Vt */int parser (void)int i, k, r, NewVn; /* NewVn holds left side of a production */i=0; k=0; /* i, k is index of a and stack

36、separately */stack0= #;doint j;r=ai+;if (IsVt(stackk) j=k; else j=k-1;while (IsHigherThan(stackj,r)int q;do q=stackj;if (IsVt(stackj-1) j-; else j-=2; while(!IsLowerThan(stackj,q);NewVn=Reduce(stackj+1,stackk,k-j);k=j+1; /* reduce the leftmost prime phrase */stackk=NewVn; /* it is stackj+1 stackj+2

37、stackk */ /*end of while*/if (IsLowerThan(stackj,r) | IsEqualTo(stackj,r)stack+k=r;else return ERROR; while (r!=#);return RIGHT;程序3給出的僅是采用算符優(yōu)先分析方法的示意性識別算法，還有許多工作要做。如：首先要確定一種合適的數(shù)據(jù)結(jié)構(gòu)，以便構(gòu)造所給文法G2的機(jī)內(nèi)表示。然后，構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣，在此可以根據(jù)算術(shù)表達(dá)式中各算符的優(yōu)先級和結(jié)合性，直接手工構(gòu)造算符優(yōu)先關(guān)系。最后，編寫程序三中所用到的各個(gè)函數(shù)，完成整個(gè)算符優(yōu)先語法分析器的開發(fā)。5、 SLR(1)分析器的

38、開發(fā)首先，對于分析對象，即算術(shù)表達(dá)式的文法G2E，引入一個(gè)新的開始符號E，得到G2E的拓廣文法G2E：0. EE 1. EE+T 2. EE-T 3. ET 4. TT*F 5. TT/F 6. TF 7. F(E) 8. Fi求出文法中各個(gè)非終結(jié)符號的FOLLOW集如下：Follow(E)=#，)，+，- Follow(T)=#，)，+，-，*，/ Follow(F)=#，)，+，-，*，/然后，根據(jù)文法G2E構(gòu)造識別其全部活前綴的DFA，以便據(jù)此構(gòu)造SLR(1)分析表，參見表3。（ 1, ）2, + 3, - 4, * 5, / 6, i 7,表3 G2E的SLR(1)分析表狀態(tài)ACTIO

39、NGOTO（1）2+3-4*5/6I7#ETF0S4S51231S6S7Acc2R3R3R3S8S9R33R6R6R6R6R6R64S4S510235R8R8R8R8R8R86S4S51137S4S51238S4S5139S4S51410S15S6S711R1R1R1S8S9R112R2R2R2S8S9R213R4R4R4R4R4R414R5R5R5R5R5R515R7R7R7R7R7R7最后，編程實(shí)現(xiàn)SLR(1)分析表的驅(qū)動(dòng)程序，即開發(fā)LR分析器的總控程序，完成對算術(shù)表達(dá)式的識別。四、擴(kuò)展實(shí)驗(yàn)1、對所給算術(shù)表達(dá)式的文法G2，完成兩種以上不同的語法分析程序的設(shè)計(jì)與實(shí)現(xiàn)。2、在G2的基礎(chǔ)上，適當(dāng)

40、增加功能，如進(jìn)一步選擇高級語言中的賦值語句、復(fù)合語句、流程控制語句等其它類型的語法結(jié)構(gòu)作為分析對象。3、 對基本實(shí)驗(yàn)內(nèi)容進(jìn)行擴(kuò)充，增加語法分析過程的可視化展現(xiàn)功能。4、 研讀GCC，CLANG等開源編譯器的語法分析部分，分析其程序結(jié)構(gòu)、實(shí)現(xiàn)方法、識別的語法結(jié)構(gòu)等。5、 其它自選題目。注意自選擴(kuò)展實(shí)驗(yàn)須經(jīng)過實(shí)驗(yàn)指導(dǎo)教師同意并備案。實(shí)驗(yàn)三 語義分析程序設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康脑趯?shí)現(xiàn)詞法、語法分析程序的基礎(chǔ)上，編寫相應(yīng)的語義子程序，進(jìn)行語義處理，加深對語法制導(dǎo)翻譯原理的理解，進(jìn)一步掌握將語法分析所識別的語法范疇變換為某種中間代碼（四元式）的語義分析方法，并完成相關(guān)語義分析器的代碼開發(fā)。二、基本實(shí)驗(yàn)內(nèi)容

41、及要求對文法G2中的產(chǎn)生式添加語義處理子程序，完成運(yùn)算對象是簡單變量（標(biāo)識符）和無符號數(shù)的四則運(yùn)算的計(jì)值處理，將輸入的四則運(yùn)算轉(zhuǎn)換為四元式形式的中間代碼。輸入：包含測試用例（由標(biāo)識符、無符號數(shù)和+、*、/、(、)構(gòu)成的算術(shù)表達(dá)式）的源程序文件。輸出：將源程序轉(zhuǎn)換為中間代碼形式表示，并將中間代碼序列輸出到文件中。若源程序中有錯(cuò)誤，應(yīng)指出錯(cuò)誤信息。要求：1、結(jié)合實(shí)驗(yàn)一和實(shí)驗(yàn)二中的相關(guān)內(nèi)容，完成語法制導(dǎo)翻譯的程序設(shè)計(jì)。2、對完成的編譯系統(tǒng)進(jìn)行全面測試，供測試的例子應(yīng)包括符合語義規(guī)則的語句，以及分析程序能夠判別的若干錯(cuò)例，并給出執(zhí)行結(jié)果。三、實(shí)現(xiàn)方法1、語法制導(dǎo)翻譯一般實(shí)現(xiàn)方法說明語法制導(dǎo)翻譯模式是在

42、語法分析的基礎(chǔ)上，增加語義操作來實(shí)現(xiàn)的，實(shí)際上是對前后文無關(guān)文法的一種擴(kuò)展。一般而言，首先需要根據(jù)進(jìn)行的語義分析工作，完成對給定文法的必要拆分和語義動(dòng)作的編寫，從而為每一個(gè)產(chǎn)生式都配備相應(yīng)的語義子程序，以便在進(jìn)行語法分析的同時(shí)進(jìn)行語義解釋。即在語法分析過程中，每當(dāng)用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的語法分析動(dòng)作之外，還要調(diào)用相應(yīng)的語義子程序，以便完成生成中間代碼、查填有關(guān)表格、檢查并報(bào)告源程序中的語義錯(cuò)誤等工作。每個(gè)語義子程序需指明相應(yīng)產(chǎn)生式中各個(gè)符號的具體含義，并規(guī)定使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語義動(dòng)作。這樣，語法制導(dǎo)翻譯程序在對源程序從左到右進(jìn)行的一遍掃描中，既完成語

43、法分析任務(wù)，又完成語義分析和中間代碼生成方面的工作。本實(shí)驗(yàn)要求從編譯器的整體設(shè)計(jì)出發(fā)，重點(diǎn)通過對實(shí)驗(yàn)二中語法分析程序的擴(kuò)展，完成一個(gè)編譯器前端程序的編寫、調(diào)試和測試工作，形成一個(gè)將源程序翻譯為中間代碼序列的編譯系統(tǒng)。2、基于遞歸下降法的語法制導(dǎo)翻譯對文法G2在利用遞歸下降法進(jìn)行語法分析的同時(shí)，生成四元式形式的中間代碼序列。其語法制導(dǎo)翻譯程序的核心部分（指表達(dá)式E、項(xiàng)T和因式F的處理）的算法思想，可用程序4所示的框架描述。程序4 利用遞歸下降法生成簡單算術(shù)表達(dá)式的四元式序列E( ) /* 識別 */E1_PLACE=T( ); /*調(diào)用T( )分析產(chǎn)生算術(shù)表達(dá)式計(jì)算的第一項(xiàng)E1*/while (

44、SYM=+ | SYM=-)ADVANCE; /*使輸入串指針指向下一個(gè)輸入符號，即調(diào)用掃描器讀入下一個(gè)單詞符號*/E2_PLACE=T( ); /*調(diào)用T( )分析產(chǎn)生算術(shù)表達(dá)式計(jì)算的第二項(xiàng)*/T1=NewTemp( ); /*分配一個(gè)新的臨時(shí)變量，以便存儲(chǔ)計(jì)算結(jié)果*/GEN(, E1_PLACE, E2_PLACE, T1); /*根據(jù)所給實(shí)參產(chǎn)生一個(gè)四元式，送入四元式表*/E1_PLACE=T1; /*將計(jì)算結(jié)果作為下一次表達(dá)式計(jì)算的第一項(xiàng)*/return E1_PLACE;T( ) /* 識別*/T1_PLACE=F( );while (SYM=* | SYM=/)ADVANCE;T2

45、_PLACE=F( );T1=NewTemp( );GEN(*/, T1_PLACE, T2_PLACE, T1);T1_PLACE=T1;return T1_PLACE;F( ) /* 識別*/if (SYM=標(biāo)識符) /*在此設(shè)運(yùn)算對象i為標(biāo)識符，即簡單變量*/ADVANCE;return Entry(i.詞文); /*以標(biāo)識符的詞文為名字查、填符號表，可理解為返回標(biāo)識符的值*/elseif ( SYM=( )ADVANCE;PLACE=E( );if ( SYM=) )ADVANCE;return PLACE;else ERROR; /*例如：輸出“缺少）錯(cuò)誤”*/else ERROR;

46、 /*例如：輸出“算術(shù)表達(dá)式應(yīng)以標(biāo)識符或（開頭”*/說明： 程序四中出現(xiàn)的主要語義變量和輔助函數(shù)的功能為：E1_PLACE：文法符號E1的一個(gè)語義屬性，用于描述變量在符號表中登記項(xiàng)的序號（0時(shí)）或臨時(shí)變量的編號（0時(shí)），可理解為代表其值。void GEN(char *Op, char *Arg1, char *Arg2, char *Result)：用來生成一個(gè)四元式，將其送到四元式表中。參考代碼如下：void GEN(char *Op, char *Arg1, char *Arg2, char *Result)strcpy (pQuadNXQ.op, Op); /*pQuad為全局變量，是用于存放四元式的數(shù)組*/strcpy (pQuadNXQ.arg1, Arg1);strcpy