代码来构建一个简单的compiler

小鱼儿 2022-03-16 14:08 185阅读 0赞

关于[compiler原理][compiler]可以参考这篇文章。或者微信搜索订阅号'北宸南蓁'或者搜索wDxKn89。

# Parsing #

我们来构建一个tokenizer用于进行lexical analysis（词法分析）

## 设计思路 ##

我们向tokenizer中传递需要转换的字符类型的code，并且将code通过一些分解规则，拆分为tokens数组。

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

### tokenizer代码实现 ###

### Parser的代码实现 ###

我们已经有了tokenizer(已经将raw code格式化为tokens array)，既然烹饪材料已经有了，就需要对'材料'进行进一步加工，从而转换为AST。

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

我们定义一个接收tokens数组的'parser'函数

# Transformation #

通过Parsing对raw code的处理，生成对应的AST。但是我们需求是对AST进行处理来生成目标AST。但是现在有一个问题，如何才能遍历这些树形结构，总不能用while来处理，同时也不能保证node信息的被按访问顺序的纪录。  
所以我们需要能利用visitor(针对树形结构的游标)来构建一个访问AST同时按照访问顺序纪录一些node信息的"遍历器"。

## traverser的代码实现 ##

大致思路,traverse接收ast,还有不同类型的visitor。

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

真实代码

## transformer ##

通过构建了traverser(),我们现在有能力可以对AST进行有目的的遍历，同时还可以保证他们直接存在的原有关联不被破坏。接下来，我们就需要利用traverser()来对AST进行有目的的改造(生成新的AST)。

**原始的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'
              }]
            }]
          }]
        }
    复制代码

转换后的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'
                        }]
                    }
                 }
            }]
    }
    复制代码

### transformer的代码实现(接收lisp ast) ###

# Code Generator #

我们采用递归调用code generator将new ast中的node字符化。 codeGenerator的代码实现

function codeGenerator(node) {
    
     // 根据type来区分不同的输出处理
     switch (node.type) {
    
       //如果遇到`Program` node，将body的数组中的item通过再次调用codeGenerator来进行类输出，（可以认为是递归调用）
       case 'Program':
         return node.body.map(codeGenerator)
           .join('\n'
           //处理
       case 'ExpressionStatement':
         return (
           codeGenerator(node.expression) +
           ';' // 为了代码格式更加的符合开发规范
         );
    
       //处理函数
       case 'CallExpression':
         return (
           codeGenerator(node.callee) +
           '(' +
           node.arguments.map(codeGenerator)
             .join(', ') +
           ')'
         );
    
       // 其实是返回了函数名
       case 'Identifier':
         return node.name;
    
       // 直接返回数据
       case 'NumberLiteral':
         return node.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);
    
      
      return output;
    }
    
    复制代码

我们也可以将这些方法进行导出

module.exports = {
      tokenizer,
      parser,
      traverser,
      transformer,
      codeGenerator,
      compiler,
    };
    复制代码

[compiler]: https://juejin.im/post/5b699d8ae51d45191d7a4348