import { previewable , PreviewableIterable } from 'previewable-iterator' ; import { match } from '../util' ; import * as t from '../lexer/token' ; import { Node , NodeConstructor , Literal , IntLit , FloatLit , StrLit , BoolLit , CharLit , Module , Import , Ident , Decl , ImportElem , Type , SimpleType , IntType , FloatType , StrType , BoolType , CharType , VoidType , Expr , LitExpr , ArrayType , TupleType , FuncType , PrimUnaryExpr , UnaryOp , PrimExpr , UnaryExpr , IdentExpr , TupleExpr , ArrayExpr , FuncExpr , Param , Block , BinaryOp , BinaryExpr , EqOp , CompOp , AddOp , MulOp , BoolOp , CallExpr , IndexExpr , CondExpr , LoopExpr , Assign , LVal , NewExpr , Break , } from './ast' ; import { ParseError } from './error' ; type ParserInput = PreviewableIterable < t . Token < any > > ; type Parser < T > = ( input : ParserInput ) => T ; export function parse ( tokens ) { const input = previewable ( tokens ) ; return parseModule ( input ) ; } function nextToken ( input , consume = false ) { if ( ! input . preview ( ) . value ) { throw new ParseError ( - 1 , - 1 , { name : 'end of token stream' } ) ; } return consume ? input . next ( ) . value : input . preview ( ) . value ; } function parseNode < T , N extends Node < T > > ( Cons , parser ) { return ( input ) => { const { row , column } = nextToken ( input ) ; return new Cons ( parser ( input ) , row , column ) ; } ; } function consume < Tk extends t . Token < any > > ( input , TokenCon , rep ? ) { const token = nextToken ( input , true ) ; if ( token . is ( TokenCon , rep ) ) { return token ; } throw new ParseError ( token . row , token . column , { name : token . constructor . name , rep : token . rep } , { name : TokenCon . name , rep : rep as any } ) ; } function manyWhile < T > ( input , parser , whilst ) { const results = [ ] ; while ( whilst ( nextToken ( input ) ) ) { results . push ( parser ( input ) ) ; } return results ; } function commaSeparated < T > ( input , parser ) { return [ parser ( input ) ] . concat ( manyWhile ( input , input => consume ( input , t . Punctuation , ',' ) && parser ( input ) , token => token . is ( t . Punctuation , ',' ) ) ) ; } const parseModule = parseNode ( Module , input => { const imports = manyWhile ( input , parseImport , token => token . is ( t . Keyword , 'import' ) ) ; const decls = manyWhile ( input , parseDecl , token => token . is ( t . Keyword , 'let' ) ) ; consume ( input , t . EOF ) ; return { imports , decls } ; } ) ; const parseImport = parseNode ( Import , input => { consume ( input , t . Keyword , 'import' ) ; const path = StrLit . from ( consume ( input , t . StrLit ) as t . StrLit ) ; consume ( input , t . Punctuation , '(' ) ; const elems = commaSeparated ( input , input => { const name = parseIdent ( input ) ; let as_ = null ; if ( nextToken ( input ) . is ( t . Keyword , 'as' ) ) { consume ( input , t . Keyword , 'as' ) ; as_ = parseIdent ( input ) ; } return { name , as : as_ } ; } ) ; consume ( input , t . Punctuation , ')' ) ; return { path , elems } ; } ) ; const parseIdent = parseNode ( Ident , input => consume ( input , t . Ident ) . rep ) ; const parseDecl = parseNode ( Decl , input => { consume ( input , t . Keyword , 'let' ) ; const name = parseIdent ( input ) ; let type_ = null ; if ( nextToken ( input ) . is ( t . Punctuation , ':' ) ) { consume ( input , t . Punctuation , ':' ) ; type_ = parseType ( input ) ; } consume ( input , t . Punctuation , '=' ) ; const expr = parseExpr ( input ) ; return { name , type : type_ , expr } ; } ) ; function parseType ( input ) { let type_ ; const token = nextToken ( input ) ; if ( token . is ( t . Punctuation , '[' ) ) { type_ = parseArrayType ( input ) ; } else if ( token . is ( t . Punctuation , '(' ) ) { type_ = parseTupleType ( input ) ; } else if ( token . is ( t . Ident ) ) { type_ = parseSimpleType ( input ) ; } else { throw new ParseError ( token . row , token . column , { name : token . constructor . name , rep : token . rep , } , { name : 'Type' , } ) ; } if ( nextToken ( input ) . is ( t . Punctuation , '->' ) ) { return parseFuncType ( input , type_ ) ; } else { return type_ ; } } const parseArrayType = parseNode ( ArrayType , input => { consume ( input , t . Punctuation , '[' ) ; const elementType = parseType ( input ) ; consume ( input , t . Punctuation , ']' ) ; return elementType ; } ) ; const parseTupleType = parseNode ( TupleType , input => { consume ( input , t . Punctuation , '(' ) ; let items = [ ] ; if ( ! nextToken ( input ) . is ( t . Punctuation , ')' ) ) { items = commaSeparated ( input , parseType ) ; } consume ( input , t . Punctuation , ')' ) ; return { size : items . length , items } ; } ) ; function parseFuncType ( input , lho ) { consume ( input , t . Punctuation , '->' ) ; return new FuncType ( { param : lho , return : parseType ( input ) , } , lho . row , lho . column ) ; } function parseSimpleType ( input ) { const ident = consume ( input , t . Ident ) ; return match ( ident . rep , [ [ 'int' , ( ) => new IntType ( null , ident . row , ident . column ) ] , [ 'float' , ( ) => new FloatType ( null , ident . row , ident . column ) ] , [ 'str' , ( ) => new StrType ( null , ident . row , ident . column ) ] , [ 'bool' , ( ) => new BoolType ( null , ident . row , ident . column ) ] , [ 'char' , ( ) => new CharType ( null , ident . row , ident . column ) ] , [ 'void' , ( ) => new VoidType ( null , ident . row , ident . column ) ] , ] , ( ) => { throw new ParseError ( ident . row , ident . column , { name : 'unknown type' , rep : ident . rep , } ) ; } ) ; } function parseLiteral ( input ) { const token = nextToken ( input , true ) ; return match < t . Literal < any > , Literal < any > > ( token , [ [ token => token . is ( t . IntLit ) , ( ) => IntLit . from ( token ) ] , [ token => token . is ( t . FloatLit ) , ( ) => FloatLit . from ( token ) ] , [ token => token . is ( t . StrLit ) , ( ) => StrLit . from ( token ) ] , [ token => token . is ( t . BoolLit ) , ( ) => BoolLit . from ( token ) ] , [ token => token . is ( t . CharLit ) , ( ) => CharLit . from ( token ) ] , ] , ( ) => { throw new ParseError ( token . row , token . column , { name : token . constructor . name , rep : token . rep , } , { name : 'Literal' , } ) ; } ) ; } function parseExpr ( input , precedence = - 1 ) { let left = parsePrimUnaryExpr ( input ) ; while ( BinaryOp . isBinaryOp ( nextToken ( input ) ) && tokenToBinaryOp ( nextToken ( input ) ) . precedence > precedence ) { left = parseBinaryExpr ( input , left , precedence ) ; } return left ; } function parsePrimUnaryExpr ( input ) { const next = nextToken ( input ) ; if ( UnaryOp . isUnaryOp ( next ) ) { return parseUnaryExpr ( input ) ; } else { return parsePrimExpr ( input ) ; } } function parseBinaryExpr ( input , left , precedence = - 1 ) { const op = parseBinaryOp ( input ) ; const right = parseExpr ( input , op . precedence ) ; return new BinaryExpr ( { op , left , right } , left . row , left . column ) ; } function parseBinaryOp ( input ) { const op = consume ( input , t . Operator ) ; return tokenToBinaryOp ( op ) ; } function tokenToBinaryOp ( op ) { switch ( op . rep ) { case '==' : case '!=' : return new EqOp ( op . rep , op . row , op . column ) ; case '<' : case '<=' : case '>' : case '>=' : return new CompOp ( op . rep , op . row , op . column ) ; case '+' : case '-' : case '|' : case '^' : return new AddOp ( op . rep , op . row , op . column ) ; case '*' : case '/' : case '%' : case '&' : return new MulOp ( op . rep , op . row , op . column ) ; case '||' : case '&&' : return new BoolOp ( op . rep , op . row , op . column ) ; default : throw new ParseError ( op . row , op . column , { name : 'non-binary operator' , rep : op . rep , } , { name : 'binary operator' , } ) ; } } const parseUnaryExpr = parseNode ( UnaryExpr , input => { const op = parseUnaryOp ( input ) ; const right = parsePrimUnaryExpr ( input ) ; return { op , right } ; } ) ; const parseUnaryOp = parseNode ( UnaryOp , input => { const op = consume ( input , t . Operator ) ; if ( op . rep === '+' || op . rep === '-' || op . rep === '!' ) { return op . rep ; } else { throw new ParseError ( op . row , op . column , { name : 'non-unary operator' , rep : op . rep , } , { name : 'unary operator' } ) ; } } ) ; function parsePrimExpr ( input ) { const token = nextToken ( input ) ; let expr = match < t . Token < any > , PrimExpr < any > > ( token , [ [ token => token instanceof t . Literal , ( ) => parseLitExpr ( input ) ] , [ token => token . is ( t . Ident ) , ( ) => parseIdentExpr ( input ) ] , [ token => token . is ( t . Punctuation , '(' ) , ( ) => parseTupleExpr ( input ) ] , [ token => token . is ( t . Punctuation , '[' ) , ( ) => parseArrayExpr ( input ) ] , [ token => token . is ( t . Keyword , 'fn' ) , ( ) => parseFuncExpr ( input ) ] , [ token => token . is ( t . Keyword , 'if' ) , ( ) => parseCondExpr ( input ) ] , [ token => token . is ( t . Keyword , 'while' ) , ( ) => parseLoopExpr ( input ) ] , [ token => token . is ( t . Keyword , 'new' ) , ( ) => parseNewExpr ( input ) ] , ] , ( ) => { throw new ParseError ( token . row , token . column , { name : token . constructor . name , rep : token . rep , } ) ; } ) ; while ( nextToken ( input ) . is ( t . Punctuation ) ) { if ( nextToken ( input ) . is ( t . Punctuation , '(' ) ) { expr = parseCallExpr ( input , expr ) ; } else if ( nextToken ( input ) . is ( t . Punctuation , '[' ) ) { expr = parseIndexExpr ( input , expr ) ; } else { break ; } } return expr ; } const parseLitExpr = parseNode ( LitExpr , parseLiteral ) ; const parseIdentExpr = parseNode ( IdentExpr , parseIdent ) ; const parseTupleExpr = parseNode ( TupleExpr , input => { consume ( input , t . Punctuation , '(' ) ; let items = [ ] ; if ( ! nextToken ( input ) . is ( t . Punctuation , ')' ) ) { items = commaSeparated ( input , parseExpr ) ; } consume ( input , t . Punctuation , ')' ) ; return { size : items . length , items } ; } ) ; const parseArrayExpr = parseNode ( ArrayExpr , input => { consume ( input , t . Punctuation , '[' ) ; let elems = [ ] ; if ( ! nextToken ( input ) . is ( t . Punctuation , ']' ) ) { elems = commaSeparated ( input , parseExpr ) ; } consume ( input , t . Punctuation , ']' ) ; return elems ; } ) ; function parseCallExpr ( input , func ) { const args = parseTupleExpr ( input ) ; return new CallExpr ( { func , args } , func . row , func . column ) ; } function parseIndexExpr ( input , target ) { consume ( input , t . Punctuation , '[' ) ; const index = parseExpr ( input ) ; consume ( input , t . Punctuation , ']' ) ; return new IndexExpr ( { target , index } , target . row , target . column ) ; } const parseFuncExpr = parseNode ( FuncExpr , input => { consume ( input , t . Keyword , 'fn' ) ; consume ( input , t . Punctuation , '(' ) ; let params = [ ] ; if ( ! nextToken ( input ) . is ( t . Punctuation , ')' ) ) { params = commaSeparated ( input , input => { const name = parseIdent ( input ) ; const type_ = parseType ( input ) ; return { name , type : type_ } ; } ) ; } consume ( input , t . Punctuation , ')' ) ; const returnType = parseType ( input ) ; const body = parseBlock ( input ) ; return { params : { size : params . length , items : params , } , returnType , body , } ; } ) ; const parseCondExpr = parseNode ( CondExpr , input => { consume ( input , t . Keyword , 'if' ) ; const if_ = parseExpr ( input ) ; const then = parseBlock ( input ) ; consume ( input , t . Keyword , 'else' ) ; const else_ = parseBlock ( input ) ; return { if : if_ , then , else : else_ } ; } ) ; const parseLoopExpr = parseNode ( LoopExpr , input => { consume ( input , t . Keyword , 'while' ) ; const while_ = parseExpr ( input ) ; const body = parseBlock ( input ) ; return { while : while_ , body } ; } ) ; const parseNewExpr = parseNode ( NewExpr , input => { consume ( input , t . Keyword , 'new' ) ; const ty = parseType ( input ) ; consume ( input , t . Punctuation , '[' ) ; const length = parseExpr ( input ) ; consume ( input , t . Punctuation , ']' ) ; return { type : ty , length } ; } ) ; const parseBlock = parseNode ( Block , input => { consume ( input , t . Punctuation , '{' ) ; let bodies = [ ] ; let returnVoid = true ; while ( ! nextToken ( input ) . is ( t . Punctuation , '}' ) ) { if ( nextToken ( input ) . is ( t . Keyword , 'let' ) ) { bodies . push ( parseDecl ( input ) ) ; } else if ( nextToken ( input ) . is ( t . Keyword , 'break' ) ) { bodies . push ( parseBreak ( input ) ) ; } else { const expr = parseExpr ( input ) ; if ( nextToken ( input ) . is ( t . Punctuation , '=' ) ) { if ( expr instanceof IdentExpr || expr instanceof IndexExpr ) { bodies . push ( parseAssign ( input , expr ) ) ; } else { throw new ParseError ( expr . row , expr . column , expr , { name : 'LVal (IdentExpr or IndexExpr)' , } ) ; } } else { bodies . push ( expr ) ; } } if ( nextToken ( input ) . is ( t . Punctuation , ';' ) ) { consume ( input , t . Punctuation , ';' ) ; returnVoid = true ; } else { returnVoid = false ; break ; } } consume ( input , t . Punctuation , '}' ) ; return { bodies , returnVoid } ; } ) ; function parseAssign ( input , lVal ) { consume ( input , t . Punctuation , '=' ) ; const expr = parseExpr ( input ) ; return new Assign ( { lVal , expr } , lVal . row , lVal . column ) ; } const parseBreak = parseNode ( Break , input => { consume ( input , t . Keyword , 'break' ) ; return null ; } ) ;