1.2.1 詞法分析

詞法分析是編譯的第一個步驟。詞法分析器讀入源程序的字符信息，將它們按照一定規(guī)則組成詞素，并檢查每一個詞素是否符合詞法規(guī)則。若所有詞素均符合詞法規(guī)則，詞法分析器生成并輸出詞法單元流。

程序設計語言通常只包含幾種有限的詞法單元類型，用于表示程序內(nèi)部的變量、數(shù)據(jù)結(jié)構(gòu)、運算符、控制流和表達式等。例如，對于我們使用的C--語言，源代碼中有如下的賦值語句：

賦值語句中包含如下的詞素：

●int是一個詞素，表示變量的類型，映射為詞法單元TYPE。

●i是一個詞素，表示一個變量，映射為詞法單元ID。

●=是一個賦值運算符，表示賦值關系，映射為詞法單元ASSIGNOP。

●123是一個詞素，表示一個整數(shù)，映射為詞法單元INT。

●；是一個詞素，表示一條語句的結(jié)束，映射為詞法單元SEMI。

于是，賦值語句所對應的詞素可以組成如下的詞法單元流：

每個詞法單元都有對應的詞法規(guī)則，如C--詞法規(guī)則中，能夠表示為詞法單元INT的詞素只包含一連串的數(shù)字，不能出現(xiàn)其他符號。詞法分析器是一個有限狀態(tài)機，當一個詞素不滿足當前程序設計語言的所有詞法規(guī)則時，將輸出詞法錯誤報告。

同時，如果一個詞素是一個變量，詞法分析器會收集變量的符號屬性（類型信息等），記錄到一個符號表中，符號表中的條目可用于語義分析和中間代碼生成。

在第2章中，我們將討論以下內(nèi)容：

●使用正則表達式描述詞素模式，正則表達式能夠精準高效地描述詞法規(guī)則。

●使用有限狀態(tài)自動機進行詞法規(guī)則匹配。

●從NFA（非確定性有限狀態(tài)自動機）到DFA（確定性有限狀態(tài)自動機）的轉(zhuǎn)換算法。

●狀態(tài)最小化算法，最終設計構(gòu)造一個簡潔且高效的詞法分析器。