實驗目的;完整地指出TINYC的詞法結構，也就是：定義記號和它們的特性實驗內容;TINYC的記號分為3個典型類型：保留字、特殊符號和“其他”記號。保留字一共有8個，它們的含義類似。特殊符號有10種：分別是4種基本的整數運算符號、2種比較符號，以及括號、分號和賦值符號。除了賦值符號是兩個字符的長度之外，其余均為一個字符。表1TINYC語言的記號保留字特殊符號其他if+數（1個或更多的數字）thenelse*end/repeatuntil<標識符（1個或更多的字母）read(write);?其他記號就是數了，它們是一個或多個數字以及標識符的序列，而標識符又是（為了簡便）一個或多個字母的序列。除了記號之外，TINYC還要遵循以下的詞法慣例：注釋應放在花括號｛...｝中，且不可嵌套；代碼應是自由格式；空白格由空格、制表位和新行組成；最長子串原則后須接識別記號。在為該語言設計掃描程序時，可以從正則表達式開始并根據前一節中的算法來開發NFA和DFA。實際上，前面已經給出了數、標識符和注釋的正則表達式。其他記號的正則表達式都是固定串，因而均不重要。由于掃描程序的DFA記號十分簡單，所以無需按照這個例程就

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