import { Expr, FunctionCallExpr, AssignExpr } from './expression'
import { Parser } from './parser'
import { IToken } from '../tokenizer/tokenizer'
import { Terminal, Identifier } from './terminal'

//表达式parser
export class expressionParser {
 //优先级序列表
 readonly PRIORITY_TABLE = {
 '+': 60,
 '-': 60,
 '*': 70,
 '/': 70,
 '>=': 80,
 '<=': 80,
 '>': 80,
 '<': 80,
 '&&': 90,
 '||': 90,
 '==': 100,
 '!=': 100,
 '(': 1000,
 ')': 1000
 }

 constructor(private parser: Parser) { }

 //表达式解析方法
 public exprParser(): (Expr | Terminal) {
 if (this.parser.lookahead.value === ')') {
 return null
 }
 // PreOrder : 前序
 // inOrder : 中序
 // PostOrder : 后序
 return this.constructAST(this.inOrderToPostOrder())
 }

 //构建AST:abcd+*+ → ab(c+d)*+ → ab*(c+d)+ → a+b*(c+d)
 private constructAST(postOrderOutput: Array<IToken | Terminal | Expr>): (Expr | Terminal) {
 const stack = []
 for (let i = 0; i < postOrderOutput.length; i++) {
 const current: (IToken | Terminal | Expr) = postOrderOutput[i]
 if ((<IToken>current).type === 'operator') {
 const r: (Terminal | Expr) = stack.pop()
 const l: Identifier = stack.pop()
 const expr: Expr = new Expr((<IToken>current).value, l, r)
 stack.push(expr)
 } else {
 stack.push(current)
 }
 }
 return stack[0]
 }

 /**
 * 帮助Pop Stack直到Prediction满足
 * @param {*} stack 
 * @param {Lambda} prediction 
 * @param {*} callback 
 */
 private popUntil(stack: Array<IToken>, prediction: (token?: IToken) => boolean, callback: (token?: IToken) => void): void {
 let token: IToken = null
 while (token = stack.pop()) {
 if (prediction(token)) {
 stack.push(token)
 break
 }
 callback(token)
 }
 }

 /**
 * 后序遍历实现表达式优先级算法:中序表达式a+b*(c+d)的转换后序表达式abcd+*+
 */
 private inOrderToPostOrder(): Array<IToken | Terminal | Expr> {
 const opStack: Array<IToken> = []
 const output: Array<IToken | Terminal | Expr> = []
 while (this.parser.lookahead.value != 'eof' && this.parser.lookahead.value !== '}') {
 if (this.parser.lookahead.value === '(') {
 opStack.push(this.parser.lookahead)
 this.parser.match('(')
 } else if (this.parser.lookahead.value === ')') {
 this.popUntil(opStack, (token: IToken) => token.value === '(', (token: IToken) => {
 output.push(token)
 })
 const op: IToken = opStack.pop()
 // 遇到没有左括号匹配的情况意味着需要停止处理
 if (!op || op.value !== '(') {
 break
 }
 this.parser.match(')')
 if (this.parser.lookahead.type != 'operator') {
 break
 }
 } else if (this.parser.lookahead.type === 'operator') {
 const op: IToken = this.parser.lookahead
 if (!(op.value in this.PRIORITY_TABLE)) {
 throw `An operator expected in @line ${this.parser.lookahead.lineNo} but ${this.parser.lookahead.value} found`
 }
 this.parser.match(op.value)
 const lastOp: IToken = opStack[opStack.length - 1]
 if (!lastOp) { // opStack是空的
 opStack.push(op)
 } else {
 if (this.PRIORITY_TABLE[op.value] <= this.PRIORITY_TABLE[lastOp.value]) {
 this.popUntil(opStack, (token: IToken) => !token || token.value === '(', (token: IToken) => {
 output.push(token)
 })
 }
 opStack.push(op)
 }
 } else {
 const factor: (Terminal | Expr) = this.parser.parseFactor()
 output.push(factor)
 if (this.parser.lookahead.type != 'operator' || this.parser.lookahead.value === '=') {
 break
 }
 }
 }
 //op栈出栈存入结果栈中
 if (opStack.length > 0) {
 while (opStack.length > 0) {
 output.push(opStack.pop())
 }
 }
 return output
 }
}