「譯」什么是抽象語法樹

JouyPub 發布于2019-08-23 18:08 / 3271人閱讀

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

原文地址：What is an Abstract Syntax Tree

原文作者：Chidume Nnamdi

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

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

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

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: [
         ]
  ]

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

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

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

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

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

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

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

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

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

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

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

23343
false
true
"nnamdi"

拿 1 舉例：

我們在 AST 的 Literal（字面量）類中來表示它。一個字面量就是一個單詞或者數字，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 語句中，只有條件為真的時候代碼塊才會執行。

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

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

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

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

現在，讓我們在 IfStmt 類中表示下面的語句

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

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

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

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

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

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

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

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

現在，把這些組合在一起，我們的 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 數組并執行里面的語句。

執行 AST

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

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

訪問者模式讓我們能夠創建單個類，并在類中編寫 AST 的實現，將類提供給 AST。每個 AST 都有一個公有的方法，解釋器會通過實現類實例對其進行調用，之后 AST 類將在傳入的實現類中調用相應的方法，從而計算其 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 都有訪問方法，但是在方法里面，它們調用訪問者實例的方法來對自身求值。Literal 調用 visitLiteral，Binary 則調用 visitBinary。

現在，將 Vistor 作為實現類，它將實現 visitLiteral 和 visitBinary 方法：

class Visitor {

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

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

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

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

binExpr.visit(visitor)

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

調用 Binary 的訪問方法。

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

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

class Visitor {

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

    visitLiteral(litExpr) {  
        return litExpr.value  
    }  
}

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

class Visitor {

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

    visitLiteral(litExpr) {  
        return litExpr.value  
    }  
}

注意，左值和右值都是表達式，可能是字面量表達式、二元表達式、調用表達式或者其它的表達式。我們并不能確保二元運算的左右兩邊總是字面量。每一個表達式必須有一個用于對表達式求值的訪問方法，因此在上面的 visitBinary 方法中，我們通過調用各自對應的 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 將會被調用，同時將 binExpr 傳入，在 Vistor 類中，visitBinary 將 oneLit 作為左值，將 twoLit 作為右值。由于 oneLit 和 twoLit 都是 Literal 的實例，因此它們的訪問方法會被調用，同時將 Visitor 類傳入。對于 oneLit，其 Literal 類內部又會調用 Vistor 類的 visitLiteral 方法，并將 oneLit 傳入，而 Vistor 中的 visitLiteral 方法返回 Literal 類的 value 屬性，也就是 1。同理，對于 twoLit 來說，返回的是 2。

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

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

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

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

1 + 2 + 3

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

上述可以用 Binary 類表示為：

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

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

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 方法，之后它將調用 visitIfStmt 方法：

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

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

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

因此，我們在 Vistor 類中實現 visitIfStmt：

class Visitor {  
    // ...

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

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

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

if(67 > 90)

添加函數調用和函數聲明

接著來添加一個函數調用。我們已經有一個對應的類了：

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))  
        // ...  
    }  
}

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

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 保存著函數，并從一個 Map 實例中取回這些函數。

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

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

現在看看怎么把我們的函數聲明放進函數保存中。

函數聲明以 fucntion 開頭。一般的函數結構是這樣的：

function function_name(params) {  
    // function body  
}

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

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

將函數名作為鍵即可保存函數。

現在，假設我們有下面這個函數：

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)

現在，我們來調用函數 logNumbers：

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

控制臺將會打印：

5
6

結論

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

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

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

類和對象

方法調用

封裝和繼承

for-of 語句

while 語句

for-in 語句

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

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

感謝！！！

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/104726.html

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

摘要：在開始解析之前，先通過詞法分析器運行源碼，這會將源碼打散成語法中全大寫的部分。我們基于每個規則的名稱的左側為其創建一個方法，再來看右側內容如果是全大寫的單詞，說明它是一個終止符即一個，詞法分析器會用到它。本文轉載自：眾成翻譯譯者：文藺鏈接：http://www.zcfy.cc/article/661原文：http://tadeuzagallo.com/blog/writing-a-l...

KitorinZero 2019-08-19 18:38 評論0 收藏0
瀏覽器工作過程詳解（譯）（二）

摘要：每種可解析的格式必須具有由詞匯及語法規則組成的特定的文法，這被稱為上下文無關文法。解析器將會從詞法分析器獲取一個新符號，并且嘗試用某一種語法規則去匹配它。第二個匹配到規則的是，它匹配到第三條語法規則。銜接接著上文繼續。在構建好render樹后，瀏覽器就開始進行布局了。這意味著瀏覽器會給每個節點正確的坐標，讓它們出現在該出現的地方。下一步就是進行繪制了，瀏覽器將會遍歷render樹...

fasss 2019-08-01 16:45 評論0 收藏0
JavaScript是如何工作的：深入類和繼承內部原理+Babel和 TypeScript 之間轉換

摘要：下面是用實現轉成抽象語法樹如下還支持繼承以下是轉換結果最終的結果還是代碼，其中包含庫中的一些函數。可以使用新的易于使用的類定義，但是它仍然會創建構造函數和分配原型。這是專門探索 JavaScript 及其所構建的組件的系列文章的第 15 篇。想閱讀更多優質文章請猛戳GitHub博客,一年百來篇優質文章等著你！如果你錯過了前面的章節，可以在這里找到它們： JavaScript 是...

PrototypeZ 2019-08-23 14:54 評論0 收藏0
[譯] 探索 Angular 使用 ViewContainerRef 操作 DOM

摘要：在探索抽象類前，先了解下如何在組件指令中獲取這些抽象類。下面示例描述在組建模板中如何創建如同其他抽象類一樣，通過屬性綁定元素，比如上例中，綁定的是會被渲染為注釋的元素，所以輸出也將是。你可以使用查詢模板引用變量來獲得抽象類。原文鏈接：Exploring Angular DOM manipulation techniques using ViewContainerRef如果想深入學習 ...

wind5o 2019-08-22 15:33 評論0 收藏0
「譯」JavaScript 究竟是如何工作的？（第一部分）

摘要：文章的第二部分涵蓋了內存管理的概念，不久后將發布。的標準化工作是由國際組織負責的，相關規范被稱為或者。隨著分析器和編譯器不斷地更改字節碼，的執行性能逐漸提高。原文地址：How Does JavaScript Really Work? (Part 1) 原文作者：Priyesh Patel 譯者：Chor showImg(https://segmentfault.com/img...

Youngdze 2019-08-26 13:43 評論0 收藏0