構造可配置詞法分析器

陳梓瀚

華南理工大學計算機軟件學院軟件工程05級本科

vczh@163.com

2007-11-8

一、問題概述

隨著計算機語言的結構越來越復雜，為了開發(fā)優(yōu)秀的編譯器，人們已經漸漸感到將詞法分析獨立出來做研究的重要性。不過詞法分析器的作用卻不限于此。回想一下我們的老師剛剛開始向我們講述程序設計的時候，總是會出一道題目：給出一個填入了四則運算式子的字符串，寫程序計算該式子的結果。除此之外，我們有時候建立了比較復雜的配置文件，譬如XML的時候，分析器首先也要對該文件進行詞法分析，把整個字符串斷成了一個一個比較短小的記號(指的是具有某種屬性的字符串)，之后才進行結構上的分析。再者，在實現某種控制臺應用程序的時候，程序需要分析用戶打進屏幕的命令。如果該命令足夠復雜的話，我們也首先要對這個命令進行詞法分析，之后得到的結果會大大方便進行接下去的工作。

當然，這些問題大部分已經得到了解決，而且歷史上也有人做出了各種各樣專門的或者通用的工具(Lex、正則表達式引擎等)來解決這一類問題。我們在使用這種工具的時候，為了更加高效地書寫配置，或者我們在某種特殊情況下需要自己制作類似的工具，就需要了解詞法分析背后的原理。本文將給出一個構造通用詞法分析工具所需要的原理。由于實現的代碼過長，本文將不附帶實現。

究竟什么是“把一個字符串斷成一些記號”呢？我們先從四則運算式子入手。一個四則運算式子是一個字符數列，可是我們關心的對象實際上是操作符、括號和數字。于是此法分析的作用就是把一個字符串斷開成我們關心的帶有屬性的記號。舉個例子：(11+22)*(33+44)是一個合法的四則運算式子，如果輸入是(左括號,”(“) (數字,”11”) (一級操作符,”+”) (數字,”22”) (右括號,”)”) (二級操作符,”*”) (左括號,”(“) (數字,”33”) (一級操作符,”+”) (數字,”44”) (右括號,”)”)的話，我們在檢查結構的時候只需要關心這個記號的屬性(也就是左括號、右括號、數字、操作符等)就行了，具體計算的時候才需要關心這個記號實際上的內容。如果式子里邊有空格的話，我們也僅僅需要把空格當成是一種記號類型，在詞法分析得出結果之后，將具有空格屬性的記號丟棄掉就可以了，接下去的步驟不需變化。

但需要注意的是，詞法分析得到的結果是沒有層次結構的，所有的記號都是等價的對象。我們在計算表達式的時候把+和*看成了不同層次的操作符，類似的結構是具有嵌套的層次的。詞法分析不能得出嵌套層次結構的信息，最多只能得到關于重復結構的信息。

二、正則表達式

我們現在需要尋找一種可以描述記號類型的工具，在此之前我們首先研究一下常見的記號的結構。為了表示出具有某種共性的字符串的集合，我們需要書寫出一些能代表字符串集合的規(guī)則。這個集合中的所有成員都將被認為是一種特定類型的記號。

首先，規(guī)則可以把一個特定的字符或者是空字符串認為是一種類型的記號的全部。上文所說到的四則運算式子的例子，“左括號”這種類型的記號就僅僅對應著字符”(“，其他的字符或者字符串都不可能是“左括號”這個類型的記號。

其次，規(guī)則可以進行串聯。串聯的意思是這樣的，我們可以讓一個字符串的前綴符合某一個指定的規(guī)則，剩下的部分的前綴符合第二個規(guī)則，剩下的部分的前綴符合第三個規(guī)則等等，一直到最后一個部分的全部要符合最后一個規(guī)則。如果我們把”function”這個字符串作為一個記號類型來處理的話，我們可以把”function”這個字符串替換成8個串聯的規(guī)則：”f”,”u”,”n”,”c”,”t”,”i”,”o”,”n”。首先，字符串”function”的前綴”f”符合規(guī)則”f”，剩下的部分”unction”的前綴”u”符合規(guī)則”u”，等等，一直到最后一個部分”n”的全部符合規(guī)則”n”。

第三，規(guī)則可以進行并聯。并聯的意思就是，如果一個字符串符合一系列規(guī)則中的其中一個的話，我們就說這個字符串符合這一些規(guī)則的并聯。于是這些規(guī)則的并聯就構成了一個新的規(guī)則。一個典型的例子就是判斷一個字符串是否關鍵字。關鍵字可以是”if”，可以是”else”，可以是”while”等等。當然，一個關鍵字是不可能同時符合這些規(guī)則的，不過只要一個字符串符合這些規(guī)則的其中一個的話，我們就說這個字符串是關鍵字。于是，關鍵字這個規(guī)則就是”if”、”else”、”while”等規(guī)則的并聯。

第四，一個規(guī)則可以是可選的。可選的規(guī)則實際上是屬于并聯的一種特殊形式。加入我們需要規(guī)則”abc”和”abcde”并聯，我們會發(fā)現這兩個規(guī)則有著相同的前綴”abc”，而且這個前綴恰好就是其中的一個規(guī)則。于是我們可以把規(guī)則改寫成”abc”與””和”de”的并聯的串聯。但是規(guī)則””指定的規(guī)則是空串，因此這個規(guī)則與”de”的并聯就可以看成是一個可選的規(guī)則”de”。

第五，規(guī)則可以被重復。有限次的重復可以使用串聯表示，但是如果我們不想限制重復的次數的話，串聯就沒法表示這個規(guī)則了，于是我們引入了“重復”。一個典型的例子就是程序設計語言的標識符。標識符可以是一個變量的名字或者是其他東西。一門語言通常沒有規(guī)定變量名的最大長度。因此為了表示這個規(guī)則，就需要將52個字母進行并聯，然后對這個規(guī)則進行重復。

上述的5種構造規(guī)則的方法中，后面的4個方法被用于把規(guī)則組合成為更大的規(guī)則。為了給出這種規(guī)則的形式化表示，我們引入了一種范式。這種范式有以下語法：

1：字符用雙引號包圍起來，空串使用ε代替。

2：兩個規(guī)則頭尾連接代表規(guī)則的串聯。

3：兩個規(guī)則使用 | 隔開代表規(guī)則的并聯。

4：規(guī)則使用[]包圍代表該規(guī)則是可選的，規(guī)則使用{}包圍代表該規(guī)則是重復的。

5：規(guī)則使用()包圍代表該規(guī)則是一個整體，通常用于改變操作符 | 的優(yōu)先級。

舉個例子，一個實數的規(guī)則書寫如下：

{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}”.”[{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}]。

但是，我們如何表示“不是數字的其他字符呢”？字符的數量是有限的，因此我們可以使用規(guī)則的并聯來表示。但是所有的字符實在是太多（ASCII字符集有127個字符，UTF-16字符集有65535個字符），因此后來人們想出了各種各樣的簡化規(guī)則書寫的辦法。比較著名的有BNF范式。BNF范式經常被用于理論研究，但是更加實用的是正則表達式。

正則表達式的字符不需要用雙引號括起來，但是如果需要表示一些被定義了的字符(如 “|” )的話，就使用轉義字符的方法表示(如 “\|”)。其次，X?代表[X]，X+代表{X}，X*代表[{X}]。字符集合可以用區(qū)間來表示，[0-9]可以表示“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”，[^0-9]則表示“除了數字以外的其他字符”。正則表達式還有各種各樣的其他規(guī)則來簡化我們的書寫，不過由于本文并不是“精通正則表達式”，因此我們只保留若干比較本質的操作來進行詞法分析原理的描述。

正則表達式的表達能力極強，小數的規(guī)則可以使用[0-9]+.[0-9]來表示，C語言的注釋可以表示為/\*([^\*]|\*+[\*/])*\*+/來表示。