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

0513《編譯原理》在線開放式作業(yè)實施方案作業(yè)內(nèi)容要求：完成掃描程序的設計與實現(xiàn),具體要求為:?設計并實現(xiàn)TINYC語言的掃描程序;?完成并提交實驗報告,掃描程序的源程序,編譯后的可執(zhí)行程序,例子和運行結(jié)果.

實驗報告至少要包含如下內(nèi)容:

1實驗目的;

2TINYC語言的詞法說明,掃描器的輸入和輸出;

3實驗原理(所采用的過程);

3.1記號種類及各記號所代表的字符串集合;

3.2各記號對應的正那么表達式及所有記號對應的正那么表達式;

3.3各記號對應的DFA及所有記號對應的DFA;

4掃描程序的功能說明和程序說明,程序模塊等;

5輸入例如及其運行結(jié)果;

6總結(jié):獲得的經(jīng)驗,遇到的問題,改良方案等.

格式及提交要求：

1、學生須按以上要求完成實驗報告作業(yè)。

2、在word文檔中完成實驗報告；使用“北京師范大學網(wǎng)絡教育課程論文”做為論文封面；正文使用宋體五號字；標題加粗。北京師范大學網(wǎng)絡教育課程作業(yè)課程代碼：課程名稱：學習中心姓名學號專業(yè)年級實驗目的;完整地指出TINYC的詞法結(jié)構(gòu)，也就是：定義記號和它們的特性實驗內(nèi)容;TINYC的記號分為3個典型類型：保存字、特殊符號和“其他”記號。保存字一共有8個，它們的含義類似。特殊符號有10種：分別是4種根本的整數(shù)運算符號、2種比擬符號，以及括號、分號和賦值符號。除了賦值符號是兩個字符的長度之外，其余均為一個字符。表1TINYC語言的記號保存字特殊符號其他if+數(shù)〔1個或更多的數(shù)字〕then-else*end/repeat=until<標識符〔1個或更多的字母〕read(write);:=其他記號就是數(shù)了，它們是一個或多個數(shù)字以及標識符的序列，而標識符又是〔為了簡便〕一個或多個字母的序列。除了記號之外，TINYC還要遵循以下的詞法慣例：注釋應放在花括號{...}中，且不可嵌套；代碼應是自由格式；空白格由空格、制表位和新行組成；最長子串原那么后須接識別記號。在為該語言設計掃描程序時，可以從正那么表達式開始并根據(jù)前一節(jié)中的算法來開發(fā)NFA和DFA。實際上，前面已經(jīng)給出了數(shù)、標識符和注釋的正那么表達式。其他記號的正那么表達式都是固定串，因而均不重要。由于掃描程序的DFA記號十分簡單，所以無需按照這個例程就可直接開發(fā)這個DFA了。我們按一下步驟進行。首先要注意到除了賦值符號之外，其他所有的特殊符號都只有一個字符，這些符號的DFA如下：在該圖中，不同的接受狀態(tài)是由掃描程序返回的記號區(qū)分開來。如果在這個將要返回的記號〔代碼中的一個變量〕中使用其他指示器，那么所有接受狀態(tài)都可集中為一個狀態(tài)，稱之為DONE。假設將這個二狀態(tài)的DFA與接受數(shù)和標識符的DFA合并在一起，就可得到下面的DFA：請注意，利用方括號指出了不可被消耗的先行字符?，F(xiàn)在需要在這個DFA中添加注釋、空白格和賦值。一個簡單的從初始狀態(tài)到其本身的循環(huán)要消耗空白格。注釋要求一個額外的狀態(tài)，它由花括號左邊到達并在花括號右邊返回到它。賦值也需要中間狀態(tài)，它由分號上的初始狀態(tài)到達。如果后面緊跟有一個等號，那么就會生成一個賦值記號。反之就不消耗下一個字符，且生成一個錯誤記號。實際上，未列在特殊符號中的所有單個字符既不是空白格或注釋，也不是數(shù)字或字母，它們應被作為錯誤而接受，我們將它們與單個字符符號混合在一起。如下列圖是為掃描程序給出的最后一個DFA。在上面的討論或上圖中的DFA都未包括保存字。這是因為根據(jù)DFA的觀點，而認為保存字與標識符相同，以后再在接受后的保存字表格中尋找標識符是最簡單的。當然，最長子串原那么保證了掃描程序唯一需要改變的動作是被返回的記號。因為，僅在識別了標識符之后才考慮保存字。現(xiàn)在再來討論實現(xiàn)這個DFA的代碼，它已被放在了scan.h文件和scan.c文件之中。其中最主要的過程是getToken，它消耗輸入字符并根據(jù)上圖中的DFA返回下一個被識別的記號。這個實現(xiàn)利用了雙重嵌套情況分析，以及一個有關狀態(tài)的大型情況列表，在大列表中的是基于當前輸入字符的單獨列表。記號本身被定義成globals.h中的枚舉類型，它包括在表1中列出的所有記號以及內(nèi)務記號ENDFILE〔當?shù)竭_文件的末尾時〕和ERROR〔當遇到錯誤字符時〕。掃描程序的狀態(tài)也被定義為一個枚舉類型，但它是位于掃描程序之中。掃描程序還需總地計算出每個記號的特性，并有時會采取其他動作〔例如將標識符插入到符號表中〕。在TINYC掃描程序中，所要計算的唯一特性是詞法或是被識別的記號的串值，它位于變量tokenString之中。這個變量同getToken一并是提供應編譯器其他局部的唯一的兩個效勞，它們的定義已被收集在頭文件scan.h。聲明了tokenString的長度固定為41，因此那個標識符也就不能超過40個字符〔加上結(jié)尾的空字符〕。后面還會提到這個限制。掃描程序使用了3個全程變量：文件變量source和listing，在globals.h中聲明且在main.c中被分配和初始化的整型變量lineno。由getToken過程完成的額外的簿記如下所述：表reservedWords和過程reservedLookup完成位于由getToken的主要循環(huán)識別的標識符之后的保存字的查找，currentToken的值也隨之改變。標志變量save被用作指示是否將一個字符增加到tokenString之上；由于需要包括空白格、注釋和非消耗的先行，所以這些都是必要的。到掃描程序的字符輸入由getNextChar函數(shù)提供，該函數(shù)將一個256-字符緩沖區(qū)內(nèi)部的lineBuf中的字符取到掃描程序中。如果已經(jīng)耗盡了這個緩沖區(qū)，且假設每一次都獲取了一個新的源代碼行〔以及增加的lineno〕，那么getNextChar就利用標準的C過程fgets從source文件更新改緩沖區(qū)。雖然這個假設允許了更簡單的代碼，但卻不能正確地處理行的字數(shù)超過255個字符的TINYC程序。最后，TINYC中的數(shù)與標識符的識別要求從INNUM和INID到最終狀態(tài)的轉(zhuǎn)換都應是非消耗的。可以通過提供一個ungetNextChar過程在輸入緩沖區(qū)中反填一個字符來完成這一任務，但對于源行很長的程序而言，這也不是很好。作為TINYC掃描程序行為的解釋，可考慮一下下面清單1中TINYC程序sample.tny。程序清單2假設將這個程序作為輸入，那么當TraceScan和EchoSource都是集合時，它列出了掃描程序的輸出。之后將詳細討論由這個掃描程序的實現(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當程序清單1中的TINY程序作為輸入時，掃描程序的輸出TINYCCOMPILATION:sample.tny1:{Sampleprogram2:inTINYClanguage-3:computesfactorial4:}5: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:repeat8:reservedword:repeat9:fact:=fact*x;9:ID,name=fact9::=9:ID,name=fact9:*9:ID,name=*9:;10:x:=x-110:ID,name=x10::=10:ID,name=x10:-10:NUM,val=111:untilx=0;11:reservedword:until11:ID,name=x11:=11:NUM,val=011:;12:writefact{outputfactorialofx}12:reservedword:write12:ID,name=fact13:end13:reservedword:end14:EOF實驗心得TINYC對保存字的識別是通過首先將它們看作是標識符，之后再在保存字表中查找它們來完成的。這在掃描程序中很平常，但它卻意味著掃描程序的效率須依賴于在保存字表中查找過程的效率。我們的掃描程序使用了一種非常簡便的方法——線性搜索，即按順序從開頭到結(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的值，且每個保存字也會生成不同的值。在處理保存字時，另一個選擇是使用儲存標識符的表格，即：符號表。在過程開始之前，將所有的保存字整個輸入到該表中并且標上“保存”〔因此不允許重新定義〕，這樣做的好處在于只要求一個查找表。但在TINYC掃描程序中，直到掃描階段之后才構(gòu)造符號表，因此這個方法對于這種類型的設計并不適宜。TINYC掃描程序設計中的另一個缺點是記號串最長僅為40個字符。由于大多數(shù)的記號的大小都是固定的，所以對于它們而言這并不是問題；但是對于標識符來講就麻煩了，這是因為程序設計語言經(jīng)常要求程序中的標識