02丨正則文法和有限自動機純手工打造詞法分析器_W

1、02 | 正則文法和有限自動機：純手工打造詞法分析器2019-08-16 宮文學編譯原理之美進入課程講述：宮文學時長 13:06 大小 12.01M上一講，我提到詞法分析的工作是將一個長長的字符串識別出一個個的單詞，這一個個單詞就是 Token。而且詞法分析的工作是一邊讀取一邊識別字符串的，不是把字符串都讀到內存再識別。你在聽一位朋友講話的時候，其實也是同樣的過程，一邊聽，一邊提取信息。那么問題來了，字符串是一連串的字符形成的，怎么把它斷開成一個個的 Token 呢？分割的依據(jù)是什么呢？本節(jié)課，我會通過講解正則表達式和有限自動機的知識帶你解決這個問題。其實，我們手工打造詞法分析器的過程，就是寫

2、出正則表達式，畫出有限自動機的圖形，然后根據(jù)圖形直觀地寫出解析代碼的過程。而我今天帶你寫的詞法分析器，能夠分析以下 3個程序語句： 下載APP age = 45int age = 402+3*5它們分別是關系表達式、變量聲明和初始化語句，以及算術表達式。接下來，我們先來解析一下“age = 45”這個關系表達式，這樣你就能理解有限自動機的概念，知道它是做詞法解析的核心機制了。解析 age = 45在“01 | 理解代碼：編譯器的前端技術”里，我舉了一個詞法分析的例子，并且提出詞法分析要用到有限自動機。當時，我畫了這樣一個示意圖：我們來描述一下標識符、比較操作符和數(shù)字字面量這三種 Token 的

3、詞法規(guī)則。標識符：第一個字符必須是字母，后面的字符可以是字母或數(shù)字。比較操作符： 和 =（其他比較操作符暫時忽略）。數(shù)字字面量：全部由數(shù)字構成（像帶小數(shù)點的浮點數(shù)，暫時不管它）。我們就是依據(jù)這樣的規(guī)則，來構造有限自動機的。這樣，詞法分析程序在遇到 age、= 和45 時，會分別識別成標識符、比較操作符和數(shù)字字面量。不過上面的圖只是一個簡化的示意圖，一個嚴格意義上的有限自動機是下面這種畫法：我來解釋一下上圖的 5 種狀態(tài)。1. 初始狀態(tài)：剛開始啟動詞法分析的時候，程序所處的狀態(tài)。2. 標識符狀態(tài)：在初始狀態(tài)時，當?shù)谝粋€字符是字母的時候，遷移到狀態(tài) 2。當后續(xù)字符是字母和數(shù)字時，保留在狀態(tài) 2。如

4、果不是，就離開狀態(tài) 2，寫下該 Token，回到初始狀態(tài)。3. 大于操作符（GT）：在初始狀態(tài)時，當?shù)谝粋€字符是 時，進入這個狀態(tài)。它是比較操作符的一種情況。4. 大于等于操作符（GE）：如果狀態(tài) 3 的下一個字符是 =，就進入狀態(tài) 4，變成 =。它也是比較操作符的一種情況。5. 數(shù)字字面量：在初始狀態(tài)時，下一個字符是數(shù)字，進入這個狀態(tài)。如果后續(xù)仍是數(shù)字，就保持在狀態(tài) 5。這里我想補充一下，你能看到上圖中的圓圈有單線的也有雙線的。雙線的意思是這個狀態(tài)已經是一個合法的 Token 了，單線的意思是這個狀態(tài)還是臨時狀態(tài)。按照這 5 種狀態(tài)遷移過程，你很容易編成程序（我用 Java 寫了代碼示例，你

5、可以用自己熟悉的語言編寫）。我們先從狀態(tài) 1 開始，在遇到不同的字符時，分別進入 2、3、5 三個狀態(tài)： 復制1234567891011121314DfaState newState = DfaState.Initial;/ 第一個字符是字母if(isAlpha(ch) newState = DfaState.Id; / 進入 Id 狀態(tài)token.type = TokenType.Identifier; tokenText.append(ch);/ 第一個字符是數(shù)字else if (isDigit(ch) newState = DfaState.IntLiteral;token.type =

6、 TokenType.IntLiteral; tokenText.append(ch);/ 第一個字符是 else if (ch = ) newState = DfaState.GT; token.type = TokenType.GT;tokenText.append(ch);上面的代碼中，nextState 是接下來要進入的狀態(tài)。我用 Java 中的枚舉（enum）類型定義了一些枚舉值來代表不同的狀態(tài)，讓代碼更容易讀。其中 Token 是自定義的一個數(shù)據(jù)結構，它有兩個主要的屬性：一個是“type”，就是Token 的類型，它用的也是一個枚舉類型的值；一個是“text”，也就是這個 Toke

7、n 的文本值。我們接著處理進入 2、3、5 三個狀態(tài)之后的狀態(tài)遷移過程： 復制123456789101112case Initial:state = initToken(ch); break;case Id:if (isAlpha(ch) | isDigit(ch) tokenText.append(ch); else / 重新確定后續(xù)狀態(tài)/ 保持標識符狀態(tài)state = initToken(ch); / 退出標識符狀態(tài)，并保存 Tokenbreak; case GT:if (ch = =) token.type = TokenType.GE; / 轉換成 GE state = DfaStat

8、e.GE; tokenText.append(ch); else 1314151617181920212223242526272829/ 退出 GT 狀態(tài)，并保存 Tokenstate = initToken(ch);break; case GE:state = initToken(ch); break;case IntLiteral:/ 退出當前狀態(tài)，并保存 Tokenif(isDigit(ch) tokenText.append(ch);/ 繼續(xù)保持在數(shù)字字面量狀態(tài)/ 退出當前狀態(tài)，并保存 Token else state = initToken(ch);運行這個示例程序，你就會成功地解析

9、類似“age = 45”這樣的程序語句。不過，你可以先根據(jù)我的講解自己實現(xiàn)一下，然后再去參考這個示例程序。示例程序的輸出如下，其中第一列是 Token 的類型，第二列是 Token 的文本值： 復制1 Identifier2 GE3 IntLiteralage= 45上面的例子雖然簡單，但其實已經講清楚了詞法原理，就是依據(jù)構造好的有限自動機，在不同的狀態(tài)中遷移，從而解析出 Token 來。你只要再擴展這個有限自動機，增加里面的狀態(tài)和遷移路線，就可以逐步實現(xiàn)一個完整的詞法分析器了。初識正則表達式但是，這里存在一個問題。我們在描述詞法規(guī)則時用了自然語言。比如，在描述標識符的規(guī)則時，我們是這樣表達的

10、：第一個字符必須是字母，后面的字符可以是字母或數(shù)字。這樣描述規(guī)則并不精確，我們需要換一種嚴謹?shù)谋磉_方式，這種方式就是正則表達式。上面的例子涉及了 4 種 Token，這 4 種 Token 用正則表達式表達，是下面的樣子： 復制1234Id :IntLiteral: GT :GE :a-zA-Z_ (a-zA-Z_ | 0-9)*0-9+ =我先來解釋一下這幾個規(guī)則中用到的一些符號：需要注意的是，不同語言的標識符、整型字面量的規(guī)則可能是不同的。比如，有的語言可以允許用 Unicode 作為標識符，也就是說變量名稱可以是中文的。還有的語言規(guī)定，十進制數(shù)字字面量的第一位不能是 0。這時候正則表達式

11、會有不同的寫法，對應的有限自動機自然也不同。而且，不同工具的正則表達式寫略有不同，但大致是差不多的。我在本節(jié)課講正則表達式，主要是為了讓詞法規(guī)則更為嚴謹，當然了，也是為后面的內容做鋪墊。在后面的課程中，我會帶你用工具生成詞法分析器，而工具讀取的就是用正則表達式描述的詞法規(guī)則。到時候，我們會把所有常用的詞法都用正則表達式描述出來。不過在這之前，如果你想主動了解更完整的正則表達式規(guī)則，完全可以參考自己所采用的正則表達式工具的文檔。比如，Java 的正則式表達式工具在 java.util.regex 包中，在其Javadoc 中有詳細的規(guī)則說明。解析 int age = 40，處理標識符和關鍵字規(guī)則

12、的沖突說完正則表達式，我們接著去處理其他詞法，比如解析“int age = 40”這個語句，以這個語句為例研究一下詞法分析中會遇到的問題：多個規(guī)則之間的沖突。如果我們把這個語句涉及的詞法規(guī)則用正則表達式寫出來，是下面這個樣子： 復制1 Int:2 Id :3 Assignmentinta-zA-Z_ (a-zA-Z_ | 0-9)*: =這時候，你可能會發(fā)現(xiàn)這樣一個問題：int 這個關鍵字，與標識符很相似，都是以字母開頭，后面跟著其他字母。換句話說，int 這個字符串，既符合標識符的規(guī)則，又符合 int 這個關鍵字的規(guī)則，這兩個規(guī)則發(fā)生了重疊。這樣就起沖突了，我們掃描字符串的時候，到底該用哪個

13、規(guī)則呢？當然，我們心里知道，int 這個關鍵字的規(guī)則，比標識符的規(guī)則優(yōu)先級高。普通的標識符是不允許跟這些關鍵字重名的。在這里，我們來回顧一下：什么是關鍵字？關鍵字是語言設計中作為語法要素的詞匯，例如表示數(shù)據(jù)類型的 int、char，表示程序結構的 while、if，表述特殊數(shù)據(jù)取值的 null、NAN 等。除了關鍵字，還有一些詞匯叫保留字。保留字在當前的語言設計中還沒用到，但是保留下來，因為將來會用到。我們命名自己的變量、類名稱，不可以用到跟關鍵字和保留字相同的字符串。那么我們在詞法分析器中，如何把關鍵字和保留字跟標識符區(qū)分開呢？以“int age = 40”為例，我們把有限自動機修改成下面的

14、樣子，借此解決關鍵字和標識符的沖突。這個思路其實很簡單。在識別普通的標識符之前，你先看看它是關鍵字還是保留字就可以了。具體做法是：當?shù)谝粋€字符是 i 的時候，我們讓它進入一個特殊的狀態(tài)。接下來，如果它遇到 n 和 t，就進入狀態(tài) 4。但這還沒有結束，如果后續(xù)的字符還有其他的字母和數(shù)字，它又變成了普通的標識符。比如，我們可以聲明一個 intA（int 和A 是連著的）這樣的變量，而不會跟 int 關鍵字沖突。相應的代碼也修改一下，文稿里的第一段代碼要改成： 復制1 if234567(isAlpha(ch) if (ch = i) DfaState.Id_int1; / 對字符 i 特殊處理new

15、State = else newState =DfaState.Id;./ 后續(xù)代碼8第二段代碼要增加下面的語句： 復制case Id_int1:123456789101112131415161718192021222324252627282930313233343536if(ch = n) state = DfaState.Id_int2; tokenText.append(ch);else if (isDigit(ch) |isAlpha(ch) state = DfaState.Id;/ 切換回 IdtokenText.append(ch);state = initToken(ch);b

16、reak; case Id_int2:狀態(tài)if(ch = t) state = DfaState.Id_int3; tokenText.append(ch);elseif(isDigit(ch)state/切 換|= Id 回isAlpha(ch)DfaState.Id;狀態(tài)tokenText.append(ch);else state = initToken(ch);break; case Id_int3:if (isBlank(ch) token.type = TokenType.Int; state = initToken(ch);/ 切換回 Id狀態(tài)state = DfaState.I

17、d;tokenText.append(ch);break;接著，我們運行示例代碼，就會輸出下面的信息： 復制IntIdentifier AssignmentIntLiteralintage= 451234而當你試著解析“intA = 10”程序的時候，會把 intA 解析成一個標識符。輸出如下： 復制1 Identifier2 Assignment3 IntLiteralintA= 10解析算術表達式解析完“int age = 40”之后，我們再按照上面的方法增加一些規(guī)則，這樣就能處理算術表達式，例如“2+3*5”。 增加的詞法規(guī)則如下： 復制Plus :+Minus : -1234Star

18、:Slash :*/然后再修改一下有限自動機和代碼，就能解析“2+3*5”了，會得到下面的輸出： 復制12345IntLiteralPlus IntLiteral Star IntLiteral2+ 3*5好了，現(xiàn)在我們已經能解析不少詞法了，之后的課程里，我會帶你實現(xiàn)一個公式計算器，所以在這里要先準備好所需要的詞法分析功能。課程小結本節(jié)課，我們實現(xiàn)了一個簡單的詞法分析器。你可以看到，要實現(xiàn)一個詞法分析器，首先需要寫出每個詞法的正則表達式，并畫出有限自動機，之后，只要用代碼表示這種狀態(tài)遷移過程就可以了。我們總是說理解原理以后，實現(xiàn)并不困難。今天的分享，你一定有所共鳴。反之，如果你在編程工作中遇到

19、困難，往往是因為不清楚原理，沒有將原理吃透。而這門課就是要幫助你真正吃透編譯技術中的幾個核心原理，讓你將知識應用到實際工作中，解決工作中遇到的困難。小試了詞法分析器之后，在下一講，我會帶你手工打造一下語法分析器，并實現(xiàn)一個公式計算器的功能。一課一思很多同學已經用到過正則表達式，這是學計算機必懂的知識點，十分有用。正則表達式工具其實就可以看做一個通用的詞法分析器。那么你都用正則表達式功能做過哪些事情？有沒有 發(fā)現(xiàn)一些軟件工具因為支持正則表達式而變得特別強大的情況呢？可以在留言區(qū)與大家一起交流。最后，感謝你的閱讀，如果這篇文章讓你有所收獲，也歡迎你將它分享給更多的朋友。另外，為了便于你更好地學習，

20、我將本節(jié)課的示例程序放到了GitHub上，你可以看一下。 版權歸極客邦科技所有，未經許可不得傳播售賣。 頁面已增加防盜追蹤，如有侵權極客邦將依法追究其法律責任。上一篇01 | 理解代碼：編譯器的前端技術精選留言 (26)KnowNothing2019-08-16老師，在關鍵字和保留字的識別上，我認為有不需要加入中間狀態(tài)的更簡單的方式：完成詞法分析后，遍歷所有ID token，如果其text在關鍵字和保留字集合內，將該token類型改成對應的關鍵字/保留字類型。或者，每當識別出一個ID token，都檢查其text，如果是在關鍵字和保留字集合內，糾正type。 寫留展開 作者回復: 沒錯，可以的

21、。但是構造成有限自動機的話，程序就可以標準化處理。不需要再手寫其他代碼。比如正則表達式工具。當然，如果純手寫詞法分析器，不受任何標準算法的限制的話，那發(fā)揮空間就會大很多。愛動腦的好同學！xindoo2019-08-16正則表達式匹配3的任意倍數(shù) /question/24824487作者回復: 哇，真好玩！ 點贊！逗逼師父2019-08-17老師您好，我的疑問是，age=45的有限狀態(tài)機圖中，為什么比較操作符不像標識符那樣停留在同一個狀態(tài)？我覺得和=都是屬于比較操作符呀展開 作者回復: 很好的問題。是這樣的。從Token分類的角度，我們確實可以把這兩個歸為

22、一類。但如果把它們看做同一個狀態(tài)，就會有一些問題。比如，接收到=號應該怎么處理呢？接收第一個=號，仍然處于比較操作符狀態(tài)。那么接收第二個呢？問題是，有限狀態(tài)機接收字符的時候，是沒法數(shù)個數(shù)的。如果你要記個數(shù)，也就相當于在內部新增加了一個狀態(tài)，還是等價于兩個狀態(tài)。我這么說你理解嗎？kirogiyi2019-08-17宮老師，例子里面的詞法分析大多是靠條件判斷來實現(xiàn)，如果對一門完整的語言來進行分析的話，工作量會不會很大。我在想，是否有其他方式可以實現(xiàn)？展開 作者回復: 課程的示例代碼的主要目的是把意思講明白，我甚至把狀態(tài)都用枚舉表示，就是為了易讀。性能不是第一考慮。從性能的角度，詞法分析可以用查表的

23、方法實現(xiàn)狀態(tài)遷移。在每個狀態(tài)，接收什么字符，切換到另外的狀態(tài)。那樣更快，這是常用的方法。不光詞法分析可以這么做，語法分析也可以。基于表驅動。這時候，最重要的是構造那張表。代碼的話，就不大看明白是啥意思。好吃的呆梨2019-08-16ts的實現(xiàn)，請老師和同學指正。/sheeeeep/fundamentals-of-compi ling/blob/Ch02/src/lexical-analyser.ts展開 作者回復: 非常好！要號召大家跟你學習！ 太棒了！你有精力的話，還可以再精進一下，參考一下成熟編譯器的詞法分析工具，從課程示例的代碼的基礎上再提升一個等級:)

24、比如說，另一個同學提到過，如何提升詞法分析的性能什么的。冬瓜2019-08-16int 后面的 id 的正則是不是 a-zA-Z_0-9a-zA-Z_*這樣就行，為啥要將數(shù)字通過|連接呢？是不是有什么用意展開 作者回復: 就是個習慣而已，把數(shù)字和字符分兩組。我們在寫正式的詞法文件時，有時會這么寫：Id: Charactor (Charactor | Digit)* Number: Digit+Charactor: a-zA-Z_ Digit: 0-9這時候，Digit在幾個不同的規(guī)則中是復用的。Fan2019-08-16宮老師，有沒有一些詞法分析的demo可以推薦看看呢？作者回復: 最好的de

25、mo，就是現(xiàn)有語言的詞法分析器，比如Java的、GNU c的，都能拿到源代碼。比如Java的編譯器在JDK的源代碼里就有。此外，我們在后端時會講到LLVM工具。LLVM的文檔里有一個小的教程，做了一個完整的前端。你也可以參考一下。/docs/tutorial/MyFirstLanguageFrontend/LangImpl01.ht ml回頭我整理一份放到github上，告訴大家去哪里下載。你的需求估計其他同學也有。謝謝你！devna2019-08-16之前做的一個項目中有大量的歷史遺留腳本是用Perl寫的，于是主動去學了下Perl，不得不說，Perl是我見過所有語

26、言里對正則表達式支持最強的，效率也是最高的(我想可能是因為P erl在語言核心內置了正則表達式引擎，不像其他語言，是通過各種模塊支持的)。后來從Perl了解到精通正則表達式這本書，買來看了下，確實是很好的一本書。雖然讀完很久很多東西都忘了，但是對正則表達式的理解深刻了很多。展開 作者回復: great!基于你已有的積累，是否可以進一步想想，能否自己寫一個支持正則的工具？比如像grep、sed這些超級命令一樣。那幾個命令被認為是神級的命令，就是因為支持正則表達式，讓它們能適應各種情況。catplanet2019-08-17golang 的實現(xiàn) /p/h

27、s-2izlOJUk梓航()2019-08-17我是來提意見的，麻煩老師在講示例的時候，把對應的github鏈接貼上，而不是在最后貼一個總的地址，我點進去一臉懵，哪個文件對應哪個例子啊？展開 作者回復: 好的，謝謝您提意見！已調整一下。02課的文件是目錄中的SimpleLexer.java文件。另，如果到github的/RichardGong/PlayWithCompiler項目主頁，里面有每堂課的課件的介紹，供您參考。janey2019-08-17Golang 語言看上去簡單搞清楚底層實現(xiàn)不容易，老師可否從編譯原理的角度指點迷津？作者回復: 這個問題有點大。可能要寫很大一篇文章才行。我記著這下問題。抽時間看能不能寫一篇博文，“從編譯原理的角度看Go語言”。如果你跟著這門課程學完，可能自己對Go語言也會有更好的認知能力。(口-口) 2019-08-1