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