亚洲国产日韩欧美一区二区三区,精品亚洲国产成人av在线,国产99视频精品免视看7,99国产精品久久久久久久成人热,欧美日韩亚洲国产综合乱

搜索

用兩百行JavaScript創(chuàng)造你自己的編程語(yǔ)言

原創(chuàng) 2016-11-10 16:53:58 334
摘要:解析器是一種超級(jí)有用的軟件庫(kù)。從概念上簡(jiǎn)單的說(shuō),它們的實(shí)現(xiàn)很有挑戰(zhàn)性,并且在計(jì)算機(jī)科學(xué)中經(jīng)常被認(rèn)為是黑魔法。在這個(gè)系列的博文中,我會(huì)向你們展示為什么你不需要成為哈利波特就能夠精通解析器這種魔法。但是為了以防萬(wàn)一帶上你的魔杖吧!我們將探索一種叫做 Ohm 的新的開(kāi)源庫(kù),它使得搭建解析器很簡(jiǎn)單并且易于重用。在這個(gè)系列里,我們使用 Ohm 去識(shí)別數(shù)字,構(gòu)建一個(gè)計(jì)算器等等。在這個(gè)系列的最后你將已經(jīng)用不到

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

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

為什么解析器很困難?

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

從根本上來(lái)說(shuō),解析器很簡(jiǎn)單:只是把一個(gè)數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化成另一個(gè)。所以你會(huì)不會(huì)覺(jué)得你要是鄧布利多校長(zhǎng)就好了?

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

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

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

Ohm 簡(jiǎn)介

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

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

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

解析整數(shù)

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

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

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

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

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

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

現(xiàn)在,我們可以讀入這個(gè)語(yǔ)法并用 Ohm 庫(kù)來(lái)運(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)用將讀入該文件并解析成一個(gè)語(yǔ)法對(duì)象?,F(xiàn)在我們可以增加一些語(yǔ)義。把下面內(nèi)容增加到你的 JavaScript 文件中:

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

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

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

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

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

使用標(biāo)準(zhǔn)的斷言 assert API,以下這個(gè)測(cè)試函數(shù)能夠匹配一些輸入并運(yùn)用我們的語(yǔ)義把它轉(zhuǎn)換成一個(gè)數(shù),然后把這個(gè)數(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ù)寫一堆測(cè)試。如果匹配失敗我們的腳本將會(huì)拋出一個(gè)例外。否則就打印成功信息。讓我們嘗試一下,把下面這些內(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ù)期的那樣,前兩個(gè)成功了,第三個(gè)失敗了。更好的是,Ohm 自動(dòng)給了我們一個(gè)很棒的錯(cuò)誤信息指出匹配失敗。

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

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

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

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

現(xiàn)在,讓我們?cè)俅慰匆幌挛覀兊恼Z(yǔ)義功能。由于我們現(xiàn)在有了新的規(guī)則所以我們需要新的功能函數(shù):一個(gè)作為整數(shù)的,一個(gè)作為浮點(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)都有相匹配的語(yǔ)法規(guī)則和函數(shù)。然而,針對(duì) Number 的功能不再有任何意義。它接收子節(jié)點(diǎn) a 然后返回該子節(jié)點(diǎn)的 toJS 結(jié)果。換句話說(shuō),Number 規(guī)則簡(jiǎn)單的返回相匹配的子規(guī)則。由于這是在 Ohm 中任何規(guī)則的默認(rèn)行為,因此實(shí)際上我們不用去考慮 Number 的作用,Ohm 會(huì)替我們做好這件事。

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

float  = digit+ "." digit+

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

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

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

注意最后一個(gè)測(cè)試將會(huì)失敗。一個(gè)浮點(diǎn)數(shù)必須以一個(gè)數(shù)開(kāi)始,即使它就是個(gè) 0,.123 不是有效的,實(shí)際上真正的 JavaScript 語(yǔ)言也有相同的規(guī)則。

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

現(xiàn)在我們已經(jīng)有了整數(shù)和浮點(diǎn)數(shù),但是還有一些其它的數(shù)的語(yǔ)法最好可以支持:十六進(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í),你可以僅僅使用兩個(gè)數(shù)字表示 0 到 255 的數(shù)。

在絕大多數(shù)源自 C 的編程語(yǔ)言(包括 JavaScript),十六進(jìn)制數(shù)通過(guò)在前面加上 0x 來(lái)向編譯器表明后面跟的是一個(gè)十六進(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)表明它是一個(gè) 0x 后面一個(gè)或多個(gè)十六進(jìn)制數(shù)字(hexDigits)的串。一個(gè)十六進(jìn)制數(shù)字(hexDigit)是從 0 到 9,或從 a 到 f,或 A 到 F(包括大寫和小寫的情況)的一個(gè)字符。我也修改了 Number 規(guī)則來(lái)識(shí)別十六進(jìn)制數(shù)作為另外一種可能的情況?,F(xiàn)在我們只需要另一條針對(duì)十六進(jìn)制數(shù)的功能規(guī)則。

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

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

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

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

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

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

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

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

最后,讓我們來(lái)支持科學(xué)計(jì)數(shù)??茖W(xué)計(jì)數(shù)是針對(duì)非常大或非常小的數(shù)的,比如 1.8×10^3。在大多數(shù)編程語(yǔ)言中,科學(xué)計(jì)數(shù)法表示的數(shù)會(huì)寫成這樣:1.8e3 表示 18000,或者 1.8e-3 表示 .018。讓我們?cè)黾恿硗庖粚?duì)規(guī)則來(lái)支持這個(gè)指數(shù)表示:

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

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

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

現(xiàn)在我們的測(cè)試可以通過(guò)了:

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

結(jié)論

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

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

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

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

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


發(fā)布手記

熱門詞條