與大多數(shù)程序員一樣，我經(jīng)常需要標(biāo)識(shí)存在于文本文檔中的部件和結(jié)構(gòu)，這些文檔包括：日志文件、配置文件、分隔的數(shù)據(jù)以及格式更自由的（但還是半結(jié)構(gòu)化的）報(bào)表格式。所有這些文檔都擁有它們自己的“小語言”，用于規(guī)定什么能夠出現(xiàn)在文檔內(nèi)。
我編寫處理這些非正式解析任務(wù)的程序的方法總是有點(diǎn)象大雜燴，其中包括定制狀態(tài)機(jī)、正則表達(dá)式以及上下文驅(qū)動(dòng)的字符串測(cè)試。這些程序中的模式大概總是這樣：“讀一些文本，弄清是否可以用它來做些什么，然后可能再多讀一些文本，一直嘗試下去。”
各種形式的解析器將文檔中部件和結(jié)構(gòu)的描述提煉成簡(jiǎn)明、清晰和 說明性的規(guī)則，該規(guī)則規(guī)定了如何標(biāo)識(shí)文檔的組成部分。這里，說明性方面是最引人注目的。我所有的舊的特別的解析器都采用了這種風(fēng)格：讀一些字符、作決定、累加一些變量、清空、重復(fù)。正如本專欄關(guān)于函數(shù)型編程的部分文章中所評(píng)述的，程序流的方法風(fēng)格相對(duì)來說容易出錯(cuò)并且難以維護(hù)。
正式解析器幾乎總是使用擴(kuò)展巴科斯范式（Extended Backus-Naur Form(EBNF)）上的變體來描述它們所描述語言的“語法”。我們?cè)谶@里研究的工具是這樣做的，流行的編譯器開發(fā)工具 YACC（及其變體）也是這樣做的。基本上，EBNF 語法對(duì)您可能在文檔中找到的 部件賦予名稱；另外，經(jīng)常將較小的部件組成較大的部件。由運(yùn)算符 ― 通常和您在正則表達(dá)式中看到的符號(hào)相同 ― 來指定小部件在較大的部件中出現(xiàn)的頻率和順序。在解析器交談（parser-talk）中，語法中每個(gè)命名的部件稱為一個(gè)“產(chǎn)品（production）”。
可能讀者甚至還不知道 EBNF，卻已經(jīng)看到過運(yùn)行的 EBNF 描述了。例如，大家熟悉的 Python 語言參考大全（Python Language Reference）定義了浮點(diǎn)數(shù)在 Python 中是什么樣子：
EBNF 樣式的浮點(diǎn)數(shù)描述
floatnumber: pointfloat | exponentfloat
pointfloat: [intpart] fraction | intpart "."
exponentfloat: (nonzerodigit digit* | pointfloat) exponent
intpart: nonzerodigit digit* | "0"
fraction: "." digit+
exponent: ("e"|"E") ["+"|"-"] digit+
或者您可能見過以 EBNF 樣式定義的 XML DTD 元素。例如，developerWorks 教程的 <body> 類似于：
developerWorks DTD 中 EBNF 樣式的描述
拼寫稍有不同，但是量化、交替和定序這些一般概念都存在于所有 EBNF 樣式的語言語法中。
使用 SimpleParse 構(gòu)建標(biāo)記列表
SimpleParse 是一個(gè)有趣的工具。要使用這個(gè)模塊，您需要底層模塊 mxTextTools ，它用 C 實(shí)現(xiàn)了一個(gè)“標(biāo)記引擎”。 mxTextTools （請(qǐng)參閱本文后面的 參考資料）的功能強(qiáng)大，但是相當(dāng)難用。一旦在 mxTextTools 上放置了 SimpleParse 后，工作就簡(jiǎn)單多了。
使用 SimpleParse 確實(shí)很簡(jiǎn)單，因?yàn)椴恍枰紤] mxTextTools 的大部分復(fù)雜性。首先，應(yīng)該創(chuàng)建一種 EBNF 樣式的語法，用來描述要處理的語言。第二步是調(diào)用 mxTextTools 來創(chuàng)建一個(gè) 標(biāo)記列表，當(dāng)語法應(yīng)用于文檔時(shí)，該列表描述所有成功的產(chǎn)品。最后，使用 mxTextTools 返回的標(biāo)記列表來進(jìn)行實(shí)際操作。
對(duì)于本文，我們要解析的“語言”是“智能 ASCII”所使用的一組標(biāo)記代碼，這些代碼用來表示諸如黑體、模塊名以及書籍標(biāo)題之類的內(nèi)容。這就是先前使用 mxTextTools 來標(biāo)識(shí)的同一種語言，在先前的部分中，使用正則表達(dá)式和狀態(tài)機(jī)。該語言比完整的編程語言簡(jiǎn)單得多，但已經(jīng)足夠復(fù)雜而有代表性。
這里，我們可能需要回顧一下。 mxTextTools 提供給我們的“標(biāo)記列表”是什么東西？這基本上是一個(gè)嵌套結(jié)構(gòu)，它只是給出了每個(gè)產(chǎn)品在源文本中匹配的字符偏移量。 mxTextTools 快速遍歷源文本，但是它不對(duì)源文本本身 做任何操作（至少當(dāng)使用 SimpleParse 語法時(shí)不進(jìn)行任何操作）。讓我們研究一個(gè)簡(jiǎn)化的標(biāo)記列表：
從 SimpleParse 語法生成的標(biāo)記列表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
(1, [('plain', 0, 15, [('word', 0, 4, [('alphanums', 0, 4, [])]), ('whitespace', 4, 5, []), ('word', 5, 10, [('alphanums', 5, 10, [])]), ('whitespace', 10, 11, []), ('word', 11, 14, [('alphanums', 11, 14, [])]), ('whitespace', 14, 15, [])]), ('markup', 15, 27, ... 289) |
中間的省略號(hào)表示了一批更多的匹配。但是我們看到的部分?jǐn)⑹隽讼铝袃?nèi)容。根產(chǎn)品（“para”）取得成功并結(jié)束于偏移量 289 處（源文本的長(zhǎng)度）。子產(chǎn)品“plain”的偏移量為 0 到 15。“plain”子產(chǎn)品本身由更小的產(chǎn)品組成。在“plain”產(chǎn)品之后，“markup”產(chǎn)品的偏移量為 15 到 27。這里省略了詳細(xì)信息，但是第一個(gè)“markup”由組件組成，并且源文本中稍后還有另外的產(chǎn)品取得成功。
“智能 ASCII”的 EBNF 樣式的語法
我們已經(jīng)瀏覽了 SimpleParse + mxTextTools 所能提供的標(biāo)記列表。但是我們確實(shí)需要研究用來生成這個(gè)標(biāo)記列表的語法。實(shí)際工作在語法中發(fā)生。EBNF 語法讀起來幾乎不需加以說明（盡管 確實(shí)需要一點(diǎn)思考和測(cè)試來設(shè)計(jì)一個(gè)語法）：
typographify.def
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
para := (plain / markup)+plain := (word / whitespace / punctuation)+whitespace := [ \t\r\n]+alphanums := [a-zA-Z0-9]+word := alphanums, (wordpunct, alphanums)*, contraction?wordpunct := [-_]contraction := "'", ('am'/'clock'/'d'/'ll'/'m'/'re'/'s'/'t'/'ve')markup := emph / strong / module / code / titleemph := '-', plain, '-'strong := '*', plain, '*'module := '[', plain, ']'code := "'", plain, "'"title := '_', plain, '_'punctuation := (safepunct / mdash)mdash := '--'safepunct := [!@#$%^&()+=|\{}:;<>,.?/"] |
這種語法和您口頭描述“智能 ASCII”的方式幾乎完全相同，非常清晰。段落由一些純文本和一些標(biāo)記文本組成。純文本由某些字、空白和標(biāo)點(diǎn)符號(hào)的集合組成。標(biāo)記文本可能是強(qiáng)調(diào)文本、著重強(qiáng)調(diào)文本或模塊名等等。著重強(qiáng)調(diào)文本由星號(hào)環(huán)繞。標(biāo)記文本就是由諸如此類的部分組成的。需要考慮的是幾個(gè)特性，類似于到底什么是“字”，或者可以用什么符號(hào)結(jié)束縮寫，但是 EBNF 的句法不會(huì)成為障礙。
相比之下，使用正則表達(dá)式可以更精練地描述同類規(guī)則。“智能 ASCII”標(biāo)記程序的第一個(gè)版本就是這樣做的。但是編寫這種精練難度大得多，并且以后調(diào)整也更為困難。下列代碼表示了很大程度上（但不精確地）相同的規(guī)則集：
智能 ASCII 的 Python regexs
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
# [module] names re_mods = r""'([\(\s'/">]|^)\[(.*?)\]([<\s\.\),:;'"?!/-])"""# *strongly emphasize* words re_strong = r""'([\(\s'/"]|^)\*(.*?)\*([\s\.\),:;'"?!/-])"""# -emphasize- words re_emph = r""'([\(\s'/"]|^)-(.*?)-([\s\.\),:;'"?!/])"""# _Book Title_ citations re_title = r""'([\(\s'/"]|^)_(.*?)_([\s\.\),:;'"?!/-])"""# 'Function()" names re_funcs = r""'([\(\s/"]|^)'(.*?)'([\s\.\),:;"?!/-])""" |
如果您發(fā)現(xiàn)或發(fā)明了該語言的某種經(jīng)過微小更新的變體，將它和 EBNF 語法一起使用要比和那些正則表達(dá)式一起使用簡(jiǎn)單得多。此外，通常使用 mxTextTools 執(zhí)行模式操作甚至更快些。
生成和使用標(biāo)記列表
對(duì)于樣本程序，我們將實(shí)際語法放置在一個(gè)單獨(dú)的文件中。對(duì)于大多數(shù)用途而言，這種組織比較好，便于使用。通常，更改語法和更改應(yīng)用程序邏輯是不同種類的任務(wù)；這些文件反映了這一點(diǎn)。但是我們對(duì)語法所做的全部處理就是將它作為一個(gè)字符串傳遞給 SimpleParse 函數(shù)，因此我們大體上可以將它包括到主應(yīng)用程序中（或者甚至以某種方式動(dòng)態(tài)生成它）。
讓我們研究完整的（簡(jiǎn)化）標(biāo)記應(yīng)用程序：
typographify.py
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import os from sys import stdin, stdout, stderr from simpleparse import generator from mx.TextTools import TextToolsinput = stdin.read()decl = open( 'typographify.def' ).read() from typo_html import codesparser = generator.buildParser(decl).parserbyname( 'para' )taglist = TextTools.tag(input, parser) for tag, beg, end, parts in taglist[1]: if tag == 'plain' : stdout.write(input[beg:end]) elif tag == 'markup' : markup = parts[0] mtag, mbeg, mend = markup[:3] start, stop = codes.get(mtag, ( '<!-- unknown -->' , '<!-- / -->' )) stdout.write(start + input[mbeg+1:mend-1] + stop)stderr.write( 'parsed %s chars of %s\n' % (taglist[-1], len(input))) |
這就是它所做的。首先讀入語法，然后根據(jù)語法創(chuàng)建一個(gè) mxTextTools 解析器。接下來，我們將標(biāo)記表／解析器應(yīng)用于輸入源來創(chuàng)建一個(gè)標(biāo)記列表。最后，我們循環(huán)遍歷標(biāo)記列表，并且發(fā)出一些新的標(biāo)記文本。當(dāng)然，該循環(huán)可以對(duì)遇到的每個(gè)產(chǎn)品做我們所期望的任何其它事情。
由于智能 ASCII 所使用的特殊語法，源文本中的任何內(nèi)容都可歸類于“plain”產(chǎn)品或“markup”產(chǎn)品。因此，對(duì)于循環(huán)遍歷標(biāo)記列表中的單個(gè)級(jí)別，它已經(jīng)足夠了（除非我們正好尋找比特定標(biāo)記產(chǎn)品級(jí)別低一級(jí)的級(jí)別，譬如“title”）。但是格式更自由的語法 ― 譬如出現(xiàn)在大多數(shù)編程語言中的語法 ― 可以輕松地在標(biāo)記列表中向下遞歸，并在每個(gè)級(jí)別上尋找產(chǎn)品名稱。例如，如果一種語法中允許嵌套標(biāo)記代碼，或許可以使用這種遞歸風(fēng)格。您可能會(huì)喜歡弄清如何調(diào)整語法的練習(xí)（提示：請(qǐng)記住允許各產(chǎn)品彼此遞歸）。
轉(zhuǎn)至輸出的特殊標(biāo)記代碼還是存儲(chǔ)到另一個(gè)文件中了，這是由于組織的原因而非本質(zhì)原因。在這里我們使用了一個(gè)技巧，就是用一個(gè)字典作為一個(gè) switch 語句（盡管示例中的 otherwise 情況還是太狹窄了）。這個(gè)想法就是：將來我們可能希望創(chuàng)建多種“輸出格式”的文件，比如說 HTML、DocBook、LaTeX 或者其它格式。用于示例的特殊標(biāo)記文件類似于：
typo_html.py
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
codes = \{ 'emph' : ( '<em>' , '</em>' ), 'strong' : ( '<strong>' , '</strong>' ), 'module' : ( '<em><code>' , '</code></em>' ), 'code' : ( '<code>' , '</code>' ), 'title' : ( '<cite>' , '</cite>' ),} |
把這種格式擴(kuò)展到其它輸出格式很簡(jiǎn)單。
結(jié)束語
SimpleParse 為含義模糊的 mxTextTools C 模塊的基本功能和速度提供了一種簡(jiǎn)明的并且十分易讀的 EBNF 樣式的封裝器。此外，即使只是順便學(xué)會(huì)的，許多程序員也已經(jīng)相當(dāng)熟悉 EBNF 語法了。關(guān)于什么更容易理解，我不能提供 證明 ― 這一點(diǎn)因各人的直覺而異 ― 但是我可以根據(jù)源代碼長(zhǎng)度給出量化評(píng)估。先前手工開發(fā)的 mxTypographify 模塊的大小如下：
199 776 7041 mxTypographify.py
這 199 行中，相當(dāng)數(shù)量的行是注釋。這些行中有 18 行是標(biāo)記函數(shù)所包含的正則表達(dá)式版本，包含該標(biāo)記函數(shù)是用于計(jì)時(shí)比較。但是該程序的功能基本上和上面列出的 typographify.py 的功能相同。相比之下，我們的 SimpleParse 程序，包括其支持文件在內(nèi)，大小如下：
wc typo*.def typo*.py
19 79 645 typographify.def
20 79 721 typographify.py
6 25 205 typo_html.py
45 183 1571 total
換句話說，行數(shù)大約只有前者的四分之一。這個(gè)版本的注釋較少，但是那主要是因?yàn)?EBNF 語法的自我描述能力很強(qiáng)。我不希望太過強(qiáng)調(diào)代碼行數(shù) ― 顯然，您可以通過最小化或最大化代碼長(zhǎng)度做手腳。但是通常對(duì)程序員的工作進(jìn)行研究，少數(shù)實(shí)際經(jīng)驗(yàn)結(jié)論之一是：“千行代碼／人月”相當(dāng)接近于常數(shù)，和語言以及庫關(guān)系不大。當(dāng)然，依次地，正則表達(dá)式版本是 SimpleParse 版本長(zhǎng)度的三分之一 ― 但是我認(rèn)為其表達(dá)式的密度使得它極難維護(hù)并且更難編寫。總而言之，我認(rèn)為 SimpleParse 是所考慮的方法中最好的。
