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

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

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

{
    type: 'CallExpression',
    name: 'substract',
    params: [...nested nodes here ...],
}

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

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

const tokenizer = (input) => {
  const tokens = [];
  let current = 0;
  while (current < input.length) {
    let char = input[current];
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      })

      current++;
      continue;
    }

    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      })
      current ++;
      continue;
    }

    // 空格目前不需要處理
    if (/\s/.test(char)) {
      current++;
      continue;
    }

    // 處理數(shù)字
    if (/[0-9]/.test(char)) {
      let value = '';
      // 一直遍歷直到遇到非數(shù)字的字符
      while (/[0-9]/.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'number',
        value,
      })
      continue;
    }

    // 處理字符串
    if(/[a-z]/i.test(char)) {
      let value = '';

      while(/[a-z]/i.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'name',
        value,
      });

      continue;
    }

    // 如果存在匹配不上的 token 就拋錯(cuò)
    throw new Error(`Unknown token: ${char}`);
  }
  return tokens;
}

const parser = (tokens) => {
  let current = 0;
  
  const walk = () => {
    const token = tokens[current];
    // 如果是 number 類型的結(jié)點(diǎn)，返回一個(gè)新的 ast 節(jié)點(diǎn)即可
    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }

    // 接下來(lái)檢查 CallExpression 類型，先從左圓括號(hào)開(kāi)始
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 跳過(guò)左圓括號(hào)
      token = tokens[++current];
      // 首先會(huì)創(chuàng)建一個(gè) CallExpression 的根節(jié)點(diǎn)，然后 name 設(shè)置成當(dāng)前的 token.value
      // 因?yàn)樽髨A括號(hào)后的 token 一定是函數(shù)名稱
      const node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 這里再跳一次函數(shù)名稱
      token = tokens[++current];

      // 通過(guò)循環(huán)遍歷接下來(lái)的每個(gè) token，直到遇到右圓括號(hào)
      // 這些 token 會(huì)成為 `CallExpression` 的  `params`

      // 以 lisp 風(fēng)格的代碼來(lái)說(shuō): (add 2 (substract 4 2))
      /**
       * token 中會(huì)有很多圓括號(hào)
       * [
          { 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: ')'        }, <<< 右圓括號(hào)
          { type: 'paren',  value: ')'        }  <<< 右圓括號(hào)
        ]
        遇到嵌套的 CallExpressions 的時(shí)候，會(huì)通過(guò) walk 函數(shù)來(lái)處理
       *
       */
      while (
        token.type !== 'paren' ||
        (token.value !== ')' && token.type === 'paren')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      current++;
      return node;
    }
    throw new Error(`Unknown token type: ${token.type}`);
  }

  const ast = {
    type: 'Program',
    body: [],
  }

  /**
   * 使用遞歸函數(shù)將結(jié)點(diǎn)處理進(jìn) ast.body 中
   */
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

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

const traverser = (ast, visitor) => {

  // 用于對(duì)數(shù)組中的每個(gè)元素都調(diào)用 traverseNode 函數(shù)
  const traverseArray = (array, parent) => {
    array.forEach((child) => {
      traverseNode(child, parent);
    });
  }

  // 函數(shù)接收一個(gè) node 以及其父結(jié)點(diǎn)作為參數(shù)
  // 這個(gè)結(jié)點(diǎn)會(huì)被傳入到 visitor 中相應(yīng)的處理函數(shù)那里
  const traverseNode = (node, parent) => {
    const method = visitor[node.type];
    if (method) {
      method(node, parent);
    }
    // 對(duì)不同的結(jié)點(diǎn)分開(kāi)處理
    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;
        
      // 這種情況下就沒(méi)有子節(jié)點(diǎn)了，直接 break 出去
      case 'NumberLiteral':
        break;
      
      default:
        throw new Error(`Unknown node type: ${node.type}`);
    }
  }

  traverseNode(ast, null);
}

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

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

const transformer = (ast) => {
  const newAst = {
    type: 'Program',
    body: [],
  }

  ast._context = newAst.body;

  traverser(ast, {
    // 處理 NumberLiteral 類型
    NumberLiteral: (node, parent) => {
      parent._context.push({
        type: 'NumberLiteral',
        value: node.value,
      });
    },

    // 處理 CallExpression 類型
    CallExpression: (node, parent) => {

      // 初始化一個(gè) CallExpression 的新節(jié)點(diǎn)
      // 里面放個(gè)嵌套的 Identifier 節(jié)點(diǎn)
      const expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: [],
      };

      node._context = expression.arguments;

      // 看看父節(jié)點(diǎn)是不是 CallExpression
      if (parent.type !== 'CallExpression') {

        // 如果不是的話，就將 CallExpression 節(jié)點(diǎn)包在一個(gè)叫 `ExpressionStatement` 的語(yǔ)句節(jié)點(diǎn)里
        // 這么做是因?yàn)?top level 的 CallExpression 在 JavaScript 中也可以被當(dāng)成是聲明語(yǔ)句
        expression = {
          type: 'ExpressionStatement',
          expression,
        };
      }

      // 最后我們把 CallExpression 放入父結(jié)點(diǎn)的 context 中
      parent._context.push(expression);
    }
  });

  return newAst;
}

const codeGenerator = (node) => {
  switch (node.type) {
    // 如果是 Program，則會(huì)遍歷 'body' 屬性中的每個(gè)結(jié)點(diǎn)
    // 并且對(duì)這些結(jié)點(diǎn)進(jìn)行遞歸 codeGenerator,再把結(jié)果打印進(jìn)新的一行里面
    case 'Program':
      return node.body.map(codeGenerator).join('\n');
    
    // 對(duì)于 ExpressionStatement 對(duì) expression 屬性進(jìn)行遞歸調(diào)用，并加個(gè)分號(hào)
    case 'ExpressionStatement':
      return `${codeGenerator(node.expression)};`;
    
    // 對(duì)于 CallExpression 對(duì) callee 屬性進(jìn)行遞歸調(diào)用，接著加上(括號(hào)
    // 然后對(duì) arguments 屬性進(jìn)行遞歸調(diào)用，并加上)括號(hào)
    case 'CallExpression':
      return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;

    // 對(duì)于 Identifier,直接返回 name
    case 'Identifier':
      return node.name;
    
    // 對(duì)于 NumberLiteral,直接返回 value
    case 'NumberLiteral':
      return node.value;
    
    default:
      throw new Error(`Unknown node type: ${node.type}`);
  }
}

const compiler = (input) => {
  const tokens = tokenizer(input);
  const ast = parser(tokens);
  const newAst = transformer(ast);
  
  return codeGenerator(newAst);
}