/**
* 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(`));
}