Artifact Content
Not logged in

Artifact 4856c979362ef43561c09de3b26a09cc5c5fc9dd


/*
 * 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;
import std.bigint;

/// Parsing Failure

class ParserException : Exception
{
private:
	this(string msg) { super(msg); }
	static ParserException create(Lexer)(Lexer lex, string msg)
	{
		return new ParserException(sprintf!"[%s] %s"(
			lex.empty ? "EOF" : to!string(lex.front.pos), msg));
	}
}

/// Named Constructor of Parser

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

/// Named Constructor of Parser (just fwd to lexerFromString)

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

/// Named Constructor of Parser (just fwd to lexerFromFile)

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

/// Parser

class Parser(Lexer)
{
	this(Lexer lex)
	{
		this.lex = lex;
	}

	Program parseProgram()
	{
		Program p;
		while( !lex.empty )
			p ~= parseStatement();
		return p;
	}
	
	Statement parseStatement()
	{
		auto saved = lex.save;
		scope(failure) lex = saved;

		if( lex.empty )
			throw new ParserException("EOF during parsing a statement");
		auto pos = lex.front.pos;

		if( lex.front.kind==Token.Kind.identifier && lex.front.str=="var" )
		{
			// "var" Var "=" Expression ";"
			lex.popFront;
			string var = lex.front.str;
			lex.popFront;
			eat("=", "for variable declaration");
			auto parsed = new DeclStatement(pos, var, parseExpression());
			eat(";", "after variable declaration");
			return parsed;
		}
		else
		{
			// Expression ";"
			auto parsed = new ExprStatement(pos, parseExpression());
			eat(";", "after statement");
			return parsed;
		}
	}

	Expression parseExpression()
	{
		auto saved = lex.save;
		scope(failure) lex = saved;
		return parseE(0);
	}

	// [TODO] multi-char operators are not supported by the lexer...
	static immutable string[][] operator_perferences = [
		["="],
		["or"],
		["and"],
		["!="],
		["=="],
		["<","<=",">",">="],
		["|"],
		["^"],
		["&"],
		["<<", ">>"],
		["+","-"],
		["*","/","%"]
	];

	Expression parseE(int level = 0)
	{
		if( operator_perferences.length <= level )
			return parseBaseExpression();
		else
		{
			auto ops = operator_perferences[level];
			auto e = parseE(level+1);
		seq:
			while( !lex.empty )
			{
				auto pos = lex.front.pos;
				foreach(op; ops)
					if( tryEat(op) )
					{
						if( op == "=" ) // right assoc
							return new AssignExpression(e.pos, e, parseE(level));
						else
							e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, parseE(level+1));
						continue seq;
					}
				break;
			}
			return e;
		}
	}

	Expression parseBaseExpression()
	{
		if( lex.empty )
			throw new ParserException("EOF during parsing an expression");
		auto pos = lex.front.pos;
		Expression e = parseBaseBaseExpression();
		while( tryEat("(") ) // funcall
		{
			Expression[] args;
			while( !tryEat(")") ) {
				if( lex.empty ) {
					auto ex = ParserException.create(lex,"Unexpected EOF");
					throw ex;
				}
				args ~= parseE();
				if( !tryEat(",") ) {
					eat(")", "after function parameters");
					break;
				}
			}
			e = new FuncallExpression(pos, e, args);
		}
		return e;
	}

	Expression parseBaseBaseExpression()
	{
		if( lex.empty )
			throw new ParserException("EOF during parsing an expression");
		auto pos = lex.front.pos;

		if( lex.front.kind == Token.Kind.number )
		{
			scope(exit) lex.popFront;
			return new IntLiteralExpression(pos, BigInt(cast(string)lex.front.str));
		}
		if( lex.front.kind == Token.Kind.stringLiteral )
		{
			scope(exit) lex.popFront;
			return new StrLiteralExpression(pos, lex.front.str);
		}
		if( tryEat("(") )
		{
			auto e = parseE();
			eat(")", "after parenthesized expression");
			return e;
		}

		if( tryEat("fun") )
		{
			eat("(", "after fun");
			string[] params;
			for(;;)
			{
				if( lex.empty ) {
					auto e = ParserException.create(lex,"Unexpected EOF");
					throw e;
				}
				if( lex.front.kind != Token.Kind.identifier ) {
					auto e = ParserException.create(lex,"Identifier Expected for parameters");
					throw e;
				}
				params ~= lex.front.str;
				lex.popFront;
				if( !tryEat(",") ) {
					eat(")", "after function parameters");
					break;
				}
			}
			eat("{", "after function parameters");
			Statement[] funbody;
			while(!tryEat("}")) {
				if( lex.empty ) {
					auto e = ParserException.create(lex,"Unexpected EOF");
					throw e;
				}
				funbody ~= parseStatement();
			}
			return new FunLiteralExpression(pos, params, funbody);
		}
		scope(exit) lex.popFront;
		return new VarExpression(pos, lex.front.str);
	}

private:
	Lexer lex;

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

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

unittest
{
	auto p = parserFromString(`
		var x = 100;
		var y = 200;
	`);
	Program prog = p.parseProgram();
	assert( prog.length == 2 );
	auto p0 = cast(DeclStatement)prog[0];
	auto p1 = cast(DeclStatement)prog[1];
	assert( p0.var == "x" );
	assert( p1.var == "y" );
	assert( (cast(IntLiteralExpression)p0.expr).data == 100 );
	assert( (cast(IntLiteralExpression)p1.expr).data == 200 );
}

unittest
{
	auto p = parserFromString(`
		var zzz = 100; # comment
		zzz = zzz + zzz * "fo\no"; # comment
			42;
	`);
	
	auto s0 = new DeclStatement(null, "zzz", new IntLiteralExpression(null, BigInt(100)));
	auto s1 = new ExprStatement(null, new AssignExpression(null,
		new VarExpression(null, "zzz"),
		new FuncallExpression(null, new VarExpression(null,"+"),
			new VarExpression(null, "zzz"),
			new FuncallExpression(null, new VarExpression(null,"*"),
				new VarExpression(null, "zzz"),
				new StrLiteralExpression(null, "fo\\no")
				))));
	auto s2 = new ExprStatement(null, new IntLiteralExpression(null, BigInt(42)));
	
	Program prog = p.parseProgram();
	assert( prog.length == 3 );
	assert( prog[0] == s0 );
	assert( prog[1] == s1 );
	assert( prog[2] == s2 );
}

unittest
{
	auto p = parserFromString(`
		var f = fun(x,y){x+y;};
		f(1,fun(abc){}(4));
	`);
	Program prog = p.parseProgram();
	assert( prog.length == 2 );
	assert( prog[0] == new DeclStatement(null, "f", new FunLiteralExpression(null,
		["x","y"], [new ExprStatement(null,
			new FuncallExpression(null, new VarExpression(null, "+"),
			new VarExpression(null, "x"), new VarExpression(null, "y")))]
			)));
	assert( prog[1] == new ExprStatement(null, new FuncallExpression(null,
		new VarExpression(null, "f"),
		new IntLiteralExpression(null, BigInt(1)),
		new FuncallExpression(null,
			new FunLiteralExpression(null, ["abc"], [
			]),
			new IntLiteralExpression(null, BigInt(4))
			))));
}