import { Expr , FunctionCallExpr , AssignExpr } from './expression' ; import { Parser } from './parser' ; import { IToken } from '../tokenizer/tokenizer' ; import { Terminal , Identifier } from './terminal' ; export class expressionParser { readonly PRIORITY_TABLE = { '+' : 60 , '-' : 60 , '*' : 70 , '/' : 70 , '>=' : 80 , '<=' : 80 , '>' : 80 , '<' : 80 , '&&' : 90 , '||' : 90 , '==' : 100 , '!=' : 100 , '(' : 1000 , ')' : 1000 } ; constructor ( private parser ) { } public exprParser ( ) { if ( this . parser . lookahead . value === ')' ) { return null ; } return this . constructAST ( this . inOrderToPostOrder ( ) ) ; } private constructAST ( postOrderOutput ) { const stack = [ ] ; for ( let i = 0 ; i < postOrderOutput . length ; i ++ ) { const current = postOrderOutput [ i ] ; if ( ( < IToken > current ) . type === 'operator' ) { const r = stack . pop ( ) ; const l = stack . pop ( ) ; const expr = new Expr ( ( < IToken > current ) . value , l , r ) ; stack . push ( expr ) ; } else { stack . push ( current ) ; } } return stack [ 0 ] ; } param { * } stack param { Lambda } prediction param { * } callback private popUntil ( stack , prediction , callback ) { let token = null ; while ( token = stack . pop ( ) ) { if ( prediction ( token ) ) { stack . push ( token ) ; break ; } callback ( token ) ; } } /**
     * 后序遍历实现表达式优先级算法：中序表达式a+b*(c+d)的转换后序表达式abcd+*+
     */ private inOrderToPostOrder ( ) { const opStack = [ ] ; const output = [ ] ; 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 ) => token . value === '(' , ( token ) => { output . push ( token ) ; } ) ; const op = 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 = 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 = opStack [ opStack . length - 1 ] ; if ( ! lastOp ) { opStack . push ( op ) ; } else { if ( this . PRIORITY_TABLE [ op . value ] <= this . PRIORITY_TABLE [ lastOp . value ] ) { this . popUntil ( opStack , ( token ) => ! token || token . value === '(' , ( token ) => { output . push ( token ) ; } ) ; } opStack . push ( op ) ; } } else { const factor = this . parser . parseFactor ( ) ; output . push ( factor ) ; if ( this . parser . lookahead . type != 'operator' || this . parser . lookahead . value === '=' ) { break ; } } } if ( opStack . length > 0 ) { while ( opStack . length > 0 ) { output . push ( opStack . pop ( ) ) ; } } return output ; } }