北外0513編譯原理在線開放式作業(yè)答案

0513《編譯原理》在線開放式作業(yè)實施方案作業(yè)內(nèi)容要求：完成掃描程序的設(shè)計與實現(xiàn)，具體要求為：?設(shè)計并實現(xiàn)TINYC語言的掃描程序；?完成并提交實驗報告，掃描程序的源程序，編譯后的可執(zhí)行程序，例子和運行結(jié)果.實驗報告至少要包含如下內(nèi)容：1實驗?zāi)康模?TINYC語言的詞法說明，掃描器的輸入和輸出；3實驗原理（所采用的過程）；記號種類及各記號所代表的字符串集合；各記號對應(yīng)的正則表達(dá)式及所有記號對應(yīng)的正則表達(dá)式；各記號對應(yīng)的DFA及所有記號對應(yīng)的DFA;4掃描程序的功能說明和程序說明,程序模塊等；5輸入示例及其運行結(jié)果；6總結(jié):獲得的經(jīng)驗，遇到的問題，改進(jìn)方案等.格式及提交要求：1、學(xué)生須按以上要求完成實驗報告作業(yè)。2、在word文檔中完成實驗報告；使用"北京師范大學(xué)網(wǎng)絡(luò)教育課程論文”做為論文封面；正文使用宋體五號字；標(biāo)題加粗。北京師范大學(xué)網(wǎng)絡(luò)教育課程作業(yè)課程代碼：課程名稱：學(xué)習(xí)中心 姓 名 學(xué) 號 專 業(yè) 年 級 實驗?zāi)康?完整地指出TINYC的詞法結(jié)構(gòu)，也就是：定義記號和它們的特性實驗內(nèi)容；TINYC的記號分為3個典型類型：保留字、特殊符號和“其他”記號。保留字一共有8個，它們的含義類似。特殊符號有10種：分別是4種基本的整數(shù)運算符號、2種比較符號，以及括號、分號和賦值符號。除了賦值符號是兩個字符的長度之外，其余均為一個字符。表1TINYC語言的記號保留字特殊符號其他if+數(shù)（1個或更多的數(shù)字）then else*end/repeatuntil<標(biāo)識符（1個或更多的字母）read(write);:=其他記號就是數(shù)了，它們是一個或多個數(shù)字以及標(biāo)識符的序列，而標(biāo)識符又是（為了簡便）一個或多個字母的序列。除了記號之外，TINYC還要遵循以下的詞法慣例：注釋應(yīng)放在花括號｛...｝中，且不可嵌套；代碼應(yīng)是自由格式；空白格由空格、制表位和新行組成；最長子串原則后須接識別記號。在為該語言設(shè)計掃描程序時，可以從正則表達(dá)式開始并根據(jù)前一節(jié)中的算法來開發(fā)NFA和DFA。實際上，前面已經(jīng)給出了數(shù)、標(biāo)識符和注釋的正則表達(dá)式。其他記號的正則表達(dá)式都是固定串，因而均不重要。由于掃描程序的DFA記號十分簡單，所以無需按照這個例程就

可直接開發(fā)這個DFAY。我們按一下步驟進(jìn)行。首先要注意到除了賦值符號之外，其他所有的特殊符號都只有一個字符，這些符號的DFA如下:returnPLUSreturnreturnPLUSreturnMINUSreturnSEMI在該圖中，不同的接受狀態(tài)是由掃描程序返回的記號區(qū)分開來。如果在這個將要返回的記號（代碼中的一個變量）中使用其他指示器，則所有接受狀態(tài)都可集中為一個狀態(tài)，稱之為DONE。若將這個二狀態(tài)的DFA與接受數(shù)和標(biāo)識符的DFA合并在一起，就可得到下面的DFA：請注意，利用方括號指出了不可被消耗的先行字符?，F(xiàn)在需要在這個DFA中添加注釋、空白格和賦值。一個簡單的從初始狀態(tài)到其本身的循環(huán)要消耗空白格。注釋要求一個額外的狀態(tài)，它由花括號左邊達(dá)到并在花括號右邊返回到它。賦值也需要中間狀態(tài)，它由分號上的初始狀態(tài)達(dá)到。如果后面緊跟有一個等號，那么就會生成一個賦值記號。反之就不消耗下一個字符，且生成一個錯誤記號。實際上，未列在特殊符號中的所有單個字符既不是空白格或注釋，也不是數(shù)字或字母，它們應(yīng)被作為錯誤而接受，我們將它們與單個字符符號混合在一起。如下圖是為掃描程序給出的最后一個DFA。在上面的討論或上圖中的DFA都未包括保留字。這是因為根據(jù)DFA的觀點，而認(rèn)為保留字與標(biāo)識符相同，以后再在接受后的保留字表格中尋找標(biāo)識符是最簡單的。當(dāng)然，最長子串原則保證了掃描程序唯一需要改變的動作是被返回的記號。因為，僅在識別了標(biāo)識符之后才考慮保留字?，F(xiàn)在再來討論實現(xiàn)這個DFA的代碼，它已被放在了scan.h文件和scan.c文件之中。其中最主要的過程是getToken，它消耗輸入字符并根據(jù)上圖中的DFA返回下一個被識別的記號。這個實現(xiàn)利用了雙重嵌套情況分析，以及一個有關(guān)狀態(tài)的大型情況列表，在大列表中的是基于當(dāng)前輸入字符的單獨列表。記號本身被定義成globals.h中的枚舉類型，它包括在表1中列出的所有記號以及內(nèi)務(wù)記號ENDFILE（當(dāng)達(dá)到文件的末尾時）和ERROR（當(dāng)遇到錯誤字符時）。掃描程序的狀態(tài)也被定義為一個枚舉類型，但它是位于掃描程序之中。掃描程序還需總地計算出每個記號的特性，并有時會采取其他動作（例如將標(biāo)識符插入到符號表中）。在TINYC掃描程序中，所要計算的唯一特性是詞法或是被識別的記號的串值，它位于變量tokenString之中。這個變量同getToken一并是提供給編譯器其他部分的唯一的兩個服務(wù)，它們的定義已被收集在頭文件scan.h。聲明了tokenString的長度固定為41，因此那個標(biāo)識符也就不能超過40個字符（加上結(jié)尾的空字符）。后面還會提到這個限制。掃描程序使用了3個全程變量：文件變量source和listing，在globals.h中聲明且在main.c中被分配和初始化的整型變量lineno。由getToken過程完成的額外的簿記如下所述：表reservedWords和過程reservedLookup完成位于由getToken的主要循環(huán)識別的標(biāo)識符之后的保留字的查找，currentToken的值也隨之改變。標(biāo)志變量 save被用作指示是否將一個字符增加到tokenString之上；由于需要包括空白格、注釋和非消耗的先行，所以這些都是必要的。到掃描程序的字符輸入由getNextChar函數(shù)提供，該函數(shù)將一個256-字符緩沖區(qū)內(nèi)部的lineBuf中的字符取到掃描程序中。如果已經(jīng)耗盡了這個緩沖區(qū)，且假設(shè)每一次都獲取了一個新的源代碼行（以及增加的lineno），那么getNextChar就利用標(biāo)準(zhǔn)的C過程fgets從source文件更新改緩沖區(qū)。雖然這個假設(shè)允許了更簡單的代碼，但卻不能正確地處理行的字?jǐn)?shù)超過255個字符的TINYC程序。最后，TINYC中的數(shù)與標(biāo)識符的識別要求從INNUM和INID到最終狀態(tài)的轉(zhuǎn)換都應(yīng)是非消耗的。可以通過提供一個ungetNextChar過程在輸入緩沖區(qū)中反填一個字符來完成這一任務(wù)，但對于源行很長的程序而言，這也不是很好。作為TINYC掃描程序行為的解釋，可考慮一下下面清單1中TINYC程序sample.tny。程序清單2假設(shè)將這個程序作為輸入，那么當(dāng)TraceScan和EchoSource都是集合時，它列出了掃描程序的輸出。之后將詳細(xì)討論由這個掃描程序的實現(xiàn)所引出的一些問題。清單1TINYC語言中的樣本程序{SampleprogramInTINYClanguage-Computesfactorial)readx;{inputaninteger}If0<xthen{don’tcomputeifx<=0}fact:=1;repeatfact:=fact*x;x:=x-1untilx=0;writefact{outputfactorialofx}end清單2當(dāng)程序清單1中的TINY程序作為輸入時，掃描程序的輸出TINYCCOMPILATION:sample.tny{SampleprograminTINYClanguage-computesfactorial}readx;{inputaninteger}5:reservedword:read5:ID,name=x5:;6:if0<xthen{don,tcomputeifx<=0}6:reservedword:if6:NUM,val=06:<6:ID,name=x6:reservedword:then7:fact:=1;7:ID,name=fact7::=7:NUM,val=17:;8:repeatreservedword:repeatfact:=fact*x;ID,name=fact:=ID,name=fact9:*9:ID,name=*9:;x:=x-1ID,name=x10::=ID,name=x10:-NUM,val=1untilx=0;11:reservedword:until11:ID,name=x11:=11:NUM,val=011:;12:writefact{outputfactorialofx}reservedword:writeID,name=factend13:reservedword:end14:EOF實驗心得TINYC對保留字的識別是通過首先將它們看作是標(biāo)識符，之后再在保留字表中查找它們來完成的。這在掃描程序中很平常，但它卻意味著掃描程序的效率須依賴于在保留字表中查找過程的效率。我們的掃描程序使用了一種非常簡便的方法一一線性搜索，即按順序從開頭到結(jié)尾搜索表格。這對于小型表格不成問題，例如TINYC中的表格，它只有8個保留字，但對于真實語言而言，這卻是不可接受的，因為它通常有30-60個保留字。這時候就需要一個更快的查找，而這又要求使用更好的數(shù)據(jù)結(jié)構(gòu)而不是線性列表。假若保留字列表是按字母表的順序?qū)懗龅?，那么就可以使用二分搜索。另一種選擇是使用雜湊表，此時我們希望利用一個沖突性很小的雜湊函數(shù)。由于保留字不會改變（至少不會很快地），所以可事先開發(fā)出這樣一個雜湊函數(shù)，它們在表格中的位置對于編譯器的每一步運行而言都是固定的。人們已經(jīng)確定了各種語言的最小完善雜湊函數(shù)，也就是說能夠區(qū)分出保留字且具有最小數(shù)值的函數(shù)，因此雜湊表可以不大于保留字的數(shù)目。例如，如果只有8個保留字，則最小完善雜湊函數(shù)總會生成一個0-7的值，且每個保留字也會生成不同的值。在處理保留字時，另一個選擇是使用儲存標(biāo)識符的表格，即：符號表。在過程開始之前，將所有的保留字整個輸入到該表中并且標(biāo)上“保留”（因此不允許重新定義），這樣做的好處在于只要求一個查找表。但在TINYC掃描程序中，直到掃描階段之后才構(gòu)造符號表，因此這個方法對于這種類型的設(shè)計并不合適。TINYC掃描程序設(shè)計中的另一個缺點是記號串最長僅為40個字符。由于大多數(shù)的記號的大小都是固定的，所以對于它們而言這并不是問題；但是對于標(biāo)識符來講就麻煩了，這是因為程序設(shè)計語言經(jīng)常要求程序中的標(biāo)識符長度為任意值。更糟的是：如果為每