1 /**
2 * Authors: k.inaba
3 * License: NYSL 0.9982 http://www.kmonos.net/nysl/
4 *
5 * Parser for Polemy programming language
6 */
7 module polemy.parse;
8 import polemy._common;
9 import polemy.lex;
10 import polemy.ast;
11
12 ///
13 class ParseException : Exception
14 {
15 mixin ExceptionWithPosition;
16 }
17
18 /// Entry points of this module
19
20 AST parseString(S, T...)(S str, T fn_ln_cn)
21 { return parserFromString(str, fn_ln_cn).parse(); }
22
23 /// Entry points of this module
24
25 AST parseFile(S, T...)(S filename, T ln_cn)
26 { return parserFromFile(filename, ln_cn).parse(); }
27
28 // Named Constructors of Parser
29
30 private auto parserFromLexer(Lexer)(Lexer lex)
31 { return new Parser!Lexer(lex); }
32
33 private auto parserFromString(T...)(T params)
34 { return parserFromLexer(polemy.lex.lexerFromString(params)); }
35
36 private auto parserFromFile(T...)(T params)
37 { return parserFromLexer(polemy.lex.lexerFromFile(params)); }
38
39 // Parser
40
41 private class Parser(Lexer)
42 if( isForwardRange!(Lexer) && is(ElementType!(Lexer) == Token) )
43 {
44 AST parse()
45 {
46 auto e = Body();
47 if( !lex.empty )
48 throw genex!ParseException(currentPosition(), "parsing ended but some tokens left");
49 return e;
50 }
51
52 AST Body()
53 {
54 if( lex.empty || !lex.front.quoted && ["}",")","]"].canFind(lex.front.str) )
55 return doNothingExpression();
56
57 auto saved = lex.save;
58 auto pos = lex.front.pos;
59 string kwd = lex.front.str;
60 if( tryEat("let") || tryEat("var") || tryEat("def") || tryEat("@") )
61 {
62 if( kwd == "@" ) {
63 kwd ~= eatId("after @",true);
64 if( tryEat("(") ) {
65 lex = saved;
66 goto asExpression;
67 }
68 }
69 immutable LexPosition varpos = (lex.empty ? null : lex.front.pos);
70 string var = eatId("after "~kwd,true);
71 // [TODO] refactor. only auto e = ... differ
72 if(tryEat("(")) {
73 kwd = (kwd[0]=='@' ? kwd : ""); // "let, var, def ==> neutral layer"
74 auto e = parseLambdaAfterOpenParen(varpos);
75 if( tryEat(";") && !lex.empty && (lex.front.quoted || !["}",")","]"].canFind(lex.front.str)) )
76 return new LetExpression(pos, var, kwd, e, Body());
77 else
78 return new LetExpression(pos, var, kwd, e, new VarExpression(varpos, var));
79 } else {
80 eat("=", "after "~kwd);
81 kwd = (kwd[0]=='@' ? kwd : ""); // "let, var, def ==> neutral layer"
82 auto e = E(0);
83 if( tryEat(";") && !lex.empty && (lex.front.quoted || !["}",")","]"].canFind(lex.front.str)) )
84 return new LetExpression(pos, var, kwd, e, Body());
85 else
86 return new LetExpression(pos, var, kwd, e, new VarExpression(varpos, var));
87 }
88 }
89 else
90 {
91 asExpression:
92 auto e = E(0);
93 if( tryEat(";") && !lex.empty && (lex.front.quoted || (lex.front.str!="}" && lex.front.str!=")")) )
94 return new LetExpression(pos, "_", "", e, Body());
95 else
96 return e;
97 }
98 }
99
100 // [TODO] make customizable from program
101 static immutable string[][] operator_perferences = [
102 ["||"],
103 ["&&"],
104 ["!="],
105 ["=="],
106 ["<","<=",">",">="],
107 ["|"],
108 ["^"],
109 ["&"],
110 ["<<", ">>"],
111 ["+","-"],
112 ["~"],
113 ["*","/","%"],
114 ["^^"]
115 ];
116
117 AST E(int level)
118 {
119 if( operator_perferences.length <= level )
120 return Funcall();
121 else
122 {
123 auto ops = operator_perferences[level];
124 auto e = E(level+1);
125 seq:
126 while( !lex.empty )
127 {
128 auto pos = lex.front.pos;
129 foreach(op; ops)
130 if( tryEat(op) )
131 {
132 e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, E(level+1));
133 continue seq;
134 }
135 break;
136 }
137 return e;
138 }
139 }
140
141 AST Funcall()
142 {
143 auto e = BaseExpression();
144 while( tryEat("(") )
145 {
146 auto pos = currentPosition();
147 AST[] args;
148 while( !tryEat(")") ) {
149 if( lex.empty )
150 throw genex!UnexpectedEOF(pos,"Closing ')' for arguments not found");
151 args ~= E(0);
152 if( !tryEat(",") ) {
153 eat(")", "after function parameters");
154 break;
155 }
156 }
157 e = new FuncallExpression(e.pos, e, args);
158 }
159 return e;
160 }
161
162 AST BaseExpression()
163 {
164 if( lex.empty )
165 throw genex!UnexpectedEOF(currentPosition(), "Reached EOF when tried to parse an expression");
166
167 auto pos = lex.front.pos;
168 if( lex.front.quoted )
169 {
170 scope(exit) lex.popFront;
171 return new StrLiteral(pos, lex.front.str);
172 }
173 if( isNumber(lex.front.str) )
174 {
175 scope(exit) lex.popFront;
176 return new IntLiteral(pos, BigInt(cast(string)lex.front.str));
177 }
178 if( tryEat("@") )
179 {
180 auto lay = "@"~eatId("for layer ID");
181 eat("(", "for layered execution");
182 auto e = Body();
183 eat(")", "after "~lay~"(...");
184 return new LayeredExpression(pos, lay, e);
185 }
186 if( tryEat("(") )
187 {
188 auto e = Body();
189 eat(")", "after parenthesized expression");
190 return e;
191 }
192 if( tryEat("if") )
193 {
194 eat("(", "after if");
195 auto cond = E(0);
196 eat(")", "after if condition");
197 auto thenPos = lex.front.pos;
198 eat("{", "after if condition");
199 auto th = Body();
200 eat("}", "after if-then body");
201 auto el = doNothingExpression();
202 auto elsePos = (lex.empty ? LexPosition.dummy : lex.front.pos);
203 if( tryEat("else") ) {
204 eat("{", "after else");
205 el = Body();
206 eat("}", "after else body");
207 }
208 return new FuncallExpression(pos,
209 new VarExpression(pos, "if"),
210 cond,
211 new FunLiteral(thenPos, [], th),
212 new FunLiteral(elsePos, [], el)
213 );
214 }
215 if( tryEat("fun") || tryEat("\u03BB") )
216 {
217 eat("(", "after fun");
218 return parseLambdaAfterOpenParen(pos);
219 }
220 scope(exit) lex.popFront;
221 return new VarExpression(pos, lex.front.str);
222 }
223
224 AST parseLambdaAfterOpenParen(immutable LexPosition pos)
225 {
226 string[] params;
227 while( !tryEat(")") )
228 {
229 params ~= eatId("for function parameter");
230 if( !tryEat(",") ) {
231 eat(")", "after function parameters");
232 break;
233 }
234 }
235 eat("{", "after function parameters");
236 auto funbody = Body();
237 eat("}", "after function body");
238 return new FunLiteral(pos, params, funbody);
239 }
240
241 private:
242 Lexer lex;
243 this(Lexer lex) { this.lex = lex; }
244
245 void eat(string kwd, lazy string msg)
246 {
247 if( !tryEat(kwd) )
248 if( lex.empty )
249 throw genex!UnexpectedEOF(
250 currentPosition(), sprintf!"%s is expected for %s but not found"(kwd,msg));
251 else
252 throw genex!ParseException(
253 currentPosition(), sprintf!"%s is expected for %s but not found"(kwd,msg));
254 }
255
256 bool tryEat(string kwd)
257 {
258 if( lex.empty || lex.front.quoted || lex.front.str!=kwd )
259 return false;
260 lex.popFront;
261 return true;
262 }
263
264 string eatId(lazy string msg, bool allowQuoted=false)
265 {
266 if( lex.empty )
267 throw genex!UnexpectedEOF(currentPosition(), "identifier is expected but not found "~msg);
268 if( !allowQuoted && lex.front.quoted )
269 throw genex!ParseException(currentPosition(), "identifier is expected but not found "~msg);
270 scope(exit) lex.popFront;
271 return lex.front.str;
272 }
273
274 bool isNumber(string s)
275 {
276 return find!(`a<'0'||'9'<a`)(s).empty;
277 }
278
279 AST doNothingExpression()
280 {
281 return new IntLiteral(currentPosition(), BigInt(178));
282 }
283
284 immutable(LexPosition) currentPosition()
285 {
286 return lex.empty ? null : lex.front.pos;
287 }
288 }
289
290 unittest
291 {
292 mixin EasyAST;
293
294 assert_eq(parseString(`123`), intl(123));
295 assert_eq(parseString(`"foo"`), strl("foo"));
296 assert_eq(parseString(`fun(){1}`), fun([],intl(1)));
297 assert_eq(parseString(`fun(x){1}`), fun(["x"],intl(1)));
298 assert_eq(parseString("\u03BB(){1}"), fun([],intl(1)));
299 assert_eq(parseString("\u03BB(x){1}"), fun(["x"],intl(1)));
300 assert_eq(parseString(`1;2`), let("_","",intl(1),intl(2)));
301 assert_eq(parseString(`1;2;`), let("_","",intl(1),intl(2)));
302 assert_eq(parseString(`let x=1;2`), let("x","",intl(1),intl(2)));
303 assert_eq(parseString(`var x=1;2;`), let("x","",intl(1),intl(2)));
304 assert_eq(parseString(`def x=1`), let("x","",intl(1),var("x")));
305 assert_eq(parseString(`@val x=1;`), let("x","@val",intl(1),var("x")));
306 assert_eq(parseString(`@typ x="#int";`), let("x","@typ",strl("#int"),var("x")));
307 assert_eq(parseString(`f(1,2)`), call(var("f"),intl(1),intl(2)));
308 assert_eq(parseString(`if(1){2}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(178))));
309 assert_eq(parseString(`if(1){2}else{3}`), call(var("if"),intl(1),fun([],intl(2)),fun([],intl(3))));
310 assert_eq(parseString(`if(1){}else{3}()()`),
311 call(call(call(var("if"),intl(1),fun([],intl(178)),fun([],intl(3))))));
312 assert_eq(parseString(`1+2*3`), call(var("+"),intl(1),call(var("*"),intl(2),intl(3))));
313 assert_eq(parseString(`(1+2)*3`), call(var("*"),call(var("+"),intl(1),intl(2)),intl(3)));
314 assert_eq(parseString(`1*(2+3)`), call(var("*"),intl(1),call(var("+"),intl(2),intl(3))));
315 assert_eq(parseString(`1*2+3`), call(var("+"),call(var("*"),intl(1),intl(2)),intl(3)));
316 assert_eq(parseString(`@x(1)`), lay("@x", intl(1)));
317
318 assert_eq(parseString(`
319 let x = 100; #comment
320 let y = 200; #comment!!!!!
321 x+y
322 `),
323 let("x", "", intl(100), let("y", "", intl(200), call(var("+"), var("x"), var("y"))))
324 );
325
326 assert_eq(parseString(`
327 var fac = fun(x){ if(x <= 1) {1} else {x*fac(x-1)} };
328 fac(10)
329 `),
330 let("fac", "", fun(["x"],
331 call(var("if"),
332 call(var("<="), var("x"), intl(1)),
333 fun([], intl(1)),
334 fun([], call(var("*"), var("x"), call(var("fac"),call(var("-"),var("x"),intl(1)))))
335 )),
336 call(var("fac"),intl(10))
337 )
338 );
339 }
340
341 unittest
342 {
343 assert_throw!UnexpectedEOF(parseString(`1+`));
344 assert_throw!ParseException(parseString(`1+2}`));
345 assert_throw!UnexpectedEOF(parseString(`let "x"`));
346 assert_throw!UnexpectedEOF(parseString(`var`));
347 assert_throw!ParseException(parseString(`@val x ==`));
348 assert_throw!ParseException(parseString(`if(){1}`));
349 assert_throw!UnexpectedEOF(parseString(`f(`));
350 }
351
352 unittest
353 {
354 mixin EasyAST;
355 assert_eq(parseString(`def foo(x) { x+1 }; foo`),
356 let("foo", "",
357 fun(["x"], call(var("+"), var("x"), intl(1))),
358 var("foo"))
359 );
360 }