欢迎光临
我的个人博客网站

【译】一个超级小的编译器


本文是对the-super-tiny-compiler仓库的翻译,原文章(代码):https://github.com/jamiebuilds/the-super-tiny-compiler/blob/master/the-super-tiny-compiler.js

今天我们一起动手写一个编译器,但不是我们平常所说的编译器,而是一个超级超级小的编译器,小到如果你把本文件的所有注释都删了,真正的代码也就200多行。

我们将把lisp风格的函数调用编译成C风格的函数调用,如果你对这两个不熟悉的话,让我来简单介绍一下。

如果我们有两个函数:addsubtract,它们会写成下面的样子:

               LISP                      C  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)) 

是不是很简单?

很好,这就是我们要编译的,虽然这并不是一个完整的LISPC语法,但是这小部分的语法足以向我们展示一个现代编译器的主要部分。

大多数的编译器都会分成三个主要的阶段:解析(Parsing)、转换(Transformation)以及生成代码(Code Generation)。

1.Parsing会将源代码转换成更抽象的代码表示;

2.Transformation会对这个抽象的代码表示进行任何它想要的操作;

3.Code Generation会把操作完的代码抽象表示生成新代码;

解析(Parsing)

解析通常分为两个阶段:词法分析和语法分析。

1.词法分析会使用一个叫做分词器(tokenizer)的东西来把源代码切割成一个个叫做标记(token)的东西;

tokens是一个数组,里面每项都是用来描述语法中一个独立块的最小对象,它们可以是数字、标签、标点、运算符等等。

2.语法分析会把标记重新组合,用来描述语法的每个部分,并建立起它们之间的联系,这一般被称作为“抽象语法树”。

​ 一个抽象语法树(简称为AST),是一个深层嵌套的对象,以一种又简单又能告诉我们大量信息的方式来表示代码。

对于下面的语法:

(add 2 (subtract 4 2))

token列表是下面这样的:

  [      { 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: ')'        },    ] 

AST是这样的:

{      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',          }]        }]      }]    } 

转换(Transformation)

编译器的下一个阶段是转换,再强调一次,这个阶段只是把上个阶段生成的AST拿来进行一些修改,它可以保持原来的语言,也可以把它翻译成全新的语言。

让我们看看如何转换AST

你可能会注意到我们AST里的元素看起来都非常相似,这些对象都有一个type属性,每个节点都被称为AST节点,这些节点上都定义了一些属性,用来描述树的一个部分。

我们可以为NumberLiteral创建一个节点:

{      type: 'NumberLiteral',      value: '2', } 

或者为CallExpression创建一个节点:

 {      type: 'CallExpression',      name: 'subtract',      params: [...嵌套节点...], } 

当转换AST的时候,我们可以通过这些方式来操作节点:添加移除替换属性,我们可以添加新节点,或者我们可以不管现有的AST,直接在它的基础上创建一个新的AST

因为我们的目标是一个新语言,所以我们将基于目标语言创建一个全新的AST

遍历(Traversal)

为了在所有节点中穿梭,我们需要能够遍历它们,这个遍历的过程会以深度优先的方式到达每个节点。

{      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'          }]        }]      }]    } 

对于上述AST,我们将依次访问:

1.Program – 从AST的顶层开始

2.CallExpression (add) – 移动到Program的body列表的第一个元素

3.NumberLiteral (2) – 移动到CallExpression的params列表的第一个元素

4.CallExpression (subtract) – 移动到CallExpression的params列表的第二个元素

5.NumberLiteral (4) – 移动到CallExpression (subtract)的params列表的第一个元素

6.NumberLiteral (2) – 移动到CallExpression (subtract)的params列表的第二个元素

如果我们直接操作这个AST,而不是重新创建一个,我们可能会在这里引入各种抽象概念。但其实直接访问(visiting)树的每个节点就够我们使用了。

我之所以使用“访问”(visiting)这个词,是因为这里存在这样一种模式,即如何表示对对象结构上的元素的操作。

访问者(Visitors)

基本思路是创建一个visitor访问器对象,提供一些接受不同节点类型的方法。

var visitor = {     NumberLiteral() {},     CallExpression() {}, }; 

当我们遍历AST,每当遇到一个匹配的节点时,我们会调用这个访问器上对应节点类型的方法。

为了能让这些方法更有用,我们会传入两个参数,当前遍历到的节点,以及它的父节点。

var visitor = {     NumberLiteral(node, parent) {},     CallExpression(node, parent) {}, }; 

然而,当退出时也存在需要访问的可能性,想象一下我们之前列表形式的树结构:

   - Program      - CallExpression        - NumberLiteral        - CallExpression          - NumberLiteral          - NumberLiteral 

当我们向下遍历时,很容易在一个分支上走到头,当我们遍历完某个分支了我们就会退出它,所以往下走的时候我们会“进入”每个节点,往上走时会“退出”节点。

   -> Program (enter)      -> CallExpression (enter)        -> Number Literal (enter)        <- Number Literal (exit)        -> Call Expression (enter)           -> Number Literal (enter)           <- Number Literal (exit)           -> Number Literal (enter)           <- Number Literal (exit)        <- CallExpression (exit)      <- CallExpression (exit)    <- Program (exit) 

为了支持这种情况,最终的访问器是这样的:

var visitor = {     NumberLiteral: {         enter(node, parent) {},         exit(node, parent) {},     } }; 

生成代码(Code Generation)

编译器的最后一个阶段是生成代码,有时编译器会做一些和转换重合的事情,但大多数情况下,生成代码只是意味着把AST转换回代码字符串。

代码生成器有几种不同的工作方式,一些编译器会重用之前的token,其他的会创建一个独立的代码表示,这样就可以线性的打印节点,但据我所知,大多数的都会直接使用我们刚刚创建的AST,我们也会这么干。

实际上我们的代码生成器知道如何去打印AST上所有不同类型的节点,它会递归调用自己去打印所有嵌套节点,直到所有内容都被打印到一个长长的代码字符串中。

小结一下

上面就是我们要做的编译器,它包含了一个真正编译器的所有部分。

但这并不意味着所有编译器都和我上面描述的一样,每个编译器可能都有不同的用途,所以它们除了我上面提到的内容外,可能它们还会有更多的步骤。

但是你现在应该会对大多数编译器有一个总体的基本的认识。

既然我已经把编译器的内容都介绍完了,现在你是否能自己写一个编译器了呢?

开个玩笑了,下面让我来帮你一起完成它。

开始吧。。。

代码实现

分词器

我们将从解析的第一个阶段开始,使用分词器进行词法分析。

我们要做的只是把代码字符串分解成一个token数组:

(add 2 (subtract 4 2))   =>   [{ type: 'paren', value: '(' }, ...] 

函数接收一个代码字符串为入参,我们要做两件事:

function tokenizer(input) {     // `current`变量就像一个游标,跟踪我们在代码中当前的位置     let current = 0;     // `tokens`数组用来存放生成的token     let tokens = [];     // 我们从创建一个while循环开始,在循环中会按照我们想要的递增量来更新current     // 这样做是因为可能一个循环里会多次更新current,因为一个token的长度是任意的     while (current < input.length) {         // 当前位置的字符         let char = input[current];         // 首先要检查的是左括号`(`,后面会用于`CallExpression`,但是现在我们只关心字符         // 检查是否是左括号:         if (char === '(') {             // 如果匹配到了,添加一个类型为`paren`的token,设置它的值为`(`             tokens.push({                 type: 'paren',                 value: '(',             });             // 递增`current`             current++;             // 跳过当前循环,进入下一个循环             continue;         }         // 接下来检查是否是右括号`)`,和刚才一样:匹配到右括号,添加一个新的token,递增current,最后跳过当前循环进入下一个循环         if (char === ')') {             tokens.push({                 type: 'paren',                 value: ')',             });             current++;             continue;         }         // 继续,接下来我们要检查的是空白符,空白符是用来分隔字符的,但它实际上并不重要,所以不会把它当做一个token进行添加         // 所以这里我们仅仅检查是否匹配到了空白符,匹配到了就跳过         let WHITESPACE = /s/;         if (WHITESPACE.test(char)) {             current++;             continue;         }         // 下一个token类型是number,这和之前的几种不一样,因为数字可能有任意长度,我们需要把数字整体作为一个token进行添加         //         //   (add 123 456)         //        ^^^ ^^^         //        虽然有六个字符,但是只算两个单独的token         //         // 当遇到序列中的第一个数字时,我们就开始了...         let NUMBERS = /[0-9]/;         if (NUMBERS.test(char)) {             // 创建一个value变量,用来保存整个数字             let value = '';             // 接下来遍历这之后的每一个字符,直到遇到非数字字符             while (NUMBERS.test(char)) {                 // 拼接当前数字                 value += char;                 // 更新current,移动到下一个字符                 char = input[++current];             }             // 之后我们添加一个number类型的token             tokens.push({ type: 'number', value });             // 继续             continue;         }         // 我们也要增加对字符串的支持,即任何被双引号包裹起来的字符(")         //         //   (concat "foo" "bar")         //            ^^^   ^^^ 字符串类型的token         //         // 我们先检查一下开头的引号("):         if (char === '"') {             // 创建一个value变量用来保存token的值             let value = '';             // 跳过开头的双引号             char = input[++current];             // 遍历之后的每一个字符,直到遇到结尾的双引号             while (char !== '"') {                 // 更新value                 value += char;                 // 移到下一个字符                 char = input[++current];             }             // 跳过结尾的双引号             char = input[++current];             // 添加一个string类型的token             tokens.push({ type: 'string', value });             continue;         }         // 还剩最后一种`name`类型的token,这是一个字母形式的字符,不是数字,作为我们的lisp语法里的函数名         //         //   (add 2 4)         //    ^^^         //    Name token         //         let LETTERS = /[a-z]/i;         if (LETTERS.test(char)) {             let value = '';             // 同样的,还是循环遍历之后的所有字符             while (LETTERS.test(char)) {                 value += char;                 char = input[++current];             }             // 添加一个`name`类型的token,然后继续到下一个循环             tokens.push({ type: 'name', value });             continue;         }         // 最后,如果到这里还有我们没有匹配到的字符,那就相当于语法有误,我们搞不定了,那么就直接抛错然后中止循环         throw new TypeError('I dont know what this character is: ' + char);     }     // 最后的最后,我们的分词器只要返回token列表就可以了     return tokens; } 

解析器

对于解析器来说,要做的是把token列表转换成AST

[{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] } 

定义一个parser函数,接收token列表作为参数:

function parser(tokens) {     // 同样的,我们维护一个`current`变量作为游标     let current = 0;     // 但是这里我们将使用递归,而不是while循环,定义一个递归函数     function walk() {         // 先获取并保存当前位置的token         let token = tokens[current];         // 我们将把每种类型的token分成不同的代码路径,从`number`类型的token开始         //         // 判断是否是一个`number`类型的token         if (token.type === 'number') {             // 如果是的话,先递增一下current             current++;             // 返回一个新的AST节点,类型是`NumberLiteral`,它的value就是token的value             return {                 type: 'NumberLiteral',                 value: token.value,             };         }         // `string`类型和`number`类型一样,创建一个`StringLiteral`类型的节点并返回         if (token.type === 'string') {             current++;             return {                 type: 'StringLiteral',                 value: token.value,             };         }         // 接下来,我们要找的是`CallExpressions`,这从我们遇到左括号开始         if (             token.type === 'paren' &&             token.value === '('         ) {             // 递增current,跳过左括号,因为它在AST里不需要             token = tokens[++current];             // 创建一个基础的`CallExpression`节点,然后把值设置为当前token的value,因为左括号的右边紧接着就是函数名             let node = {                 type: 'CallExpression',                 name: token.value,                 params: [],             };             // 递增current跳过函数名token             token = tokens[++current];             // 接下来遍历后面的节点作为调用表达式`CallExpression`的参数`params`,直到遇到右括号             //             // 这就是递归的用处,我们将依赖递归来解析一组可能无限嵌套的节点             //             // 为了解释这一点,让我们再看看Lisp代码,你可以看到`add`方法有一个数字参数和一个嵌套的`CallExpression`,同样它又存在两个数字参数:             //             //   (add 2 (subtract 4 2))             //             // 你也会注意到token列表中存在多个右括号:             //             //   [             //     { 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: ')'        }, <<< 右括号             //   ]             //             // 我们将依赖嵌套的`walk`函数来递增`current`,直到所有的`CallExpression`之后              // 因此我们创建一个`while`循环,递归调用`walk`,直到遇到右括号             // 译者注:这里其实就是考察递归思维,如果一个任务可以拆解成更小的子任务,且子任务和大任务的逻辑是一样的就可以使用递归,对于这里来说,add函数的参数的类型是任意的,可以是数字,可以是字符串,也可以是另外一个函数,另一个函数又会遇到和add函数一样的问题,所以直接交给递归函数执行,对于add来说,你只要返回AST节点就可以了。             while (                 (token.type !== 'paren') ||                 (token.type === 'paren' && token.value !== ')')             ) {                 // 调用递归函数,它将返回一个AST节点,添加到当前的`params`列表里                 node.params.push(walk());                 token = tokens[current];             } 			// 递增current,用来跳过右括号             current++;             // 返回节点             return node;         } 		// 同样的,如果遇到我们无法识别的token就抛错         throw new TypeError(token.type);     }     // 创建一个`AST`的根节点`Program`     let ast = {         type: 'Program',         body: [],     };     // 接下来开启一个循环,来添加节点到`ast.body`数组里          // 这里使用循环是因为可能有多个并列的`CallExpression`     //     //   (add 2 2)     //   (subtract 4 2)     //     while (current < tokens.length) {         ast.body.push(walk());     }     // 最后返回ast即可     return ast; } 

遍历

到这里我们已经有AST了,我们想能通过访问器来访问不同类型的节点。我们需要能够在遇到匹配类型的节点时调用访问器上的方法。

traverse(ast, {      Program: {        enter(node, parent) {          // ...        },        exit(node, parent) {          // ...        },      },       CallExpression: {        enter(node, parent) {          // ...        },        exit(node, parent) {          // ...        },      },       NumberLiteral: {        enter(node, parent) {          // ...        },        exit(node, parent) {          // ...        },      },    }); 

所以我们定义一个traverser 函数,接收一个AST和一个访问器,内部还会再定义两个函数…

function traverser(ast, visitor) {     // `traverseArray`函数用来遍历数组,里面会调用下面定义的`traverseNode`函数     function traverseArray(array, parent) {         array.forEach(child => {             traverseNode(child, parent);         });     }     // `traverseNode`接收一个`node`和它的父节点     function traverseNode(node, parent) {         //  首先确认匹配到的`type`是否在访问器里有对应方法         let methods = visitor[node.type];         // 如果存在`enter`方法,那么就调用它,传入当前节点和父节点         if (methods && methods.enter) {             methods.enter(node, parent);         }         // 接下来根据类型类型来分别处理         switch (node.type) {                 // 从顶层节点`Program`开始,因为Program节点的属性`body`是数组类型,所以调用`traverseArray`方法来遍历                 // (记住`traverseArray`方法内部会依次调用`traverseNode`,所以会递归遍历树)             case 'Program':                 traverseArray(node.body, node);                 break;                 // `CallExpression`类型也是一样的,只不过遍历的是它的`params`属性             case 'CallExpression':                 traverseArray(node.params, node);                 break;                 // `NumberLiteral`和`StringLiteral`类型的节点没有子节点,所以直接跳过             case 'NumberLiteral':             case 'StringLiteral':                 break;                 // 还是同样的,如果出现了我们无法识别的节点就抛错             default:                 throw new TypeError(node.type);         }         // 如果存在`exit`方法,在这里调用,传入`node`和它的`parent`         if (methods && methods.exit) {             methods.exit(node, parent);         }     }     // 最后我们调用`traverseNode`来开启遍历,传入ast,因为顶层节点没有`parent`,所以传null     traverseNode(ast, null); } 

译者注:这个方法其实就是树的深度优先遍历,然后在前序遍历的位置调用访问器的enter方法,在后序遍历位置调用访问器的exit方法。

转换

接下来,转换器(transformer),它会把我们构建的AST,再加上一个访问器visitor,一起传给traverser 函数,然后返回一个新的AST

----------------------------------------------------------------------------    原 AST                           |   转换后的 AST ----------------------------------------------------------------------------    {                                |   {      type: 'Program',               |     type: 'Program',      body: [{                       |     body: [{        type: 'CallExpression',      |       type: 'ExpressionStatement',        name: 'add',                 |       expression: {        params: [{                   |         type: 'CallExpression',          type: 'NumberLiteral',     |         callee: {          value: '2'                 |           type: 'Identifier',        }, {                         |           name: 'add'          type: 'CallExpression',    |         },          name: 'subtract',          |         arguments: [{          params: [{                 |           type: 'NumberLiteral',            type: 'NumberLiteral',   |           value: '2'            value: '4'               |         }, {          }, {                       |           type: 'CallExpression',            type: 'NumberLiteral',   |           callee: {            value: '2'               |             type: 'Identifier',          }]                         |             name: 'subtract'        }]                           |           },      }]                             |           arguments: [{    }                                |             type: 'NumberLiteral',                                     |             value: '4'  ---------------------------------- |           }, {                                     |             type: 'NumberLiteral',                                     |             value: '2'                                     |           }]   (不好意思,右边的比较长)              |         }                                     |       }                                     |     }]                                     |   }  ---------------------------------------------------------------------------- 

所以我们的transformer 函数会接受一个lispAST作为参数:

(译者注:要理解下面这个函数,还是先要搞清楚从旧的到新的都做了哪些转换,回到上面的对比,可以看到CallExpression节点的type没变,但是把name属性修改成了callee,另外参数列表由params变成了arguments,最后如果CallExpression节点的父节点不是CallExpression节点的话那么会创建一个ExpressionStatement节点来包裹,所以转换过程是这样的,我们首先创建一个新的AST根节点,但是我们遍历的是旧的AST,所以怎么能在新的AST上添加节点呢,可以通过在旧的AST节点上创建一个属性来引用新的AST上的列表属性,这样就可以在遍历旧的树时往新的树的列表里添加节点。)

function transformer(ast) {     // 新AST,和之前的AST一样,也要有一个Program节点     let newAst = {         type: 'Program',         body: [],     };      // 接下来我要做一个小改动,在父节点上添加一个`context`属性,然后会把每个节点都添加到它们父节点的`context`里,通常情况下你会有一个更好的抽象,但是为了我们的目的,这样做更简单     //     // 需要注意的是旧的AST里的context属性只是新AST属性的一个引用     ast._context = newAst.body;      // 接下来调用traverser方法,传入AST和一个访问器对象     traverser(ast, {         // 第一个访问者接收`NumberLiteral`类型的节点         NumberLiteral: {             // 进入时             enter(node, parent) {                 // 创建一个新的`NumberLiteral`节点,添加到父节点的context里                 parent._context.push({                     type: 'NumberLiteral',                     value: node.value,                 });             },         },          // 接下来是`StringLiteral`         StringLiteral: {             enter(node, parent) {                 parent._context.push({                     type: 'StringLiteral',                     value: node.value,                 });             },         },          // 然后是`CallExpression`         CallExpression: {             enter(node, parent) {                 // 创建一个新节点`CallExpression`,里面嵌套一个`Identifier`节点                 let expression = {                     type: 'CallExpression',                     callee: {                         type: 'Identifier',                         name: node.name,                     },                     arguments: [],                 };                  // 接下来我们给原`CallExpression`节点定义一个新的context属性,引用我们刚才新创建的节点的arguments属性,这样在遍历旧节点的参数时就可以给新的节点添加参数了                 node._context = expression.arguments;                  // 接下来检查一下父节点是否是`CallExpression`节点                 // 如果不是的话...                 if (parent.type !== 'CallExpression') {                     // 创建一点`ExpressionStatement`节点来包裹`CallExpression`节点,这样做是因为顶层的`CallExpression`在JavaScript里实际上是语句                     expression = {                         type: 'ExpressionStatement',                         expression: expression,                     };                 }                  // 最后,把(可能是被包裹的) `CallExpression`节点添加到父节点的`context`里                 parent._context.push(expression);             },         }     });      // 函数的最后返回新创建的AST     return newAst; } 

生成代码

现在让我们来看最后一个阶段:生成代码。

我们的代码生成器会递归的调用自己,把树中的每个节点都打印到一个巨大的字符里。

function codeGenerator(node) {     // 我们将按节点类型进行分别处理     switch (node.type) {             // 如果是`Program`节点,那就遍历它的`body`列表,对每个节点调用codeGenerator方法,然后把它们用换行符拼接起来         case 'Program':             return node.body.map(codeGenerator)                 .join('n');              // 对于`ExpressionStatement`节点,对它的expression节点调用对每个节点调用codeGenerator方法方法,然后再添加一个分号...         case 'ExpressionStatement':             return (                 codeGenerator(node.expression) +                 ';' // << (...在一个语句的末尾添加分号是符合标准的)             );              // 对于`CallExpression`节点,我们要打印的是`callee`,然后拼接一个左括号,然后遍历参数`arguments`的每个节点,调用codeGenerator方法把它们转成字符串,然后用逗号拼接起来,最后再添加一个右括号         case 'CallExpression':             return (                 codeGenerator(node.callee) +                 '(' +                 node.arguments.map(codeGenerator)                 .join(', ') +                 ')'             );              // 对于`Identifier`节点,只要返回name属性的值即可         case 'Identifier':             return node.name;              // 对于`NumberLiteral`节点,返回它的value属性值         case 'NumberLiteral':             return node.value;              // 对于`StringLiteral`节点,需要使用双引号来包裹它的value值         case 'StringLiteral':             return '"' + node.value + '"';              // 如果遇到无法识别的节点,那么抛错         default:             throw new TypeError(node.type);     } } 

最终的编译器~

最后让我们来创建一个compiler函数,在这个函数里把上面的所有流程串起来:

1. input  => tokenizer   => tokens 2. tokens => parser      => ast 3. ast    => transformer => newAst 4. newAst => generator   => output 
function compiler(input) {   let tokens = tokenizer(input);   let ast    = parser(tokens);   let newAst = transformer(ast);   let output = codeGenerator(newAst);    // 把代码生成结果返回就ok了   return output; }  

大功告成

现在,让我们把上面所有的函数导出:

module.exports = {     tokenizer,     parser,     traverser,     transformer,     codeGenerator,     compiler, }; 

总结

注释太多可能影响阅读代码,可以点此阅读纯享版https://github.com/wanglin2/the-super-tiny-compiler/blob/master/the-super-tiny-compiler.js

本文由博客一文多发平台 OpenWrite 发布!

赞(0) 打赏
未经允许不得转载:张拓的天空 » 【译】一个超级小的编译器
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏