Artifact Content
Not logged in

Artifact d47e2b014f260d66e06c3c3914fcbe466f39de90


/**
 * Authors: k.inaba
 * License: NYSL 0.9982 http://www.kmonos.net/nysl/
 *
 * Parser for Polemy programming language
 */
module polemy.parse;
import polemy._common;
import polemy.lex;
import polemy.ast;

/// Exception from this module

class ParseException : Exception
{
	const LexPosition pos;

	private this( const LexPosition pos, string msg )
		{ super(sprintf!"%s [%s]"(msg, pos)); this.pos = pos; }
}

private auto createException(Lexer)(Lexer lex, string msg)
	{ return new ParseException(lex.empty?null:lex.front.pos, msg); }

/// Entry point of this module

auto parseString(S, T...)(S str, T fn_ln_cn)
	{ return parserFromString(str, fn_ln_cn).parse(); }

auto parseFile(S, T...)(S filename,T ln_cn)
	{ return parserFromString(filename, ln_cn).parse(); }

/// Named Constructor of Parser

private auto parserFromLexer(Lexer)(Lexer lex)
	{ return new Parser!Lexer(lex); }

private auto parserFromString(T...)(T params)
	{ return parserFromLexer(polemy.lex.lexerFromString(params)); }

private auto parserFromFile(T...)(T params)
	{ return parserFromLexer(polemy.lex.lexerFromFile(params)); }

/// Parser

private class Parser(Lexer)
	if( isForwardRange!(Lexer) && is(ElementType!(Lexer) == Token) )
{
	AST parse()
	{
		auto e = Body();
		if( !lex.empty )
			throw createException(lex, "input is not ended but parser came to the end");
		return e;
	}

	AST Body()
	{
		if( lex.empty || !lex.front.quoted && lex.front.str=="}" )
			return doNothingExpression();

		auto pos = lex.front.pos;
		string kwd = lex.front.str;
		if( tryEat("let") || tryEat("var") || tryEat("def") || tryEat("@") )
		{
			if( kwd == "@" )
				kwd ~= eatId("after @");
			immutable LexPosition varpos = (lex.empty ? null : lex.front.pos);
			string var = eatId("after "~kwd);
			eat("=", "after "~kwd);
			kwd = (kwd[0]=='@' ? kwd : "@val");
			auto e = E(0);
			if( tryEat(";") && !lex.empty && (lex.front.quoted || (lex.front.str!="}" && lex.front.str!=")")) )
				return new LetExpression(pos, var, kwd, e, Body());
			else
				return new LetExpression(pos, var, kwd, e, new VarExpression(varpos, var));
		}
		else
		{
			auto e = E(0);
			if( tryEat(";") && !lex.empty && (lex.front.quoted || (lex.front.str!="}" && lex.front.str!=")")) )
				return new LetExpression(pos, "_", "@val", e, Body());
			else
				return e;
		}
	}

	// [TODO] make customizable from program
	static immutable string[][] operator_perferences = [
		["||"],
		["&&"],
		["!="],
		["=="],
		["<","<=",">",">="],
		["|"],
		["^"],
		["&"],
		["<<", ">>"],
		["+","-"],
		["~"],
		["*","/","%"],
		["^^"]
	];

	AST E(int level)
	{
		if( operator_perferences.length <= level )
			return Funcall();
		else
		{
			auto ops = operator_perferences[level];
			auto e = E(level+1);
		seq:
			while( !lex.empty )
			{
				auto pos = lex.front.pos;
				foreach(op; ops)
					if( tryEat(op) )
					{
						e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, E(level+1));
						continue seq;
					}
				break;
			}
			return e;
		}
	}

	AST Funcall()
	{
		auto e = BaseExpression();
		while( tryEat("(") )
		{
			AST[] args;
			while( !tryEat(")") ) {
				if( lex.empty )
					throw createException(lex,"Unexpected EOF");
				args ~= E(0);
				if( !tryEat(",") ) {
					eat(")", "after function parameters");
					break;
				}
			}
			e = new FuncallExpression(e.pos, e, args);
		}
		return e;
	}

	AST BaseExpression()
	{
		if( lex.empty )
			throw createException(lex, "Reached EOF when tried to parse an expression");

		auto pos = lex.front.pos;
		if( lex.front.quoted )
		{
			scope(exit) lex.popFront;
			return new StrLiteral(pos, lex.front.str);
		}
		if( isNumber(lex.front.str) )
		{
			scope(exit) lex.popFront;
			return new IntLiteral(pos, BigInt(cast(string)lex.front.str));
		}
		if( tryEat("(") )
		{
			auto e = Body();
			eat(")", "after parenthesized expression");
			return e;
		}
		if( tryEat("if") )
		{
			eat("(", "after if");
			auto cond = E(0);
			eat(")", "after if condition");
			auto thenPos = lex.front.pos;
			eat("{", "after if condition");
			auto th = Body();
			eat("}", "after if-then body");
			auto el = doNothingExpression();
			auto elsePos = (lex.empty ? LexPosition.dummy : lex.front.pos);
			if( tryEat("else") ) {
				eat("{", "after else");
				el = Body();
				eat("}", "after else body");
			}
			return new FuncallExpression(pos, 
				new VarExpression(pos, "if"),
				cond,
				new FunLiteral(thenPos, [], th),
				new FunLiteral(elsePos, [], el)
			);
		}
		if( tryEat("fun") || tryEat("λ") )
		{
			eat("(", "after fun");
			string[] params;
			while( !tryEat(")") )
			{
				params ~= eatId("for function parameter");
				if( !tryEat(",") ) {
					eat(")", "after function parameters");
					break;
				}
			}
			eat("{", "after function parameters");
			auto funbody = Body();
			eat("}", "after function body");
			return new FunLiteral(pos, params, funbody);
		}
		scope(exit) lex.popFront;
		return new VarExpression(pos, lex.front.str);
	}

private:
	Lexer lex;
	this(Lexer lex) { this.lex = lex; }

	void eat(string kwd, lazy string msg)
	{
		if( !tryEat(kwd) )
			throw createException(lex, "'"~kwd~"' is expected "~msg~" but '"
				~(lex.empty ? "EOF" : lex.front.str)~"' occured");
	}

	bool tryEat(string kwd)
	{
		if( lex.empty || lex.front.quoted || lex.front.str!=kwd )
			return false;
		lex.popFront;
		return true;
	}

	string eatId(lazy string msg)
	{
		if( lex.empty || lex.front.quoted )
			throw createException(lex, "identifier is expected but not found "~msg);
		string id = lex.front.str;
		lex.popFront;
		return id;
	}

	bool isNumber(string s)
	{
		return find!(`a<'0'||'9'<a`)(s).empty;
	}

	AST doNothingExpression()
	{
		return new IntLiteral(lex.empty?null:lex.front.pos, BigInt(178));
	}
}

unittest
{
	mixin EasyAST;

	assert_eq(parseString(`123`), intl(123));
	assert_eq(parseString(`"foo"`), strl("foo"));
	assert_eq(parseString(`fun(){1}`), fun([],intl(1)));
	assert_eq(parseString(`fun(x){1}`), fun(["x"],intl(1)));
	assert_eq(parseString(`λ(){1}`), fun([],intl(1)));
	assert_eq(parseString(`λ(x){1}`), fun(["x"],intl(1)));
	assert_eq(parseString(`1;2`), let("_","@val",intl(1),intl(2)));
	assert_eq(parseString(`1;2;`), let("_","@val",intl(1),intl(2)));
	assert_eq(parseString(`let x=1;2`), let("x","@val",intl(1),intl(2)));
	assert_eq(parseString(`var x=1;2;`), let("x","@val",intl(1),intl(2)));
	assert_eq(parseString(`def x=1`), let("x","@val",intl(1),var("x")));
	assert_eq(parseString(`@val x=1;`), let("x","@val",intl(1),var("x")));
	assert_eq(parseString(`@typ x="#int";`), let("x","@typ",strl("#int"),var("x")));
	assert_eq(parseString(`f(1,2)`), call(var("f"),intl(1),intl(2)));
	assert_eq(parseString(`if(1){2}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(178))));
	assert_eq(parseString(`if(1){2}else{3}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(3))));
	assert_eq(parseString(`if(1){}else{3}()()`),
		call(call(call(var("if"),intl(1),fun([],intl(178)),fun([],intl(3))))));
	assert_eq(parseString(`1+2*3`), call(var("+"),intl(1),call(var("*"),intl(2),intl(3))));
	assert_eq(parseString(`(1+2)*3`), call(var("*"),call(var("+"),intl(1),intl(2)),intl(3)));
	assert_eq(parseString(`1*(2+3)`), call(var("*"),intl(1),call(var("+"),intl(2),intl(3))));
	assert_eq(parseString(`1*2+3`), call(var("+"),call(var("*"),intl(1),intl(2)),intl(3)));

	assert_eq(parseString(`
		let x = 100; #comment
		let y = 200; #comment!!!!!
			x+y
	`),
		let("x", "@val", intl(100), let("y", "@val", intl(200), call(var("+"), var("x"), var("y"))))
	);

	assert_eq(parseString(`
		var fac = fun(x){ if(x <= 1) {1} else {x*fac(x-1)} };
		fac(10)
	`),
		let("fac", "@val", fun(["x"],
			call(var("if"),
				call(var("<="), var("x"), intl(1)),
				fun([], intl(1)),
				fun([], call(var("*"), var("x"), call(var("fac"),call(var("-"),var("x"),intl(1)))))
			)),
			call(var("fac"),intl(10))
		)
	);
}

unittest
{
	assert_throw!ParseException(parseString(`1+`));
	assert_throw!ParseException(parseString(`1+2}`));
	assert_throw!ParseException(parseString(`let "x"`));
	assert_throw!ParseException(parseString(`var`));
	assert_throw!ParseException(parseString(`@val x ==`));
	assert_throw!ParseException(parseString(`if(){1}`));
	assert_throw!ParseException(parseString(`f(`));
}