Artifact Content
Not logged in

Artifact 45c4aa9e0628516eb63b92e468d6edd5bca20d43


/**
 * 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.failure;
import polemy.lex;
import polemy.ast;
import polemy.layer;
import polemy.fresh;

/// Parse a string and return its AST

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

/// Parse the content of a file and return its AST

AST parseFile(S, T...)(S filename, T ln_cn)
{
	return parserFromFile(filename, ln_cn).parse();
}

// Named Constructors of Parser

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

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

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

// Parser

private class Parser(Lexer)
	if( isForwardRange!(Lexer) && is(ElementType!(Lexer) == Token) )
{
	AST parse()
	{
		auto e = Body();
		if( !lex.empty )
			throw genex!ParseException(currentPosition(), "parsing ended but some tokens left");
		return e;
	}

	AST Body()
	{
		/// Body ::= Declaration
		///        | TopLevelExpression

		if( closingBracket() )
			return doNothingExpression();

		auto saved = lex.save;
		if( auto e = Declaration() )
			return e;
		lex = saved;
		return TopLevelExpression();
	}

	AST Declaration() // returns null if it is not a declaration
	{
		/// Declaration ::=
		///    ["@" Layer|"let"|"var"|"def"] Var "=" Expression ([";"|"in"] Body?)?
		///  | ["@" Layer|"let"|"var"|"def"] Var "(" Param%"," ")" "{" Body "}" ([";"|"in"] Body?)?
		///  | ["@" "@" Layer "=" Expression ([";"|"in"] Body?)?
		///  | ["@" "@" Layer "(" Param%"," ")" "{" Body "}" ([";"|"in"] Body?)?

		auto pos = currentPosition();
		Layer layer = "";
		bool layerLiftDecl = false;

		if( tryEat("@") )
		{
			layer = "@" ~ eatId("after @", AllowQuoted);
			if( layer == "@@" )
			{
				layer = "@" ~ eatId("after @@", AllowQuoted);
				layerLiftDecl = true;
			}
			else
			{
				if( tryEat("(") )
					return null; // @lay(...) expression, not a declaration
			}
		}

		// [TODO] Refactor
		if( layerLiftDecl )
		{
			string kwd = "@" ~ layer;
			string var = layer;

			auto e = tryEat("(")
				? parseLambdaAfterOpenParen(pos)  // let var ( ...
				: (eat("=", "after "~kwd), E(0)); // let var = ...
			if( moreDeclarationExists() )
				return new Let(pos, var, LiftLayer, e, Body());
			else
				return new Let(pos, var, LiftLayer, e,
					new Lay(pos, LiftLayer, new Var(pos, var))
				);
		}
		else
		{
			string kwd = layer;
			if( layer.empty && !tryEat(kwd="let") && !tryEat(kwd="var") && !tryEat(kwd="def") )
				return null; // none of {@lay, let, var, def} occurred, it's not a declaration

			auto varpos = currentPosition();
			string var = eatId("after "~kwd, AllowQuoted); // name of the declared variable

			auto e = tryEat("(")
				? parseLambdaAfterOpenParen(pos)  // let var ( ...
				: (eat("=", "after "~kwd), E(0)); // let var = ...
			if( moreDeclarationExists() )
				return new Let(pos, var, layer, e, Body());
			else {
				if( layer.empty )
					return new Let(pos, var, layer, e, new Var(varpos, var));
				else if( isMacroLayer(layer) )
					return new Let(pos, var, layer, e, new Str(varpos, "(macro definition)"));
				else
					return new Let(pos, var, layer, e, new Lay(varpos, layer, new Var(varpos, var)));
			}
		}
	}

	AST TopLevelExpression()
	{
		/// TopLevelExpression ::= Expression ([";"|"in"] Body?)?

		auto pos = currentPosition();
		auto e = E(0);
		if( moreDeclarationExists() )
			return new Let(pos, "_", "", e, Body());
		else
			return e;
	}

	private bool moreDeclarationExists()
	{
		return (tryEat(";") || tryEat("in")) && !closingBracket();
	}

	private bool closingBracket()
	{
		return lex.empty || !lex.front.quoted && ["}",")","]",","].canFind(lex.front.str);
	}

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

	AST E(size_t level)
	{
		/// Expression ::= (Binary left-associative operators over) Funcall

		AST rec(AST lhs)
		{
			if( closingBracket() )
				return lhs;

			auto pos = currentPosition();
			foreach(op; operator_perferences[level])
				if( tryEat(op) )
					if( op[0]=='.' )
						return rec(
							new App(lhs.pos, new Var(pos, op), lhs, parseId()));
					else
						return rec(
							new App(lhs.pos, new Var(pos, op), lhs, E(level+1)));
			return lhs;
		}

		if( operator_perferences.length <= level )
			return Funcall();
		else
			return rec(E(level+1));
	}

	AST Funcall()
	{
		/// Funcall ::= BaseExpression ["(" Expression%"," ")" | "{" ENTRIES "}"]*

		auto e = BaseExpression();
		for(;;)
			if( tryEat("(") )
			{
				auto pos = currentPosition();
				AST[] args;
				while( !tryEat(")") ) {
					if( lex.empty )
						throw genex!UnexpectedEOF(pos, "closing ')' for arguments not found");
					args ~= E(0);
					if( !tryEat(",") ) {
						eat(")", "after function parameters");
						break;
					}
				}
				e = new App(e.pos, e, args);
			}
			else if( tryEat("{") )
			{
				e = parseTableSetAfterBrace(e);
			}
			else
				break;
		return e;
	}

	AST parseTableSetAfterBrace(AST e)
	{
		/// TableSet ::= "{" (ID ":" E) % "," "}"
		
		if( tryEat("}") )
			return e;
		auto pos = currentPosition();
		for(;;)
		{
			string key = eatId("for table key", AllowQuoted);
			eat(":", "after table key");
			AST val = E(0);
			e = new App(pos, new Var(pos,".="),
					e, new Str(pos,key), val);
			if( !tryEat(",") )
			{
				eat("}", "for the end of table literal");
				break;
			}
		}
		return e;
	}

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

		auto pos = currentPosition();
		if( lex.front.quoted )
		{
			scope(exit) lex.popFront;
			return new Str(pos, lex.front.str);
		}
		if( isNumber(lex.front.str) )
		{
			scope(exit) lex.popFront;
			return new Int(pos, BigInt(cast(string)lex.front.str));
		}
		if( tryEat("...") )
		{
			return new Die(pos);
		}
		if( tryEat("@") )
		{
			auto lay = "@"~eatId("for layer ID");
			eat("(", "for layered execution");
			auto e = Body();
			eat(")", "after "~lay~"(...");
			return new Lay(pos, lay, e);
		}
		if( tryEat("(") )
		{
			auto e = Body();
			eat(")", "after parenthesized expression");
			return e;
		}
		if( tryEat("{") )
		{
			AST e = new App(pos, new Var(pos,"{}"));
			return parseTableSetAfterBrace(e);
		}
		if( tryEat("if") )
		{
			return parseIfAfterIf(pos);
		}
		if( tryEat("case") )
		{
			return parsePatternMatch(pos);
		}
		if( tryEat("fun") || tryEat("\u03BB") ) // lambda!!
		{
			eat("(", "after fun");
			return parseLambdaAfterOpenParen(pos);
		}
		scope(exit) lex.popFront;
		return new Var(pos, lex.front.str);
	}

	AST parseIfAfterIf(LexPosition pos)
	{
		auto cond = E(0);
		auto thenPos = currentPosition();
		if(!tryEat(":")) {
			eat("then", "after if condition");
			tryEat(":");
		}
		AST th = E(0);
		auto el = doNothingExpression();
		auto elsePos = currentPosition();
		if( tryEat("else") ) {
			tryEat(":");
			el = E(0);
		}
		return new App(pos, new Var(pos,"if"), cond, new Fun(thenPos,[],th), new Fun(elsePos,[],el));
	}

	AST parsePatternMatch(LexPosition pos)
	{
		//   case pmExpr CASES
		//==>
		//   let pmVar = pmExpr in (... let pmTryFirst = ... in pmTryFirst())
		AST   pmExpr = E(0);
		string pmVar = freshVarName();
		string pmTryFirst = freshVarName();
		AST   pmBody = parsePatternMatchCases(pos, pmVar, pmTryFirst,
			new App(pos, new Var(pos, pmTryFirst)));
		return new Let(pos, pmVar, [], pmExpr, pmBody);
	}

	AST parsePatternMatchCases(LexPosition casePos, string pmVar, string tryThisBranchVar, AST thenDoThis)
	{
		//    when pat: cBody
		//==>
		//    ... let failBranchVar = ... in
		//    let tryThisBranchVar = fun(){ if(test){cBody}else{failBranchVar()} } in thenDoThis
		if( tryEat("when") )
		{
			auto pos = currentPosition();
			string failBranchVar = freshVarName();

			auto pr = parsePattern();
			eat(":", "after when pattern");
			AST cBody = E(0);
			AST judgement = new App(pos, new Var(pos, "if"),
				ppTest(pmVar, pr), new Fun(pos,[],ppBind(pmVar, pr, cBody)),
				new Var(pos, failBranchVar));
			return parsePatternMatchCases(casePos, pmVar, failBranchVar, 
				new Let(pos, tryThisBranchVar, [],
					new Fun(pos,[],judgement), thenDoThis)
			);
		}
		else
		{
			AST doNothing = new Fun(casePos,[], new Die(casePos));
			return new Let(casePos, tryThisBranchVar, [], doNothing, thenDoThis);
		}
	}

// hageshiku tenuki
	abstract class SinglePattern
	{
		string[] path;
		mixin SimpleClass;
		private AST access(string pmVar, string[] path) {
			auto pos = currentPosition();
			AST e = new Var(pos, pmVar);
			foreach(p; path)
				e = new App(pos, new Var(pos, "."), e, new Str(pos, p));
			return e;
		}
		private AST has(AST e, string k) {
			auto pos = currentPosition();
			return opAndAnd(
				new App(pos, new Var(pos, "_istable"), e),
				new App(pos, new Var(pos, ".?"), e, new Str(pos, k))
			);
		}
		private AST opAndAnd(AST a, AST b) {
			if( a is null ) return b;
			if( b is null ) return a;
			auto pos = currentPosition();
			return new App(pos,
				new Var(pos, "if"),
				a,
				new Fun(pos, [], b),
				new Fun(pos, [], new Int(pos, 0))
			);
		}
		AST ppTest(string pmVar) {
			AST c = null;
			for(int i=0; i<path.length; ++i)
				c = opAndAnd(c, has(access(pmVar,path[0..i]), path[i]));
			return c;
		}
		AST ppBind(string pmVar, AST thenDoThis) { return thenDoThis; }
	}
	class WildPattern : SinglePattern
	{
		mixin SimpleClass;
	}
	class VarPattern : SinglePattern
	{
		string name;
		mixin SimpleClass;
		AST ppBind(string pmVar, AST thenDoThis) {
			auto pos = currentPosition();
			return new Let(pos, name, [], access(pmVar,path), thenDoThis);
		}
	}
	class ConstantPattern : SinglePattern
	{
		AST e;
		mixin SimpleClass;
		AST ppTest(string pmVar) {
			auto pos = currentPosition();
			return opAndAnd( super.ppTest(pmVar),
				new App(pos, new Var(pos,"=="), access(pmVar,path), e)
			);
		}
	}

	SinglePattern[] parsePattern(string[] path = null)
	{
		SinglePattern[] result;
		if( tryEat("{") )
		{
			if( !tryEat("}") ) {
				do {
					string key = eatId("in table pattern", AllowQuoted);
					eat(":", "after field-id in table pattern");
					result ~= parsePattern(path ~ key);
				} while( tryEat(",") );
				eat("}", "at the end of table pattern");
			}
		}
		else
		{
			AST e = E(0);
			if(auto ev = cast(Var)e)
				if(ev.name == "_")
					result ~= new WildPattern(path);
				else
					result ~= new VarPattern(path, ev.name);
			else
				result ~= new ConstantPattern(path, e);
		}
		return result;
	}

	AST ppTest(string pmVar, SinglePattern[] pats)
	{
		auto pos = currentPosition();
		AST cond = null;
		foreach(p; pats) {
			AST c2 = p.ppTest(pmVar);
			if( c2 !is null )
				cond = cond is null ? c2
				    : new App(pos, new Var(pos,"&&"), cond, c2);
		}
		return cond is null ? new Int(currentPosition(), 1) : cond;
	}

	AST ppBind(string pmVar, SinglePattern[] pats, AST thenDoThis)
	{
		foreach(p; pats)
			thenDoThis = p.ppBind(pmVar, thenDoThis);
		return thenDoThis;
	}

	AST parseId()
	{
		scope(exit) lex.popFront;
		return new Str(currentPosition(), lex.front.str);
	}

	AST parseLambdaAfterOpenParen(LexPosition pos)
	{
		Parameter[] params;
		while( !tryEat(")") )
		{
			params ~= parseParam();
			if( !tryEat(",") ) {
				eat(")", "after function parameters");
				break;
			}
		}
		eat("{", "after function parameters");
		auto funbody = Body();
		eat("}", "after function body");
		return new Fun(pos, params, funbody);
	}

	Parameter parseParam()
	{
		string var;
		string[] lay;
		while( !closingBracket() && !lex.empty && lex.front.str!="," )
		{
			auto pos = currentPosition();
			string p = eatId("for function parameter", AllowQuoted);
			if( p == "@" )
				lay ~= "@" ~ eatId("after @", AllowQuoted);
			else if( var.empty )
				var = p;
			else
				throw genex!ParseException(pos, "one parameter has two names");
		}
		return new Parameter(var, lay);
	}

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

	bool isNumber(string s)
	{
		return find!(`a<'0' || '9'<a`)(s).empty;
	}
	
	void eat(string kwd, lazy string msg)
	{
		if( !tryEat(kwd) )
			if( lex.empty )
				throw genex!UnexpectedEOF(
					currentPosition(), sprintf!"%s is expected %s but not found"(kwd,msg));
			else
				throw genex!ParseException(
					currentPosition(), sprintf!"%s is expected for %s but not found"(kwd,msg));
	}

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

	enum {AllowQuoted=true, DisallowQuoted=false};
	string eatId(lazy string msg, bool aq=DisallowQuoted)
	{
		if( lex.empty )
			throw genex!UnexpectedEOF(currentPosition(), "identifier is expected but not found "~msg);
		if( !aq && lex.front.quoted )
			throw genex!ParseException(currentPosition(), "identifier is expected but not found "~msg);
		scope(exit) lex.popFront;
		return lex.front.str;
	}

	AST doNothingExpression()
	{
		return new Str(currentPosition(), "(empty function body)");
	}

	LexPosition currentPosition()
	{
		return lex.empty ? new LexPosition("EOF",0,0) : lex.front.pos;
	}
}

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("\u03BB(){1}"), fun([],intl(1)));
	assert_eq(parseString("\u03BB(x,y){1}"), fun(["x","y"],intl(1)));
	assert_eq(parseString(`1;2`), let("_","",intl(1),intl(2)));
	assert_eq(parseString(`1;2;`), let("_","",intl(1),intl(2)));
	assert_eq(parseString(`let x=1 in 2`), let("x","",intl(1),intl(2)));
	assert_eq(parseString(`var x=1;2;`), let("x","",intl(1),intl(2)));
	assert_eq(parseString(`def x=1`), let("x","",intl(1),var("x")));
	assert_eq(parseString(`@val x=1;`), let("x","@val",intl(1),lay("@val",var("x"))));
	assert_eq(parseString(`@typ x="#int";`), let("x","@typ",strl("#int"),lay("@typ",var("x"))));
	assert_eq(parseString(`@macro x=1`), let("x","@macro",intl(1),strl("(macro definition)")));
	assert_eq(parseString(`f(1,2)`), call(var("f"),intl(1),intl(2)));
	assert_eq(parseString(`if 1 then 2`), call(var("if"),intl(1),fun([],intl(2)),fun([],strl("(empty function body)"))));
	assert_eq(parseString(`if 1 then: 2 else(3)`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(3))));
	assert_eq(parseString(`(if 1 then () else 3)()()`),
		call(call(call(var("if"),intl(1),fun([],strl("(empty function body)")),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(`@x(1)`), lay("@x", intl(1)));
	assert_eq(parseString(`fun(x @v @t, y, z @t){}`),
		funp([param("x",["@v","@t"]), param("y",[]), param("z",["@t"])], strl("(empty function body)")));

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

	assert_eq(parseString(`
		var fac = fun(x){ if(x <= 1) then 1 else x*fac(x-1) };
		fac(10)
	`),
		let("fac", "", 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!UnexpectedEOF(parseString(`1+`));
	assert_throw!ParseException(parseString(`1+2}`));
	assert_throw!UnexpectedEOF(parseString(`let "x"`));
	assert_throw!UnexpectedEOF(parseString(`var`));
	assert_throw!ParseException(parseString(`@val x ==`));
	assert_throw!ParseException(parseString(`if(){1}`));
	assert_throw!UnexpectedEOF(parseString(`f(`));
}

unittest
{
	mixin EasyAST;
	assert_eq(parseString(`def foo(x) { x+1 }; foo`),
		let("foo", "",
			fun(["x"], call(var("+"), var("x"), intl(1))),
			var("foo"))
	);

	assert_eq(parseString(`@@type ( x ) { x }`),
		let("@type", LiftLayer, fun(["x"], var("x")), lay(LiftLayer, var("@type"))) );

	assert_eq(parseString(`{}`), call(var("{}")));
	assert_eq(parseString(`{foo:1,"bar":2}`),
		call(var(".="), call(var(".="), call(var("{}")), strl("foo"), intl(1)), strl("bar"), intl(2)));
	assert_eq(parseString(`{}.foo`), call(var("."),call(var("{}")),strl("foo")));
	assert_eq(parseString(`{}.?foo`), call(var(".?"),call(var("{}")),strl("foo")));
	assert_eq(parseString(`x{y:1}`), call(var(".="),var("x"),strl("y"),intl(1)));
}

unittest
{
	assert_nothrow(parseString(`
		case( 1 )
			when(x): 1
	`));
	assert_nothrow(parseString(`
		case 1
			when {aaaa:_}: 1
	`));
	assert_nothrow(parseString(`
		case 1
			when {aaaa:@value(x)}: 1
			when {aaaa:{bbb:_}, ccc:123}: 1
	`));
}