5081139836 2010-11-09 kinaba: /** 4198578702 2010-11-07 kinaba: * Authors: k.inaba 4198578702 2010-11-07 kinaba: * License: NYSL 0.9982 http://www.kmonos.net/nysl/ 4198578702 2010-11-07 kinaba: * 4198578702 2010-11-07 kinaba: * Parser for Polemy programming language 423f308350 2010-11-07 kinaba: */ 4198578702 2010-11-07 kinaba: module polemy.parse; 4198578702 2010-11-07 kinaba: import polemy._common; 423f308350 2010-11-07 kinaba: import polemy.lex; 423f308350 2010-11-07 kinaba: import polemy.ast; 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: /// Exception from this module 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: class ParseException : Exception 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: const LexPosition pos; b985f3bf91 2010-11-08 kinaba: d78d700f7a 2010-11-09 kinaba: this( const LexPosition pos, string msg, string file=null, size_t line=0, Throwable next=null ) 7de80acfb8 2010-11-09 kinaba: { super(sprintf!"[%s] %s"(pos, msg), file, line, next); this.pos = pos; } 423f308350 2010-11-07 kinaba: } b985f3bf91 2010-11-08 kinaba: b985f3bf91 2010-11-08 kinaba: private auto createException(Lexer)(Lexer lex, string msg) b985f3bf91 2010-11-08 kinaba: { return new ParseException(lex.empty?null:lex.front.pos, msg); } b985f3bf91 2010-11-08 kinaba: 8de5b49cdf 2010-11-09 kinaba: /// Entry points of this module b985f3bf91 2010-11-08 kinaba: b985f3bf91 2010-11-08 kinaba: auto parseString(S, T...)(S str, T fn_ln_cn) b985f3bf91 2010-11-08 kinaba: { return parserFromString(str, fn_ln_cn).parse(); } b985f3bf91 2010-11-08 kinaba: 7de80acfb8 2010-11-09 kinaba: auto parseFile(S, T...)(S filename, T ln_cn) d78d700f7a 2010-11-09 kinaba: { return parserFromFile(filename, ln_cn).parse(); } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: /// Named Constructor of Parser 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: private auto parserFromLexer(Lexer)(Lexer lex) b985f3bf91 2010-11-08 kinaba: { return new Parser!Lexer(lex); } 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: private auto parserFromString(T...)(T params) b985f3bf91 2010-11-08 kinaba: { return parserFromLexer(polemy.lex.lexerFromString(params)); } 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: private auto parserFromFile(T...)(T params) b985f3bf91 2010-11-08 kinaba: { return parserFromLexer(polemy.lex.lexerFromFile(params)); } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: /// Parser 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: private class Parser(Lexer) b985f3bf91 2010-11-08 kinaba: if( isForwardRange!(Lexer) && is(ElementType!(Lexer) == Token) ) 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: AST parse() 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: auto e = Body(); b985f3bf91 2010-11-08 kinaba: if( !lex.empty ) b985f3bf91 2010-11-08 kinaba: throw createException(lex, "input is not ended but parser came to the end"); b985f3bf91 2010-11-08 kinaba: return e; 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: AST Body() 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: if( lex.empty || !lex.front.quoted && lex.front.str=="}" ) b985f3bf91 2010-11-08 kinaba: return doNothingExpression(); 5d4cb856d8 2010-11-07 kinaba: 5d4cb856d8 2010-11-07 kinaba: auto pos = lex.front.pos; aa770610d3 2010-11-08 kinaba: string kwd = lex.front.str; aa770610d3 2010-11-08 kinaba: if( tryEat("let") || tryEat("var") || tryEat("def") || tryEat("@") ) 5d4cb856d8 2010-11-07 kinaba: { aa770610d3 2010-11-08 kinaba: if( kwd == "@" ) aa770610d3 2010-11-08 kinaba: kwd ~= eatId("after @"); b985f3bf91 2010-11-08 kinaba: immutable LexPosition varpos = (lex.empty ? null : lex.front.pos); aa770610d3 2010-11-08 kinaba: string var = eatId("after "~kwd); aa770610d3 2010-11-08 kinaba: eat("=", "after "~kwd); aa770610d3 2010-11-08 kinaba: kwd = (kwd[0]=='@' ? kwd : "@val"); b985f3bf91 2010-11-08 kinaba: auto e = E(0); b985f3bf91 2010-11-08 kinaba: if( tryEat(";") && !lex.empty && (lex.front.quoted || (lex.front.str!="}" && lex.front.str!=")")) ) aa770610d3 2010-11-08 kinaba: return new LetExpression(pos, var, kwd, e, Body()); b985f3bf91 2010-11-08 kinaba: else aa770610d3 2010-11-08 kinaba: return new LetExpression(pos, var, kwd, e, new VarExpression(varpos, var)); 5d4cb856d8 2010-11-07 kinaba: } 5d4cb856d8 2010-11-07 kinaba: else 5d4cb856d8 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: auto e = E(0); b985f3bf91 2010-11-08 kinaba: if( tryEat(";") && !lex.empty && (lex.front.quoted || (lex.front.str!="}" && lex.front.str!=")")) ) aa770610d3 2010-11-08 kinaba: return new LetExpression(pos, "_", "@val", e, Body()); b985f3bf91 2010-11-08 kinaba: else b985f3bf91 2010-11-08 kinaba: return e; 5d4cb856d8 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: // [TODO] make customizable from program 5d4cb856d8 2010-11-07 kinaba: static immutable string[][] operator_perferences = [ b985f3bf91 2010-11-08 kinaba: ["||"], b985f3bf91 2010-11-08 kinaba: ["&&"], 5d4cb856d8 2010-11-07 kinaba: ["!="], 5d4cb856d8 2010-11-07 kinaba: ["=="], 5d4cb856d8 2010-11-07 kinaba: ["<","<=",">",">="], 5d4cb856d8 2010-11-07 kinaba: ["|"], 5d4cb856d8 2010-11-07 kinaba: ["^"], 5d4cb856d8 2010-11-07 kinaba: ["&"], 5d4cb856d8 2010-11-07 kinaba: ["<<", ">>"], 5d4cb856d8 2010-11-07 kinaba: ["+","-"], b985f3bf91 2010-11-08 kinaba: ["~"], b985f3bf91 2010-11-08 kinaba: ["*","/","%"], b985f3bf91 2010-11-08 kinaba: ["^^"] 5d4cb856d8 2010-11-07 kinaba: ]; 5d4cb856d8 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: AST E(int level) 423f308350 2010-11-07 kinaba: { 5d4cb856d8 2010-11-07 kinaba: if( operator_perferences.length <= level ) b985f3bf91 2010-11-08 kinaba: return Funcall(); 423f308350 2010-11-07 kinaba: else 423f308350 2010-11-07 kinaba: { 5d4cb856d8 2010-11-07 kinaba: auto ops = operator_perferences[level]; b985f3bf91 2010-11-08 kinaba: auto e = E(level+1); 5d4cb856d8 2010-11-07 kinaba: seq: 5d4cb856d8 2010-11-07 kinaba: while( !lex.empty ) 5d4cb856d8 2010-11-07 kinaba: { 5d4cb856d8 2010-11-07 kinaba: auto pos = lex.front.pos; 5d4cb856d8 2010-11-07 kinaba: foreach(op; ops) 5d4cb856d8 2010-11-07 kinaba: if( tryEat(op) ) 5d4cb856d8 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, E(level+1)); 5d4cb856d8 2010-11-07 kinaba: continue seq; 5d4cb856d8 2010-11-07 kinaba: } 5d4cb856d8 2010-11-07 kinaba: break; 5d4cb856d8 2010-11-07 kinaba: } 5d4cb856d8 2010-11-07 kinaba: return e; 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: AST Funcall() 3f5dc76a75 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: auto e = BaseExpression(); b985f3bf91 2010-11-08 kinaba: while( tryEat("(") ) 3f5dc76a75 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: AST[] args; 3f5dc76a75 2010-11-07 kinaba: while( !tryEat(")") ) { b985f3bf91 2010-11-08 kinaba: if( lex.empty ) b985f3bf91 2010-11-08 kinaba: throw createException(lex,"Unexpected EOF"); b985f3bf91 2010-11-08 kinaba: args ~= E(0); 3f5dc76a75 2010-11-07 kinaba: if( !tryEat(",") ) { 3f5dc76a75 2010-11-07 kinaba: eat(")", "after function parameters"); 3f5dc76a75 2010-11-07 kinaba: break; 3f5dc76a75 2010-11-07 kinaba: } 3f5dc76a75 2010-11-07 kinaba: } b985f3bf91 2010-11-08 kinaba: e = new FuncallExpression(e.pos, e, args); 3f5dc76a75 2010-11-07 kinaba: } 3f5dc76a75 2010-11-07 kinaba: return e; 3f5dc76a75 2010-11-07 kinaba: } 3f5dc76a75 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: AST BaseExpression() 423f308350 2010-11-07 kinaba: { 423f308350 2010-11-07 kinaba: if( lex.empty ) b985f3bf91 2010-11-08 kinaba: throw createException(lex, "Reached EOF when tried to parse an expression"); 423f308350 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: auto pos = lex.front.pos; 8d297342aa 2010-11-08 kinaba: if( lex.front.quoted ) 423f308350 2010-11-07 kinaba: { 423f308350 2010-11-07 kinaba: scope(exit) lex.popFront; b985f3bf91 2010-11-08 kinaba: return new StrLiteral(pos, lex.front.str); 423f308350 2010-11-07 kinaba: } b985f3bf91 2010-11-08 kinaba: if( isNumber(lex.front.str) ) 423f308350 2010-11-07 kinaba: { 423f308350 2010-11-07 kinaba: scope(exit) lex.popFront; b985f3bf91 2010-11-08 kinaba: return new IntLiteral(pos, BigInt(cast(string)lex.front.str)); 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: if( tryEat("(") ) 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: auto e = Body(); 423f308350 2010-11-07 kinaba: eat(")", "after parenthesized expression"); 423f308350 2010-11-07 kinaba: return e; 3f5dc76a75 2010-11-07 kinaba: } 633e700889 2010-11-07 kinaba: if( tryEat("if") ) 633e700889 2010-11-07 kinaba: { 633e700889 2010-11-07 kinaba: eat("(", "after if"); b985f3bf91 2010-11-08 kinaba: auto cond = E(0); 633e700889 2010-11-07 kinaba: eat(")", "after if condition"); 633e700889 2010-11-07 kinaba: auto thenPos = lex.front.pos; 633e700889 2010-11-07 kinaba: eat("{", "after if condition"); b985f3bf91 2010-11-08 kinaba: auto th = Body(); 633e700889 2010-11-07 kinaba: eat("}", "after if-then body"); b985f3bf91 2010-11-08 kinaba: auto el = doNothingExpression(); b985f3bf91 2010-11-08 kinaba: auto elsePos = (lex.empty ? LexPosition.dummy : lex.front.pos); 633e700889 2010-11-07 kinaba: if( tryEat("else") ) { 633e700889 2010-11-07 kinaba: eat("{", "after else"); b985f3bf91 2010-11-08 kinaba: el = Body(); 633e700889 2010-11-07 kinaba: eat("}", "after else body"); 633e700889 2010-11-07 kinaba: } 633e700889 2010-11-07 kinaba: return new FuncallExpression(pos, 633e700889 2010-11-07 kinaba: new VarExpression(pos, "if"), 633e700889 2010-11-07 kinaba: cond, b985f3bf91 2010-11-08 kinaba: new FunLiteral(thenPos, [], th), b985f3bf91 2010-11-08 kinaba: new FunLiteral(elsePos, [], el) 633e700889 2010-11-07 kinaba: ); 633e700889 2010-11-07 kinaba: } 5081139836 2010-11-09 kinaba: if( tryEat("fun") || tryEat("ă") ) 3f5dc76a75 2010-11-07 kinaba: { 3f5dc76a75 2010-11-07 kinaba: eat("(", "after fun"); 3f5dc76a75 2010-11-07 kinaba: string[] params; b985f3bf91 2010-11-08 kinaba: while( !tryEat(")") ) 3f5dc76a75 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: params ~= eatId("for function parameter"); 3f5dc76a75 2010-11-07 kinaba: if( !tryEat(",") ) { 3f5dc76a75 2010-11-07 kinaba: eat(")", "after function parameters"); 3f5dc76a75 2010-11-07 kinaba: break; 3f5dc76a75 2010-11-07 kinaba: } 3f5dc76a75 2010-11-07 kinaba: } 3f5dc76a75 2010-11-07 kinaba: eat("{", "after function parameters"); b985f3bf91 2010-11-08 kinaba: auto funbody = Body(); b985f3bf91 2010-11-08 kinaba: eat("}", "after function body"); b985f3bf91 2010-11-08 kinaba: return new FunLiteral(pos, params, funbody); 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: scope(exit) lex.popFront; 423f308350 2010-11-07 kinaba: return new VarExpression(pos, lex.front.str); 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: private: 423f308350 2010-11-07 kinaba: Lexer lex; b985f3bf91 2010-11-08 kinaba: this(Lexer lex) { this.lex = lex; } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: void eat(string kwd, lazy string msg) 423f308350 2010-11-07 kinaba: { 423f308350 2010-11-07 kinaba: if( !tryEat(kwd) ) b985f3bf91 2010-11-08 kinaba: throw createException(lex, "'"~kwd~"' is expected "~msg~" but '" 423f308350 2010-11-07 kinaba: ~(lex.empty ? "EOF" : lex.front.str)~"' occured"); 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: bool tryEat(string kwd) 423f308350 2010-11-07 kinaba: { 8d297342aa 2010-11-08 kinaba: if( lex.empty || lex.front.quoted || lex.front.str!=kwd ) 423f308350 2010-11-07 kinaba: return false; 423f308350 2010-11-07 kinaba: lex.popFront; 423f308350 2010-11-07 kinaba: return true; 8d297342aa 2010-11-08 kinaba: } 8d297342aa 2010-11-08 kinaba: b985f3bf91 2010-11-08 kinaba: string eatId(lazy string msg) b985f3bf91 2010-11-08 kinaba: { b985f3bf91 2010-11-08 kinaba: if( lex.empty || lex.front.quoted ) b985f3bf91 2010-11-08 kinaba: throw createException(lex, "identifier is expected but not found "~msg); b985f3bf91 2010-11-08 kinaba: string id = lex.front.str; b985f3bf91 2010-11-08 kinaba: lex.popFront; b985f3bf91 2010-11-08 kinaba: return id; b985f3bf91 2010-11-08 kinaba: } b985f3bf91 2010-11-08 kinaba: 8d297342aa 2010-11-08 kinaba: bool isNumber(string s) 8d297342aa 2010-11-08 kinaba: { 8d297342aa 2010-11-08 kinaba: return find!(`a<'0'||'9'<a`)(s).empty; 8d297342aa 2010-11-08 kinaba: } 8d297342aa 2010-11-08 kinaba: b985f3bf91 2010-11-08 kinaba: AST doNothingExpression() b985f3bf91 2010-11-08 kinaba: { b985f3bf91 2010-11-08 kinaba: return new IntLiteral(lex.empty?null:lex.front.pos, BigInt(178)); b985f3bf91 2010-11-08 kinaba: } 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: unittest 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: mixin EasyAST; b985f3bf91 2010-11-08 kinaba: b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`123`), intl(123)); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`"foo"`), strl("foo")); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`fun(){1}`), fun([],intl(1))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`fun(x){1}`), fun(["x"],intl(1))); 5081139836 2010-11-09 kinaba: assert_eq(parseString(`ă(){1}`), fun([],intl(1))); 5081139836 2010-11-09 kinaba: assert_eq(parseString(`ă(x){1}`), fun(["x"],intl(1))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`1;2`), let("_","@val",intl(1),intl(2))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`1;2;`), let("_","@val",intl(1),intl(2))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`let x=1;2`), let("x","@val",intl(1),intl(2))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`var x=1;2;`), let("x","@val",intl(1),intl(2))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`def x=1`), let("x","@val",intl(1),var("x"))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`@val x=1;`), let("x","@val",intl(1),var("x"))); aa770610d3 2010-11-08 kinaba: assert_eq(parseString(`@typ x="#int";`), let("x","@typ",strl("#int"),var("x"))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`f(1,2)`), call(var("f"),intl(1),intl(2))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`if(1){2}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(178)))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`if(1){2}else{3}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(3)))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`if(1){}else{3}()()`), b985f3bf91 2010-11-08 kinaba: call(call(call(var("if"),intl(1),fun([],intl(178)),fun([],intl(3)))))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`1+2*3`), call(var("+"),intl(1),call(var("*"),intl(2),intl(3)))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`(1+2)*3`), call(var("*"),call(var("+"),intl(1),intl(2)),intl(3))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`1*(2+3)`), call(var("*"),intl(1),call(var("+"),intl(2),intl(3)))); b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(`1*2+3`), call(var("+"),call(var("*"),intl(1),intl(2)),intl(3))); 3f5dc76a75 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(` aa770610d3 2010-11-08 kinaba: let x = 100; #comment aa770610d3 2010-11-08 kinaba: let y = 200; #comment!!!!! b985f3bf91 2010-11-08 kinaba: x+y b985f3bf91 2010-11-08 kinaba: `), aa770610d3 2010-11-08 kinaba: let("x", "@val", intl(100), let("y", "@val", intl(200), call(var("+"), var("x"), var("y")))) b985f3bf91 2010-11-08 kinaba: ); 3f5dc76a75 2010-11-07 kinaba: b985f3bf91 2010-11-08 kinaba: assert_eq(parseString(` b985f3bf91 2010-11-08 kinaba: var fac = fun(x){ if(x <= 1) {1} else {x*fac(x-1)} }; b985f3bf91 2010-11-08 kinaba: fac(10) b985f3bf91 2010-11-08 kinaba: `), aa770610d3 2010-11-08 kinaba: let("fac", "@val", fun(["x"], b985f3bf91 2010-11-08 kinaba: call(var("if"), b985f3bf91 2010-11-08 kinaba: call(var("<="), var("x"), intl(1)), b985f3bf91 2010-11-08 kinaba: fun([], intl(1)), b985f3bf91 2010-11-08 kinaba: fun([], call(var("*"), var("x"), call(var("fac"),call(var("-"),var("x"),intl(1))))) b985f3bf91 2010-11-08 kinaba: )), b985f3bf91 2010-11-08 kinaba: call(var("fac"),intl(10)) b985f3bf91 2010-11-08 kinaba: ) b985f3bf91 2010-11-08 kinaba: ); 423f308350 2010-11-07 kinaba: } 423f308350 2010-11-07 kinaba: 423f308350 2010-11-07 kinaba: unittest 423f308350 2010-11-07 kinaba: { b985f3bf91 2010-11-08 kinaba: assert_throw!ParseException(parseString(`1+`)); b985f3bf91 2010-11-08 kinaba: assert_throw!ParseException(parseString(`1+2}`)); aa770610d3 2010-11-08 kinaba: assert_throw!ParseException(parseString(`let "x"`)); b985f3bf91 2010-11-08 kinaba: assert_throw!ParseException(parseString(`var`)); aa770610d3 2010-11-08 kinaba: assert_throw!ParseException(parseString(`@val x ==`)); b985f3bf91 2010-11-08 kinaba: assert_throw!ParseException(parseString(`if(){1}`)); b985f3bf91 2010-11-08 kinaba: assert_throw!ParseException(parseString(`f(`)); 423f308350 2010-11-07 kinaba: }