構(gòu)造可配置詞法分析器
陳梓瀚
華南理工大學(xué)計(jì)算機(jī)軟件學(xué)院軟件工程05級(jí)本科
vczh@163.com
2007-11-8
一、問(wèn)題概述
隨著計(jì)算機(jī)語(yǔ)言的結(jié)構(gòu)越來(lái)越復(fù)雜，為了開(kāi)發(fā)優(yōu)秀的編譯器，人們已經(jīng)漸漸感到將詞法分析獨(dú)立出來(lái)做研究的重要性。不過(guò)詞法分析器的作用卻不限于此?；叵胍幌挛覀兊睦蠋焺倓傞_(kāi)始向我們講述程序設(shè)計(jì)的時(shí)候，總是會(huì)出一道題目：給出一個(gè)填入了四則運(yùn)算式子的字符串，寫程序計(jì)算該式子的結(jié)果。除此之外，我們有時(shí)候建立了比較復(fù)雜的配置文件，譬如XML的時(shí)候，分析器首先也要對(duì)該文件進(jìn)行詞法分析，把整個(gè)字符串?dāng)喑闪艘粋€(gè)一個(gè)比較短小的記號(hào)(指的是具有某種屬性的字符串)，之后才進(jìn)行結(jié)構(gòu)上的分析。再者，在實(shí)現(xiàn)某種控制臺(tái)應(yīng)用程序的時(shí)候，程序需要分析用戶打進(jìn)屏幕的命令。如果該命令足夠復(fù)雜的話，我們也首先要對(duì)這個(gè)命令進(jìn)行詞法分析，之后得到的結(jié)果會(huì)大大方便進(jìn)行接下去的工作。
當(dāng)然，這些問(wèn)題大部分已經(jīng)得到了解決，而且歷史上也有人做出了各種各樣專門的或者通用的工具(Lex、正則表達(dá)式引擎等)來(lái)解決這一類問(wèn)題。我們?cè)谑褂眠@種工具的時(shí)候，為了更加高效地書寫配置，或者我們?cè)谀撤N特殊情況下需要自己制作類似的工具，就需要了解詞法分析背后的原理。本文將給出一個(gè)構(gòu)造通用詞法分析工具所需要的原理。由于實(shí)現(xiàn)的代碼過(guò)長(zhǎng)，本文將不附帶實(shí)現(xiàn)。
究竟什么是“把一個(gè)字符串?dāng)喑梢恍┯浱?hào)”呢？我們先從四則運(yùn)算式子入手。一個(gè)四則運(yùn)算式子是一個(gè)字符數(shù)列，可是我們關(guān)心的對(duì)象實(shí)際上是操作符、括號(hào)和數(shù)字。于是此法分析的作用就是把一個(gè)字符串?dāng)嚅_(kāi)成我們關(guān)心的帶有屬性的記號(hào)。舉個(gè)例子：(11+22)*(33+44)是一個(gè)合法的四則運(yùn)算式子，如果輸入是(左括號(hào),”(“) (數(shù)字,”11”) (一級(jí)操作符,”+”) (數(shù)字,”22”) (右括號(hào),”)”) (二級(jí)操作符,”*”) (左括號(hào),”(“) (數(shù)字,”33”) (一級(jí)操作符,”+”) (數(shù)字,”44”) (右括號(hào),”)”)的話，我們?cè)跈z查結(jié)構(gòu)的時(shí)候只需要關(guān)心這個(gè)記號(hào)的屬性(也就是左括號(hào)、右括號(hào)、數(shù)字、操作符等)就行了，具體計(jì)算的時(shí)候才需要關(guān)心這個(gè)記號(hào)實(shí)際上的內(nèi)容。如果式子里邊有空格的話，我們也僅僅需要把空格當(dāng)成是一種記號(hào)類型，在詞法分析得出結(jié)果之后，將具有空格屬性的記號(hào)丟棄掉就可以了，接下去的步驟不需變化。
但需要注意的是，詞法分析得到的結(jié)果是沒(méi)有層次結(jié)構(gòu)的，所有的記號(hào)都是等價(jià)的對(duì)象。我們?cè)谟?jì)算表達(dá)式的時(shí)候把+和*看成了不同層次的操作符，類似的結(jié)構(gòu)是具有嵌套的層次的。詞法分析不能得出嵌套層次結(jié)構(gòu)的信息，最多只能得到關(guān)于重復(fù)結(jié)構(gòu)的信息。
二、正則表達(dá)式
我們現(xiàn)在需要尋找一種可以描述記號(hào)類型的工具，在此之前我們首先研究一下常見(jiàn)的記號(hào)的結(jié)構(gòu)。為了表示出具有某種共性的字符串的集合，我們需要書寫出一些能代表字符串集合的規(guī)則。這個(gè)集合中的所有成員都將被認(rèn)為是一種特定類型的記號(hào)。
首先，規(guī)則可以把一個(gè)特定的字符或者是空字符串認(rèn)為是一種類型的記號(hào)的全部。上文所說(shuō)到的四則運(yùn)算式子的例子，“左括號(hào)”這種類型的記號(hào)就僅僅對(duì)應(yīng)著字符”(“，其他的字符或者字符串都不可能是“左括號(hào)”這個(gè)類型的記號(hào)。
其次，規(guī)則可以進(jìn)行串聯(lián)。串聯(lián)的意思是這樣的，我們可以讓一個(gè)字符串的前綴符合某一個(gè)指定的規(guī)則，剩下的部分的前綴符合第二個(gè)規(guī)則，剩下的部分的前綴符合第三個(gè)規(guī)則等等，一直到最后一個(gè)部分的全部要符合最后一個(gè)規(guī)則。如果我們把”function”這個(gè)字符串作為一個(gè)記號(hào)類型來(lái)處理的話，我們可以把”function”這個(gè)字符串替換成8個(gè)串聯(lián)的規(guī)則：”f”,”u”,”n”,”c”,”t”,”i”,”o”,”n”。首先，字符串”function”的前綴”f”符合規(guī)則”f”，剩下的部分”unction”的前綴”u”符合規(guī)則”u”，等等，一直到最后一個(gè)部分”n”的全部符合規(guī)則”n”。
第三，規(guī)則可以進(jìn)行并聯(lián)。并聯(lián)的意思就是，如果一個(gè)字符串符合一系列規(guī)則中的其中一個(gè)的話，我們就說(shuō)這個(gè)字符串符合這一些規(guī)則的并聯(lián)。于是這些規(guī)則的并聯(lián)就構(gòu)成了一個(gè)新的規(guī)則。一個(gè)典型的例子就是判斷一個(gè)字符串是否關(guān)鍵字。關(guān)鍵字可以是”if”，可以是”else”，可以是”while”等等。當(dāng)然，一個(gè)關(guān)鍵字是不可能同時(shí)符合這些規(guī)則的，不過(guò)只要一個(gè)字符串符合這些規(guī)則的其中一個(gè)的話，我們就說(shuō)這個(gè)字符串是關(guān)鍵字。于是，關(guān)鍵字這個(gè)規(guī)則就是”if”、”else”、”while”等規(guī)則的并聯(lián)。
第四，一個(gè)規(guī)則可以是可選的。可選的規(guī)則實(shí)際上是屬于并聯(lián)的一種特殊形式。加入我們需要規(guī)則”abc”和”abcde”并聯(lián)，我們會(huì)發(fā)現(xiàn)這兩個(gè)規(guī)則有著相同的前綴”abc”，而且這個(gè)前綴恰好就是其中的一個(gè)規(guī)則。于是我們可以把規(guī)則改寫成”abc”與””和”de”的并聯(lián)的串聯(lián)。但是規(guī)則””指定的規(guī)則是空串，因此這個(gè)規(guī)則與”de”的并聯(lián)就可以看成是一個(gè)可選的規(guī)則”de”。
第五，規(guī)則可以被重復(fù)。有限次的重復(fù)可以使用串聯(lián)表示，但是如果我們不想限制重復(fù)的次數(shù)的話，串聯(lián)就沒(méi)法表示這個(gè)規(guī)則了，于是我們引入了“重復(fù)”。一個(gè)典型的例子就是程序設(shè)計(jì)語(yǔ)言的標(biāo)識(shí)符。標(biāo)識(shí)符可以是一個(gè)變量的名字或者是其他東西。一門語(yǔ)言通常沒(méi)有規(guī)定變量名的最大長(zhǎng)度。因此為了表示這個(gè)規(guī)則，就需要將52個(gè)字母進(jìn)行并聯(lián)，然后對(duì)這個(gè)規(guī)則進(jìn)行重復(fù)。
上述的5種構(gòu)造規(guī)則的方法中，后面的4個(gè)方法被用于把規(guī)則組合成為更大的規(guī)則。為了給出這種規(guī)則的形式化表示，我們引入了一種范式。這種范式有以下語(yǔ)法：
1：字符用雙引號(hào)包圍起來(lái)，空串使用ε代替。
2：兩個(gè)規(guī)則頭尾連接代表規(guī)則的串聯(lián)。
3：兩個(gè)規(guī)則使用 | 隔開(kāi)代表規(guī)則的并聯(lián)。
4：規(guī)則使用[]包圍代表該規(guī)則是可選的，規(guī)則使用{}包圍代表該規(guī)則是重復(fù)的。
5：規(guī)則使用()包圍代表該規(guī)則是一個(gè)整體，通常用于改變操作符 | 的優(yōu)先級(jí)。
舉個(gè)例子，一個(gè)實(shí)數(shù)的規(guī)則書寫如下：
{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}”.”[{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}]。
但是，我們?nèi)绾伪硎?#8220;不是數(shù)字的其他字符呢”？字符的數(shù)量是有限的，因此我們可以使用規(guī)則的并聯(lián)來(lái)表示。但是所有的字符實(shí)在是太多（ASCII字符集有127個(gè)字符，UTF-16字符集有65535個(gè)字符），因此后來(lái)人們想出了各種各樣的簡(jiǎn)化規(guī)則書寫的辦法。比較著名的有BNF范式。BNF范式經(jīng)常被用于理論研究，但是更加實(shí)用的是正則表達(dá)式。
正則表達(dá)式的字符不需要用雙引號(hào)括起來(lái)，但是如果需要表示一些被定義了的字符(如 “|” )的話，就使用轉(zhuǎn)義字符的方法表示(如 “\|”)。其次，X?代表[X]，X+代表{X}，X*代表[{X}]。字符集合可以用區(qū)間來(lái)表示，[0-9]可以表示“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”，[^0-9]則表示“除了數(shù)字以外的其他字符”。正則表達(dá)式還有各種各樣的其他規(guī)則來(lái)簡(jiǎn)化我們的書寫，不過(guò)由于本文并不是“精通正則表達(dá)式”，因此我們只保留若干比較本質(zhì)的操作來(lái)進(jìn)行詞法分析原理的描述。
正則表達(dá)式的表達(dá)能力極強(qiáng)，小數(shù)的規(guī)則可以使用[0-9]+.[0-9]來(lái)表示，C語(yǔ)言的注釋可以表示為/\*([^\*]|\*+[\*/])*\*+/來(lái)表示。