「譯」什么是抽象語法樹

JouyPub 發(fā)布于2019-08-23 18:08 / 3281人閱讀

摘要：原文地址原文作者是抽象語法樹的縮寫詞，表示編程語言的語句和表達式中生成的。解釋器將會遍歷該數(shù)組并執(zhí)行里面的語句。，，，是一組相關(guān)的類，每一個類都需要攜帶方法以使解釋器獲得它們的值或者對它們求值。

原文地址：What is an Abstract Syntax Tree

原文作者：Chidume Nnamdi

AST 是抽象語法樹的縮寫詞，表示編程語言的語句和表達式中生成的 token。有了 AST，解釋器或編譯器就可以生成機器碼或者對一條指令求值。

小貼士: 通過使用 Bit，你可以將任意的 JS 代碼轉(zhuǎn)換為一個可在項目和應(yīng)用中共享、使用和同步的 API，從而更快地構(gòu)建并重用更多代碼。試一下吧。

假設(shè)我們有下面這條簡單的表達式：

1 + 2

用 AST 來表示的話，它是這樣的：

+ BinaryExpression
 - type: +
 - left_value: 
  LiteralExpr:
   value: 1
 - right_vaue:
  LiteralExpr:
   value: 2

諸如 if 的語句則可以像下面這樣表示：

if(2 > 6) {
    var d  = 90
    console.log(d)
}
IfStatement
 - condition
  + BinaryExpression
   - type: >
   - left_value: 2
   - right_value: 6
 - body
  [
    - Assign
        - left: "d";
        - right: 
            LiteralExpr:
            - value: 90
    - MethodCall:
         - instanceName: console
         - methodName: log
         - args: [
         ]
  ]

這告訴解釋器如何解釋語句，同時告訴編譯器如何生成語句對應(yīng)的代碼。

看看這條表達式： 1 + 2。我們的大腦判定這是一個將左值和右值相加的加法運算?，F(xiàn)在，為了讓計算機像我們的大腦那樣工作，我們必須以類似于大腦看待它的形式來表示它。

我們用一個類來表示，其中的屬性告訴解釋器運算的全部內(nèi)容、左值和右值。因為一個二元運算涉及兩個值，所以我們給這個類命名為 Binary：

class Binary {  
    constructor(left, operator, right) {  
        this.left = left  
        this.operator = operator  
        this.right = right  
    }  
}

實例化期間，我們將會把 1 傳給第一個屬性，把 ADD 傳給第二個屬性，把 2 傳給第三個屬性：

new Binary("1", "ADD", "2")

當我們把它傳遞給解釋器的時候，解釋器認為這是一個二元運算，接著檢查操作符，認為這是一個加法運算，緊接著繼續(xù)請求實例中的 left 值和 right 值，并將二者相加：

const binExpr = new Binary("1", "ADD", "2")

if(binExpr.operator == "ADD") {  
    return binExpr.left + binExpr.right  
}  
// 返回 `3`

看，AST 可以像大腦那樣執(zhí)行表達式和語句。

單數(shù)字、字符串、布爾值等都是表達式，它們可以在 AST 中表示并求值。

23343
false
true
"nnamdi"

拿 1 舉例：

我們在 AST 的 Literal（字面量）類中來表示它。一個字面量就是一個單詞或者數(shù)字，Literal 類用一個屬性來保存它：

class Literal {  
    constructor(value) {  
        this.value = value  
    }  
}

我們可以像下面這樣表示 Literal 中的 1：

new Literal(1)

當解釋器對它求值時，它會請求 Literal 實例中 value 屬性的值：

const oneLit = new Literal(1)  
oneLit.value  
// `1`

在我們的二元表達式中，我們直接傳遞了值

new Binary("1", "ADD", "2")

這其實并不合理。因為正如我們在上面看到的，1 和 2 都是一條表達式，一條基本的表達式。作為字面量，它們同樣需要被求值，并且用 Literal 類來表示。

const oneLit = new Literal("1")  
const twoLit = new Literal("2")

因此，二元表達式會將 oneLit 和 twoLit 分別作為左屬性和右屬性。

// ...  
new Binary(oneLit, "ADD", twoLit)

在求值階段，左屬性和右屬性同樣需要進行求值，以獲得各自的值：

const oneLit = new Literal("1")  
const twoLit = new Literal("2")  
const binExpr = new Binary(oneLit, "ADD", twoLit)

if(binExpr.operator == "ADD") {  
    return binExpr.left.value + binExpr.right.value  
}  
// 返回 `3`

其它語句在 AST 中也大多是用二元來表示的，例如 if 語句。

我們知道，在 if 語句中，只有條件為真的時候代碼塊才會執(zhí)行。

if(9 > 7) {  
    log("Yay!!")  
}

上面的 if 語句中，代碼塊執(zhí)行的條件是 9 必須大于 7，之后我們可以在終端上看到輸出 Yay!!。

為了讓解釋器或者編譯器這樣執(zhí)行，我們將會在一個包含 condition、 body 屬性的類中來表示它。condition 保存著解析后必須為真的條件，body 則是一個數(shù)組，它包含著 if 代碼塊中的所有語句。解釋器將會遍歷該數(shù)組并執(zhí)行里面的語句。

class IfStmt {  
    constructor(condition, body) {  
        this.condition = condition  
        this.body = body  
    }  
}

現(xiàn)在，讓我們在 IfStmt 類中表示下面的語句

if(9 > 7) {  
    log("Yay!!")  
}

條件是一個二元運算，這將表示為：

const cond = new Binary(new Literal(9), "GREATER", new Literal(7))

就像之前一樣，但愿你還記得？這回是一個 GREATER 運算。

if 語句的代碼塊只有一條語句：一個函數(shù)調(diào)用。函數(shù)調(diào)用同樣可以在一個類中表示，它包含的屬性有：用于指代所調(diào)用函數(shù)的 name 以及用于表示傳遞的參數(shù)的 args：

class FuncCall {  
    constructor(name, args) {  
        this.name = name  
        this.args = args  
    }  
}

因此，log("Yay!!") 調(diào)用可以表示為：

const logFuncCall = new FuncCall("log", [])

現(xiàn)在，把這些組合在一起，我們的 if 語句就可以表示為：

const cond = new Binary(new Literal(9), "GREATER", new Literal(7));  
const logFuncCall = new FuncCall("log", []);

const ifStmt = new IfStmt(cond, [  
    logFuncCall  
])

解釋器可以像下面這樣解釋 if 語句：

const ifStmt = new IfStmt(cond, [  
    logFuncCall  
])

function interpretIfStatement(ifStmt) {  
    if(evalExpr(ifStmt.conditon)) {  
        for(const stmt of ifStmt.body) {  
            evalStmt(stmt)  
        }  
    }  
}

interpretIfStatement(ifStmt)

輸出：

Yay!!

因為 9 > 7 :)

我們通過檢查 condition 解析后是否為真來解釋 if 語句。如果為真，我們遍歷 body 數(shù)組并執(zhí)行里面的語句。

執(zhí)行 AST

使用訪問者模式對 AST 進行求值。訪問者模式是設(shè)計模式的一種，允許一組對象的算法在一個地方實現(xiàn)。

ASTs，Literal，Binary，IfStmnt 是一組相關(guān)的類，每一個類都需要攜帶方法以使解釋器獲得它們的值或者對它們求值。

訪問者模式讓我們能夠創(chuàng)建單個類，并在類中編寫 AST 的實現(xiàn)，將類提供給 AST。每個 AST 都有一個公有的方法，解釋器會通過實現(xiàn)類實例對其進行調(diào)用，之后 AST 類將在傳入的實現(xiàn)類中調(diào)用相應(yīng)的方法，從而計算其 AST。

class Literal {  
    constructor(value) {  
        this.value = value  
    }

    visit(visitor) {  
        return visitor.visitLiteral(this)  
    }  
}

class Binary {  
    constructor(left, operator, right) {  
        this.left = left  
        this.operator = operator  
        this.right = right  
    }

    visit(visitor) {  
        return visitor.visitBinary(this)  
    }  
}

看，AST Literal 和 Binary 都有訪問方法，但是在方法里面，它們調(diào)用訪問者實例的方法來對自身求值。Literal 調(diào)用 visitLiteral，Binary 則調(diào)用 visitBinary。

現(xiàn)在，將 Vistor 作為實現(xiàn)類，它將實現(xiàn) visitLiteral 和 visitBinary 方法：

class Visitor {

    visitBinary(binExpr) {  
        // ...  
        log("not yet implemented")  
    }

    visitLiteral(litExpr) {  
        // ...  
        log("not yet implemented")  
    }  
}

visitBinary 和 visitLiteral 在 Vistor 類中將會有自己的實現(xiàn)。因此，當一個解釋器想要解釋一個二元表達式時，它將調(diào)用二元表達式的訪問方法，并傳遞 Vistor 類的實例：

const binExpr = new Binary(...)  
const visitor = new Visitor()

binExpr.visit(visitor)

訪問方法將調(diào)用訪問者的 visitBinary，并將其傳遞給方法，之后打印 not yet implemented。這稱為雙重分派。

調(diào)用 Binary 的訪問方法。

它 (Binary) 反過來調(diào)用 Visitor 實例的visitBinary。

我們把 visitLiteral 的完整代碼寫一下。由于 Literal 實例的 value 屬性保存著值，所以這里只需返回這個值就好：

class Visitor {

    visitBinary(binExpr) {  
        // ...  
        log("not yet implemented")  
    }

    visitLiteral(litExpr) {  
        return litExpr.value  
    }  
}

對于 visitBinary，我們知道 Binary 類有操作符、左屬性和右屬性。操作符表示將對左右屬性進行的操作。我們可以編寫實現(xiàn)如下：

class Visitor {

    visitBinary(binExpr) {  
        switch(binExpr.operator) {  
            case "ADD":  
            // ...  
        }  
    }

    visitLiteral(litExpr) {  
        return litExpr.value  
    }  
}

注意，左值和右值都是表達式，可能是字面量表達式、二元表達式、調(diào)用表達式或者其它的表達式。我們并不能確保二元運算的左右兩邊總是字面量。每一個表達式必須有一個用于對表達式求值的訪問方法，因此在上面的 visitBinary 方法中，我們通過調(diào)用各自對應(yīng)的 visit 方法對 Binary 的左屬性和右屬性進行求值：

class Visitor {

    visitBinary(binExpr) {  
        switch(binExpr.operator) {  
            case "ADD":  
                return binExpr.left.visit(this) + binExpr.right.visit(this)  
        }  
    }

    visitLiteral(litExpr) {  
        return litExpr.value  
    }  
}

因此，無論左值和右值保存的是哪一種表達式，最后都可以進行傳遞。

因此，如果我們有下面這些語句:

const oneLit = new Literal("1")  
const twoLit = new Literal("2")  
const binExpr = new Binary(oneLit, "ADD", twoLit)  
const visitor = new Visitor()

binExpr.visit(visitor)

在這種情況下，二元運算保存的是字面量。

訪問者的 visitBinary 將會被調(diào)用，同時將 binExpr 傳入，在 Vistor 類中，visitBinary 將 oneLit 作為左值，將 twoLit 作為右值。由于 oneLit 和 twoLit 都是 Literal 的實例，因此它們的訪問方法會被調(diào)用，同時將 Visitor 類傳入。對于 oneLit，其 Literal 類內(nèi)部又會調(diào)用 Vistor 類的 visitLiteral 方法，并將 oneLit 傳入，而 Vistor 中的 visitLiteral 方法返回 Literal 類的 value 屬性，也就是 1。同理，對于 twoLit 來說，返回的是 2。

因為執(zhí)行了 switch 語句中的 case "ADD"，所以返回的值會相加，最后返回 3。

如果我們將 binExpr.visit(visitor) 傳給 console.log，它將會打印 3

console.log(binExpr.visit(visitor))  
// 3

如下，我們傳遞一個 3 分支的二元運算：

1 + 2 + 3

首先，我們選擇 1 + 2，那么其結(jié)果將作為左值，即 + 3。

上述可以用 Binary 類表示為：

new Binary (new Literal(1), "ADD", new Binary(new Literal(2), "ADD", new Literal(3)))

可以看到，右值不是字面量，而是一個二元表達式。所以在執(zhí)行加法運算之前，它必須先對這個二元表達式求值，并將其結(jié)果作為最終求值時的右值。

const oneLit = new Literal(1)  
const threeLit =new Literal(3)  
const twoLit = new Literal(2)

const binExpr2 = new Binary(twoLit, "ADD", threeLit)  
const binExpr1 = new Binary (oneLit, "ADD", binExpr2)

const visitor = new Visitor()

log(binExpr1.visit(visitor))

6

添加 if 語句

將 if 語句帶到等式中。為了對一個 if 語句求值，我們將會給 IfStmt 類添加一個 visit 方法，之后它將調(diào)用 visitIfStmt 方法：

class IfStmt {  
    constructor(condition, body) {  
        this.condition = condition  
        this.body = body  
    }

    visit(visitor) {  
        return visitor.visitIfStmt(this)  
    }  
}

見識到訪問者模式的威力了嗎？我們向一些類中新增了一個類，對應(yīng)地只需要添加相同的訪問方法即可，而這將調(diào)用它位于 Vistor 類中的對應(yīng)方法。這種方式將不會破壞或者影響到其它的相關(guān)類，訪問者模式讓我們遵循了開閉原則。

因此，我們在 Vistor 類中實現(xiàn) visitIfStmt：

class Visitor {  
    // ...

    visitIfStmt(ifStmt) {  
        if(ifStmt.condition.visit(this)) {  
            for(const stmt of ifStmt.body) {  
                stmt.visit(this)  
            }  
        }  
    }  
}

因為條件是一個表達式，所以我們調(diào)用它的訪問方法對其進行求值。我們使用 JS 中的 if 語句檢查返回值，如果為真，則遍歷語句的代碼塊 ifStmt.body，通過調(diào)用 visit 方法并傳入 Vistor，對數(shù)組中每一條語句進行求值。

因此我們可以翻譯出這條語句：

if(67 > 90)

添加函數(shù)調(diào)用和函數(shù)聲明

接著來添加一個函數(shù)調(diào)用。我們已經(jīng)有一個對應(yīng)的類了：

class FuncCall {  
    constructor(name, args) {  
        this.name = name  
        this.args = args  
    }  
}

添加一個訪問方法：

class FuncCall {  
    constructor(name, args) {  
        this.name = name  
        this.args = args  
    }

    visit(visitor) {  
        return visitor.visitFuncCall(this)  
    }  
}

給 Visitor 類添加 visitFuncCall 方法：

class Visitor {  
    // ...

    visitFuncCall(funcCall) {  
        const funcName = funcCall.name  
        const args = []  
        for(const expr of funcCall.args)  
            args.push(expr.visit(this))  
        // ...  
    }  
}

這里有一個問題。除了內(nèi)置函數(shù)之外，還有自定義函數(shù)，我們需要為后者創(chuàng)建一個“容器”，并在里面通過函數(shù)名保存和引用該函數(shù)。

const FuncStore = (  
    class FuncStore {

        constructor() {  
            this.map = new Map()  
        }

        setFunc(name, body) {  
            this.map.set(name, body)  
        }

        getFunc(name) {  
            return this.map.get(name)  
        }  
    }  
    return new FuncStore()  
)()

FuncStore 保存著函數(shù)，并從一個 Map 實例中取回這些函數(shù)。

class Visitor {  
    // ...

    visitFuncCall(funcCall) {  
        const funcName = funcCall.name  
        const args = []  
        for(const expr of funcCall.args)  
            args.push(expr.visit(this))  
        if(funcName == "log")  
            console.log(...args)  
        if(FuncStore.getFunc(funcName))  
            FuncStore.getFunc(funcName).forEach(stmt => stmt.visit(this))  
    }  
}

看下我們做了什么。如果函數(shù)名 funcName（記住，FuncCall 類將函數(shù)名保存在 name 屬性中）為 log，則運行 JS console.log(...)，并傳參給它。如果我們在函數(shù)保存中找到了函數(shù)，那么就對該函數(shù)體進行遍歷，依次訪問并執(zhí)行。

現(xiàn)在看看怎么把我們的函數(shù)聲明放進函數(shù)保存中。

函數(shù)聲明以 fucntion 開頭。一般的函數(shù)結(jié)構(gòu)是這樣的：

function function_name(params) {  
    // function body  
}

因此，我們可以在一個類中用屬性表示一個函數(shù)聲明：name 保存函數(shù)函數(shù)名，body 則是一個數(shù)組，保存函數(shù)體中的語句：

class FunctionDeclaration {  
    constructor(name, body) {  
        this.name = name  
        this.body = body  
    }  
}

我們添加一個訪問方法，該方法在 Vistor 中被稱為 visitFunctionDeclaration：

class FunctionDeclaration {  
    constructor(name, body) {  
        this.name = name  
        this.body = body  
    }

    visit(visitor) {  
        return visitor.visitFunctionDeclaration(this)  
    }  
}

在 Visitor 中：

class Visitor {  
    // ...

    visitFunctionDeclaration(funcDecl) {  
        FuncStore.setFunc(funcDecl.name, funcDecl.body)  
    }  
}

將函數(shù)名作為鍵即可保存函數(shù)。

現(xiàn)在，假設(shè)我們有下面這個函數(shù)：

function addNumbers(a, b) {  
    log(a + b)  
}

function logNumbers() {  
    log(5)  
    log(6)  
}

它可以表示為：

const funcDecl = new FunctionDeclaration("logNumbers", [  
    new FuncCall("log", [new Literal(5)]),  
    new FuncCall("log", [new Literal(6)])  
])

visitor.visitFunctionDeclaration(funcDecl)

現(xiàn)在，我們來調(diào)用函數(shù) logNumbers：

const funcCall = new FuncCall("logNumbers", [])  
visitor.visitFuncCall(funcCall)

控制臺將會打?。?/p>

5
6

結(jié)論

理解 AST 的過程是令人望而生畏并且非常消耗腦力的。即使是編寫最簡單的解析器也需要大量的代碼。

注意，我們并沒有介紹掃描儀和解析器，而是先行解釋了 ASTs 以展示它們的工作過程。如果你能夠深入理解 AST 以及它所需要的內(nèi)容，那么在你開始編寫自己的編程語言時，自然就事半功倍了。

熟能生巧，你可以繼續(xù)添加其它的編程語言特性，例如：

類和對象

方法調(diào)用

封裝和繼承

for-of 語句

while 語句

for-in 語句

其它任何你能想到的有趣特性

如果你對此有任何疑問，或者是任何我需要添加、修改、刪減的內(nèi)容，歡迎評論和致郵。

感謝 ?。?！

GPU云服務(wù)器云服務(wù)器抽象語法樹 python 語法樹服務(wù)器段注釋語法是 linux下編譯阿里

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104726.html

發(fā)表評論

登陸后可評論

0條評論

JouyPub

男|高級講師

我要關(guān)注我要私信

TA的文章

第九講軟件測試面試題一

閱讀 1386·2021-10-08 10:04
云主機熱遷移是什么意思-云主機的優(yōu)缺點是什么呢？

閱讀 2707·2021-09-22 15:23
世間最美好的相遇是久別重逢、猶如你在什么時候選擇軟件測試、不思量自難忘...

閱讀 2733·2021-09-04 16:40
webpack 性能提速

閱讀 1184·2019-08-29 17:29
# CSS 絕對定位釋義

閱讀 1503·2019-08-29 17:28
我腦中飄來飄去的css魔幻屬性

閱讀 3001·2019-08-29 14:02
css 定位及屬性命名規(guī)范

閱讀 2230·2019-08-29 13:18
Chrome 控制臺常用調(diào)試技巧詳解

閱讀 851·2019-08-23 18:35

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

「譯」什么是抽象語法樹

相關(guān)文章

【譯】小二百行 JavaScript 打造 lambda 演算解釋器

瀏覽器工作過程詳解（譯）（二）

JavaScript是如何工作的：深入類和繼承內(nèi)部原理+Babel和 TypeScript 之間轉(zhuǎn)換

[譯] 探索 Angular 使用 ViewContainerRef 操作 DOM

「譯」JavaScript 究竟是如何工作的？（第一部分）

發(fā)表評論

0條評論

JouyPub

男|高級講師

TA的文章

第九講軟件測試面試題一

云主機熱遷移是什么意思-云主機的優(yōu)缺點是什么呢？

世間最美好的相遇是久別重逢、猶如你在什么時候選擇軟件測試、不思量自難忘...

webpack 性能提速

# CSS 絕對定位釋義

我腦中飄來飄去的css魔幻屬性

css 定位及屬性命名規(guī)范

Chrome 控制臺常用調(diào)試技巧詳解

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

「譯」什么是抽象語法樹

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！