1.需求分析 #

//假设我们有两个函数,`add` 和 `subtract`,那么它们的写法将会是下面这样
                  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))

2.编译器分为三个阶段 #

2.1 解析(Parsing) #

原始lisp代码

(add 2 (subtract 4 2))

tokens

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

2.2 转换(Transformation) #

{
      type: 'NumberLiteral',
      value: '2'
}
 {
    type: 'CallExpression',
    name: 'subtract',
    params: [...nested nodes go here...]
 }

2.3 遍历(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'
       }]
     }]
   }]
 }
Program - 从 AST 的顶部结点开始
  CallExpression (add) - Program 的第一个子元素
    NumberLiteral (2) - CallExpression (add) 的第一个子元素
    CallExpression (subtract) - CallExpression (add) 的第二个子元素
      NumberLiteral (4) - CallExpression (subtract) 的第一个子元素
      NumberLiteral (2) - CallExpression (subtract) 的第二个子元素

2.4 访问者(Visitors) #

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

2.5 代码生成(Code Generation) #

3.实现编译器 #

3.1 词法分析器(Tokenizer) #

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

main.js

let tokenizer = require('./tokenizer');
let tokens = tokenizer("(add 11 22)");
console.log(tokens);

tokenizer.js

let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
function tokenizer(input){
  //current类似指标,用于记录我们在代码字符串中的位置
  let current=0;
  //tokens是一个数组,用来放置我们的token
  let tokens = [];
  //可能会在单个循环中多次增加current  
  while(current < input.length){
    //char 指向当前字符串
    let char = input[current];
    //先检查是不是一个左圆括号
    if(char === '('){
        //如果是的话,我们往tokens里push一个type为paren,value为左圆括号的对象
        tokens.push({
            type:'paren',
            value:'('
        });
        //自增current
        current++;
        //结束本次循环,进入下一个循环
        continue;
    //如果token是函数名,函数名是由一系列字母组成 比如  (add 11 22)
    }else if(LETTERS.test(char)){
        let value = '';
        //用内层循环遍历所有的字母,把它们存入value中
        while(LETTERS.test(char)){
            value+=char;
            char = input[++current];
        }
        //然后添加一个类型为name的token,进入下一个循环
        tokens.push({
            type:'name',
            value
        });
        continue;
    }else if(WHITESPACE.test(char)){
        //token并不是有效的token,所以直接进入下一个循环
        current++;
        continue;
    }else if(NUMBERS.test(char)){
        let value = '';
        //用内层循环遍历所有的数字,把它们存入value中
        while(NUMBERS.test(char)){
            value+=char;
            char = input[++current];
        }
        //然后添加一个类型为number的token,进入下一个循环
        tokens.push({
            type:'number',
            value
        });
        continue;
    }else if(char === ')'){
        tokens.push({
            type: 'paren',
            value: ')'
          });
        current++;
        continue;
    }
    //如果没有匹配上任何类型的token,则抛出一个错误
    throw new TypeError('I dont know what this character is '+ char);
  }
  return tokens;
}
module.exports = tokenizer;

3.2 语法分析器(Parser) #

3.2.1 main.js #

let tokenizer = require('./tokenizer');
+let parser = require('./parser');
+let tokens = tokenizer("(add 11 (sub 3 1))");
console.log(tokens);
+let ast  = parser(tokens);
+console.log(JSON.stringify(ast,null,2));

3.2.2 parser.js #

/**
 *  语法分析器接受 token 数组,然后把它转化为 AST
 *   [{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] }
 */
//现在我们定义parser函数,接受tokens数组
function parser(tokens) { // (add 11 22) (add 2 (subtract 4 2))
    //我们再次声明一个current变量指针
    let current = 0;
    //但是这次我们使用递归而不是 `while` 循环,所以我们定义一个 `walk` 函数
    function walk() {
        // walk函数里,我们从当前token开始
        let token = tokens[current];
        //我们检查是不是 CallExpressions 类型,我们从左圆括号开始
        if (token.type === 'paren' && token.value == '(') {
            // 我们会自增 `current` 来跳过这个括号,因为括号在 AST 中是不重要的
            token = tokens[++current];
            //我们创建一个类型为 `CallExpression` 的根节点,然后把它的 name 属性设置为当前token 的值
            //因为紧跟在左圆括号后面的 token 一定是调用的函数的名字
            let node = {
                type: 'CallExpression',
                name: token.value,
                params: []
            }
            // 我们再次自增 `current` 变量,跳过当前的 token 
            token = tokens[++current];
            //现在我们循环遍历接下来的每一个 token,直到我们遇到右圆括号,这些 token 将会是 `CallExpression` 的 `params`(参数)
            //这也是递归开始的地方,我们采用递归的方式来解决问题,而不是去尝试解析一个可能有无限层嵌套的结点 
            //(add 2 (subtract 4 2))
            //所以我们创建一个 `while` 循环,直到遇到类型为 `'paren'`,值为右圆括号的 token
            while (token.type != 'paren' || token.type == 'paren' && token.value != ')') {
                //我们调用 `walk` 函数,它将会返回一个结点,然后我们把这个节点放入 `node.params` 中
                node.params.push(walk());
                token = tokens[current];
            }
            // 我们最后一次增加 `current`,跳过右圆括号
            current++;
            // 返回结点
            return node;
        //检查是不是 `number` 类型
        }else if(token.type === 'number'){
            // 如果是,`current` 自增。
            current++;
            // 然后我们会返回一个新的 AST 结点 `NumberLiteral`,并且把它的值设为 token 的值。
            return {
              type: 'NumberLiteral',
              value: token.value
            };
        }
        //同样,如果我们遇到了一个类型未知的结点,就抛出一个错误。
        throw new TypeError(token.type);
    }
    //现在,我们创建 AST,根结点是一个类型为 `Program` 的结点
    var ast = {
        type: 'Program',
        body: []
    };
    //现在我们开始 `walk` 函数,把结点放入 `ast.body` 中
    //之所以在一个循环中处理,是因为我们的程序可能在 `CallExpressions` 后面包含连续的两个参数,而不是嵌套的
    //(add 2 2)  (subtract 4 2)
    while (current < tokens.length) {
        ast.body.push(walk());
    }

    // 最后我们的语法分析器返回 AST 
    return ast;
}
module.exports  = parser;

3.3 遍历器 #

 traverse(ast, {
  Program(node, parent) {
      console.log(node);
  },
  CallExpression(node, parent) {
    console.log(node);
  },
  NumberLiteral(node, parent) {
    console.log(node);
  },
});

3.3.1 main.js #

let tokenizer = require("./tokenizer");
let parser = require("./parser");
+let traverser = require("./traverser");
let tokens = tokenizer("(add 11 (sub 3 1))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
+let vistor = {
+  Program(node, parent) {
+      console.log(node);
+  },
+  CallExpression(node, parent) {
+    console.log(node);
+  },
+  NumberLiteral(node, parent) {
+    console.log(node);
+  },
+};
+traverser(ast,vistor);

3.3.2 traverser.js #

// 所以我们定义一个遍历器,它有两个参数,AST 和 vistor。在它的里面我们又定义了两个函数...
function traverser(ast, visitor) {
     // `traverseArray` 函数允许我们对数组中的每一个元素调用 `traverseNode` 函数。
    function traverseArray(array, parent) {
        array.forEach(function(child) {
           traverseNode(child, parent);
        });
    }

    // `traverseNode` 函数接受一个 `node` 和它的父结点 `parent` 作为参数,这个结点会被
    // 传入到 visitor 中相应的处理函数那里。
    function traverseNode(node,parent){
        // 首先我们看看 visitor 中有没有对应 `type` 的处理函数。
       var method = visitor[node.type];
        // 如果有,那么我们把 `node` 和 `parent` 都传入其中。
        if (method) {
            method(node, parent);
        }
        // 下面我们对每一个不同类型的结点分开处理。
        switch (node.type) {
            //我们从顶层的 `Program` 开始,Program 结点中有一个 body 属性,它是一个由若干个结点组成的数组,所以我们对这个数组调用 `traverseArray`
            //记住 `traverseArray` 会调用 `traverseNode`,所以我们会递归地遍历这棵树。
            case 'Program':
              traverseArray(node.body, node);
            break;
            //下面我们对 `CallExpressions` 做同样的事情,遍历它的 `params`。
            case 'CallExpression':
              traverseArray(node.params, node);
              break;
              // 如果是 `NumberLiterals`,那么就没有任何子结点了,所以我们直接 break
            case 'NumberLiteral':
                break;
            // 同样,如果我们不能识别当前的结点,那么就抛出一个错误。
            default:
                throw new TypeError(node.type);
            }
    }
    // 最后我们对 AST 调用 `traverseNode`,开始遍历。注意 AST 并没有父结点。
    traverseNode(ast, null);
}
module.exports = traverser;

3.4 转换AST #

transformerAST

3.4.1 main.js #

let tokenizer = require("./tokenizer");
let parser = require("./parser");
let traverser = require("./traverser");
+let transformer = require("./transformer");
let tokens = tokenizer("(add 2 (subtract 4 2))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
let vistor = {
  Program(node, parent) {
      console.log(node);
  },
  CallExpression(node, parent) {
    console.log(node);
  },
  NumberLiteral(node, parent) {
    console.log(node);
  },
};
//traverser(ast,vistor);
+var newAst = transformer(ast);
+console.log(JSON.stringify(newAst, null, 2));

3.4.2 transformer.js #

let traverser = require('./traverser');
function transformer(ast) {
  // 创建 `newAST`,它与我们之前的 AST 类似,有一个类型为 Program 的根节点。
  var newAst = {
    type: 'Program',
    body: []
  };//老的ast有一个属性_context指向新的ast的body
  ast._context = newAst.body;
  // 我们把 AST 和 visitor 函数传入遍历器
  traverser(ast,{
    NumberLiteral(node,parent){
        // 我们创建一个新结点,名字叫 `NumberLiteral`,并把它放入父结点的 context 中。
        parent._context.push({
            type:'NumberLiteral',
            value:node.value
        });
    },
    CallExpression(node,parent){
      //我们创建一个 `CallExpression` 结点,里面有一个嵌套的 `Identifier`
      var expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: []
      };
      // 下面我们在原来的 `CallExpression` 结点上定义一个新的 context,它是 expression
      // 中 arguments 这个数组的引用,我们可以向其中放入参数。
      node._context = expression.arguments;
      // 最后我们把 `CallExpression`放入父结点的 context 中。
      parent._context.push(expression);
    }
  });
  // 最后返回创建好的新 AST
  return newAst;
}
module.exports = transformer;

3.5 代码生成 #

3.5.1 main.js #

let tokenizer = require("./tokenizer");
let parser = require("./parser");
let traverser = require("./traverser");
let transformer = require("./transformer");
let codeGenerator = require("./codeGenerator");
let tokens = tokenizer("(add 2 (subtract 4 2))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
let vistor = {
  Program(node, parent) {
      console.log(node);
  },
  CallExpression(node, parent) {
    console.log(node);
  },
  NumberLiteral(node, parent) {
    console.log(node);
  },
};
//traverser(ast,vistor);
var newAst = transformer(ast);
console.log(JSON.stringify(newAst, null, 2));

let newCode = codeGenerator(newAst);
console.log(newCode);

3.5.2 codeGenerator.js #

function codeGenerator(node) {
    // 对于不同 `type` 的结点分开处理。
    switch (node.type) {
      // 如果是 `Program` 结点,那么我们会遍历它的 `body` 属性中的每一个结点,并且递归地
      // 对这些结点再次调用 codeGenerator,再把结果打印进入新的一行中。
      case 'Program':
        return node.body.map(codeGenerator)
          .join('\n');
      // 对于 `CallExpressions`,我们会打印出 `callee`,接着是一个左圆括号,然后对
      // arguments 递归调用 codeGenerator,并且在它们之间加一个逗号,最后加上右圆括号。
      case 'CallExpression':
        return (
          codeGenerator(node.callee) +
          '(' +
          node.arguments.map(codeGenerator)
            .join(', ') +
          ')'
        );

      // 对于 `Identifiers` 我们只是返回 `node` 的 name。
      case 'Identifier':
        return node.name;

      // 对于 `NumberLiterals` 我们只是返回 `node` 的 value
      case 'NumberLiteral':
        return node.value;

      // 如果我们不能识别这个结点,那么抛出一个错误。
      default:
        throw new TypeError(node.type);
    }
  }
  module.exports = codeGenerator;

3.6 打包 #

3.6.1 main.js #

const compier = require("./compiler");

let compiler = require('./compiler');
let output = compiler("(add 2 (subtract 4 2))");
console.log(output);

3.6.2 compiler\index.js #

compiler\index.js

const tokenizer = require("./tokenizer");
const parser = require("./parser");
const transformer = require("./transformer");
const codeGenerator = require("./codeGenerator");

function compier(input){
    let tokens = tokenizer(input);
    let ast = parser(tokens);
    let newAst = transformer(ast);
    let output = codeGenerator(newAst);
    return output;
}
module.exports = compier;

3.6.3 tokenizer.js #

compiler\tokenizer.js

let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
function tokenizer(input){
  //current类似指标,用于记录我们在代码字符串中的位置
  let current=0;
  //tokens是一个数组,用来放置我们的token
  let tokens = [];
  //可能会在单个循环中多次增加current  
  while(current < input.length){
    //char 指向当前字符串
    let char = input[current];
    //先检查是不是一个左圆括号
    if(char === '('){
        //如果是的话,我们往tokens里push一个type为paren,value为左圆括号的对象
        tokens.push({
            type:'paren',
            value:'('
        });
        //自增current
        current++;
        //结束本次循环,进入下一个循环
        continue;
    //如果token是函数名,函数名是由一系列字母组成 比如  (add 11 22)
    }else if(LETTERS.test(char)){
        let value = '';
        //用内层循环遍历所有的字母,把它们存入value中
        while(LETTERS.test(char)){
            value+=char;
            char = input[++current];
        }
        //然后添加一个类型为name的token,进入下一个循环
        tokens.push({
            type:'name',
            value
        });
        continue;
    }else if(WHITESPACE.test(char)){
        //token并不是有效的token,所以直接进入下一个循环
        current++;
        continue;
    }else if(NUMBERS.test(char)){
        let value = '';
        //用内层循环遍历所有的数字,把它们存入value中
        while(NUMBERS.test(char)){
            value+=char;
            char = input[++current];
        }
        //然后添加一个类型为number的token,进入下一个循环
        tokens.push({
            type:'number',
            value
        });
        continue;
    }else if(char === ')'){
        tokens.push({
            type: 'paren',
            value: ')'
          });
        current++;
        continue;
    }
    //如果没有匹配上任何类型的token,则抛出一个错误
    throw new TypeError('I dont know what this character is '+ char);
  }
  return tokens;
}
module.exports = tokenizer;

3.6.4 parser.js #

compiler\parser.js

/**
 *  语法分析器接受 token 数组,然后把它转化为 AST
 *   [{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] }
 */
//现在我们定义parser函数,接受tokens数组
function parser(tokens) { // (add 11 22) (add 2 (subtract 4 2))
    //我们再次声明一个current变量指针
    let current = 0;
    //但是这次我们使用递归而不是 `while` 循环,所以我们定义一个 `walk` 函数
    function walk() {
        // walk函数里,我们从当前token开始
        let token = tokens[current];
        //我们检查是不是 CallExpressions 类型,我们从左圆括号开始
        if (token.type === 'paren' && token.value == '(') {
            // 我们会自增 `current` 来跳过这个括号,因为括号在 AST 中是不重要的
            token = tokens[++current];
            //我们创建一个类型为 `CallExpression` 的根节点,然后把它的 name 属性设置为当前token 的值
            //因为紧跟在左圆括号后面的 token 一定是调用的函数的名字
            let node = {
                type: 'CallExpression',
                name: token.value,
                params: []
            }
            // 我们再次自增 `current` 变量,跳过当前的 token 
            token = tokens[++current];
            //现在我们循环遍历接下来的每一个 token,直到我们遇到右圆括号,这些 token 将会是 `CallExpression` 的 `params`(参数)
            //这也是递归开始的地方,我们采用递归的方式来解决问题,而不是去尝试解析一个可能有无限层嵌套的结点 
            //(add 2 (subtract 4 2))
            //所以我们创建一个 `while` 循环,直到遇到类型为 `'paren'`,值为右圆括号的 token
            while (token.type != 'paren' || token.type == 'paren' && token.value != ')') {
                //我们调用 `walk` 函数,它将会返回一个结点,然后我们把这个节点放入 `node.params` 中
                node.params.push(walk());
                token = tokens[current];
            }
            // 我们最后一次增加 `current`,跳过右圆括号
            current++;
            // 返回结点
            return node;
        //检查是不是 `number` 类型
        }else if(token.type === 'number'){
            // 如果是,`current` 自增。
            current++;
            // 然后我们会返回一个新的 AST 结点 `NumberLiteral`,并且把它的值设为 token 的值。
            return {
              type: 'NumberLiteral',
              value: token.value
            };
        }
        //同样,如果我们遇到了一个类型未知的结点,就抛出一个错误。
        throw new TypeError(token.type);
    }
    //现在,我们创建 AST,根结点是一个类型为 `Program` 的结点
    var ast = {
        type: 'Program',
        body: []
    };
    //现在我们开始 `walk` 函数,把结点放入 `ast.body` 中
    //之所以在一个循环中处理,是因为我们的程序可能在 `CallExpressions` 后面包含连续的两个参数,而不是嵌套的
    //(add 2 2)  (subtract 4 2)
    while (current < tokens.length) {
        ast.body.push(walk());
    }

    // 最后我们的语法分析器返回 AST 
    return ast;
}
module.exports  = parser;

3.6.5 transformer.js #

let traverser = require('./traverser');
function transformer(ast) {
  // 创建 `newAST`,它与我们之前的 AST 类似,有一个类型为 Program 的根节点。
  var newAst = {
    type: 'Program',
    body: []
  };//老的ast有一个属性_context指向新的ast的body
  ast._context = newAst.body;
  // 我们把 AST 和 visitor 函数传入遍历器
  traverser(ast,{
    NumberLiteral(node,parent){
        // 我们创建一个新结点,名字叫 `NumberLiteral`,并把它放入父结点的 context 中。
        parent._context.push({
            type:'NumberLiteral',
            value:node.value
        });
    },
    CallExpression(node,parent){
      //我们创建一个 `CallExpression` 结点,里面有一个嵌套的 `Identifier`
      var expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: []
      };
      // 下面我们在原来的 `CallExpression` 结点上定义一个新的 context,它是 expression
      // 中 arguments 这个数组的引用,我们可以向其中放入参数。
      node._context = expression.arguments;
      // 最后我们把 `CallExpression`放入父结点的 context 中。
      parent._context.push(expression);
    }
  });
  // 最后返回创建好的新 AST
  return newAst;
}
module.exports = transformer;

3.6.6 codeGenerator.js #

function codeGenerator(node) {
    // 对于不同 `type` 的结点分开处理。
    switch (node.type) {
      // 如果是 `Program` 结点,那么我们会遍历它的 `body` 属性中的每一个结点,并且递归地
      // 对这些结点再次调用 codeGenerator,再把结果打印进入新的一行中。
      case 'Program':
        return node.body.map(codeGenerator)
          .join('\n');
      // 对于 `CallExpressions`,我们会打印出 `callee`,接着是一个左圆括号,然后对
      // arguments 递归调用 codeGenerator,并且在它们之间加一个逗号,最后加上右圆括号。
      case 'CallExpression':
        return (
          codeGenerator(node.callee) +
          '(' +
          node.arguments.map(codeGenerator)
            .join(', ') +
          ')'
        );

      // 对于 `Identifiers` 我们只是返回 `node` 的 name。
      case 'Identifier':
        return node.name;

      // 对于 `NumberLiterals` 我们只是返回 `node` 的 value
      case 'NumberLiteral':
        return node.value;

      // 如果我们不能识别这个结点,那么抛出一个错误。
      default:
        throw new TypeError(node.type);
    }
  }
  module.exports = codeGenerator;

3.6.7 compiler\traverser.js #

// 所以我们定义一个遍历器,它有两个参数,AST 和 vistor。在它的里面我们又定义了两个函数...
function traverser(ast, visitor) {
     // `traverseArray` 函数允许我们对数组中的每一个元素调用 `traverseNode` 函数。
    function traverseArray(array, parent) {
        array.forEach(function(child) {
           traverseNode(child, parent);
        });
    }

    // `traverseNode` 函数接受一个 `node` 和它的父结点 `parent` 作为参数,这个结点会被
    // 传入到 visitor 中相应的处理函数那里。
    function traverseNode(node,parent){
        // 首先我们看看 visitor 中有没有对应 `type` 的处理函数。
       var method = visitor[node.type];
        // 如果有,那么我们把 `node` 和 `parent` 都传入其中。
        if (method) {
            method(node, parent);
        }
        // 下面我们对每一个不同类型的结点分开处理。
        switch (node.type) {
            //我们从顶层的 `Program` 开始,Program 结点中有一个 body 属性,它是一个由若干个结点组成的数组,所以我们对这个数组调用 `traverseArray`
            //记住 `traverseArray` 会调用 `traverseNode`,所以我们会递归地遍历这棵树。
            case 'Program':
              traverseArray(node.body, node);
            break;
            //下面我们对 `CallExpressions` 做同样的事情,遍历它的 `params`。
            case 'CallExpression':
              traverseArray(node.params, node);
              break;
              // 如果是 `NumberLiterals`,那么就没有任何子结点了,所以我们直接 break
            case 'NumberLiteral':
                break;
            // 同样,如果我们不能识别当前的结点,那么就抛出一个错误。
            default:
                throw new TypeError(node.type);
            }
    }
    // 最后我们对 AST 调用 `traverseNode`,开始遍历。注意 AST 并没有父结点。
    traverseNode(ast, null);
}
module.exports = traverser;

4.有限状态机 #

statemachine.jpg

let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
let currentToken;

function start(char){
    if(char === '('){
        emit({ type: 'paren',  value: '('});
        return foundParen;
    }else{
        return start;
    }
}
function foundParen(char){
    if(LETTERS.test(char)){
        currentToken = {
            type:'name',
            value:''
        }
        return name(char);
    }
    throw new TypeError('函数名必须是字符 '+ char); 
}
function name(char){
    if(char.match(/^[a-zA-Z]$/)){
        currentToken.value += char;
        return name;
    }else if(char == " "){
        emit(currentToken);
        currentToken = {
            type:'number',
            value:''
        }
        return number;
    }
    throw new TypeError('函数名必须以空格结束 '+ char); 
}
function number(char){
    if(NUMBERS.test(char)){
        currentToken.value += char;
        return number;
    }else if(char == " "){
        emit(currentToken);
        currentToken = {
            type:'number',
            value:''
        }
        return number;
    }else if(char == ")"){
        emit(currentToken);
        emit({ type: 'paren',  value: ')'});
        return start;
    }
    throw new TypeError('参数必须是数字 '+ char); 
}

function tokenizer(input){
    let state = start;
    for(let char of input){
        state = state(char);
    }
}

function emit(token){
    console.log(token);
}
tokenizer('(add 45 23)');

5.正则分词 #

let RegExpObject = /([0-9]+)|([ ])|(\+)|(\-)|(\*)|(\/)|([\(])|([\)])/g;
let names = ["Number","Space","+","-","*","/","(",")"];

function* tokenize(source){
  let result = null;
  while(true){
      result = RegExpObject.exec(source);
      if(!result) break;
      let token = {type:null,value:null};
      let index = result.find((item,index)=>index>0&&!!item);
      token.type = names[index];
      token.value = (result[0]);
      yield token;
  }
}
let tokens = [];
for(let token of tokenize("33+44-55*66*(77+55)")){
    tokens.push(token);
}
console.log(tokens);