SOURCE

/** 
 *   [
 *     { 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: ')'        },
 *   ]
 *
 * And an Abstract Syntax Tree (AST) might look like this:
 *
 *   {
 *     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',
 *         }]
 *       }]
 *     }]
 *   }
 */

function parser(tokens){
    let current = 0
    function walk(){
        let token = tokens[current]
        if(token.type==='number'){
            current++
            return {
                type: 'NumberLiteral',
                value:token.value,
            }
        }

        if(token.type==='string'){
            current++
            return {
                type: 'StringLiteral',
                value:token.value,
            }
        }
        if(token.type==='paren' && token.value==="("){
            token = tokens[++current] //add
            const node = {
                type: 'CallExpression',
                name: token.value,
                params: []
            }

            token = tokens[++current] //num || (

            while((token.type!=="paren") || (token.type==='paren' && token.value!==")")){
                node.params.push(walk()) // current add 4
                token = tokens[current];// 递归结束,此时current往前推进，所以要重新赋值token，来继续while判断
            }
            current++
            return node
        }
    }
    const ast = {
        type:'Program',
        body:[]
    }
    
    ast.body.push(walk())
    console.log(ast)
}

const 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: ')'        },
    ]
parser(tokens)