《編譯原理》實驗指導(dǎo)書-城市學(xué)院

1、編譯原理實驗指導(dǎo)書實驗?zāi)康暮蛢?nèi)容編譯原理實驗的目的是使學(xué)生將編譯理論運用到實際當(dāng)中，實現(xiàn)一個簡單語言集的詞法、語法和語義分析程序，驗證實際編譯系統(tǒng)的實現(xiàn)方法，并加深對編譯技術(shù)的認(rèn)識。實驗內(nèi)容共需實現(xiàn)編譯器的詞法、語法和語義分析程序三個組成部分。要求學(xué)生必須完成每個實驗的基本題目要求，有余力的同學(xué)可嘗試實驗的擴展要求部分。實驗報告要求每人針對所完成的實驗內(nèi)容上交一份實驗報告，其中主要包括三方面內(nèi)容：1、實驗設(shè)計：實驗采用的實現(xiàn)方法和依據(jù)（如描述語言的文法及其機內(nèi)表示，詞法分析的單詞分類碼表、狀態(tài)轉(zhuǎn)換圖或狀態(tài)矩陣等，語法分析中用到的分析表或優(yōu)先矩陣等，語法制導(dǎo)翻譯中文法的拆分和語義動作的設(shè)計編寫等

2、）；具體的設(shè)計結(jié)果（應(yīng)包括整體設(shè)計思想和實現(xiàn)算法，程序結(jié)構(gòu)的描述，各部分主要功能的說明，以及所用數(shù)據(jù)結(jié)構(gòu)的介紹等）。2、程序代碼：實驗實現(xiàn)的源程序，要求符合一般的程序書寫風(fēng)格，并包括必要的注釋。3、實驗結(jié)果分析：自行編寫若干源程序作為測試用例，對所生成的編譯程序進行測試（編譯程序的輸入與輸出以文件的形式給出）；運行結(jié)果分析（至少包括一個正確和一個錯誤單詞或語句的運行結(jié)果）；以及改進設(shè)想等。另外，在實驗報告的最后，歡迎每位同學(xué)寫上對每個實驗的收獲、體會，特別是希望和建議，以利于今后不斷改進教學(xué)，積累經(jīng)驗。注意事項1、電子版實驗報告和源程序在最后一次機時后的一周內(nèi)上交。（每個同學(xué)上交一個壓縮文件，

3、其命名格式為“學(xué)號_姓名.rar”，內(nèi)含實驗報告和一個命名為“源程序”的文件夾。注意提交的源程序應(yīng)是經(jīng)過調(diào)試、測試成功的較為通用的程序，并應(yīng)有相應(yīng)的注釋、運行環(huán)境和使用方法簡介。）2、不接受不完整的實驗報告和沒有說明注釋的源程序，或者說明與程序、運行結(jié)果不符合的作業(yè)。特別鼓勵：擴展題目1、為親身經(jīng)歷一個小型編譯器的開發(fā)全過程，觸摸一下與實際編譯器開發(fā)相關(guān)的工作，大家可以自由組成3人左右的小組，推舉組長，模擬一個團隊分工協(xié)作開發(fā)大型軟件的實戰(zhàn)環(huán)境，融入軟件工程的思想規(guī)范和一般理論方法，初步體驗從系統(tǒng)分析設(shè)計、編碼測試到交付維護的一個完整編譯器軟件的開發(fā)過程。要求組長為每個小組成員分配主要負(fù)責(zé)的任

4、務(wù)，完成相應(yīng)的分析設(shè)計員、程序員和測試員等角色的工作，并以小組為單位提交一份實驗報告和源程序，在報告封面上寫明每個同學(xué)主要完成和負(fù)責(zé)的部分。2、以組為單位完成的實驗內(nèi)容至少必須整合詞法、語法和語義三個部分的實驗，對于選定的適當(dāng)規(guī)模的文法（如C語言的一個大小適宜的子集），進行系統(tǒng)的總體設(shè)計、功能分析、編碼測試等工作。完成一個從對源程序的詞法分析開始，到中間代碼生成的完整的編譯器前端的開發(fā)，使所涉及到的編譯系統(tǒng)的各個組成模塊有機地銜接在一起，提交一份完整的實驗報告和源程序，并將以下幾個方面描述清楚：1）任務(wù)概述2）系統(tǒng)的設(shè)計3）系統(tǒng)實現(xiàn)（包括框圖，各.h和.c文件說明，所有函數(shù)功能的說明，數(shù)據(jù)結(jié)構(gòu)

5、、各種表格、變量等的說明，以及函數(shù)調(diào)用關(guān)系圖等）4）系統(tǒng)工作過程及運行說明（使用操作指南）5）源程序清單（要求有詳細(xì)注釋）和實例程序運行結(jié)果6）體會和討論3、實驗題目1）參考題目：在詞法、語法和語義三個基本實驗題目的基礎(chǔ)上，完成以下擴展部分的要求：實驗一：（1）擴充關(guān)鍵字的數(shù)目、增加單詞類別（如分界符、邏輯運算符等）、將常數(shù)分成字符串常量、整型常量和實型常量等；添加詞法分析中單詞出錯的位置、加細(xì)錯誤類型的檢查以及刪除注釋部分等；并考慮如何在詞法分析階段建立變量名表和常數(shù)表，以備后續(xù)的編譯過程查詢。（2）選作：識別一個程序設(shè)計語言（如C語言）所有單詞的詞法分析程序設(shè)計。建議自學(xué)LEX系統(tǒng)。實驗二

6、：（1）至少完成文法G2的兩種典型的語法分析程序的設(shè)計與實現(xiàn)。（2）在所給文法G2的基礎(chǔ)上，適當(dāng)擴大分析對象，增加功能。如賦值語句的左部不再只局限于簡單變量和常數(shù)，可以是下標(biāo)變量等；右部的算術(shù)表達式中可以包括函數(shù)調(diào)用、數(shù)組元素等。除賦值語句外，還可進一步選擇高級語言的其它語法結(jié)構(gòu)類型，如流程控制語句、子程序結(jié)構(gòu)語句、說明語句等。語法分析的結(jié)果以語法樹的形式輸出，并顯示分析過程的信息（如分析棧、符號棧、當(dāng)前應(yīng)被歸約的最左子串、歸約后所得的符號等）。（3）增強錯誤檢查和處理能力。例如，當(dāng)輸入的源程序存在錯誤時，把所發(fā)現(xiàn)的每一處錯誤的性質(zhì)（錯誤編碼）和位置填入一張表中，以備以后輸出之用；同時再跳過錯

7、誤所在的語法范疇（如單詞、表達式、語句等），繼續(xù)對輸入串的后續(xù)部分進行編譯。至于對錯誤的具體處理措施應(yīng)結(jié)合所采用的語法分析方法，以LR分析為例，可對LR分析表中的空白單元進行出錯原因分析，填入一個指向出錯處理子程序的指示字。（4）選作：學(xué)習(xí)編譯器的自動生成工具LEX、YACC（或其它類似工具）的使用方法，運用LEX和YACC編寫并生成以下文法G所定義語言的詞法和語法分析程序。G： PROGRAM; BEGINEND. VAR; : | :; INTEGER | REAL | , | ; | | | := IFTHENELSE WHILEDO BEGINEND | + | - | * | / |

8、 | () | | | | | | | = | A|B|C|X|Y|Z|a|b|c|x|y|z 0|1|2|9實驗三：（1）增加語義分析的范圍，如進一步完成布爾表達式（參見教材P200）、常見程序流程控制語句（參見教材P205）等的翻譯。（2）語法制導(dǎo)翻譯過程的可視化處理，選擇編譯各階段用到的典型算法實現(xiàn)其動態(tài)演示。（3）選作：完成實驗二中文法G所定義的語言的語法制導(dǎo)翻譯程序。2）自擬題目：根據(jù)小組成員的興趣自主選擇或自定實驗題目。要求先提交一份申請文檔，說明所選題目、實現(xiàn)方案和技術(shù)路線；然后小組成員再與教師就題目的難易程度和工作量具體討論調(diào)整，細(xì)化課程設(shè)計內(nèi)容，最終確定要完成的主要工作；在得

9、到老師的認(rèn)可之后方可繼續(xù)進行。實驗一 詞法分析程序?qū)崿F(xiàn)一、實驗?zāi)康呐c要求通過編寫和調(diào)試一個詞法分析程序，掌握在對程序設(shè)計語言的源程序進行掃描的過程中，將字符形式的源程序流轉(zhuǎn)化為一個由各類單詞符號組成的流的詞法分析方法。二、實驗內(nèi)容根據(jù)教學(xué)要求并結(jié)合學(xué)生自己的興趣和具體情況，從具有代表性的高級程序設(shè)計語言的各類典型單詞中，選取一個適當(dāng)大小的子集。例如，可以完成無符號常數(shù)這一類典型單詞的識別后，再完成一個盡可能兼顧到各種常數(shù)、關(guān)鍵字、標(biāo)識符和各種運算符的掃描器的設(shè)計和實現(xiàn)。輸入：由符合和不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序文件。輸出：把單詞的字符形式表示翻譯成編譯器的內(nèi)部表示，確定單詞

10、串的輸出形式，并將其結(jié)果放到某個文件中。要求所輸出的每一單詞均按形如（CLASS，VALUE）的二元式編碼。對于變量和常數(shù)，CLASS字段為相應(yīng)的類別碼；VALUE字段則是該標(biāo)識符、常數(shù)的具體值或在其符號表中登記項的序號（要求在變量名表登記項中存放該標(biāo)識符的字符串；常數(shù)表登記項中則存放該常數(shù)的二進制形式）。對于關(guān)鍵字和運算符，采用一詞一類的編碼形式；由于采用一詞一類的編碼方式，所以僅需在二元式的CLASS字段上放置相應(yīng)的單詞的類別碼，VALUE字段則為“空”。不過，為便于查看由詞法分析程序所輸出的單詞串，要求在CLASS字段上放置單詞類別的助記符。三、實現(xiàn)方法與環(huán)境詞法分析是編譯程序的第一個處

11、理階段，可以通過兩種途徑來構(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)造詞法分析程序的另外一種途徑是所謂的詞法分析程序的自動生成，即首先用正規(guī)式對語言中的各類單詞符號進行詞型描述，并分別指出在識別單詞時，詞法分析程序所應(yīng)進行的語義處理工作，然后由一個所謂詞法分析程序的構(gòu)造程序?qū)ι鲜鲂畔⑦M行加工。如美國BELL實驗室研制的LEX就是一個被廣泛使用的詞法分析程序的自

12、動生成工具?？偟膩碚f，開發(fā)一種新語言時，由于它的單詞符號在不停地修改，采用LEX等工具生成的詞法分析程序比較易于修改和維護。一旦一種語言確定了，則采用手工編寫詞法分析程序效率更高。四、基本實驗題目題目1：試用手工編碼方式構(gòu)造識別以下給定單詞的某一語言的詞法分析程序。語言中具有的單詞包括五個關(guān)鍵字begin、end、if、then、else；標(biāo)識符；整型常數(shù)；六種關(guān)系運算符；一個賦值符和四個算術(shù)運算符。參考實現(xiàn)方法簡述如下。單詞的分類：構(gòu)造上述語言中的各類單詞符號及其分類碼表。表I 語言中的各類單詞符號及其分類碼表單詞符號類別編碼類別碼的助記符單詞值begin1BEGINend2ENDif3IF

13、then4THENelse5ELSE標(biāo)識符6ID字母打頭的字母數(shù)字串整常數(shù)7INT數(shù)字串8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI處理過程：在一個程序設(shè)計語言中，一般都含有若干類單詞符號，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖，然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖，即得到了一個有限自動機，再進行必要的確定化和狀態(tài)數(shù)最小化處理，最后據(jù)此構(gòu)造詞法分析程序。在此為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問題的糾纏，假定要編譯的語言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識符；在源程序的輸入文本中，關(guān)鍵字、標(biāo)識

14、符、整常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運算符以及賦值符，則至少須用一個空白字符加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標(biāo)識符的識別統(tǒng)一進行處理。即每當(dāng)開始識別一個單詞時，若掃視到的第一個字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依次進行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個盡可能長的字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表已事先造好），若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識符。采用上述策略后，針對表I中部分單詞可以構(gòu)造一個如圖1所示的有限自動機（以狀態(tài)轉(zhuǎn)換圖表示）。在圖1中添加了當(dāng)進行狀態(tài)轉(zhuǎn)移時，詞法分析程序應(yīng)執(zhí)行的語義動作。根據(jù)圖1，可用

15、C語言編寫出符合以上幾項要求的一個相應(yīng)的掃描器程序，如程序一所示。圖1 識別表I所列語言中的部分單詞的DFA及相關(guān)的語義過程圖1及程序一中所出現(xiàn)的語義變量及語義函數(shù)的含義和功能說明如下：函數(shù)GETCHAR：每調(diào)用一次，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量ch，然后把掃描指示器前推一個字符位置。字符數(shù)組TOKEN：用來依次存放一個單詞詞文中的各個字符。函數(shù)CAT：每調(diào)用一次，就把當(dāng)前ch中的字符拼接于TOKEN中所存字符串的右邊。函數(shù)LOOKUP：每調(diào)用一次，就以TOKEN中的字符串查保留字表，若查到，就將相應(yīng)關(guān)鍵字的類別碼賦給整型變量c；否則將c置為零。函數(shù)RETRACT：每調(diào)用一

16、次，就把掃描指示器回退一個字符位置（即退回多讀的那個字符）。函數(shù)OUT：一般僅在進入終態(tài)時調(diào)用此函數(shù)，調(diào)用的形式為OUT(c，VAL)。其中，實參c為相應(yīng)單詞的類別碼或其助記符；當(dāng)所識別的單詞為標(biāo)識符和整數(shù)時，實參VAL為TOKEN（即詞文分別為字母數(shù)字串和數(shù)字串），對于其余種類的單詞，VAL均為空串。函數(shù)OUT的功能是，在送出一個單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個程序。程序一 根據(jù)圖1編寫的掃描器# include # include # include # define ID 6# define INT 7# define LT 8# define LE 9# define

17、 EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20；extern int lookup (char*);extern 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)T

18、OKENi=ch; i+；ch=fgetc (fp);TOKENi= 0fseek(fp,-1,1); /* retract*/c=lookup (TOKEN);if (c=0) 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,

19、 );else if(ch=) out (NE, );elsefseek (fp,-1,1);out (LT, );break;case =: out(EQ, ); break;case : ch=fgetc(fp);if(ch=)out(GE, );elsefseek(fp,-1,1);out(GT, );break;default: report_error( ); break;return;提示：掃描器所用的若干函數(shù)以及主程序有待于具體編寫，并需事先建立好保留字表，以備查詢。例如：/* 建立保留字表 */#define MAX_KEY_NUMBER 20 /*關(guān)鍵字的數(shù)量*/#defin

20、e KEY_WORD_END “waiting for your expanding” /*關(guān)鍵字結(jié)束標(biāo)記*/char *KeyWordTableMAX_KEY_NUMBER=“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) /*比較toke

21、n所指向的關(guān)鍵字和保留字表中哪個關(guān)鍵字相符*/return n+1; /*根據(jù)單詞分類碼表I，設(shè)置正確的關(guān)鍵字類別碼，并返回此類別碼的值*/break;n+;return 0; /*單詞不是關(guān)鍵字，而是標(biāo)識符*/另外，在掃描源程序字符串時，一旦識別出關(guān)鍵字、標(biāo)識符、整常數(shù)以及運算符中之一，即以二元式形式（類別編碼，值）輸出單詞到指定文件中。每次調(diào)用該詞法分析程序，它均能自動繼續(xù)掃描下去，形成下一個單詞，直至整個源程序全部掃描完畢，并形成相應(yīng)的單詞串形式的源程序文件。題目2：將表I單詞集中的整常數(shù)改為無符號常數(shù), 修改題目1中已開發(fā)的掃描器。無符號常數(shù)的單詞分類碼助記符：UCON；其值為無符號常

22、數(shù)的機內(nèi)二進制表示。描述無符號數(shù)的正規(guī)文法和狀態(tài)轉(zhuǎn)換圖：無符號數(shù)的右線性文法G1如下：無符號數(shù) d余留無符號數(shù)無符號數(shù) 小數(shù)部分無符號數(shù) d余留無符號數(shù) d余留無符號數(shù)余留無符號數(shù) 十進小數(shù)余留無符號數(shù) E指數(shù)部分余留無符號數(shù) d余留無符號數(shù) 十進小數(shù) E指數(shù)部分十進小數(shù) d十進小數(shù)十進小數(shù) d小數(shù)部分 d十進小數(shù)小數(shù)部分 d指數(shù)部分 d余留整指數(shù)指數(shù)部分 +整指數(shù)指數(shù)部分 -整指數(shù)指數(shù)部分 d整指數(shù) d余留整指數(shù)整指數(shù) d余留整指數(shù) d余留整指數(shù)余留整指數(shù) d圖2所示為上述文法的狀態(tài)轉(zhuǎn)換圖，其中編號0、1、2、6分別代表非終結(jié)符號、及。圖2 文法G1的狀態(tài)轉(zhuǎn)換圖實現(xiàn)無符號數(shù)識別的參考方法：在

23、計算機內(nèi)實現(xiàn)狀態(tài)轉(zhuǎn)換圖的方法之一，是以狀態(tài)圖中的各個狀態(tài)為行，以可能輸入的各個輸入符號為列，組成一個狀態(tài)矩陣。其中，矩陣的元素用來指明下一個狀態(tài)和掃描器應(yīng)完成的語義動作（如拼接字符、數(shù)制轉(zhuǎn)換、查填符號表以及輸出單詞的內(nèi)部表示等）。由于在一個狀態(tài)矩陣中，通常有許多狀態(tài)都是出錯狀態(tài)，為了節(jié)省存放狀態(tài)矩陣的存儲空間，在具體實現(xiàn)時，常常采用更為緊湊和有效的數(shù)據(jù)結(jié)構(gòu)。例如，對于文法G1的狀態(tài)轉(zhuǎn)換圖，可按表II的形式來存放其狀態(tài)矩陣。表II中的第一列為各狀態(tài)Si的編號，第二列分別列出了在每一狀態(tài)下可能掃視到的輸入符號aj（其中“other”是一個符號集合，用來表示在相應(yīng)狀態(tài)所屬的那一欄中，除其前所列字符之

24、外的全部其它字符），第三列指出當(dāng)（Si,aj）出現(xiàn)時應(yīng)執(zhí)行的語義動作（通常用若干個語句來實現(xiàn)，若其為空，則表示不進行任何處理），最后一列用來指明下一狀態(tài)的編號（若其為NULL或“結(jié)束”則表示無后繼狀態(tài)）。狀態(tài)矩陣中所嵌入的語義動作，其功能是在掃描源程序字符串的過程中，把識別出的字符串形式的無符號數(shù)的值，逐步轉(zhuǎn)換為相應(yīng)的二進制整數(shù)（ICON）或二進制浮點數(shù)（FCON）的內(nèi)部形式，方法詳見教材第56頁。（注：考慮能否采用C語言的庫函數(shù)實現(xiàn)此語義處理工作。）表II 包含語義處理過程的識別無符號數(shù)的狀態(tài)矩陣根據(jù)加入語義過程說明的識別無符號數(shù)的狀態(tài)矩陣，編寫詞法分析程序，部分實現(xiàn)代碼如程序二所示。程序二

25、 單詞分類碼為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 Cla

26、ss; /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 (E

27、rror!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:sw

28、itch (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=

29、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:

30、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(

31、 );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 9

32、4 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 五、注意1、上機前的準(zhǔn)備：完成詞法分析程序的程序流圖，并選擇好相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。2、編程：用C語言或你熟悉的其它高級程序設(shè)計語言編寫一個規(guī)模適當(dāng)?shù)膾呙杵鳌?、調(diào)試：將各個模塊連接成一個完整程序，并整體調(diào)試成功。4、測試：用于測試掃描器的

33、實例源文件中應(yīng)有詞法正確的，也應(yīng)有錯誤的字符串，并至少應(yīng)包含兩行以上的源代碼。5、輸出結(jié)果：對于輸入的測試用例的源程序文件，以對照的形式將掃描器的分析結(jié)果在輸出文件中表示出來，必要時給出錯誤提示信息。例如，輸入：“1.5E2+100”，輸出：（UCON，0.015）對應(yīng)“1.5E2”（PL， ）對應(yīng)“+”（UCON，100）對應(yīng)“100”實驗二 語法分析程序?qū)崿F(xiàn)一、實驗?zāi)康呐c要求通過設(shè)計、編制、調(diào)試一個典型的語法分析程序（任選有代表性的語法分析方法，如算符優(yōu)先法、遞歸下降法、LL(1)、SLR(1)、LR(1)等，作為編制語法分析程序的依據(jù)），對掃描器所提供的單詞序列進行語法檢查和結(jié)構(gòu)分析，實

34、現(xiàn)并進一步掌握常用的語法分析方法。二、實驗內(nèi)容選擇對各種常見高級程序設(shè)計語言都較為通用的語法結(jié)構(gòu)作為分析對象，給出其文法描述（注意應(yīng)與所采用的語法分析方法比較貼近），設(shè)計并實現(xiàn)一個完整的語法分析程序（分析過程暫不嵌入任何的語義動作）。輸入：由實驗一輸出的單詞串，例如：UCON，PL，UCON 輸出：對于輸入的符號串，若是給定文法定義的合法句子，則輸出“RIGHT”，并且給出每一步分析過程；若不是句子，即輸入串有錯誤，則輸出“ERROR”，并且顯示分析至此所得的中間結(jié)果，如分析棧、符號棧中的信息等，以及必要的出錯說明信息。三、一般實現(xiàn)方法說明例如，以如下文法G2所定義的算術(shù)表達式的賦值語句作為分

35、析對象，編寫并調(diào)試一個語法分析程序。G2： beginend |; := | + | - | * | / | | () | | | | | A|B|C|X|Y|Z|a|b|c|x|y|z 0|1|2|9說明：1）可將以上文法G2中的語法范疇替換為實驗一中的文法G1，并將單詞類型無符號常數(shù)進一步細(xì)分成整數(shù)和浮點數(shù)兩類單詞。2）注意修改實驗一中的詞法分析程序，將它編寫為子程序的形式，以便供語法分析程序調(diào)用，從而在對源程序的一遍掃描過程中，同時完成詞法和語法分析任務(wù)。3）應(yīng)加強錯誤檢查，對輸入符號串中的詞法、語法錯誤，給出必要的說明信息，盡可能多地、確切地指出錯誤的位置、原因和性質(zhì)。例如，在詞法分析

36、階段，對當(dāng)前正在處理的字符ch，可進一步定義一些與該字符相關(guān)的信息row和col，分別表示該字符所在的行和列，這些內(nèi)容在出錯處理時用來提供和源程序位置相關(guān)的信息。即定義：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*/四、基本實驗題目題目：對算術(shù)表達式的一個簡化子集，根據(jù)如下其語法結(jié)構(gòu)的BNF定義G3，任選學(xué)過的一種語法分析方

37、法，針對運算對象為無符號數(shù)的四則運算，編制一個語法分析程序。G3： | + | - | * | / | ()若將非終結(jié)符號、和分別用E、T、F和i代表，則G3可寫成：ET|E+T|E-T TF|T*F|T/F Fi|(E)下面簡要給出基于遞歸下降法、預(yù)測分析法、算符優(yōu)先法、SLR(1)四種語法分析程序的開發(fā)方法示例說明。示例一：采用具有遞歸功能的高級語言編制遞歸下降法的語法分析程序。運算對象i可以進一步定義為變量、常數(shù)等，例如，此處將i定義為：i A|B|C|X|Y|Z利用擴充的BNF消除G3E中E和T的左遞歸后，采用遞歸下降法分析上述算術(shù)表達式的框圖見圖3。其中ZC過程為總控程序，被設(shè)計成可

38、以分析無窮多個算術(shù)表達式，主要完成：1）通知外界鍵入算術(shù)表達式。2）控制E過程分析算術(shù)表達式。3）根據(jù)分析結(jié)果之正誤，分別輸出不同的信息。圖3 遞歸下降法分析算術(shù)表達式的框圖(a) ZC過程 (b) E過程 (c) T過程 (d) F過程 (e) SYM函數(shù) (f) ADVANCE過程E、T和F三個過程分別對應(yīng)、和三個產(chǎn)生式的處理。它們利用到兩個公共函數(shù)：一個是函數(shù)SYM，它負(fù)責(zé)從輸入字符串ST中取出下一個字符，并存入SYM中等待分析；另一個是ADVANCE過程，負(fù)責(zé)剔除ST中的首字符，可通過挪動字符串指針的辦法來實現(xiàn)。實際上是通過調(diào)用詞法分析程序來實現(xiàn)SYM和ADANCE功能的。變量TZ之值

39、標(biāo)志分析的結(jié)果（表達式是否有錯）。示例二：基于預(yù)測分析法的語法分析程序。參考教材P121例4.3，首先編寫無二義性的簡單算術(shù)表達式的文法（4.1），并通過消除左遞歸對其進行改寫。然后求出如表4-1所示的各個FIRST集和FOLLOW集。再檢查是不是LL(1)文法，并按照LL(1)文法構(gòu)造如表4-2所示的預(yù)測分析表。最后根據(jù)預(yù)測分析器的工作流程，實現(xiàn)預(yù)測分析器的控制程序。示例三：用C語言編制算符優(yōu)先分析法的語法分析程序如程序三所示。其中使用了分析棧stack，用來在分析過程中存放當(dāng)前句型的某一前綴，一旦句型的最左素短語在棧頂形成，便立即進行歸約。程序三 算符優(yōu)先分析算法#define RIGHT

40、 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, int); /* priority detection */int IsEqualTo (int, int); /* priority detection */int Reduce (int b

41、egin, 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 separately */stack0= #;doint j;r=ai+;if (IsVt(stackk) j=k; else j=k-1;while (IsHigherThan(stackj,r

42、)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 stackk */ /*end of while*/if (IsLowerThan(stackj,r) | IsEqualTo(stackj,r)stack+k=r;else return ERR

43、OR; while (r!=#);return RIGHT;首先，對于分析對象，如無符號數(shù)的四則運算編寫文法G3，確定一種合適的數(shù)據(jù)結(jié)構(gòu)，以構(gòu)造所給文法的機內(nèi)表示。然后，構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣。在此可以根據(jù)算術(shù)表達式中各算符的優(yōu)先級和結(jié)合性，直接手工構(gòu)造算符優(yōu)先關(guān)系。最后，編寫程序三中所用到的各個函數(shù)，完成整個算符優(yōu)先語法分析器的開發(fā)。另外，如果我們希望在分析過程中為句子建立一棵“語法樹”，則可在每移進一個終結(jié)符號時，就建立一個末端結(jié)點；而在用某一產(chǎn)生式將句型的最左素短語歸約為某個非終結(jié)符號N時，就建立以N為標(biāo)記的結(jié)點，此結(jié)點的各子結(jié)點（從左到右）依次是最左素短語的各個符號。示例四：SL

44、R(1)分析器的開發(fā)?？梢愿鶕?jù)文法G3構(gòu)造識別其全部活前綴的DFA，再據(jù)此構(gòu)造SLR(1)分析表，然后編程實現(xiàn)SLR(1)分析表的驅(qū)動程序，即LR分析器的總控程序，完成對算術(shù)表達式的識別。五、注意1、上機前的準(zhǔn)備：結(jié)合題目的要求，確定語法分析程序的流程圖，同時考慮相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用C或其它高級語言初步編寫一個語法分析源程序。2、調(diào)試：將詞法、語法分析合在一起構(gòu)成一個完整的程序，并調(diào)試成功。3、測試：供測試的例子應(yīng)包括符合語法規(guī)則的語句，以及分析程序能夠判別的若干錯例。4、結(jié)果輸出：對于所輸入的字符串，不論對錯，都應(yīng)有明確的信息告訴外界。5、編寫的源程序中應(yīng)有較為詳細(xì)的說明和注釋。例如，對文法機

45、內(nèi)表示的解釋、數(shù)據(jù)結(jié)構(gòu)的說明、函數(shù)的作用、全局變量的含義等等。實驗三 語義分析程序?qū)崿F(xiàn)一、實驗?zāi)康呐c要求在實現(xiàn)詞法、語法分析程序的基礎(chǔ)上，編寫相應(yīng)的語義子程序，進行簡單的語義處理，加深對語法制導(dǎo)翻譯原理的理解，進一步掌握將語法分析所識別的語法范疇變換為某種中間代碼（四元式）的語義分析方法，并完成相關(guān)語義分析器的代碼開發(fā)。二、實驗內(nèi)容語法制導(dǎo)翻譯模式是在語法分析的基礎(chǔ)上，增加語義操作來實現(xiàn)的。對于給定文法中的每一產(chǎn)生式，編寫相應(yīng)的語義子程序。在語法分析過程中，每當(dāng)用一個產(chǎn)生式進行推導(dǎo)或歸約時，語法分析程序除執(zhí)行相應(yīng)的語法分析動作之外，還要調(diào)用相應(yīng)的語義子程序，以便完成生成中間代碼、查填有關(guān)表格、

46、檢查并報告源程序中的語義錯誤等工作。每個語義子程序需指明相應(yīng)產(chǎn)生式中各個符號的具體含義，并規(guī)定使用該產(chǎn)生式進行分析時所應(yīng)采取的語義動作。這樣，語法制導(dǎo)翻譯程序在對源程序從左到右進行的一遍掃描中，既完成語法分析任務(wù)，又完成語義分析和中間代碼生成方面的工作。輸入：包含測試用例，如由無符號數(shù)和+、*、/、(、)構(gòu)成的算術(shù)表達式的源程序文件。輸出：將源程序轉(zhuǎn)換為中間代碼形式表示，并將中間代碼序列輸出到文件中。若源程序中有錯誤，應(yīng)指出錯誤信息。三、一般實現(xiàn)方法語法制導(dǎo)翻譯模式實際上是對前后文無關(guān)文法的一種擴展。一般而言，首先需要根據(jù)進行的語義工作，完成對文法的必要拆分和語義動作的編寫，從而為每個產(chǎn)生式都

47、配備相應(yīng)的語義子程序，以便在進行語法分析的同時進行語義解釋。要求從編譯器的整體設(shè)計出發(fā)，重點通過對實驗二中語法分析程序的擴展，完成一個編譯器前端程序的編寫、調(diào)試和測試工作，形成一個將源程序翻譯為中間代碼序列的編譯系統(tǒng)。四、基本實驗題目題目：對文法G3中的產(chǎn)生式添加語義處理子程序，完成無符號數(shù)的四則運算的計值處理，輸出運算結(jié)果；或者將輸入的四則運算轉(zhuǎn)換為四元式形式的中間代碼。例如，對文法G3在利用遞歸下降法進行語法分析的同時，生成四元式形式的中間代碼序列。其語法制導(dǎo)翻譯程序的核心部分（指表達式、項和因式的處理）的算法思想，可用程序四所示的框架描述。程序四 利用遞歸下降法生成簡單算術(shù)表達式的四元式

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

49、_PLACE;T( ) /* 識別*/T1_PLACE=F( );while (SYM=* | SYM=/)ADVANCE;T2_PLACE=F( );T1=NewTemp( );GEN(*/, T1_PLACE, T2_PLACE, T1);T1_PLACE=T1;return T1_PLACE;F( ) /* 識別*/if (SYM=標(biāo)識符) /*在此設(shè)運算對象i為標(biāo)識符，即簡單變量*/ADVANCE;return Entry(i.詞文); /*以標(biāo)識符的詞文為名字查、填符號表，可理解為返回標(biāo)識符的值*/elseif ( SYM=( )ADVANCE;PLACE=E( );if ( SYM=) )ADVANCE;return PLACE;else ERROR; /*例如：輸出“缺少）錯誤”*/else ERROR; /*例如：輸出“算術(shù)表達式應(yīng)以標(biāo)識符或（開頭”*/說明：1）程序四中出現(xiàn)的主要語義變量和輔助函數(shù)的功能為：E1_PLACE：文法符號E1的一個語義屬性，用于描述變量在符號表中登記項的序號（0時）或臨時變量的編號（0時），可理解為代表其值。void GEN(char *Op, char *Arg1, char *