[[172341]]

解析器是一種超級有用的軟件庫。從概念上簡單的說，它們的實(shí)現(xiàn)很有挑戰(zhàn)性，并且在計(jì)算機(jī)科學(xué)中經(jīng)常被認(rèn)為是黑魔法。在這個系列的博文中，我會向你們展示為什么你不需要成為哈利波特就能夠精通解析器這種魔法。但是為了以防萬一帶上你的魔杖吧!

我們將探索一種叫做 Ohm 的新的開源庫，它使得搭建解析器很簡單并且易于重用。在這個系列里，我們使用 Ohm 去識別數(shù)字，構(gòu)建一個計(jì)算器等等。在這個系列的***你將已經(jīng)用不到 200 行的代碼發(fā)明了一種完整的編程語言。這個強(qiáng)大的工具將讓你能夠做到一些你可能過去認(rèn)為不可能的事情。

為什么解析器很困難?

解析器非常有用。在很多時候你可能需要一個解析器。或許有一種你需要處理的新的文件格式，但還沒有人為它寫了一個庫;又或許你發(fā)現(xiàn)了一種古老格式的文件，但是已有的解析器不能在你的平臺上構(gòu)建。我已經(jīng)看到這樣的事發(fā)生無數(shù)次。 Code 在或者不在， Data 就在那里，不增不減。

從根本上來說，解析器很簡單：只是把一個數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化成另一個。所以你會不會覺得你要是鄧布利多校長就好了?

解析器歷來是出奇地難寫，所面臨的挑戰(zhàn)是絕大多數(shù)現(xiàn)有的工具都很老，并且需要一定的晦澀難懂的計(jì)算機(jī)科學(xué)知識。如果你在大學(xué)里上過編譯器課程，那么課本里也許還有從上世紀(jì)七十年傳下來的技術(shù)。幸運(yùn)的是，解析器技術(shù)從那時候起已經(jīng)提高了很多。

典型的，解析器是通過使用一種叫作形式語法(formal grammar)的特殊語法來定義你想要解析的東西來創(chuàng)造的，然后你需要把它放入像 Bison 和 Yacc 的工具中，這些工具能夠產(chǎn)生一堆 C 代碼，這些代碼你需要修改或者鏈接到你實(shí)際寫入的編程語言中。另外的選擇是用你更喜歡的語言親自動手寫一個解析器，這很慢且很容易出錯，在你能夠真正使用它之前還有許多額外的工作。

想像一下，是否你關(guān)于你想要解析的東西的語法描述也是解析器?如果你能夠只是直接運(yùn)行這些語法，然后僅在你需要的地方增加一些掛鉤(hook)呢?那就是 Ohm 所可以做到的事。

Ohm 簡介

Ohm 是一種新的解析系統(tǒng)。它類似于你可能已經(jīng)在課本里面看到過的語法，但是它更強(qiáng)大，使用起來更簡單。通過 Ohm, 你能夠使用一種靈活的語法在一個 .ohm 文件中來寫你自己的格式定義，然后使用你的宿主語言把語義加入到里面。在這篇博文里，我們將用 JavaScript 作為宿主語言。

Ohm 建立于一個為創(chuàng)造更簡單、更靈活的解析器的多年研究基礎(chǔ)之上。VPRI 的 STEPS program (pdf) 使用 Ohm 的前身 Ometa 為許多特殊的任務(wù)創(chuàng)造了專門的語言(比如一個有 400 行代碼的平行制圖描繪器)。

Ohm 有許多有趣的特點(diǎn)和符號，但是相比于全部解釋它們，我認(rèn)為我們只需要深入其中并構(gòu)建一些東西就行了。

解析整數(shù)

讓我們來解析一些數(shù)字。這看起來會很簡單，只需在一個文本串中尋找毗鄰的數(shù)字，但是讓我們嘗試去處理所有形式的數(shù)字：整數(shù)和浮點(diǎn)數(shù)、十六進(jìn)制數(shù)和八進(jìn)制數(shù)、科學(xué)計(jì)數(shù)、負(fù)數(shù)。解析數(shù)字很簡單，正確解析卻很難。

親自構(gòu)建這個代碼將會很困難，會有很多問題，會伴隨有許多特殊的情況，比如有時會相互矛盾。正則表達(dá)式或許可以做的這一點(diǎn)，但是它會非常丑陋而難以維護(hù)。讓我們用 Ohm 來試試。

用 Ohm 構(gòu)建的解析器涉及三個部分：語法(grammar)、語義(semantics)和測試(tests)。我通常挑選問題的一部分為它寫測試，然后構(gòu)建足夠的語法和語義來使測試通過。然后我再挑選問題的另一部分，增加更多的測試、更新語法和語義，從而確保所有的測試能夠繼續(xù)通過。即使我們有了新的強(qiáng)大的工具，寫解析器從概念上來說依舊很復(fù)雜。測試是用一種合理的方式來構(gòu)建解析器的唯一方法?，F(xiàn)在，讓我們開始工作。

我們將從整數(shù)開始。一個整數(shù)由一系列相互毗鄰的數(shù)字組成。讓我們把下面的內(nèi)容放入一個叫做 grammar.ohm 的文件中：

CoolNums { 
   // just a basic integer 
   Number = digit+ 
} 

這創(chuàng)造了一條匹配一個或多個數(shù)字(digit)叫作 Number 的單一規(guī)則。+ 意味著一個或更多，就在正則表達(dá)式中一樣。當(dāng)有一個或更多的數(shù)字時，這個規(guī)則將會匹配它們，如果沒有數(shù)字或者有一些不是數(shù)字的東西將不會匹配。“數(shù)字(digit)”的定義是從 0 到 9 其中的一個字符。digit 也是像 Number 一樣的規(guī)則，但是它是 Ohm 的其中一條構(gòu)建規(guī)則因此我們不需要去定義它。如果我們想的話可以推翻它，但在這時候這沒有任何意義，畢竟我們不打算去發(fā)明一種新的數(shù)。

現(xiàn)在，我們可以讀入這個語法并用 Ohm 庫來運(yùn)行它。

把它放入 test1.js： 

var ohm = require('ohm-js'); 
var fs = require('fs'); 
var assert = require('assert'); 
var grammar = ohm.grammar(fs.readFileSync('src/blog_numbers/syntax1.ohm').toString()); 

Ohm.grammar 調(diào)用將讀入該文件并解析成一個語法對象?，F(xiàn)在我們可以增加一些語義。把下面內(nèi)容增加到你的 JavaScript 文件中：

var sem = grammar.createSemantics().addOperation('toJS', { 
    Number: function(a) { 
        return parseInt(this.sourceString,10); 
    } 
}); 

這通過 toJS 操作創(chuàng)造了一個叫作 sem 的語法集。這些語義本質(zhì)上是一些對應(yīng)到語法中每個規(guī)則的函數(shù)。每個函數(shù)當(dāng)與之相匹配的語法規(guī)則被解析時將會被調(diào)用。上面的 Number 函數(shù)將會在語法中的 Number 規(guī)則被解析時被調(diào)用。語法(grammar)定義了在語言中這些代碼是什么，語義(semantics)定義了當(dāng)這些代碼被解析時應(yīng)該做什么。

語義函數(shù)能夠做我們想做的任何事，比如打印出故障信息、創(chuàng)建對象，或者在任何子節(jié)點(diǎn)上遞歸調(diào)用 toJS。此時我們僅僅想把匹配的文本轉(zhuǎn)換成真正的 JavaScript 整數(shù)。

所有的語義函數(shù)有一個內(nèi)含的 this 對象，帶有一些有用的屬性。其 source 屬性代表了輸入文本中和這個節(jié)點(diǎn)相匹配的部分。this.sourceString 是一個匹配輸入的串，調(diào)用內(nèi)置在 JavaScript 中的 parseInt 函數(shù)會把這個串轉(zhuǎn)換成一個數(shù)。傳給 parseInt 的 10 這個參數(shù)告訴 JavaScript 我們輸入的是一個以 10 為基底(10 進(jìn)制)的數(shù)。如果少了這個參數(shù)， JavaScript 也會假定以 10 為基底，但是我們把它包含在里面因?yàn)楹竺嫖覀儗⒅С忠?16 為基底的數(shù)，所以使之明確比較好。

既然我們有一些語法，讓我們來實(shí)際解析一些東西看一看我們的解析器是否能夠工作。如何知道我們的解析器可以工作?通過測試，許多許多的測試，每一個可能的邊緣情況都需要一個測試。

使用標(biāo)準(zhǔn)的斷言 assert API，以下這個測試函數(shù)能夠匹配一些輸入并運(yùn)用我們的語義把它轉(zhuǎn)換成一個數(shù)，然后把這個數(shù)和我們期望的輸入進(jìn)行比較。

function test(input, answer) { 
  var match = grammar.match(input); 
  if(match.failed()) return console.log("input failed to match " + input + match.message);      
  var result = sem(match).toJS(); 
  assert.deepEqual(result,answer); 
  console.log('success = ', result, answer); 
 } 

就是如此。現(xiàn)在我們能夠?yàn)楦鞣N不同的數(shù)寫一堆測試。如果匹配失敗我們的腳本將會拋出一個例外。否則就打印成功信息。讓我們嘗試一下，把下面這些內(nèi)容加入到腳本中： 

test("123",123); 
test("999",999); 
test("abc",999); 

然后用 node test1.js 運(yùn)行腳本。

你的輸出應(yīng)該是這樣：

success =  123 123 
success =  999 999 
input failed to match abcLine 1, col 1: 
> 1 | abc 
      ^ 
Expected a digit 

真酷。正如預(yù)期的那樣，前兩個成功了，第三個失敗了。更好的是，Ohm 自動給了我們一個很棒的錯誤信息指出匹配失敗。

浮點(diǎn)數(shù)

我們的解析器工作了，但是它做的工作不是很有趣。讓我們把它擴(kuò)展成既能解析整數(shù)又能解析浮點(diǎn)數(shù)。改變 grammar.ohm 文件使它看起來像下面這樣：

CoolNums { 
  // just a basic integer 
  Number = float | int 
  int    = digit+ 
  float  = digit+ "." digit+ 
} 

這把 Number 規(guī)則改變成指向一個浮點(diǎn)數(shù)(float)或者一個整數(shù)(int)。這個 | 代表著“或”。我們把這個讀成“一個 Number 由一個浮點(diǎn)數(shù)或者一個整數(shù)構(gòu)成。”然后整數(shù)(int)定義成 digit+，浮點(diǎn)數(shù)(float)定義成 digit+ 后面跟著一個句號然后再跟著另一個 digit+。這意味著在句號前和句號后都至少要有一個數(shù)字。如果一個數(shù)中沒有一個句號那么它就不是一個浮點(diǎn)數(shù)，因此就是一個整數(shù)。

現(xiàn)在，讓我們再次看一下我們的語義功能。由于我們現(xiàn)在有了新的規(guī)則所以我們需要新的功能函數(shù)：一個作為整數(shù)的，一個作為浮點(diǎn)數(shù)的。

var sem = grammar.createSemantics().addOperation('toJS', { 
    Number: function(a) { 
        return a.toJS(); 
    }, 
    int: function(a) { 
        console.log("doing int", this.sourceString); 
        return parseInt(this.sourceString,10); 
    }, 
    float: function(a,b,c) { 
        console.log("doing float", this.sourceString); 
        return parseFloat(this.sourceString); 
    } 
}); 

這里有兩件事情需要注意。首先，整數(shù)(int)、浮點(diǎn)數(shù)(float)和數(shù)(Number)都有相匹配的語法規(guī)則和函數(shù)。然而，針對 Number 的功能不再有任何意義。它接收子節(jié)點(diǎn) a 然后返回該子節(jié)點(diǎn)的 toJS 結(jié)果。換句話說，Number 規(guī)則簡單的返回相匹配的子規(guī)則。由于這是在 Ohm 中任何規(guī)則的默認(rèn)行為，因此實(shí)際上我們不用去考慮 Number 的作用，Ohm 會替我們做好這件事。

其次，整數(shù)(int)有一個參數(shù) a，然而浮點(diǎn)數(shù)有三個：a、b 和 c。這是由于規(guī)則的實(shí)參數(shù)量(arity)決定的。實(shí)參數(shù)量(arity)意味著一個規(guī)則里面有多少參數(shù)。如果我們回過頭去看語法，浮點(diǎn)數(shù)(float)的規(guī)則是： 

float  = digit+ "." digit+ 

浮點(diǎn)數(shù)規(guī)則通過三個部分來定義：***個 digit+、.、以及第二個 digit+。這三個部分都會作為參數(shù)傳遞給浮點(diǎn)數(shù)的功能函數(shù)。因此浮點(diǎn)數(shù)必須有三個參數(shù)，否則 Ohm 庫會給出一個錯誤。在這種情況下我們不用在意參數(shù)，因?yàn)槲覀儍H僅直接攫取了輸入串，但是我們?nèi)匀恍枰獏?shù)列在那里來避免編譯器錯誤。后面我們將實(shí)際使用其中一些參數(shù)。

現(xiàn)在我們可以為新的浮點(diǎn)數(shù)支持添加更多的測試。

test("123",123); 
test("999",999); 
//test("abc",999); 
test('123.456',123.456); 
test('0.123',0.123); 
test('.123',0.123); 

注意***一個測試將會失敗。一個浮點(diǎn)數(shù)必須以一個數(shù)開始，即使它就是個 0，.123 不是有效的，實(shí)際上真正的 JavaScript 語言也有相同的規(guī)則。

十六進(jìn)制數(shù)

現(xiàn)在我們已經(jīng)有了整數(shù)和浮點(diǎn)數(shù)，但是還有一些其它的數(shù)的語法***可以支持：十六進(jìn)制數(shù)和科學(xué)計(jì)數(shù)。十六進(jìn)制數(shù)是以 16 為基底的整數(shù)。十六進(jìn)制數(shù)的數(shù)字能從 0 到 9 和從 A 到 F。十六進(jìn)制數(shù)經(jīng)常用在計(jì)算機(jī)科學(xué)中，當(dāng)用二進(jìn)制數(shù)據(jù)工作時，你可以僅僅使用兩個數(shù)字表示 0 到 255 的數(shù)。

在絕大多數(shù)源自 C 的編程語言(包括 JavaScript)，十六進(jìn)制數(shù)通過在前面加上 0x 來向編譯器表明后面跟的是一個十六進(jìn)制數(shù)。為了讓我們的解析器支持十六進(jìn)制數(shù)，我們只需要添加另一條規(guī)則。 

Number = hex | float | int 
int    = digit+ 
float  = digit+ "." digit+ 
hex    = "0x" hexDigit+ 
hexDigit := "0".."9" | "a".."f" | "A".."F" 

我實(shí)際上已經(jīng)增加了兩條規(guī)則。十六進(jìn)制數(shù)(hex)表明它是一個 0x 后面一個或多個十六進(jìn)制數(shù)字(hexDigits)的串。一個十六進(jìn)制數(shù)字(hexDigit)是從 0 到 9，或從 a 到 f，或 A 到 F(包括大寫和小寫的情況)的一個字符。我也修改了 Number 規(guī)則來識別十六進(jìn)制數(shù)作為另外一種可能的情況。現(xiàn)在我們只需要另一條針對十六進(jìn)制數(shù)的功能規(guī)則。 

hex: function(a,b) { 
    return parseInt(this.sourceString,16); 
} 

注意到，在這種情況下，我們把 16 作為基底傳遞給 parseInt，因?yàn)槲覀兿Ｍ?JavaScript 知道這是一個十六進(jìn)制數(shù)。

我略過了一些很重要需要注意的事。hexDigit 的規(guī)則像下面這樣： 

hexDigit := "0".."9" | "a".."f" | "A".."F" 

注意我使用的是 := 而不是 =。在 Ohm 中，:= 是當(dāng)你需要推翻一條規(guī)則的時候使用。這表明 Ohm 已經(jīng)有了一條針對 hexDigit 的默認(rèn)規(guī)則，就像 digit、space 等一堆其他的東西。如果我使用了 =, Ohm 將會報告一個錯誤。這是一個檢查，從而避免我無意識的推翻一個規(guī)則。由于新的 hexDigit 規(guī)則和 Ohm 的構(gòu)建規(guī)則一樣，所以我們可以把它注釋掉，然后讓 Ohm 自己來實(shí)現(xiàn)它。我留下這個規(guī)則只是因?yàn)檫@樣我們可以看到它實(shí)際上是如何進(jìn)行的。

現(xiàn)在，我們可以添加更多的測試然后看到十六進(jìn)制數(shù)真的能工作：

test('0x456',0x456); 
test('0xFF',255); 

科學(xué)計(jì)數(shù)

***，讓我們來支持科學(xué)計(jì)數(shù)?？茖W(xué)計(jì)數(shù)是針對非常大或非常小的數(shù)的，比如 1.8×10^3。在大多數(shù)編程語言中，科學(xué)計(jì)數(shù)法表示的數(shù)會寫成這樣：1.8e3 表示 18000，或者 1.8e-3 表示 .018。讓我們增加另外一對規(guī)則來支持這個指數(shù)表示： 

float  = digit+ "." digit+ exp? 
exp    = "e" "-"? digit+ 

上面在浮點(diǎn)數(shù)規(guī)則末尾增加了一個指數(shù)(exp)規(guī)則和一個 ?。? 表示沒有或有一個，所以指數(shù)(exp)是可選的，但是不能超過一個。增加指數(shù)(exp)規(guī)則也改變了浮點(diǎn)數(shù)規(guī)則的實(shí)參數(shù)量，所以我們需要為浮點(diǎn)數(shù)功能增加另一個參數(shù)，即使我們不使用它。 

float: function(a,b,c,d) { 
        console.log("doing float", this.sourceString); 
        return parseFloat(this.sourceString); 
    }, 

現(xiàn)在我們的測試可以通過了：

test('4.8e10',4.8e10); 
test('4.8e-10',4.8e-10); 

結(jié)論

Ohm 是構(gòu)建解析器的一個很棒的工具，因?yàn)樗子谏鲜郑⑶夷憧梢赃f增的增加規(guī)則。Ohm 也還有其他我今天沒有寫到的很棒的特點(diǎn)，比如調(diào)試觀察儀和子類化。

到目前為止，我們已經(jīng)使用 Ohm 來把字符串翻譯成 JavaScript 數(shù)，并且 Ohm 經(jīng)常用于把一種表示方式轉(zhuǎn)化成另外一種。然而，Ohm 還有更多的用途。通過放入不同的語義功能集，你可以使用 Ohm 來真正處理和計(jì)算東西。一個單獨(dú)的語法可以被許多不同的語義使用，這是 Ohm 的魔法之一。

在這個系列的下一篇文章中，我將向你們展示如何像真正的計(jì)算機(jī)一樣計(jì)算像 (4.85 + 5 * (238 - 68)/2) 這樣的數(shù)學(xué)表達(dá)式，不僅僅是解析數(shù)。

額外的挑戰(zhàn)：你能夠擴(kuò)展語法來支持八進(jìn)制數(shù)嗎?這些以 8 為基底的數(shù)能夠只用 0 到 7 這幾個數(shù)字來表示，前面加上一個數(shù)字 0 或者字母 o?？纯瘁槍ο旅孢@些測試情況是夠正確。下次我將給出答案。 

test('0o77',7*8+7); 
test('0o23',0o23);