編譯原理（4.5講）續上一篇實現狀態轉換圖

來自專欄編譯原理學習筆記

之所以寫4.5.。。。是因為發現這課程視頻有個問題，有些章節直接跳過了，真的可惜了，我交好不容易錄個這麼優秀的老師的視頻。。結果還TM不全。。不全的部分只能先看PPT和書整理了。

還有發現有朋友陸續關注。。受寵若驚，鄙人只是渣渣大二學生。。這只是看MOOC的學習筆記，以應對大學的考試為主要目的。難免會出現問題，希望各位看的時候指出錯誤。歡迎交流。

OK

（接上篇2.2.4）

在四裡面我們學習了預處理和超前搜索，然後引入了新的概念--狀態轉換圖，因為他可以十分清晰而簡易的描述詞法分析，最後我們談到實現狀態轉換圖，引入了一組全局變數和過程。

（下面這塊PPT很多地方存在問題，書也講得很爛，這個語言到底怎麼回事。。想詳細了解很困難，但是知道實現狀態轉換圖的思想，和理解這些偽代碼的大體意思基本可以滿足要求。。哎，怪不得沒有錄進視頻，不知道老師怎麼講的）

使用它們來構造狀態轉換圖的對應程序（還有其他一些過程。。後面的例子中給出補充）。每個狀態節點對應一段程序。

為了把狀態轉換圖轉化成程序，每個狀態要建立一段程序，它要做的工作如下：

第一步：從輸入緩衝區中取一個字元。為此，我們使用函數GETCHAR，每次調用它，推進先行指針（搜索指針），送回一個字元。

第二步：確定在本狀態下，哪一條箭弧是用剛剛來的輸入字元標識的。如果找到，控制就轉到該弧所指向的狀態；若找不到，那麼尋找該單詞的企圖就失敗了。

失 敗：搜索指針必須重新回到起點指針處，並用另一狀態圖來搜索另一單詞。如果所有的狀態轉換圖都試過之後，還沒有匹配的，就表明這是一個詞法錯誤，此時，調用錯誤校正程序。

什麼叫每個狀態節點對應一段程序，看幾個例子：

例如：我們可以讓不含迴路的分叉結，對應一個CASE語句，或者是一組IF…THEN…ELSE語句：

下面是一個典型的識別標識符的狀態轉換圖：

下面是表示狀態2，終態結一般對應一個RETURN(C,VAL)語句。其中C為單詞種別編碼；VAL是字元數組的TOKEN，或者是一個整數值，或者無定義。這個RETURN意味著從分析器返回給調用者，一般是返回給語法分析器，

如下：

有迴路的狀態點，對應一個含WHILE的程序段：