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