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 /// Parsing Failure
13
14 class ParserException : Exception
15 {
16 private:
17 this(string msg) { super(msg); }
18 static ParserException create(Lexer)(Lexer lex, string msg)
19 {
20 return new ParserException(sprintf!"[%s] %s"(
21 lex.empty ? "EOF" : to!string(lex.front.pos), msg));
22 }
23 }
24
25 /// Named Constructor of Parser
26
27 auto parserFromLexer(Lexer)(Lexer lex)
28 {
29 return new Parser!Lexer(lex);
30 }
31
32 /// Named Constructor of Parser (just fwd to lexerFromString)
33
34 auto parserFromString(T...)(T params)
35 {
36 return parserFromLexer(polemy.lex.lexerFromString(params));
37 }
38
39 /// Named Constructor of Parser (just fwd to lexerFromFile)
40
41 auto parserFromFile(T...)(T params)
42 {
43 return parserFromLexer(polemy.lex.lexerFromFile(params));
44 }
45
46 /// Parser
47
48 class Parser(Lexer)
49 {
50 this(Lexer lex)
51 {
52 this.lex = lex;
53 }
54
55 Program parseProgram()
56 {
57 Program p = parseStatements();
58 if( !lex.empty ) {
59 auto e = ParserException.create(lex, "cannot reach eof");
60 throw e;
61 }
62 return p;
63 }
64
65 Program parseStatements()
66 {
67 Program p;
68 while( !lex.empty && (lex.front.quoted || lex.front.str!="}") )
69 p ~= parseStatement();
70 return p;
71 }
72
73 Statement parseStatement()
74 {
75 auto saved = lex.save;
76 scope(failure) lex = saved;
77
78 if( lex.empty )
79 throw new ParserException("EOF during parsing a statement");
80 auto pos = lex.front.pos;
81
82 if( !lex.front.quoted && lex.front.str=="var" )
83 {
84 // "var" Var "=" Expression ";"
85 lex.popFront;
86 string var = lex.front.str;
87 lex.popFront;
88 eat("=", "for variable declaration");
89 auto parsed = new DeclStatement(pos, var, parseExpression());
90 eat(";", "after variable declaration");
91 return parsed;
92 }
93 else
94 {
95 // Expression ";"
96 auto parsed = new ExprStatement(pos, parseExpression());
97 eat(";", "after statement");
98 return parsed;
99 }
100 }
101
102 Expression parseExpression()
103 {
104 auto saved = lex.save;
105 scope(failure) lex = saved;
106 return parseE(0);
107 }
108
109 // [TODO] multi-char operators are not supported by the lexer...
110 static immutable string[][] operator_perferences = [
111 ["="],
112 ["or"],
113 ["and"],
114 ["!="],
115 ["=="],
116 ["<","<=",">",">="],
117 ["|"],
118 ["^"],
119 ["&"],
120 ["<<", ">>"],
121 ["+","-"],
122 ["*","/","%"]
123 ];
124
125 Expression parseE(int level = 0)
126 {
127 if( operator_perferences.length <= level )
128 return parseBaseExpression();
129 else
130 {
131 auto ops = operator_perferences[level];
132 auto e = parseE(level+1);
133 seq:
134 while( !lex.empty )
135 {
136 auto pos = lex.front.pos;
137 foreach(op; ops)
138 if( tryEat(op) )
139 {
140 if( op == "=" ) // right assoc
141 return new AssignExpression(e.pos, e, parseE(level));
142 else
143 e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, parseE(level+1));
144 continue seq;
145 }
146 break;
147 }
148 return e;
149 }
150 }
151
152 Expression parseBaseExpression()
153 {
154 if( lex.empty )
155 throw new ParserException("EOF during parsing an expression");
156 auto pos = lex.front.pos;
157 Expression e = parseBaseBaseExpression();
158 while( tryEat("(") ) // funcall
159 {
160 Expression[] args;
161 while( !tryEat(")") ) {
162 if( lex.empty ) {
163 auto ex = ParserException.create(lex,"Unexpected EOF");
164 throw ex;
165 }
166 args ~= parseE();
167 if( !tryEat(",") ) {
168 eat(")", "after function parameters");
169 break;
170 }
171 }
172 e = new FuncallExpression(pos, e, args);
173 }
174 return e;
175 }
176
177 Expression parseBaseBaseExpression()
178 {
179 if( lex.empty )
180 throw new ParserException("EOF during parsing an expression");
181 auto pos = lex.front.pos;
182
183 if( lex.front.quoted )
184 {
185 scope(exit) lex.popFront;
186 return new StrLiteralExpression(pos, lex.front.str);
187 }
188 if( isNumber(lex.front.str) ) // is_number
189 {
190 scope(exit) lex.popFront;
191 return new IntLiteralExpression(pos, BigInt(cast(string)lex.front.str));
192 }
193 if( tryEat("(") )
194 {
195 auto e = parseE();
196 eat(")", "after parenthesized expression");
197 return e;
198 }
199 if( tryEat("if") )
200 {
201 eat("(", "after if");
202 auto cond = parseE();
203 eat(")", "after if condition");
204 auto thenPos = lex.front.pos;
205 eat("{", "after if condition");
206 Statement[] th = parseStatements();
207 eat("}", "after if-then body");
208 Statement[] el;
209 auto elsePos = lex.front.pos;
210 if( tryEat("else") ) {
211 eat("{", "after else");
212 el = parseStatements();
213 eat("}", "after else body");
214 }
215 return new FuncallExpression(pos,
216 new VarExpression(pos, "if"),
217 cond,
218 new FunLiteralExpression(thenPos, [], th),
219 new FunLiteralExpression(elsePos, [], el)
220 );
221 }
222
223 if( tryEat("fun") )
224 {
225 eat("(", "after fun");
226 string[] params;
227 while(!tryEat(")"))
228 {
229 if( lex.empty ) {
230 auto e = ParserException.create(lex,"Unexpected EOF");
231 throw e;
232 }
233 if( lex.front.quoted ) {
234 auto e = ParserException.create(lex,"Identifier Expected for parameters");
235 throw e;
236 }
237 params ~= lex.front.str;
238 lex.popFront;
239 if( !tryEat(",") ) {
240 eat(")", "after function parameters");
241 break;
242 }
243 }
244 eat("{", "after function parameters");
245 Statement[] funbody;
246 while(!tryEat("}")) {
247 if( lex.empty ) {
248 auto e = ParserException.create(lex,"Unexpected EOF");
249 throw e;
250 }
251 funbody ~= parseStatement();
252 }
253 return new FunLiteralExpression(pos, params, funbody);
254 }
255 scope(exit) lex.popFront;
256 return new VarExpression(pos, lex.front.str);
257 }
258
259 private:
260 Lexer lex;
261
262 void eat(string kwd, lazy string msg)
263 {
264 if( !tryEat(kwd) )
265 {
266 auto e = ParserException.create(lex, "'"~kwd~"' is expected "~msg~" but '"
267 ~(lex.empty ? "EOF" : lex.front.str)~"' occured");
268 throw e;
269 }
270 }
271
272 bool tryEat(string kwd)
273 {
274 if( lex.empty || lex.front.quoted || lex.front.str!=kwd )
275 return false;
276 lex.popFront;
277 return true;
278 }
279
280 bool isNumber(string s)
281 {
282 return find!(`a<'0'||'9'<a`)(s).empty;
283 }
284 }
285
286 unittest
287 {
288 auto p = parserFromString(`
289 var x = 100;
290 var y = 200;
291 `);
292 Program prog = p.parseProgram();
293 assert( prog.length == 2 );
294 auto p0 = cast(DeclStatement)prog[0];
295 auto p1 = cast(DeclStatement)prog[1];
296 assert( p0.var == "x" );
297 assert( p1.var == "y" );
298 assert( (cast(IntLiteralExpression)p0.expr).data == 100 );
299 assert( (cast(IntLiteralExpression)p1.expr).data == 200 );
300 }
301
302 unittest
303 {
304 auto p = parserFromString(`
305 var zzz = 100; # comment
306 zzz = zzz + zzz * "fo\no"; # comment
307 42;
308 `);
309
310 mixin EasyAst;
311 auto s0 = decl("zzz", intl(BigInt(100)));
312 auto s1 = expr( new AssignExpression(null,
313 new VarExpression(null, "zzz"),
314 new FuncallExpression(null, new VarExpression(null,"+"),
315 new VarExpression(null, "zzz"),
316 new FuncallExpression(null, new VarExpression(null,"*"),
317 new VarExpression(null, "zzz"),
318 new StrLiteralExpression(null, "fo\\no")
319 ))));
320 auto s2 = new ExprStatement(null, new IntLiteralExpression(null, BigInt(42)));
321
322 Program prog = p.parseProgram();
323 assert( prog.length == 3 );
324 assert( prog[0] == s0 );
325 assert( prog[1] == s1 );
326 assert( prog[2] == s2 );
327 }
328
329 unittest
330 {
331 auto p = parserFromString(`
332 var f = fun(x,y){x+y;};
333 f(1,fun(abc){}(4));
334 `);
335 mixin EasyAst;
336 Program prog = p.parseProgram();
337 assert( prog.length == 2 );
338 assert( prog[0] == decl("f", fun(
339 ["x","y"], [expr(funcall(var("+"), var("x"), var("y")))]
340 )));
341 assert( prog[1] == expr(funcall(var("f"),
342 intl(BigInt(1)),
343 funcall(
344 fun(["abc"], cast(Statement[])[]),
345 intl(BigInt(4))
346 ))));
347 }
348
349 unittest
350 {
351 auto p = parserFromString(`var x = 1; var f = fun(){x=x+1;}; f(); f(); x;`);
352 Program prog = p.parseProgram();
353 }
354
355 unittest
356 {
357 auto p = parserFromString(`if(x<2){1;}else{x;};`);
358 Program prog = p.parseProgram();
359 assert( prog[0] == new ExprStatement(null, new FuncallExpression(null,
360 new VarExpression(null, "if"),
361 new FuncallExpression(null, new VarExpression(null,"<"), new VarExpression(null,"x"),
362 new IntLiteralExpression(null, BigInt(2))),
363 new FunLiteralExpression(null, [], [new ExprStatement(null, new IntLiteralExpression(null, BigInt(1)))]),
364 new FunLiteralExpression(null, [], [new ExprStatement(null, new VarExpression(null, "x"))])
365 )));
366 }