用JavaScript實現一個編譯器
現在前端開發中，我們常常會用到babel來編譯例如react、vue框架的代碼，以支持更多的(更古老的)瀏覽器，babel編譯代碼的過程就是編譯原理的應用之一。
Babel is a JavaScript compiler!這是Babel官方對于babel的定義。身為前端工程師，因此有必要了解編譯原理，幸運的是，“The Super Tiny Compiler”開源項目利用JavaScript寫了一個簡單的編譯器。
麻雀雖小，五臟俱全，通過對該項目的學習，一起加深對編譯過程的理解，以提升我們寫出更高質量的程序!
一、收益
通過掌握(了解)編譯原理，將有如下收益：
加深對編程語言的認識，無論何種編程語言，萬變不離其宗
殊途同歸，有利于理解babel等轉譯器、eslint、prettier、less等工具的工作原理，可開發相關插件
可以造更多輪子了🐶
二、編譯過程概述
編譯過程的具體實現主要分為三步驟：
- 代碼解析(parse)
- 代碼轉換(Transformation)
- 代碼生成(Code Generation)
通過上述三步驟，可以將我們的原代碼，轉換(編譯)到目標代碼，例如把javascript代碼轉換到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))
二、轉換過程
基于“The Super Tiny Compiler”項目，實現一個將LISP函數轉換到C語言函數編寫形式!
- （源代碼）LISP CODE: (add 2 (subtract 4 2))
- （目標代碼）C CODE: add(2, subtract(4, 2))
2.1 解析(Parse)
具象到具象的轉換是很難的，但抽象到具象的轉換往往是容易的。
解析的過程中包含了兩個關鍵步驟詞法分析(Lexical Analysis)和語法分析(Syntactic Analysis)，解析就是一個具象到抽象的過程。
2.1.1 詞法分析
詞法分析的過程，主要是將原代碼(字符串)，通過分詞的方式生成一個具有描述程序語義的token列表。
分詞的原理：逐個讀取源代碼中的字符，與預設的關鍵詞、字符串、數字、操作符等LISP語言定義的語法相關規則，轉換成 {type: 'xx', value: 'xx'} 的具有描述意義的形式
例如LISP：(add 2 (subtract 4 2))，經過詞法分析會得到如下結果：
- [
- { 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列表已經可以描述LISP的語法，但是還并不抽象，因為直觀看來，我們無法解讀這個程序的意思，這就需要將其轉換為AST(Abstract Syntax Tree，抽象語法樹)。
為什么要將其轉換到AST，AST能更好的描述源代碼的語義、描述結構更加通用，tokens列表只是描述了“符號”的意義，可以將詞法分析過程看作是分類過程，而語法分析的過程，則是將符號組合，使其具有了執行順序以及執行規則的語法，抽象語法樹，因為更抽象，因而能更高效率轉換到其他形式。
操作LISP得到的AST能更好轉換到C語言的AST，因為他們的AST結構都是類似的，操作AST比tokens更容易。
語法分析的過程，將tokens列表轉化成為一個樹結構：
- {
- 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 代碼轉換(Transform)
代碼轉換的過程是將傳入的AST結構，通過在AST上例如增、刪、改屬性，將傳入AST轉換為C語言需要的標準AST結構。
為了實現轉換，我們增加了一個 traverser(ast, visitor) 函數，這個函數接收parse過程得到的AST和visitor規則轉換對象。
visitor對象實際可理解為轉換規則，traverser函數在遍歷AST結構時，會根據visitor中定義的規則執行轉換，用于生成新的符合C語言描述標準的AST結構。
最后通過 transform(ast)(預處理，定義visitor對象) -> traverser(ast, visitor) 過程，得到一個新的AST結構：
- {
- 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，根據C語言的語法規則，轉換成為C語言格式
codeGenerator(newAst) 函數如下，接收新生成的AST結構：
- 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代碼格式化插件是不是也是這么做的?
四、總結
推薦大家完整閱讀一下“The Super Tiny Compiler”開源項目，作者寫的代碼注釋也非常詳細。編譯(轉譯)的過程原理基本類似，還有很多優秀的項目，比如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/
