雖然文章的標(biāo)題是詞法分析，但首先還是要從編譯原理說(shuō)開(kāi)來(lái)。編譯原理應(yīng)該很多人都聽(tīng)說(shuō)過(guò)，雖然不一定會(huì)有多么了解。

簡(jiǎn)單的說(shuō)，編譯原理就是研究如何進(jìn)行編譯——也就如何從代碼（*.cs 文件）轉(zhuǎn)換為計(jì)算機(jī)可以執(zhí)行的程序（*.exe 文件）。當(dāng)然也有些語(yǔ)言如 JavaScript 是解釋執(zhí)行的，它的代碼是直接被執(zhí)行的，不需要生成可執(zhí)行程序。

編譯過(guò)程是很復(fù)雜的，它涉及到很多步驟，直接拿《編譯原理》（Compilers: Principles, Techniques and Tools，紅龍書）上的圖來(lái)看：

圖 1 編譯器的各個(gè)步驟，其實(shí)是我根據(jù)書上的圖綜合了一下后畫的

這里給出了 7 個(gè)步驟（后面的優(yōu)化步驟是可選的），其中前 4 個(gè)步驟是分析部分（也被稱為前端 front end），是把源程序分解為多個(gè)組成要素，并在這些要素上加上語(yǔ)法結(jié)構(gòu)，最后把信息存放在符號(hào)表（symbol table）中。后三個(gè)步驟是綜合部分（也成為后端 back end），它們根據(jù)中間表示和符號(hào)表中的信息構(gòu)造期待的目標(biāo)程序。

將編譯器分為這么多步驟，其好處就是使得每個(gè)步驟更加簡(jiǎn)單，從而使編譯器更加容易設(shè)計(jì)，也可以利用很多現(xiàn)有的工具——例如詞法分析器可以用 Lex 或 Flex 生成，語(yǔ)法分析器可以用 Yacc 或 Bison 生成，幾乎不用做太多編碼工作就能得到一顆語(yǔ)法樹(shù)，前端的工作也就完成的差不多了。而至于后端，也有很多現(xiàn)有的技術(shù)可以使用，例如現(xiàn)成的虛擬機(jī)（CLR 或 Java，只要翻譯成相應(yīng)的 IL 就可以了）。

這個(gè)系列的文章，說(shuō)的就是編譯原理的第一步：語(yǔ)法分析。大部分算法和理論都來(lái)自《編譯原理》，其余的部分則是自己搞出來(lái)的，或者是參考了 Flex 的實(shí)現(xiàn)（這里的 Flex 是指 fast lexical analyzer generator，一種著名的提供詞法分析的程序，而不是 Adobe 的 Flex）。

我會(huì)盡量完整的介紹詞法分析器的編寫過(guò)程，包括一些細(xì)節(jié)的實(shí)現(xiàn)。當(dāng)然，目前只能根據(jù)正則表達(dá)式定義得到一個(gè)可以用來(lái)進(jìn)行詞法分析的對(duì)象，要想達(dá)到 Flex 那樣直接根據(jù)詞法定義文件生成詞法分析器源代碼，還有很多工作要做，不是短期內(nèi)能夠搞定的。

本篇文章作為系列的第一篇，將會(huì)對(duì)詞法分析做綜合的概述，介紹一下其中用到的技術(shù)和大致的流程。

詞法分析（lexical analysis）或掃描（scanning）是編譯器的第一個(gè)步驟。詞法分析器讀入組成源程序的字符流，并且將它們組織成有意義的詞素（lexeme）的序列，并對(duì)每個(gè)詞素產(chǎn)生詞法單元（token）作為輸出。

簡(jiǎn)單的來(lái)說(shuō)，詞法分析就是將源程序（可以認(rèn)為是一個(gè)很長(zhǎng)的字符串）讀進(jìn)來(lái)，并且“切”成小段（每一段就是一個(gè)詞法單元 token），每個(gè)單元都是有具體的意義的，例如表示某個(gè)特定的關(guān)鍵詞，或者代表一個(gè)數(shù)字。而這個(gè)詞法單元在源程序中對(duì)應(yīng)的文本，就叫做“詞素”。

以計(jì)算器來(lái)舉例，12+34*9 這一段“源程序”的詞法分析過(guò)程如下所示：

圖 2 算式的詞法分析過(guò)程

一段對(duì)計(jì)算機(jī)來(lái)說(shuō)豪無(wú)意義的字符串，經(jīng)過(guò)語(yǔ)法分析后就得到了略微有意義的 Token 流。digit 就表示這個(gè)詞法單元對(duì)應(yīng)的是數(shù)字，operator 則表示操作符，后面相應(yīng)的數(shù)字和符號(hào)（粉色背景）就是詞素。同時(shí)，程序中一些不必要的空白、注釋也可以由詞法分析器來(lái)過(guò)濾掉，這樣，之后的語(yǔ)法分析等步驟處理起來(lái)就會(huì)容易得多。

在實(shí)際的程序中，詞法單元都會(huì)以枚舉或數(shù)字來(lái)表示這是哪一類詞法單元。我的 Token.cs 定義如下所示：

里面的 Index 和 Text 屬性不必多做解釋，Start 和 End 是用來(lái)在源文件中定位的（索引，行數(shù)和列數(shù)），Value 則僅僅是為了方便傳遞一些值而設(shè)。

二、如何描述詞素

現(xiàn)在知道了詞法分析可以將詞素分割開(kāi)來(lái)，那么詞素是怎么描述的？或者說(shuō)，為什么 12、+ 和 34 都是詞素，而 1、 2+3 和 4 就不是詞素呢？這就需要用到模式了。

模式（pattern）描述了一個(gè)詞法單元的詞素可能具有的形式。

也就是說(shuō)，我定義了 digit 模式為“由一個(gè)或多個(gè)數(shù)字組成的序列”，和 operator 模式為“單個(gè) + 或 * 字符”，詞法分析器就知道 12 是一個(gè)詞素，而 2+3 則不是詞素了。

現(xiàn)在，模式一般都是用正則表達(dá)式（regular expression）表示的，這里所謂的正則表達(dá)式，與平常所說(shuō)的正則表達(dá)式（例如 System.Text.RegularExpressions.Regex 類）形式完全相同，功能卻更有限，它只包含了字符串的匹配能力，而沒(méi)有分組、引用和替換的能力。簡(jiǎn)單的舉個(gè)例子，a+ 這個(gè)正則表達(dá)式就表示“由一個(gè)或多個(gè)字符 a 組成的序列”。關(guān)于正則表達(dá)式更多詳細(xì)信息，我會(huì)在后面的文章中列出來(lái)，當(dāng)然，有限的參考一下 System.Text.RegularExpressions.Regex 也是可以的。

在本系列之后的文章中所提的正則表達(dá)式，都指的是這種只具有字符串匹配能力的正則表達(dá)式，大家一定要注意不要與 System.Text.RegularExpressions.Regex 相混淆。

三、如何構(gòu)造詞法分析器

說(shuō)完了詞素的描述，就到如何根據(jù)詞素的描述來(lái)構(gòu)造詞法分析器了。大致的流程如下：

圖 3 構(gòu)造詞法分析器

從上圖來(lái)看，定義了模式的正則表達(dá)式，經(jīng)過(guò) NFA 轉(zhuǎn)換、DFA 轉(zhuǎn)換和 DFA 化簡(jiǎn)，得到了一張轉(zhuǎn)換表。這張轉(zhuǎn)換表再加上一個(gè)固定的 DFA 模擬器，就組成了詞法分析器。它不斷的從輸入緩沖區(qū)中讀取字符，利用自動(dòng)機(jī)來(lái)識(shí)別詞素并輸出?？梢哉f(shuō)，詞法分析的精華就是如何得到這張轉(zhuǎn)換表。

說(shuō)了這么多，詞法分析算是簡(jiǎn)單的介紹完了，從下一篇開(kāi)始，就是如何一步一步實(shí)現(xiàn)完整的詞法分析器。

最新評(píng)論