摘要:原文地址原文作者是抽象語(yǔ)法樹(shù)的縮寫(xiě)詞,表示編程語(yǔ)言的語(yǔ)句和表達(dá)式中生成的。解釋器將會(huì)遍歷該數(shù)組并執(zhí)行里面的語(yǔ)句。,,,是一組相關(guān)的類,每一個(gè)類都需要攜帶方法以使解釋器獲得它們的值或者對(duì)它們求值。
原文地址:What is an Abstract Syntax Tree
原文作者:Chidume Nnamdi
AST 是抽象語(yǔ)法樹(shù)的縮寫(xiě)詞,表示編程語(yǔ)言的語(yǔ)句和表達(dá)式中生成的 token。有了 AST,解釋器或編譯器就可以生成機(jī)器碼或者對(duì)一條指令求值。
小貼士: 通過(guò)使用 Bit,你可以將任意的 JS 代碼轉(zhuǎn)換為一個(gè)可在項(xiàng)目和應(yīng)用中共享、使用和同步的 API,從而更快地構(gòu)建并重用更多代碼。試一下吧。
假設(shè)我們有下面這條簡(jiǎn)單的表達(dá)式:
1 + 2
用 AST 來(lái)表示的話,它是這樣的:
+ BinaryExpression - type: + - left_value: LiteralExpr: value: 1 - right_vaue: LiteralExpr: value: 2
諸如 if 的語(yǔ)句則可以像下面這樣表示:
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ǔ)句,同時(shí)告訴編譯器如何生成語(yǔ)句對(duì)應(yīng)的代碼。
看看這條表達(dá)式: 1 + 2。我們的大腦判定這是一個(gè)將左值和右值相加的加法運(yùn)算。現(xiàn)在,為了讓計(jì)算機(jī)像我們的大腦那樣工作,我們必須以類似于大腦看待它的形式來(lái)表示它。
我們用一個(gè)類來(lái)表示,其中的屬性告訴解釋器運(yùn)算的全部?jī)?nèi)容、左值和右值。因?yàn)橐粋€(gè)二元運(yùn)算涉及兩個(gè)值,所以我們給這個(gè)類命名為 Binary:
class Binary { constructor(left, operator, right) { this.left = left this.operator = operator this.right = right } }
實(shí)例化期間,我們將會(huì)把 1 傳給第一個(gè)屬性,把 ADD 傳給第二個(gè)屬性,把 2 傳給第三個(gè)屬性:
new Binary("1", "ADD", "2")
當(dāng)我們把它傳遞給解釋器的時(shí)候,解釋器認(rèn)為這是一個(gè)二元運(yùn)算,接著檢查操作符,認(rèn)為這是一個(gè)加法運(yùn)算,緊接著繼續(xù)請(qǐng)求實(shí)例中的 left 值和 right 值,并將二者相加:
const binExpr = new Binary("1", "ADD", "2") if(binExpr.operator == "ADD") { return binExpr.left + binExpr.right } // 返回 `3`
看,AST 可以像大腦那樣執(zhí)行表達(dá)式和語(yǔ)句。
單數(shù)字、字符串、布爾值等都是表達(dá)式,它們可以在 AST 中表示并求值。
23343 false true "nnamdi"
拿 1 舉例:
1
我們?cè)?AST 的 Literal(字面量) 類中來(lái)表示它。一個(gè)字面量就是一個(gè)單詞或者數(shù)字,Literal 類用一個(gè)屬性來(lái)保存它:
class Literal { constructor(value) { this.value = value } }
我們可以像下面這樣表示 Literal 中的 1:
new Literal(1)
當(dāng)解釋器對(duì)它求值時(shí),它會(huì)請(qǐng)求 Literal 實(shí)例中 value 屬性的值:
const oneLit = new Literal(1) oneLit.value // `1`
在我們的二元表達(dá)式中,我們直接傳遞了值
new Binary("1", "ADD", "2")
這其實(shí)并不合理。因?yàn)檎缥覀冊(cè)谏厦婵吹降模?b>1 和 2 都是一條表達(dá)式,一條基本的表達(dá)式。作為字面量,它們同樣需要被求值,并且用 Literal 類來(lái)表示。
const oneLit = new Literal("1") const twoLit = new Literal("2")
因此,二元表達(dá)式會(huì)將 oneLit 和 twoLit 分別作為左屬性和右屬性。
// ... new Binary(oneLit, "ADD", twoLit)
在求值階段,左屬性和右屬性同樣需要進(jìn)行求值,以獲得各自的值:
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`
其它語(yǔ)句在 AST 中也大多是用二元來(lái)表示的,例如 if 語(yǔ)句。
我們知道,在 if 語(yǔ)句中,只有條件為真的時(shí)候代碼塊才會(huì)執(zhí)行。
if(9 > 7) { log("Yay!!") }
上面的 if 語(yǔ)句中,代碼塊執(zhí)行的條件是 9 必須大于 7,之后我們可以在終端上看到輸出 Yay!!。
為了讓解釋器或者編譯器這樣執(zhí)行,我們將會(huì)在一個(gè)包含 condition、 body 屬性的類中來(lái)表示它。condition 保存著解析后必須為真的條件,body 則是一個(gè)數(shù)組,它包含著 if 代碼塊中的所有語(yǔ)句。解釋器將會(huì)遍歷該數(shù)組并執(zhí)行里面的語(yǔ)句。
class IfStmt { constructor(condition, body) { this.condition = condition this.body = body } }
現(xiàn)在,讓我們?cè)?IfStmt 類中表示下面的語(yǔ)句
if(9 > 7) { log("Yay!!") }
條件是一個(gè)二元運(yùn)算,這將表示為:
const cond = new Binary(new Literal(9), "GREATER", new Literal(7))
就像之前一樣,但愿你還記得?這回是一個(gè) GREATER 運(yùn)算。
if 語(yǔ)句的代碼塊只有一條語(yǔ)句:一個(gè)函數(shù)調(diào)用。函數(shù)調(diào)用同樣可以在一個(gè)類中表示,它包含的屬性有:用于指代所調(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 語(yǔ)句就可以表示為:
const cond = new Binary(new Literal(9), "GREATER", new Literal(7)); const logFuncCall = new FuncCall("log", []); const ifStmt = new IfStmt(cond, [ logFuncCall ])
解釋器可以像下面這樣解釋 if 語(yǔ)句:
const ifStmt = new IfStmt(cond, [ logFuncCall ]) function interpretIfStatement(ifStmt) { if(evalExpr(ifStmt.conditon)) { for(const stmt of ifStmt.body) { evalStmt(stmt) } } } interpretIfStatement(ifStmt)
輸出:
Yay!!
因?yàn)?9 > 7 :)
我們通過(guò)檢查 condition 解析后是否為真來(lái)解釋 if 語(yǔ)句。如果為真,我們遍歷 body 數(shù)組并執(zhí)行里面的語(yǔ)句。
執(zhí)行 AST使用訪問(wèn)者模式對(duì) AST 進(jìn)行求值。訪問(wèn)者模式是設(shè)計(jì)模式的一種,允許一組對(duì)象的算法在一個(gè)地方實(shí)現(xiàn)。
ASTs,Literal,Binary,IfStmnt 是一組相關(guān)的類,每一個(gè)類都需要攜帶方法以使解釋器獲得它們的值或者對(duì)它們求值。
訪問(wèn)者模式讓我們能夠創(chuàng)建單個(gè)類,并在類中編寫(xiě) AST 的實(shí)現(xiàn),將類提供給 AST。每個(gè) AST 都有一個(gè)公有的方法,解釋器會(huì)通過(guò)實(shí)現(xiàn)類實(shí)例對(duì)其進(jìn)行調(diào)用,之后 AST 類將在傳入的實(shí)現(xiàn)類中調(diào)用相應(yīng)的方法,從而計(jì)算其 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 都有訪問(wèn)方法,但是在方法里面,它們調(diào)用訪問(wèn)者實(shí)例的方法來(lái)對(duì)自身求值。Literal 調(diào)用 visitLiteral,Binary 則調(diào)用 visitBinary。
現(xiàn)在,將 Vistor 作為實(shí)現(xiàn)類,它將實(shí)現(xiàn) visitLiteral 和 visitBinary 方法:
class Visitor { visitBinary(binExpr) { // ... log("not yet implemented") } visitLiteral(litExpr) { // ... log("not yet implemented") } }
visitBinary 和 visitLiteral 在 Vistor 類中將會(huì)有自己的實(shí)現(xiàn)。因此,當(dāng)一個(gè)解釋器想要解釋一個(gè)二元表達(dá)式時(shí),它將調(diào)用二元表達(dá)式的訪問(wèn)方法,并傳遞 Vistor 類的實(shí)例:
const binExpr = new Binary(...) const visitor = new Visitor() binExpr.visit(visitor)
訪問(wèn)方法將調(diào)用訪問(wèn)者的 visitBinary,并將其傳遞給方法,之后打印 not yet implemented。這稱為雙重分派。
調(diào)用 Binary 的訪問(wèn)方法。
它 (Binary) 反過(guò)來(lái)調(diào)用 Visitor 實(shí)例的visitBinary。
我們把 visitLiteral 的完整代碼寫(xiě)一下。由于 Literal 實(shí)例的 value 屬性保存著值,所以這里只需返回這個(gè)值就好:
class Visitor { visitBinary(binExpr) { // ... log("not yet implemented") } visitLiteral(litExpr) { return litExpr.value } }
對(duì)于 visitBinary,我們知道 Binary 類有操作符、左屬性和右屬性。操作符表示將對(duì)左右屬性進(jìn)行的操作。我們可以編寫(xiě)實(shí)現(xiàn)如下:
class Visitor { visitBinary(binExpr) { switch(binExpr.operator) { case "ADD": // ... } } visitLiteral(litExpr) { return litExpr.value } }
注意,左值和右值都是表達(dá)式,可能是字面量表達(dá)式、二元表達(dá)式、調(diào)用表達(dá)式或者其它的表達(dá)式。我們并不能確保二元運(yùn)算的左右兩邊總是字面量。每一個(gè)表達(dá)式必須有一個(gè)用于對(duì)表達(dá)式求值的訪問(wèn)方法,因此在上面的 visitBinary 方法中,我們通過(guò)調(diào)用各自對(duì)應(yīng)的 visit 方法對(duì) Binary 的左屬性和右屬性進(jìn)行求值:
class Visitor { visitBinary(binExpr) { switch(binExpr.operator) { case "ADD": return binExpr.left.visit(this) + binExpr.right.visit(this) } } visitLiteral(litExpr) { return litExpr.value } }
因此,無(wú)論左值和右值保存的是哪一種表達(dá)式,最后都可以進(jìn)行傳遞。
因此,如果我們有下面這些語(yǔ)句:
const oneLit = new Literal("1") const twoLit = new Literal("2") const binExpr = new Binary(oneLit, "ADD", twoLit) const visitor = new Visitor() binExpr.visit(visitor)
在這種情況下,二元運(yùn)算保存的是字面量。
訪問(wèn)者的 visitBinary 將會(huì)被調(diào)用,同時(shí)將 binExpr 傳入,在 Vistor 類中,visitBinary 將 oneLit 作為左值,將 twoLit 作為右值。由于 oneLit 和 twoLit 都是 Literal 的實(shí)例,因此它們的訪問(wèn)方法會(huì)被調(diào)用,同時(shí)將 Visitor 類傳入。對(duì)于 oneLit,其 Literal 類內(nèi)部又會(huì)調(diào)用 Vistor 類的 visitLiteral 方法,并將 oneLit 傳入,而 Vistor 中的 visitLiteral 方法返回 Literal 類的 value 屬性,也就是 1。同理,對(duì)于 twoLit 來(lái)說(shuō),返回的是 2。
因?yàn)閳?zhí)行了 switch 語(yǔ)句中的 case "ADD",所以返回的值會(huì)相加,最后返回 3。
如果我們將 binExpr.visit(visitor) 傳給 console.log,它將會(huì)打印 3
console.log(binExpr.visit(visitor)) // 3
如下,我們傳遞一個(gè) 3 分支的二元運(yùn)算:
1 + 2 + 3
首先,我們選擇 1 + 2,那么其結(jié)果將作為左值,即 + 3。
上述可以用 Binary 類表示為:
new Binary (new Literal(1), "ADD", new Binary(new Literal(2), "ADD", new Literal(3)))
可以看到,右值不是字面量,而是一個(gè)二元表達(dá)式。所以在執(zhí)行加法運(yùn)算之前,它必須先對(duì)這個(gè)二元表達(dá)式求值,并將其結(jié)果作為最終求值時(shí)的右值。
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 語(yǔ)句
將 if 語(yǔ)句帶到等式中。為了對(duì)一個(gè) if 語(yǔ)句求值,我們將會(huì)給 IfStmt 類添加一個(gè) visit 方法,之后它將調(diào)用 visitIfStmt 方法:
class IfStmt { constructor(condition, body) { this.condition = condition this.body = body } visit(visitor) { return visitor.visitIfStmt(this) } }
見(jiàn)識(shí)到訪問(wèn)者模式的威力了嗎?我們向一些類中新增了一個(gè)類,對(duì)應(yīng)地只需要添加相同的訪問(wèn)方法即可,而這將調(diào)用它位于 Vistor 類中的對(duì)應(yīng)方法。這種方式將不會(huì)破壞或者影響到其它的相關(guān)類,訪問(wèn)者模式讓我們遵循了開(kāi)閉原則。
因此,我們?cè)?Vistor 類中實(shí)現(xiàn) visitIfStmt:
class Visitor { // ... visitIfStmt(ifStmt) { if(ifStmt.condition.visit(this)) { for(const stmt of ifStmt.body) { stmt.visit(this) } } } }
因?yàn)闂l件是一個(gè)表達(dá)式,所以我們調(diào)用它的訪問(wèn)方法對(duì)其進(jìn)行求值。我們使用 JS 中的 if 語(yǔ)句檢查返回值,如果為真,則遍歷語(yǔ)句的代碼塊 ifStmt.body,通過(guò)調(diào)用 visit 方法并傳入 Vistor,對(duì)數(shù)組中每一條語(yǔ)句進(jìn)行求值。
因此我們可以翻譯出這條語(yǔ)句:
if(67 > 90)添加函數(shù)調(diào)用和函數(shù)聲明
接著來(lái)添加一個(gè)函數(shù)調(diào)用。我們已經(jīng)有一個(gè)對(duì)應(yīng)的類了:
class FuncCall { constructor(name, args) { this.name = name this.args = args } }
添加一個(gè)訪問(wèn)方法:
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)) // ... } }
這里有一個(gè)問(wèn)題。除了內(nèi)置函數(shù)之外,還有自定義函數(shù),我們需要為后者創(chuàng)建一個(gè)“容器”,并在里面通過(guò)函數(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ù),并從一個(gè) Map 實(shí)例中取回這些函數(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,則運(yùn)行 JS console.log(...),并傳參給它。如果我們?cè)诤瘮?shù)保存中找到了函數(shù),那么就對(duì)該函數(shù)體進(jìn)行遍歷,依次訪問(wèn)并執(zhí)行。
現(xiàn)在看看怎么把我們的函數(shù)聲明放進(jìn)函數(shù)保存中。
函數(shù)聲明以 fucntion 開(kāi)頭。一般的函數(shù)結(jié)構(gòu)是這樣的:
function function_name(params) { // function body }
因此,我們可以在一個(gè)類中用屬性表示一個(gè)函數(shù)聲明:name 保存函數(shù)函數(shù)名,body 則是一個(gè)數(shù)組,保存函數(shù)體中的語(yǔ)句:
class FunctionDeclaration { constructor(name, body) { this.name = name this.body = body } }
我們添加一個(gè)訪問(wèn)方法,該方法在 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è)我們有下面這個(gè)函數(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)在,我們來(lái)調(diào)用函數(shù) logNumbers:
const funcCall = new FuncCall("logNumbers", []) visitor.visitFuncCall(funcCall)
控制臺(tái)將會(huì)打印:
5 6結(jié)論
理解 AST 的過(guò)程是令人望而生畏并且非常消耗腦力的。即使是編寫(xiě)最簡(jiǎn)單的解析器也需要大量的代碼。
注意,我們并沒(méi)有介紹掃描儀和解析器,而是先行解釋了 ASTs 以展示它們的工作過(guò)程。如果你能夠深入理解 AST 以及它所需要的內(nèi)容,那么在你開(kāi)始編寫(xiě)自己的編程語(yǔ)言時(shí),自然就事半功倍了。
熟能生巧,你可以繼續(xù)添加其它的編程語(yǔ)言特性,例如:
類和對(duì)象
方法調(diào)用
封裝和繼承
for-of 語(yǔ)句
while 語(yǔ)句
for-in 語(yǔ)句
其它任何你能想到的有趣特性
如果你對(duì)此有任何疑問(wèn),或者是任何我需要添加、修改、刪減的內(nèi)容,歡迎評(píng)論和致郵。
感謝 ?。?!
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://www.ezyhdfw.cn/yun/104726.html
摘要:在開(kāi)始解析之前,先通過(guò)詞法分析器運(yùn)行源碼,這會(huì)將源碼打散成語(yǔ)法中全大寫(xiě)的部分。我們基于每個(gè)規(guī)則的名稱的左側(cè)為其創(chuàng)建一個(gè)方法,再來(lái)看右側(cè)內(nèi)容如果是全大寫(xiě)的單詞,說(shuō)明它是一個(gè)終止符即一個(gè),詞法分析器會(huì)用到它。 本文轉(zhuǎn)載自:眾成翻譯譯者:文藺鏈接:http://www.zcfy.cc/article/661原文:http://tadeuzagallo.com/blog/writing-a-l...
摘要:每種可解析的格式必須具有由詞匯及語(yǔ)法規(guī)則組成的特定的文法,這被稱為上下文無(wú)關(guān)文法。解析器將會(huì)從詞法分析器獲取一個(gè)新符號(hào),并且嘗試用某一種語(yǔ)法規(guī)則去匹配它。第二個(gè)匹配到規(guī)則的是,它匹配到第三條語(yǔ)法規(guī)則。 銜接 接著上文繼續(xù)。 在構(gòu)建好render樹(shù)后,瀏覽器就開(kāi)始進(jìn)行布局了。這意味著瀏覽器會(huì)給每個(gè)節(jié)點(diǎn)正確的坐標(biāo),讓它們出現(xiàn)在該出現(xiàn)的地方。下一步就是進(jìn)行繪制了,瀏覽器將會(huì)遍歷render樹(shù)...
摘要:下面是用實(shí)現(xiàn)轉(zhuǎn)成抽象語(yǔ)法樹(shù)如下還支持繼承以下是轉(zhuǎn)換結(jié)果最終的結(jié)果還是代碼,其中包含庫(kù)中的一些函數(shù)。可以使用新的易于使用的類定義,但是它仍然會(huì)創(chuàng)建構(gòu)造函數(shù)和分配原型。 這是專門(mén)探索 JavaScript 及其所構(gòu)建的組件的系列文章的第 15 篇。 想閱讀更多優(yōu)質(zhì)文章請(qǐng)猛戳GitHub博客,一年百來(lái)篇優(yōu)質(zhì)文章等著你! 如果你錯(cuò)過(guò)了前面的章節(jié),可以在這里找到它們: JavaScript 是...
摘要:在探索抽象類前,先了解下如何在組件指令中獲取這些抽象類。下面示例描述在組建模板中如何創(chuàng)建如同其他抽象類一樣,通過(guò)屬性綁定元素,比如上例中,綁定的是會(huì)被渲染為注釋的元素,所以輸出也將是。你可以使用查詢模板引用變量來(lái)獲得抽象類。 原文鏈接:Exploring Angular DOM manipulation techniques using ViewContainerRef如果想深入學(xué)習(xí) ...
摘要:文章的第二部分涵蓋了內(nèi)存管理的概念,不久后將發(fā)布。的標(biāo)準(zhǔn)化工作是由國(guó)際組織負(fù)責(zé)的,相關(guān)規(guī)范被稱為或者。隨著分析器和編譯器不斷地更改字節(jié)碼,的執(zhí)行性能逐漸提高。 原文地址:How Does JavaScript Really Work? (Part 1) 原文作者:Priyesh Patel 譯者:Chor showImg(https://segmentfault.com/img...
閱讀 1488·2021-10-08 10:04
閱讀 2893·2021-09-22 15:23
閱讀 2867·2021-09-04 16:40
閱讀 1251·2019-08-29 17:29
閱讀 1578·2019-08-29 17:28
閱讀 3067·2019-08-29 14:02
閱讀 2308·2019-08-29 13:18
閱讀 953·2019-08-23 18:35