院長(zhǎng)，別說(shuō)了，拔刀吧

三天狂風(fēng)暴雨般的發(fā)泄后，憔悴的小劉坐在臺(tái)階上吸著煙，開(kāi)始想怎么去做這個(gè)事。有兩種方案：

• 1:選一門現(xiàn)成的編程語(yǔ)言，但大部分都是老外寫(xiě)的，語(yǔ)言關(guān)鍵字和規(guī)則繁多，老人們吃不消
• 2:自己設(shè)計(jì)一門中文的編程語(yǔ)言，實(shí)現(xiàn)簡(jiǎn)單的輸入輸出，告訴老人什么是編程就行了

小劉選擇自己設(shè)計(jì)一門編程語(yǔ)言，提筆一揮，寥寥的在小字本上涂涂畫(huà)畫(huà)。

定義 A,B,C;
B 等于 3;
輸入 A ;
C 等于 A乘B;
輸出 C;

當(dāng)然，上面的例子，這只是小劉寫(xiě)在小字本上的草稿，具體語(yǔ)言規(guī)則怎么定義？怎么解析這個(gè)語(yǔ)言？怎么執(zhí)行這個(gè)語(yǔ)言？懵逼的小劉開(kāi)始查閱一些資料。了解市面上的語(yǔ)言是如何實(shí)現(xiàn)的。

小劉的故事先說(shuō)到這兒。我們開(kāi)始嚴(yán)肅一點(diǎn)...

『設(shè)計(jì)模式』中有一個(gè)模式可以解釋特定的語(yǔ)法規(guī)則，它就是解釋器模式（Interpreter Pattern），不同于的工廠模式或者策略模式，解釋器模式在java或者.net中并不常見(jiàn)，業(yè)務(wù)中很少用去解釋特定的語(yǔ)法，所以并不被廣泛的使用。一個(gè)解釋器可大可小，大可為復(fù)雜的編譯器，小可以是一個(gè)簡(jiǎn)單的字符串解析。但本質(zhì)都是對(duì)特定語(yǔ)法做出合理解釋。

假設(shè)輸入一個(gè)公式字符串: 1+2*3 注意這是一個(gè)字符串，要解析這個(gè)公式字符串，得到最終的值我們有兩種方案：

• 循環(huán)遍歷字符串，將括號(hào)，運(yùn)算符，數(shù)字提取出來(lái)，然后根據(jù)運(yùn)算符左右結(jié)合以及優(yōu)先級(jí)來(lái)計(jì)算
• 將表達(dá)式轉(zhuǎn)換為樹(shù)結(jié)構(gòu)的對(duì)象，樹(shù)結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)，可以是數(shù)字，可以是運(yùn)算符，每個(gè)節(jié)點(diǎn)類型不
  同，然后遞歸遍歷這個(gè)樹(shù)結(jié)構(gòu)，遇到運(yùn)算符號(hào)節(jié)點(diǎn)，遞歸求運(yùn)算符節(jié)點(diǎn)下的左右節(jié)點(diǎn)值，然后將兩個(gè)節(jié)點(diǎn)值做相應(yīng)的運(yùn)算。
  很顯然，第一種方案簡(jiǎn)單直白易理解，但實(shí)現(xiàn)起來(lái)相當(dāng)繁重，代碼可讀性也不佳。第二種則是目前最好的解決方式,將表達(dá)式字符串解析為一個(gè)對(duì)象樹(shù)。

所以我們的第一個(gè)難點(diǎn)是如何將表達(dá)式轉(zhuǎn)換為一顆樹(shù)

對(duì)于算術(shù)表達(dá)式而言，比如1+3-2，6-1，語(yǔ)法是兩個(gè)數(shù)字之間必須出現(xiàn)+，-，*，/，如果出現(xiàn)1+-2,6--1那這就是錯(cuò)誤的語(yǔ)法
那我們?cè)趺磥?lái)制定語(yǔ)法呢，在編譯原理領(lǐng)域，有一個(gè)通用的方法來(lái)描述語(yǔ)法，叫是BNF范式

語(yǔ)言的描述——BNF范式

為什么不用自然語(yǔ)言來(lái)定義我們的語(yǔ)言的規(guī)范？很難??！，現(xiàn)在自然語(yǔ)言處理，仍然是世界性的難題，目前還沒(méi)有哪種程序能夠?qū)⒆匀徽Z(yǔ)言處理的很好。

描述一個(gè)文法，我們常常使用巴斯克范式（BNF范式）來(lái)描述一個(gè)文法的結(jié)構(gòu)

科普一下，世間萬(wàn)語(yǔ)，皆可用歸納為4種文法，計(jì)算機(jī)編程主要使用 2型，3型 文法。（0，1型交給我們語(yǔ)文老師處理了）

• 0型即自然語(yǔ)言文法
• 1型稱為上下文相關(guān)文法
• 2型稱為上下文無(wú)關(guān)文法
• 3型稱為正則文法

簡(jiǎn)單介紹一下bnf范式文件格式

• < > 尖括號(hào)內(nèi)為必選項(xiàng)
• | 豎線表示在其左右兩邊任選一項(xiàng)，相當(dāng)于"OR"的意思
• ::= 是“被定義為”的意思
  一條BNF的生成規(guī)則形如：

<char>  ::= A|B|C|D|E|F|G|H|... 偷個(gè)懶

更詳細(xì)的規(guī)則，可參考巴科斯范式

針對(duì)上面四則運(yùn)算，簡(jiǎn)單的 bnf 文件內(nèi)容如下：

<exp>  ::= <fac>|<fac>+<exp>|<fac>-<exp>
<fac>  ::= <int>|<int>*<int>|<int>/<int>
<int>  ::= <digit><int>|<digit>
<digit>  ::= 0|1|2|3|4|5|6|7|8|9

digt: 數(shù)字，int 整形，fac:優(yōu)先級(jí)高的運(yùn)算，exp:表達(dá)式

有了bnf范式規(guī)則，我們需要表達(dá)式字符串1+3-2構(gòu)造成一個(gè)符合bnf規(guī)則的數(shù)據(jù)結(jié)構(gòu)，如下圖：

四則運(yùn)算_ast.png

我們需要自己寫(xiě)解析函數(shù)，然后構(gòu)造成上圖所示的數(shù)據(jù)結(jié)構(gòu)，在編譯原理領(lǐng)域這種結(jié)構(gòu)叫 抽象語(yǔ)法樹(shù)(AST)

簡(jiǎn)單介紹一下抽象語(yǔ)法樹(shù)

抽象語(yǔ)法樹(shù)（AST）

語(yǔ)言解釋分為前后端，前端語(yǔ)言 java,c,php,js。后端主要是指編譯器 例如 GJC,GCC 等。

例如實(shí)現(xiàn)一個(gè)c 版的 for 循環(huán)，需要用GCC 將c 源代碼編譯成一個(gè)GCC語(yǔ)言版抽象語(yǔ)法樹(shù)，然后GCC 在解釋執(zhí)行這個(gè)抽象語(yǔ)法樹(shù)。

抽象語(yǔ)法樹(shù)特點(diǎn)

• 不依賴源語(yǔ)言文法
  如果按bnf 文法解析源代碼，解析為一個(gè)自定義的結(jié)構(gòu)，那在解釋這個(gè)自定義結(jié)構(gòu)的時(shí)候，肯定是為bnf 文法量身定制的。一旦這個(gè)語(yǔ)言有了升級(jí)，bnf 文法發(fā)生變動(dòng)，相應(yīng)的，后端解釋器也會(huì)做相應(yīng)的改動(dòng)，十分麻煩。
  抽象語(yǔ)法樹(shù)，相當(dāng)于一個(gè)后端解釋器給前端定制的一個(gè)規(guī)范，無(wú)論語(yǔ)言規(guī)范怎么變動(dòng)，只需要改變將源代碼解析為抽象語(yǔ)法樹(shù)的解析器就行了，解析抽象語(yǔ)法樹(shù)的解釋器并不用改動(dòng)。

• 不依賴細(xì)節(jié)
  不同語(yǔ)言實(shí)現(xiàn)一個(gè)for 循環(huán)
  在c中為：

if(condition){
  dosomthing();
}

在fortran中為：

If condition then
    dosomthing()
end if

語(yǔ)法樹(shù)只需要兩個(gè)分支節(jié)點(diǎn)來(lái)表示

AST_IF.png

在源程序中出現(xiàn)的關(guān)鍵字 if 括號(hào)等，都將忽略，兩種語(yǔ)言最終生成一樣的抽象語(yǔ)法樹(shù)

抽象語(yǔ)法樹(shù)作用

前端領(lǐng)域使用抽象語(yǔ)法樹(shù)極為廣泛，將js代碼轉(zhuǎn)換為抽象語(yǔ)法樹(shù)后，可以很輕松的對(duì)語(yǔ)法樹(shù)進(jìn)行分析與優(yōu)化，語(yǔ)法樹(shù)帶給我們的便利充斥在開(kāi)發(fā)過(guò)程中的方方面面，例如IDE對(duì)代碼進(jìn)行格式化縮進(jìn)。
簡(jiǎn)單列舉抽象語(yǔ)法樹(shù)，的作用：

• 格式化存儲(chǔ)（存儲(chǔ)網(wǎng)頁(yè)，存儲(chǔ)sql 語(yǔ)句，描述json 的json）
• 語(yǔ)法檢查、格式化、高亮、錯(cuò)誤提示、代自動(dòng)補(bǔ)全
  • ide 功能糖
• 代碼混淆
  • uglifyjs
  • CssMinify
• 代碼優(yōu)化
  • webpack 梳理依賴關(guān)系
  • amd,cmd 規(guī)范相互轉(zhuǎn)換
  • bable 編譯 es6
  • CoffeeScript、TypeScript、JSX等轉(zhuǎn)化為原生Javascript

抽象語(yǔ)法樹(shù)結(jié)構(gòu)

將 javascript 源代碼 1+1 轉(zhuǎn)換為抽象語(yǔ)法樹(shù)(AST)
源代碼

1+1

將js 源代碼轉(zhuǎn)換為AST 抽象語(yǔ)法樹(shù)，

{
    "type": "Program",
    "body": [
        {
            "type": "ExpressionStatement",
            "expression": {
                "type": "BinaryExpression",
                "operator": "+",
                "left": {
                    "type": "Literal",
                    "value": 1,
                    "raw": "1"
                },
                "right": {
                    "type": "Literal",
                    "value": 1,
                    "raw": "1"
                }
            }
        }
    ],
    "sourceType": "script"
}

轉(zhuǎn)換為AST語(yǔ)法樹(shù)的工具比較多，v8,Esprima,UglifyJS2,Acorn 等。能轉(zhuǎn)換抽象語(yǔ)法樹(shù)的也不只是 java,js ,php 等，html,css,sql,json,這些都可轉(zhuǎn)換為抽象語(yǔ)法樹(shù)

這種樹(shù)結(jié)構(gòu)為js 通用的AST樹(shù)結(jié)構(gòu)，基本上主流開(kāi)源的解析器都解析為這種結(jié)構(gòu)，當(dāng)然也可以轉(zhuǎn)換為其他格式的AST樹(shù)結(jié)構(gòu)，相應(yīng)的，解析器就需要自己去實(shí)現(xiàn)。

回到正題，我們有了語(yǔ)法樹(shù)，接下來(lái)要做啥？

我們需要去遍歷這個(gè)樹(shù)，然后對(duì)樹(shù)的每個(gè)節(jié)點(diǎn)，做相應(yīng)的處理，例如,遇到 int 節(jié)點(diǎn)，直接返回他的值，遇到 exp節(jié)點(diǎn)，則先計(jì)算 exp 左右節(jié)點(diǎn)的值，然后根據(jù)自身的運(yùn)算符號(hào)（+,-等）做相應(yīng)的加減操作。

遍歷節(jié)點(diǎn)，并處理節(jié)點(diǎn)這個(gè)過(guò)程，我們叫文法識(shí)別（解釋器），也是解釋器模式中的解釋過(guò)程。在編程語(yǔ)言領(lǐng)域，做這方面工作的我們叫編譯器

這兒就一筆帶過(guò)說(shuō)一下解釋器，我了解的并不深入。

文法識(shí)別 (解釋器)

解釋器，輸入為ast抽象語(yǔ)法樹(shù)，然后遍歷ast的每個(gè)節(jié)點(diǎn)，針對(duì)每個(gè)節(jié)點(diǎn)做響應(yīng)處理，直到節(jié)點(diǎn)遍歷完成。

• 任何語(yǔ)言的抽象語(yǔ)法樹(shù)和解釋器都是基于他底層語(yǔ)言的，例如v8引擎 js解析的底層就是c ，他的AST抽象語(yǔ)法樹(shù)，也是c語(yǔ)言版本的語(yǔ)法樹(shù)，解釋器也是c 語(yǔ)言版本的解釋器。而c語(yǔ)言的抽象語(yǔ)法樹(shù)則是GCC編譯器了。

• 像ide,uglifyjs,bable 等雖然也可以解析js 為抽象語(yǔ)法樹(shù)，但這個(gè)語(yǔ)法樹(shù)都是js 版本的語(yǔ)法樹(shù)，并不需要解釋器，語(yǔ)法樹(shù)只是輔助他們做一些js 語(yǔ)法的優(yōu)化等。如果用js 寫(xiě)一個(gè)java 抽象語(yǔ)法樹(shù)的解釋器，那就可以在node 里面執(zhí)行 java 了（意義何在？）

自定義編程語(yǔ)言

上面的描述，我已經(jīng)寫(xiě)懵逼了，估計(jì)看的人也是懵逼的,接下來(lái)我們要用解釋器模式，實(shí)現(xiàn)一套自己的編程語(yǔ)言 ,bnf+ast+ 解釋器。取個(gè)好聽(tīng)的名字 懵逼 語(yǔ)言

首先定義我們語(yǔ)言的bnf 范式，如下：

    <程序>     ::= <語(yǔ)句 塊>
    <定義>     ::= 定義  <變量 組> ;
    <變量 組>  ::= <變量> , <變量 組> | <變量>
    <語(yǔ)句 塊>  ::= <語(yǔ)句> <語(yǔ)句 塊> | <語(yǔ)句>
    <語(yǔ)句>     ::= <賦值>|<判斷>|<循環(huán)>|<輸出>|<輸入>|<定義> 
    <輸入>     ::= 輸入 <變量 組> ;
    <輸出>     ::= 輸出 <變量 組> ;    
    <判斷>     ::= 如果 <條件> { <語(yǔ)句 塊> } ;
    <條件>     ::= <比較> | ! <條件> | [ <條件> && <條件> ] | [ <條件> or <條件> ]   
    <比較>     ::= ( <值> <比較 符> <值> )
    <比較 符>  ::= != | == | < | > | <= | >=   
    <值>       ::= <整形> | <變量> | ( <表達(dá)式> )|<字符串>
    <變量>     ::= <字符 <變量> | <字符><整形> | <字符>
    <字符>     ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
    <整形>     ::= <數(shù)字><整形> | <數(shù)字>
    <數(shù)字>     ::= 0|1|2|3|4|5|6|7|8|9

然后編寫(xiě)符合上述范式規(guī)則的程序源代碼
源代碼

定義 Y;
輸入 Y;
如果 ( Y > 0 ) {
   輸出 Y ;
};

然后是寫(xiě)解析器，將源代碼按bnf 規(guī)則，解析為抽象語(yǔ)法樹(shù)。

解析器代碼這兒就不粘貼，可以在git 項(xiàng)目中查看 （解析器源代碼）

語(yǔ)法樹(shù)可視化后如下

火星語(yǔ)言_AST.png

此時(shí) ast 構(gòu)造已經(jīng)完成，剩下的就是實(shí)現(xiàn)解釋器。解釋器，輸入為AST樹(shù)對(duì)象，然后對(duì)樹(shù)進(jìn)行遞歸遍歷，針對(duì)不同節(jié)點(diǎn)，做不同處理。最終將整個(gè)AST 樹(shù)執(zhí)行完。后續(xù)再粘代碼...
demo 地址
git 地址