Generate AST

parser.js

/**
 *if (1 > 0) {
   alert('1 > 0');
 }
 *
 * @param {*} params
 */

function parser(tokens) {
  let i = -1;
  let currToken;
  const ast = {
    type: 'Program',
    body: []
  }

  const stashStock = [];

  function stash() {
    stashStock.push(i);
  }

  function rewind() {
    i = stashStock.pop();
    currToken = tokens[i];
  }

  function commit() {
   stashStock.pop(); 
  }

  function nextToken() {
    do {
      i++;
      currToken = tokens[i] || {
        type: 'EOF'
      };
    } while (currToken.type === 'whitespace');
  }

  function nextStatement() {
    stash();
    nextToken();
    if (currToken.type === 'identifier' && currToken.value === 'if') {
      const statement = {
        type: 'IfStatement'
      }

      nextToken();
      if (currToken.type !== 'parens' || currToken.value !== '(') {
        throw new Error('Excepted ( after if');
      }

      statement.test = nextExpression();

      nextToken();
      if (currToken.type !== 'parens' || currToken.value !== ')') {
        throw new Error('Excepted ) after if test expression');        
      }

      statement.consequent = nextStatement();

      console.log('currToken :', currToken);
      nextToken();
      if (currToken.type === 'identifier' && currToken.value === 'else') {
        statement.alternative = nextStatement();
      } else {
        statement.alternative = null;
      }

      return statement;
    }

    if (currToken.type === 'brace' && currToken.value === '{') {
      const statement = {
        type: 'BlockStatement',
        body: []
      }
      while (i < tokens.length) {
        stash();
        nextToken();
        if (currToken.type === 'brace' && currToken.value === '}') {
          commit();
          break;
        }
        rewind();
        statement.body.push(nextStatement());
      }
      return statement;
    }

    rewind();
    const statement = {
      type: 'ExpressionStatement',
      expression: nextExpression()
    }
    if (statement.expression) {
      nextToken();
      // TEST: 这个是否可以不用？
      if (currToken.type !== 'EOF' && currToken.type !== 'sep') {
        throw new Error('Missing ; at end of expression');
      }
      return statement;
    }
  }

  function nextExpression() {
    nextToken();
    if (currToken.type === 'number' || currToken.type === 'string') {
      const literal = {
        type: 'Literal',
        value: eval(currToken.value)
      }

      stash();
      nextToken();
      if (currToken.type === 'operator') {
        commit();
        return {
          type: 'BinaryExpression',
          left: literal,
          right: nextExpression()
        }
      }
      rewind();
      return literal;
    }

    if (currToken.type === 'identifier') {
      const identifier = {
        type: 'Identifier',
        name: currToken.value
      }

      stash();
      nextToken();
      if (currToken.type === 'parens' && currToken.value === '(') {
        const expr = {
          type: 'CallExpression',
          caller: identifier,
          arguments: []
        }

        stash();
        nextToken();
        if (currToken.type === 'parens' && currToken.value === '') {
          commit();
        } else {
          rewind();
          while (i < tokens.length) {
            expr.arguments.push(nextExpression());
            nextToken();
            if (currToken.type === 'parens' && currToken.value === ')') {
              break;
            }
            if (currToken.type !== 'comma' && currToken.value !== ',') {
              throw new Error('Expected , between arguments');
            }
          }
        }
        commit();
        return expr;
      }

      rewind();
      return identifier;
    }
  }

  while (i < tokens.length) {
    const statement = nextStatement();
    if (!statement) break;

    ast.body.push(statement);
  }

  return ast;
}

const ast = parser([
    {
      type: 'whitespace',
      value: '\n'
    }, {
      type: 'identifier',
      value: 'if'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'parens',
      value: '('
    }, {
      type: 'number',
      value: '1'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'operator',
      value: '>'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'number',
      value: '0'
    }, {
      type: 'parens',
      value: ')'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'brace',
      value: '{'
    }, {
      type: 'whitespace',
      value: '\n  '
    }, {
      type: 'identifier',
      value: 'alert'
    }, {
      type: 'parens',
      value: '('
    }, {
      type: 'string',
      value: '"if 1 > 0"'
    }, {
      type: 'parens',
      value: ')'
    }, {
      type: 'sep',
      value: ';'
    }, {
      type: 'whitespace',
      value: '\n'
    }, {
      type: 'brace',
      value: '}'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'identifier',
      value: 'else'
    }, {
      type: 'whitespace',
      value: ' '
    }, {
      type: 'brace',
      value: '{'
    }, {
      type: 'whitespace',
      value: '\n  '
    }, {
      type: 'identifier',
      value: 'alert'
    }, {
      type: 'parens',
      value: '('
    }, {
      type: 'string',
      value: "'XXX'"
    }, {
      type: 'parens',
      value: ')'
    }, {
      type: 'sep',
      value: ';'
    }, {
      type: 'whitespace',
      value: '\n'
    }, {
      type: 'brace',
      value: '}'
    }, {
      type: 'whitespace',
      value: '\n'
    }
]);

console.log(JSON.stringify(ast));