[[172341]]

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

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

為什么解析器很困難?

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

從根本上來說，解析器很簡單：只是把一個數據結構轉化成另一個。所以你會不會覺得你要是鄧布利多校長就好了?

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

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

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

Ohm 簡介

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

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

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

解析整數

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

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

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

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

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

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

現在，我們可以讀入這個語法并用 Ohm 庫來運行它。

把它放入 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 調用將讀入該文件并解析成一個語法對象。現在我們可以增加一些語義。把下面內容增加到你的 JavaScript 文件中：

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

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

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

所有的語義函數有一個內含的 this 對象，帶有一些有用的屬性。其 source 屬性代表了輸入文本中和這個節(jié)點相匹配的部分。this.sourceString 是一個匹配輸入的串，調用內置在 JavaScript 中的 parseInt 函數會把這個串轉換成一個數。傳給 parseInt 的 10 這個參數告訴 JavaScript 我們輸入的是一個以 10 為基底(10 進制)的數。如果少了這個參數， JavaScript 也會假定以 10 為基底，但是我們把它包含在里面因為后面我們將支持以 16 為基底的數，所以使之明確比較好。

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

使用標準的斷言 assert API，以下這個測試函數能夠匹配一些輸入并運用我們的語義把它轉換成一個數，然后把這個數和我們期望的輸入進行比較。

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); 
 } 

就是如此。現在我們能夠為各種不同的數寫一堆測試。如果匹配失敗我們的腳本將會拋出一個例外。否則就打印成功信息。讓我們嘗試一下，把下面這些內容加入到腳本中： 

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

然后用 node test1.js 運行腳本。

你的輸出應該是這樣：

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

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

浮點數

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

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

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

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

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); 
    } 
}); 

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

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

float  = digit+ "." digit+ 

浮點數規(guī)則通過三個部分來定義：***個 digit+、.、以及第二個 digit+。這三個部分都會作為參數傳遞給浮點數的功能函數。因此浮點數必須有三個參數，否則 Ohm 庫會給出一個錯誤。在這種情況下我們不用在意參數，因為我們僅僅直接攫取了輸入串，但是我們仍然需要參數列在那里來避免編譯器錯誤。后面我們將實際使用其中一些參數。

現在我們可以為新的浮點數支持添加更多的測試。

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

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

十六進制數

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

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

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

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

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

注意到，在這種情況下，我們把 16 作為基底傳遞給 parseInt，因為我們希望 JavaScript 知道這是一個十六進制數。

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

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

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

現在，我們可以添加更多的測試然后看到十六進制數真的能工作：

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

科學計數

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

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

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

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

現在我們的測試可以通過了：

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

結論

Ohm 是構建解析器的一個很棒的工具，因為它易于上手，并且你可以遞增的增加規(guī)則。Ohm 也還有其他我今天沒有寫到的很棒的特點，比如調試觀察儀和子類化。

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

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

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

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