用JavaScript實現(xiàn)一個編譯器
現(xiàn)在前端開發(fā)中，我們常常會用到babel來編譯例如react、vue框架的代碼，以支持更多的(更古老的)瀏覽器，babel編譯代碼的過程就是編譯原理的應(yīng)用之一。
Babel is a JavaScript compiler!這是Babel官方對于babel的定義。身為前端工程師，因此有必要了解編譯原理，幸運的是，“The Super Tiny Compiler”開源項目利用JavaScript寫了一個簡單的編譯器。
麻雀雖小，五臟俱全，通過對該項目的學(xué)習(xí)，一起加深對編譯過程的理解，以提升我們寫出更高質(zhì)量的程序!
一、收益
通過掌握(了解)編譯原理，將有如下收益：
加深對編程語言的認識，無論何種編程語言，萬變不離其宗
殊途同歸，有利于理解babel等轉(zhuǎn)譯器、eslint、prettier、less等工具的工作原理，可開發(fā)相關(guān)插件
可以造更多輪子了🐶
二、編譯過程概述
編譯過程的具體實現(xiàn)主要分為三步驟：
- 代碼解析(parse)
- 代碼轉(zhuǎn)換(Transformation)
- 代碼生成(Code Generation)
通過上述三步驟，可以將我們的原代碼，轉(zhuǎn)換(編譯)到目標代碼，例如把javascript代碼轉(zhuǎn)換到python一樣。
編譯過程
“The Super Tiny Compiler”項目中是將LISP語言編譯為C語言，如下案例：
- * LISP(source) C(target)
- *
- * 2 + 2 (add 2 2) add(2, 2)
- * 4 - 2 (subtract 4 2) subtract(4, 2)
- * 2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
二、轉(zhuǎn)換過程
基于“The Super Tiny Compiler”項目，實現(xiàn)一個將LISP函數(shù)轉(zhuǎn)換到C語言函數(shù)編寫形式!
- （源代碼）LISP CODE: (add 2 (subtract 4 2))
- （目標代碼）C CODE: add(2, subtract(4, 2))
2.1 解析(Parse)
具象到具象的轉(zhuǎn)換是很難的，但抽象到具象的轉(zhuǎn)換往往是容易的。
解析的過程中包含了兩個關(guān)鍵步驟詞法分析(Lexical Analysis)和語法分析(Syntactic Analysis)，解析就是一個具象到抽象的過程。
2.1.1 詞法分析
詞法分析的過程，主要是將原代碼(字符串)，通過分詞的方式生成一個具有描述程序語義的token列表。
分詞的原理：逐個讀取源代碼中的字符，與預(yù)設(shè)的關(guān)鍵詞、字符串、數(shù)字、操作符等LISP語言定義的語法相關(guān)規(guī)則，轉(zhuǎn)換成 {type: 'xx', value: 'xx'} 的具有描述意義的形式
例如LISP：(add 2 (subtract 4 2))，經(jīng)過詞法分析會得到如下結(jié)果：
- [
- { type: 'paren', value: '(' },
- { type: 'name', value: 'add' },
- { type: 'number', value: '2' },
- { type: 'paren', value: '(' },
- { type: 'name', value: 'subtract' },
- { type: 'number', value: '4' },
- { type: 'number', value: '2' },
- { type: 'paren', value: ')' },
- { type: 'paren', value: ')' },
- ]
這樣一個列表(暫稱作：tokens列表)按照順序下來很好的描述了源代碼中的字符串和編程語義。
2.1.2 語法分析
詞法分析后得到的tokens列表已經(jīng)可以描述LISP的語法，但是還并不抽象，因為直觀看來，我們無法解讀這個程序的意思，這就需要將其轉(zhuǎn)換為AST(Abstract Syntax Tree，抽象語法樹)。
為什么要將其轉(zhuǎn)換到AST，AST能更好的描述源代碼的語義、描述結(jié)構(gòu)更加通用，tokens列表只是描述了“符號”的意義，可以將詞法分析過程看作是分類過程，而語法分析的過程，則是將符號組合，使其具有了執(zhí)行順序以及執(zhí)行規(guī)則的語法，抽象語法樹，因為更抽象，因而能更高效率轉(zhuǎn)換到其他形式。
操作LISP得到的AST能更好轉(zhuǎn)換到C語言的AST，因為他們的AST結(jié)構(gòu)都是類似的，操作AST比tokens更容易。
語法分析的過程，將tokens列表轉(zhuǎn)化成為一個樹結(jié)構(gòu)：
- {
- type: 'Program',
- body: [
- {
- type: 'CallExpression',
- name: 'add',
- params: [
- {
- type: 'NumberLiteral',
- value: '2',
- },
- {
- type: 'CallExpression',
- name: 'subtract',
- params: [
- {
- type: 'NumberLiteral',
- value: '4',
- },
- {
- type: 'NumberLiteral',
- value: '2',
- }
- ]
- }
- ]
- }
- ]
- }
2.2 代碼轉(zhuǎn)換(Transform)
代碼轉(zhuǎn)換的過程是將傳入的AST結(jié)構(gòu)，通過在AST上例如增、刪、改屬性，將傳入AST轉(zhuǎn)換為C語言需要的標準AST結(jié)構(gòu)。
為了實現(xiàn)轉(zhuǎn)換，我們增加了一個 traverser(ast, visitor) 函數(shù)，這個函數(shù)接收parse過程得到的AST和visitor規(guī)則轉(zhuǎn)換對象。
visitor對象實際可理解為轉(zhuǎn)換規(guī)則，traverser函數(shù)在遍歷AST結(jié)構(gòu)時，會根據(jù)visitor中定義的規(guī)則執(zhí)行轉(zhuǎn)換，用于生成新的符合C語言描述標準的AST結(jié)構(gòu)。
最后通過 transform(ast)(預(yù)處理，定義visitor對象) -> traverser(ast, visitor) 過程，得到一個新的AST結(jié)構(gòu)：
- {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'CallExpression',
- callee: {
- type: 'Identifier',
- name: 'add'
- },
- arguments: [
- {
- type: 'NumberLiteral',
- value: '2'
- },
- {
- type: 'CallExpression',
- callee: {
- type: 'Identifier',
- name: 'subtract'
- },
- arguments: [
- {
- type: 'NumberLiteral',
- value: '4'
- },
- {
- type: 'NumberLiteral',
- value: '2'
- }
- ]
- }
- }
- }
- ]
- }
2.3 生成目標代碼(Code Generate)
最后通過解析符合C語言標準的AST，根據(jù)C語言的語法規(guī)則，轉(zhuǎn)換成為C語言格式
codeGenerator(newAst) 函數(shù)如下，接收新生成的AST結(jié)構(gòu)：
- function codeGenerator(newAst) {
- switch (newAst.type) {
- case "Program":
- return newAst.body.map(codeGenerator).join("\n");
- case "ExpressionStatement":
- return codeGenerator(newAst.expression) + ";";
- case "CallExpression":
- return (
- codeGenerator(newAst.callee) +
- "(" +
- newAst.arguments.map(codeGenerator).join(", ") +
- ")"
- );
- case "Identifier":
- return newAst.name;
- case "NumberLiteral":
- return newAst.value;
- case "StringLiteral":
- return '"' + newAst.value + '"';
- default:
- throw new TypeError(newAst.type);
- }
- }
同時還做了代碼的部分格式化，比如空格、換行符添加等。
此時自然會思考下，VScode編輯器中的Prettier代碼格式化插件是不是也是這么做的?
四、總結(jié)
推薦大家完整閱讀一下“The Super Tiny Compiler”開源項目，作者寫的代碼注釋也非常詳細。編譯(轉(zhuǎn)譯)的過程原理基本類似，還有很多優(yōu)秀的項目，比如codeMirror、babel、esprima、acorn、recast都是值得閱讀的源碼，喜歡的小伙伴一定要去瞅瞅。
Reference
- 《Babel Docs》- https://babeljs.io/docs/en/
- 《the super tiny complier》- https://github.com/jamiebuilds/the-super-tiny-compiler/
