129      阿裏雲  技術社區[雲棲]

Ohm：用兩百行 JavaScript 創造你自己的編程語言

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

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

為什麼解析器很困難？

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

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

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

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

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

Ohm 簡介

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

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

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

解析整數

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

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

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

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

1. CoolNums {
2. // just a basic integer
3. Number = digit+
4. }

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

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

把它放入 test1.js：

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

Ohm.grammar 調用將讀入該文件並解析成一個語法對象。現在我們可以增加一些語義。把下麵內容增加到你的 JavaScript 文件中：

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

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

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

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

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

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

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

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

1. test("123",123);
2. test("999",999);
3. test("abc",999);

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

你的輸出應該是這樣：

1. success = 123 123
2. success = 999 999
3. input failed to match abcLine 1, col 1:
4. > 1 | abc
5. ^
6. Expected a digit

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

浮點數

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

1. CoolNums {
2. // just a basic integer
3. Number = float | int
4. int = digit+
5. float = digit+ "." digit+
6. }

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

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

1. var sem = grammar.createSemantics().addOperation('toJS', {
2. Number: function(a) {
3. return a.toJS();
4. },
5. int: function(a) {
6. console.log("doing int", this.sourceString);
7. return parseInt(this.sourceString,10);
8. },
9. float: function(a,b,c) {
10. console.log("doing float", this.sourceString);
11. return parseFloat(this.sourceString);
12. }
13. });

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

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

1. float = digit+ "." digit+

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

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

1. test("123",123);
2. test("999",999);
3. //test("abc",999);
4. test('123.456',123.456);
5. test('0.123',0.123);
6. test('.123',0.123);

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

十六進製數

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

在絕大多數源自 C 的編程語言（包括 JavaScript），十六進製數通過在前麵加上 0x 來向編譯器表明後麵跟的是一個十六進製數。為了讓我們的解析器支持十六進製數，我們隻需要添加另一條規則。

1. Number = hex | float | int
2. int = digit+
3. float = digit+ "." digit+
4. hex = "0x" hexDigit+
5. hexDigit := "0".."9" | "a".."f" | "A".."F"

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

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

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

我略過了一些很重要需要注意的事。hexDigit 的規則像下麵這樣：

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

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

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

1. test('0x456',0x456);
2. test('0xFF',255);

科學計數

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

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

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

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

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

1. test('4.8e10',4.8e10);
2. test('4.8e-10',4.8e-10);

結論

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

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

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

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

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

原文發布時間為：2016-09-25

本文來自雲棲社區合作夥伴“Linux中國”

最後更新：2017-06-06 16:32:14

  上一篇：  如何用四個簡單的步驟加速 LibreOffice

  下一篇：  理解 Linux 下 Shell 命令的不同分類及它們的用法