/**
* 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 = parseStatements();
if( !lex.empty ) {
auto e = ParserException.create(lex, "cannot reach eof");
throw e;
}
return p;
}
Program parseStatements()
{
Program p;
while( !lex.empty && (lex.front.kind!=Token.Kind.identifier || lex.front.str!="}") )
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("if") )
{
eat("(", "after if");
auto cond = parseE();
eat(")", "after if condition");
auto thenPos = lex.front.pos;
eat("{", "after if condition");
Statement[] th = parseStatements();
eat("}", "after if-then body");
Statement[] el;
auto elsePos = lex.front.pos;
if( tryEat("else") ) {
eat("{", "after else");
el = parseStatements();
eat("}", "after else body");
}
return new FuncallExpression(pos,
new VarExpression(pos, "if"),
cond,
new FunLiteralExpression(thenPos, [], th),
new FunLiteralExpression(elsePos, [], el)
);
}
if( tryEat("fun") )
{
eat("(", "after fun");
string[] params;
while(!tryEat(")"))
{
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))
))));
}
unittest
{
auto p = parserFromString(`var x = 1; var f = fun(){x=x+1;}; f(); f(); x;`);
Program prog = p.parseProgram();
}
unittest
{
auto p = parserFromString(`if(x<2){1;}else{x;};`);
Program prog = p.parseProgram();
assert( prog[0] == new ExprStatement(null, new FuncallExpression(null,
new VarExpression(null, "if"),
new FuncallExpression(null, new VarExpression(null,"<"), new VarExpression(null,"x"),
new IntLiteralExpression(null, BigInt(2))),
new FunLiteralExpression(null, [], [new ExprStatement(null, new IntLiteralExpression(null, BigInt(1)))]),
new FunLiteralExpression(null, [], [new ExprStatement(null, new VarExpression(null, "x"))])
)));
}