4198578702 2010-11-07        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: import std.bigint;
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: /// Parsing Failure
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: class ParserException : Exception
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: private:
423f308350 2010-11-07        kinaba: 	this(string msg) { super(msg); }
423f308350 2010-11-07        kinaba: 	static ParserException create(Lexer)(Lexer lex, string msg)
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		return new ParserException(sprintf!"[%s] %s"(
423f308350 2010-11-07        kinaba: 			lex.empty ? "EOF" : to!string(lex.front.pos), msg));
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: /// Named Constructor of Parser
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: auto parserFromLexer(Lexer)(Lexer lex)
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	return new Parser!Lexer(lex);
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: /// Named Constructor of Parser (just fwd to lexerFromString)
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: auto parserFromString(T...)(T params)
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	return parserFromLexer(polemy.lex.lexerFromString(params));
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: /// Named Constructor of Parser (just fwd to lexerFromFile)
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: auto parserFromFile(T...)(T params)
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	return parserFromLexer(polemy.lex.lexerFromFile(params));
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: /// Parser
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: class Parser(Lexer)
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	this(Lexer lex)
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		this.lex = lex;
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	Program parseProgram()
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		Program p;
423f308350 2010-11-07        kinaba: 		while( !lex.empty )
423f308350 2010-11-07        kinaba: 			p ~= parseStatement();
423f308350 2010-11-07        kinaba: 		return p;
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	Statement parseStatement()
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		auto saved = lex.save;
423f308350 2010-11-07        kinaba: 		scope(failure) lex = saved;
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 		if( lex.empty )
423f308350 2010-11-07        kinaba: 			throw new ParserException("EOF during parsing a statement");
423f308350 2010-11-07        kinaba: 		auto pos = lex.front.pos;
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 		if( lex.front.kind==Token.Kind.identifier && lex.front.str=="var" )
423f308350 2010-11-07        kinaba: 		{
423f308350 2010-11-07        kinaba: 			// "var" Var "=" Expression ";"
423f308350 2010-11-07        kinaba: 			lex.popFront;
423f308350 2010-11-07        kinaba: 			string var = lex.front.str;
423f308350 2010-11-07        kinaba: 			lex.popFront;
423f308350 2010-11-07        kinaba: 			eat("=", "for variable declaration");
423f308350 2010-11-07        kinaba: 			auto parsed = new DeclStatement(pos, var, parseExpression());
423f308350 2010-11-07        kinaba: 			eat(";", "after variable declaration");
423f308350 2010-11-07        kinaba: 			return parsed;
423f308350 2010-11-07        kinaba: 		}
423f308350 2010-11-07        kinaba: 		else
423f308350 2010-11-07        kinaba: 		{
423f308350 2010-11-07        kinaba: 			// Expression ";"
423f308350 2010-11-07        kinaba: 			auto parsed = new ExprStatement(pos, parseExpression());
423f308350 2010-11-07        kinaba: 			eat(";", "after statement");
423f308350 2010-11-07        kinaba: 			return parsed;
423f308350 2010-11-07        kinaba: 		}
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	Expression parseExpression()
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		auto saved = lex.save;
423f308350 2010-11-07        kinaba: 		scope(failure) lex = saved;
5d4cb856d8 2010-11-07        kinaba: 		return parseE(0);
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: 
5d4cb856d8 2010-11-07        kinaba: 	// [TODO] multi-char operators are not supported by the lexer...
5d4cb856d8 2010-11-07        kinaba: 	static immutable string[][] operator_perferences = [
3f5dc76a75 2010-11-07        kinaba: 		["="],
5d4cb856d8 2010-11-07        kinaba: 		["or"],
5d4cb856d8 2010-11-07        kinaba: 		["and"],
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: 		["+","-"],
5d4cb856d8 2010-11-07        kinaba: 		["*","/","%"]
5d4cb856d8 2010-11-07        kinaba: 	];
423f308350 2010-11-07        kinaba: 
5d4cb856d8 2010-11-07        kinaba: 	Expression parseE(int level = 0)
423f308350 2010-11-07        kinaba: 	{
5d4cb856d8 2010-11-07        kinaba: 		if( operator_perferences.length <= level )
5d4cb856d8 2010-11-07        kinaba: 			return parseBaseExpression();
5d4cb856d8 2010-11-07        kinaba: 		else
423f308350 2010-11-07        kinaba: 		{
5d4cb856d8 2010-11-07        kinaba: 			auto ops = operator_perferences[level];
5d4cb856d8 2010-11-07        kinaba: 			auto e = parseE(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: 					{
5d4cb856d8 2010-11-07        kinaba: 						if( op == "=" ) // right assoc
5d4cb856d8 2010-11-07        kinaba: 							return new AssignExpression(e.pos, e, parseE(level));
5d4cb856d8 2010-11-07        kinaba: 						else
5d4cb856d8 2010-11-07        kinaba: 							e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, parseE(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: 
5d4cb856d8 2010-11-07        kinaba: 	Expression parseBaseExpression()
423f308350 2010-11-07        kinaba: 	{
5d4cb856d8 2010-11-07        kinaba: 		if( lex.empty )
5d4cb856d8 2010-11-07        kinaba: 			throw new ParserException("EOF during parsing an expression");
5d4cb856d8 2010-11-07        kinaba: 		auto pos = lex.front.pos;
3f5dc76a75 2010-11-07        kinaba: 		Expression e = parseBaseBaseExpression();
3f5dc76a75 2010-11-07        kinaba: 		while( tryEat("(") ) // funcall
3f5dc76a75 2010-11-07        kinaba: 		{
3f5dc76a75 2010-11-07        kinaba: 			Expression[] args;
3f5dc76a75 2010-11-07        kinaba: 			while( !tryEat(")") ) {
3f5dc76a75 2010-11-07        kinaba: 				if( lex.empty ) {
3f5dc76a75 2010-11-07        kinaba: 					auto ex = ParserException.create(lex,"Unexpected EOF");
3f5dc76a75 2010-11-07        kinaba: 					throw ex;
3f5dc76a75 2010-11-07        kinaba: 				}
3f5dc76a75 2010-11-07        kinaba: 				args ~= parseE();
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: 			e = new FuncallExpression(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: 
3f5dc76a75 2010-11-07        kinaba: 	Expression parseBaseBaseExpression()
3f5dc76a75 2010-11-07        kinaba: 	{
3f5dc76a75 2010-11-07        kinaba: 		if( lex.empty )
3f5dc76a75 2010-11-07        kinaba: 			throw new ParserException("EOF during parsing an expression");
3f5dc76a75 2010-11-07        kinaba: 		auto pos = lex.front.pos;
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 		if( lex.front.kind == Token.Kind.number )
423f308350 2010-11-07        kinaba: 		{
423f308350 2010-11-07        kinaba: 			scope(exit) lex.popFront;
423f308350 2010-11-07        kinaba: 			return new IntLiteralExpression(pos, BigInt(cast(string)lex.front.str));
423f308350 2010-11-07        kinaba: 		}
423f308350 2010-11-07        kinaba: 		if( lex.front.kind == Token.Kind.stringLiteral )
423f308350 2010-11-07        kinaba: 		{
423f308350 2010-11-07        kinaba: 			scope(exit) lex.popFront;
423f308350 2010-11-07        kinaba: 			return new StrLiteralExpression(pos, lex.front.str);
423f308350 2010-11-07        kinaba: 		}
423f308350 2010-11-07        kinaba: 		if( tryEat("(") )
423f308350 2010-11-07        kinaba: 		{
5d4cb856d8 2010-11-07        kinaba: 			auto e = parseE();
423f308350 2010-11-07        kinaba: 			eat(")", "after parenthesized expression");
423f308350 2010-11-07        kinaba: 			return e;
3f5dc76a75 2010-11-07        kinaba: 		}
3f5dc76a75 2010-11-07        kinaba: 
3f5dc76a75 2010-11-07        kinaba: 		if( tryEat("fun") )
3f5dc76a75 2010-11-07        kinaba: 		{
3f5dc76a75 2010-11-07        kinaba: 			eat("(", "after fun");
3f5dc76a75 2010-11-07        kinaba: 			string[] params;
0569f7b8c2 2010-11-07        kinaba: 			while(!tryEat(")"))
3f5dc76a75 2010-11-07        kinaba: 			{
3f5dc76a75 2010-11-07        kinaba: 				if( lex.empty ) {
3f5dc76a75 2010-11-07        kinaba: 					auto e = ParserException.create(lex,"Unexpected EOF");
3f5dc76a75 2010-11-07        kinaba: 					throw e;
3f5dc76a75 2010-11-07        kinaba: 				}
3f5dc76a75 2010-11-07        kinaba: 				if( lex.front.kind != Token.Kind.identifier ) {
3f5dc76a75 2010-11-07        kinaba: 					auto e = ParserException.create(lex,"Identifier Expected for parameters");
3f5dc76a75 2010-11-07        kinaba: 					throw e;
3f5dc76a75 2010-11-07        kinaba: 				}
3f5dc76a75 2010-11-07        kinaba: 				params ~= lex.front.str;
3f5dc76a75 2010-11-07        kinaba: 				lex.popFront;
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");
3f5dc76a75 2010-11-07        kinaba: 			Statement[] funbody;
3f5dc76a75 2010-11-07        kinaba: 			while(!tryEat("}")) {
3f5dc76a75 2010-11-07        kinaba: 				if( lex.empty ) {
3f5dc76a75 2010-11-07        kinaba: 					auto e = ParserException.create(lex,"Unexpected EOF");
3f5dc76a75 2010-11-07        kinaba: 					throw e;
3f5dc76a75 2010-11-07        kinaba: 				}
3f5dc76a75 2010-11-07        kinaba: 				funbody ~= parseStatement();
3f5dc76a75 2010-11-07        kinaba: 			}
3f5dc76a75 2010-11-07        kinaba: 			return new FunLiteralExpression(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;
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) )
423f308350 2010-11-07        kinaba: 		{
423f308350 2010-11-07        kinaba: 			auto e = ParserException.create(lex, "'"~kwd~"' is expected "~msg~" but '"
423f308350 2010-11-07        kinaba: 				~(lex.empty ? "EOF" : lex.front.str)~"' occured");
423f308350 2010-11-07        kinaba: 			throw e;
423f308350 2010-11-07        kinaba: 		}
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	bool tryEat(string kwd)
423f308350 2010-11-07        kinaba: 	{
423f308350 2010-11-07        kinaba: 		if( lex.empty || lex.front.kind!=Token.Kind.identifier || 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;
423f308350 2010-11-07        kinaba: 	}
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: unittest
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	auto p = parserFromString(`
423f308350 2010-11-07        kinaba: 		var x = 100;
423f308350 2010-11-07        kinaba: 		var y = 200;
423f308350 2010-11-07        kinaba: 	`);
423f308350 2010-11-07        kinaba: 	Program prog = p.parseProgram();
423f308350 2010-11-07        kinaba: 	assert( prog.length == 2 );
423f308350 2010-11-07        kinaba: 	auto p0 = cast(DeclStatement)prog[0];
423f308350 2010-11-07        kinaba: 	auto p1 = cast(DeclStatement)prog[1];
423f308350 2010-11-07        kinaba: 	assert( p0.var == "x" );
423f308350 2010-11-07        kinaba: 	assert( p1.var == "y" );
423f308350 2010-11-07        kinaba: 	assert( (cast(IntLiteralExpression)p0.expr).data == 100 );
423f308350 2010-11-07        kinaba: 	assert( (cast(IntLiteralExpression)p1.expr).data == 200 );
423f308350 2010-11-07        kinaba: }
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: unittest
423f308350 2010-11-07        kinaba: {
423f308350 2010-11-07        kinaba: 	auto p = parserFromString(`
423f308350 2010-11-07        kinaba: 		var zzz = 100; # comment
423f308350 2010-11-07        kinaba: 		zzz = zzz + zzz * "fo\no"; # comment
423f308350 2010-11-07        kinaba: 			42;
423f308350 2010-11-07        kinaba: 	`);
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	auto s0 = new DeclStatement(null, "zzz", new IntLiteralExpression(null, BigInt(100)));
5d4cb856d8 2010-11-07        kinaba: 	auto s1 = new ExprStatement(null, new AssignExpression(null,
423f308350 2010-11-07        kinaba: 		new VarExpression(null, "zzz"),
5d4cb856d8 2010-11-07        kinaba: 		new FuncallExpression(null, new VarExpression(null,"+"),
423f308350 2010-11-07        kinaba: 			new VarExpression(null, "zzz"),
5d4cb856d8 2010-11-07        kinaba: 			new FuncallExpression(null, new VarExpression(null,"*"),
423f308350 2010-11-07        kinaba: 				new VarExpression(null, "zzz"),
423f308350 2010-11-07        kinaba: 				new StrLiteralExpression(null, "fo\\no")
423f308350 2010-11-07        kinaba: 				))));
423f308350 2010-11-07        kinaba: 	auto s2 = new ExprStatement(null, new IntLiteralExpression(null, BigInt(42)));
423f308350 2010-11-07        kinaba: 
423f308350 2010-11-07        kinaba: 	Program prog = p.parseProgram();
423f308350 2010-11-07        kinaba: 	assert( prog.length == 3 );
423f308350 2010-11-07        kinaba: 	assert( prog[0] == s0 );
423f308350 2010-11-07        kinaba: 	assert( prog[1] == s1 );
423f308350 2010-11-07        kinaba: 	assert( prog[2] == s2 );
3f5dc76a75 2010-11-07        kinaba: }
3f5dc76a75 2010-11-07        kinaba: 
3f5dc76a75 2010-11-07        kinaba: unittest
3f5dc76a75 2010-11-07        kinaba: {
3f5dc76a75 2010-11-07        kinaba: 	auto p = parserFromString(`
3f5dc76a75 2010-11-07        kinaba: 		var f = fun(x,y){x+y;};
3f5dc76a75 2010-11-07        kinaba: 		f(1,fun(abc){}(4));
3f5dc76a75 2010-11-07        kinaba: 	`);
3f5dc76a75 2010-11-07        kinaba: 	Program prog = p.parseProgram();
3f5dc76a75 2010-11-07        kinaba: 	assert( prog.length == 2 );
3f5dc76a75 2010-11-07        kinaba: 	assert( prog[0] == new DeclStatement(null, "f", new FunLiteralExpression(null,
3f5dc76a75 2010-11-07        kinaba: 		["x","y"], [new ExprStatement(null,
3f5dc76a75 2010-11-07        kinaba: 			new FuncallExpression(null, new VarExpression(null, "+"),
3f5dc76a75 2010-11-07        kinaba: 			new VarExpression(null, "x"), new VarExpression(null, "y")))]
3f5dc76a75 2010-11-07        kinaba: 			)));
3f5dc76a75 2010-11-07        kinaba: 	assert( prog[1] == new ExprStatement(null, new FuncallExpression(null,
3f5dc76a75 2010-11-07        kinaba: 		new VarExpression(null, "f"),
3f5dc76a75 2010-11-07        kinaba: 		new IntLiteralExpression(null, BigInt(1)),
3f5dc76a75 2010-11-07        kinaba: 		new FuncallExpression(null,
3f5dc76a75 2010-11-07        kinaba: 			new FunLiteralExpression(null, ["abc"], [
3f5dc76a75 2010-11-07        kinaba: 			]),
3f5dc76a75 2010-11-07        kinaba: 			new IntLiteralExpression(null, BigInt(4))
3f5dc76a75 2010-11-07        kinaba: 			))));
0569f7b8c2 2010-11-07        kinaba: }
0569f7b8c2 2010-11-07        kinaba: unittest
0569f7b8c2 2010-11-07        kinaba: {
0569f7b8c2 2010-11-07        kinaba: 	auto p = parserFromString(`var x = 1; var f = fun(){x=x+1;}; f(); f(); x;`);
0569f7b8c2 2010-11-07        kinaba: 	Program prog = p.parseProgram();
423f308350 2010-11-07        kinaba: }