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;
59 while( !lex.empty )
60 p ~= parseStatement();
61 return p;
62 }
63
64 Statement parseStatement()
65 {
66 auto saved = lex.save;
67 scope(failure) lex = saved;
68
69 if( lex.empty )
70 throw new ParserException("EOF during parsing a statement");
71 auto pos = lex.front.pos;
72
73 if( lex.front.kind==Token.Kind.identifier && lex.front.str=="var" )
74 {
75 // "var" Var "=" Expression ";"
76 lex.popFront;
77 string var = lex.front.str;
78 lex.popFront;
79 eat("=", "for variable declaration");
80 auto parsed = new DeclStatement(pos, var, parseExpression());
81 eat(";", "after variable declaration");
82 return parsed;
83 }
84 else
85 {
86 // Expression ";"
87 auto parsed = new ExprStatement(pos, parseExpression());
88 eat(";", "after statement");
89 return parsed;
90 }
91 }
92
93 Expression parseExpression()
94 {
95 auto saved = lex.save;
96 scope(failure) lex = saved;
97 return parseE(0);
98 }
99
100 // [TODO] multi-char operators are not supported by the lexer...
101 static immutable string[][] operator_perferences = [
102 ["="],
103 ["or"],
104 ["and"],
105 ["!="],
106 ["=="],
107 ["<","<=",">",">="],
108 ["|"],
109 ["^"],
110 ["&"],
111 ["<<", ">>"],
112 ["+","-"],
113 ["*","/","%"]
114 ];
115
116 Expression parseE(int level = 0)
117 {
118 if( operator_perferences.length <= level )
119 return parseBaseExpression();
120 else
121 {
122 auto ops = operator_perferences[level];
123 auto e = parseE(level+1);
124 seq:
125 while( !lex.empty )
126 {
127 auto pos = lex.front.pos;
128 foreach(op; ops)
129 if( tryEat(op) )
130 {
131 if( op == "=" ) // right assoc
132 return new AssignExpression(e.pos, e, parseE(level));
133 else
134 e = new FuncallExpression(e.pos, new VarExpression(pos, op), e, parseE(level+1));
135 continue seq;
136 }
137 break;
138 }
139 return e;
140 }
141 }
142
143 Expression parseBaseExpression()
144 {
145 if( lex.empty )
146 throw new ParserException("EOF during parsing an expression");
147 auto pos = lex.front.pos;
148 Expression e = parseBaseBaseExpression();
149 while( tryEat("(") ) // funcall
150 {
151 Expression[] args;
152 while( !tryEat(")") ) {
153 if( lex.empty ) {
154 auto ex = ParserException.create(lex,"Unexpected EOF");
155 throw ex;
156 }
157 args ~= parseE();
158 if( !tryEat(",") ) {
159 eat(")", "after function parameters");
160 break;
161 }
162 }
163 e = new FuncallExpression(pos, e, args);
164 }
165 return e;
166 }
167
168 Expression parseBaseBaseExpression()
169 {
170 if( lex.empty )
171 throw new ParserException("EOF during parsing an expression");
172 auto pos = lex.front.pos;
173
174 if( lex.front.kind == Token.Kind.number )
175 {
176 scope(exit) lex.popFront;
177 return new IntLiteralExpression(pos, BigInt(cast(string)lex.front.str));
178 }
179 if( lex.front.kind == Token.Kind.stringLiteral )
180 {
181 scope(exit) lex.popFront;
182 return new StrLiteralExpression(pos, lex.front.str);
183 }
184 if( tryEat("(") )
185 {
186 auto e = parseE();
187 eat(")", "after parenthesized expression");
188 return e;
189 }
190
191 if( tryEat("fun") )
192 {
193 eat("(", "after fun");
194 string[] params;
195 while(!tryEat(")"))
196 {
197 if( lex.empty ) {
198 auto e = ParserException.create(lex,"Unexpected EOF");
199 throw e;
200 }
201 if( lex.front.kind != Token.Kind.identifier ) {
202 auto e = ParserException.create(lex,"Identifier Expected for parameters");
203 throw e;
204 }
205 params ~= lex.front.str;
206 lex.popFront;
207 if( !tryEat(",") ) {
208 eat(")", "after function parameters");
209 break;
210 }
211 }
212 eat("{", "after function parameters");
213 Statement[] funbody;
214 while(!tryEat("}")) {
215 if( lex.empty ) {
216 auto e = ParserException.create(lex,"Unexpected EOF");
217 throw e;
218 }
219 funbody ~= parseStatement();
220 }
221 return new FunLiteralExpression(pos, params, funbody);
222 }
223 scope(exit) lex.popFront;
224 return new VarExpression(pos, lex.front.str);
225 }
226
227 private:
228 Lexer lex;
229
230 void eat(string kwd, lazy string msg)
231 {
232 if( !tryEat(kwd) )
233 {
234 auto e = ParserException.create(lex, "'"~kwd~"' is expected "~msg~" but '"
235 ~(lex.empty ? "EOF" : lex.front.str)~"' occured");
236 throw e;
237 }
238 }
239
240 bool tryEat(string kwd)
241 {
242 if( lex.empty || lex.front.kind!=Token.Kind.identifier || lex.front.str!=kwd )
243 return false;
244 lex.popFront;
245 return true;
246 }
247 }
248
249 unittest
250 {
251 auto p = parserFromString(`
252 var x = 100;
253 var y = 200;
254 `);
255 Program prog = p.parseProgram();
256 assert( prog.length == 2 );
257 auto p0 = cast(DeclStatement)prog[0];
258 auto p1 = cast(DeclStatement)prog[1];
259 assert( p0.var == "x" );
260 assert( p1.var == "y" );
261 assert( (cast(IntLiteralExpression)p0.expr).data == 100 );
262 assert( (cast(IntLiteralExpression)p1.expr).data == 200 );
263 }
264
265 unittest
266 {
267 auto p = parserFromString(`
268 var zzz = 100; # comment
269 zzz = zzz + zzz * "fo\no"; # comment
270 42;
271 `);
272
273 auto s0 = new DeclStatement(null, "zzz", new IntLiteralExpression(null, BigInt(100)));
274 auto s1 = new ExprStatement(null, new AssignExpression(null,
275 new VarExpression(null, "zzz"),
276 new FuncallExpression(null, new VarExpression(null,"+"),
277 new VarExpression(null, "zzz"),
278 new FuncallExpression(null, new VarExpression(null,"*"),
279 new VarExpression(null, "zzz"),
280 new StrLiteralExpression(null, "fo\\no")
281 ))));
282 auto s2 = new ExprStatement(null, new IntLiteralExpression(null, BigInt(42)));
283
284 Program prog = p.parseProgram();
285 assert( prog.length == 3 );
286 assert( prog[0] == s0 );
287 assert( prog[1] == s1 );
288 assert( prog[2] == s2 );
289 }
290
291 unittest
292 {
293 auto p = parserFromString(`
294 var f = fun(x,y){x+y;};
295 f(1,fun(abc){}(4));
296 `);
297 Program prog = p.parseProgram();
298 assert( prog.length == 2 );
299 assert( prog[0] == new DeclStatement(null, "f", new FunLiteralExpression(null,
300 ["x","y"], [new ExprStatement(null,
301 new FuncallExpression(null, new VarExpression(null, "+"),
302 new VarExpression(null, "x"), new VarExpression(null, "y")))]
303 )));
304 assert( prog[1] == new ExprStatement(null, new FuncallExpression(null,
305 new VarExpression(null, "f"),
306 new IntLiteralExpression(null, BigInt(1)),
307 new FuncallExpression(null,
308 new FunLiteralExpression(null, ["abc"], [
309 ]),
310 new IntLiteralExpression(null, BigInt(4))
311 ))));
312 }
313 unittest
314 {
315 auto p = parserFromString(`var x = 1; var f = fun(){x=x+1;}; f(); f(); x;`);
316 Program prog = p.parseProgram();
317 }