mildew.parser source code

1 /**
2  * This module implements the Parser struct, which generates Nodes from tokens that are used internally.
3  */
4 module mildew.parser;
5 
6 import std.conv: to, parse;
7 debug
8 {
9     import std.stdio;
10 }
11 
12 import mildew.exceptions: ScriptCompileException;
13 import mildew.lexer: Token;
14 import mildew.nodes;
15 import mildew.types.any: ScriptAny;
16 import mildew.types.func: ScriptFunction;
17 
18 private int unaryOpPrecedence(Token opToken, bool isPost = false)
19 {
20     if(opToken.isKeyword("typeof"))
21     {
22         if(!isPost)
23             return 17;
24     }
25 
26     // see grammar.txt for explanation of magic constants
27     switch(opToken.type)
28     {
29         // TODO handle ++, -- postfix
30         case Token.Type.BIT_NOT: 
31         case Token.Type.NOT:
32         case Token.Type.PLUS:
33         case Token.Type.DASH:
34             if(!isPost)
35                 return 17;
36             else
37                 return 0;
38         case Token.Type.INC:
39         case Token.Type.DEC:
40             if(isPost)
41                 return 18;
42             else
43                 return 17;
44         default: 
45             return 0;
46     }
47 }
48 
49 private int binaryOpPrecedence(Token opToken)
50 {
51     // TODO handle keywords in as 12 here
52     if(opToken.isKeyword("instanceof"))
53         return 12;
54 
55     // see grammar.txt for explanation of magic constants
56     switch(opToken.type)
57     {
58         case Token.Type.LBRACKET:
59         case Token.Type.DOT: 
60         case Token.Type.LPAREN:
61             return 20;
62         case Token.Type.POW:
63             return 16;
64         case Token.Type.STAR: 
65         case Token.Type.FSLASH: 
66         case Token.Type.PERCENT:
67             return 15;
68         case Token.Type.PLUS: 
69         case Token.Type.DASH:
70             return 14;
71         case Token.Type.BIT_LSHIFT: 
72         case Token.Type.BIT_RSHIFT: 
73         case Token.Type.BIT_URSHIFT:
74             return 13;
75         case Token.Type.LT: 
76         case Token.Type.LE: 
77         case Token.Type.GT: 
78         case Token.Type.GE:
79             return 12;
80         case Token.Type.EQUALS: 
81         case Token.Type.NEQUALS: 
82         case Token.Type.STRICT_EQUALS: 
83         case Token.Type.STRICT_NEQUALS:
84             return 11;
85         case Token.Type.BIT_AND:
86             return 10;
87         case Token.Type.BIT_XOR:
88             return 9;
89         case Token.Type.BIT_OR:
90             return 8;
91         case Token.Type.AND:
92             return 7;
93         case Token.Type.OR:
94             return 6;
95         case Token.Type.QUESTION:
96             return 4;
97         case Token.Type.ASSIGN:
98         case Token.Type.PLUS_ASSIGN:
99         case Token.Type.DASH_ASSIGN:
100             return 3;
101         default:
102             return 0;
103     }
104     // TODO null coalesce 5,yield 2, comma 1?
105 }
106 
107 private bool isBinaryOpLeftAssociative(in Token opToken)
108 {
109     switch(opToken.type)
110     {
111         case Token.Type.LBRACKET:
112         case Token.Type.DOT: 
113         case Token.Type.LPAREN:
114             return true;
115         case Token.Type.POW:
116             return false;
117         case Token.Type.STAR: 
118         case Token.Type.FSLASH: 
119         case Token.Type.PERCENT:
120             return true;
121         case Token.Type.PLUS: 
122         case Token.Type.DASH:
123             return true;
124         case Token.Type.BIT_LSHIFT: 
125         case Token.Type.BIT_RSHIFT: 
126         case Token.Type.BIT_URSHIFT:
127             return true;
128         case Token.Type.LT: 
129         case Token.Type.LE: 
130         case Token.Type.GT: 
131         case Token.Type.GE:
132             return true;
133         case Token.Type.EQUALS: 
134         case Token.Type.NEQUALS: 
135         case Token.Type.STRICT_EQUALS: 
136         case Token.Type.STRICT_NEQUALS:
137             return true;
138         case Token.Type.BIT_AND:
139             return true;
140         case Token.Type.BIT_XOR:
141             return true;
142         case Token.Type.BIT_OR:
143             return true;
144         case Token.Type.AND:
145             return true;
146         case Token.Type.OR:
147             return true;
148         case Token.Type.QUESTION:
149             return false;
150         case Token.Type.ASSIGN:
151         case Token.Type.PLUS_ASSIGN:
152         case Token.Type.DASH_ASSIGN:
153             return false;
154         default:
155             return false;
156     }   
157 }
158 
159 private bool tokenBeginsLoops(const Token tok)
160 {
161     return tok.type == Token.Type.LABEL 
162         || tok.isKeyword("while")
163         || tok.isKeyword("do")
164         || tok.isKeyword("for");
165 }
166 
167 /**
168  * The parser is used by the interpreter to generate a syntax tree out of tokens.
169  */
170 struct Parser
171 {
172     /**
173      * The constructor takes all tokens so that in the future, looking ahead for specific tokens
174      * can allow support for lambdas and other complex language features.
175      */
176     this(Token[] tokens)
177     {
178         _tokens = tokens;
179         nextToken(); // prime
180     }
181 
182     /**
183      * The main starting point. Also the "program" grammar rule. The generates a block statement
184      * node where the interpreter iterates through each statement and executes it.
185      */
186     BlockStatementNode parseProgram()
187     {
188         immutable lineNo = _currentToken.position.line;
189         auto statements = parseStatements(Token.Type.EOF);
190         return new BlockStatementNode(lineNo, statements);
191     }
192 
193 package:
194 
195     /// parse a single expression. See https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing
196     /// for algorithm.
197     ExpressionNode parseExpression(int minPrec = 1)
198     {      
199         ExpressionNode primaryLeft = null;
200 
201         immutable unOpPrec = _currentToken.unaryOpPrecedence;
202         if(unOpPrec > minPrec)
203         {
204             auto opToken = _currentToken;
205             nextToken();
206             primaryLeft = parsePrimaryExpression();
207             primaryLeft = new UnaryOpNode(opToken, primaryLeft);
208         }
209         else
210         {
211             primaryLeft = parsePrimaryExpression();
212         }
213 
214         while(_currentToken.binaryOpPrecedence >= minPrec || _currentToken.unaryOpPrecedence(true) >= minPrec)
215         {
216             if(_currentToken.unaryOpPrecedence(true) >= minPrec)
217             {
218                 // writeln("We must handle postfix " ~ _currentToken.symbol ~ " for " ~ primaryLeft.toString);
219                 primaryLeft = new PostfixOpNode(_currentToken, primaryLeft);
220                 nextToken();
221             }
222             else 
223             {
224                 auto opToken = _currentToken;
225                 immutable prec = opToken.binaryOpPrecedence;
226                 immutable isLeftAssoc = opToken.isBinaryOpLeftAssociative;
227                 immutable nextMinPrec = isLeftAssoc? prec + 1 : prec;
228                 nextToken();
229                 if(opToken.type == Token.Type.QUESTION)
230                 {
231                     // primaryLeft is our condition node
232                     auto onTrue = parseExpression();
233                     if(_currentToken.type != Token.Type.COLON)
234                         throw new ScriptCompileException("Expected ':' in terniary operator expression", _currentToken);
235                     nextToken();
236                     auto onFalse = parseExpression();
237                     primaryLeft = new TerniaryOpNode(primaryLeft, onTrue, onFalse);
238                 }
239                 else if(opToken.type == Token.Type.DOT)
240                 {
241                     auto right = parsePrimaryExpression();
242                     if(cast(VarAccessNode)right is null)
243                         throw new ScriptCompileException("Object members must be valid identifiers", _currentToken);
244                     if(unOpPrec != 0 && prec > unOpPrec)
245                     {
246                         auto uon = cast(UnaryOpNode)primaryLeft;
247                         primaryLeft = new UnaryOpNode(uon.opToken, new MemberAccessNode(uon.operandNode, right));
248                     }
249                     else
250                         primaryLeft = new MemberAccessNode(primaryLeft, right);
251                 }
252                 else if(opToken.type == Token.Type.LBRACKET)
253                 {
254                     auto index = parseExpression();
255                     if(_currentToken.type != Token.Type.RBRACKET)
256                         throw new ScriptCompileException("Missing ']'", _currentToken);
257                     nextToken();
258                     if(unOpPrec != 0 && prec > unOpPrec)
259                     {
260                         auto uon = cast(UnaryOpNode)primaryLeft;
261                         primaryLeft = new UnaryOpNode(uon.opToken, new ArrayIndexNode(uon.operandNode, index));
262                     }
263                     else
264                         primaryLeft = new ArrayIndexNode(primaryLeft, index);
265                 }
266                 else if(opToken.type == Token.Type.LPAREN)
267                 {
268                     auto params = parseCommaSeparatedExpressions(Token.Type.RPAREN);
269                     nextToken();
270                     if(unOpPrec != 0 && prec > unOpPrec)
271                     {
272                         auto uon = cast(UnaryOpNode)primaryLeft;
273                         primaryLeft = new UnaryOpNode(uon.opToken, new FunctionCallNode(uon.operandNode, params));
274                     }
275                     else
276                         primaryLeft = new FunctionCallNode(primaryLeft, params);
277                 }
278                 else 
279                 {
280                     ExpressionNode primaryRight = parseExpression(nextMinPrec);
281                     primaryLeft = new BinaryOpNode(opToken, primaryLeft, primaryRight);
282                 }
283             }
284         }
285 
286         return primaryLeft;
287     }
288 
289 private:
290 
291     /// parses a single statement
292     StatementNode parseStatement()
293         in { assert(_loopStack >= 0); } do
294     {
295         StatementNode statement;
296         immutable lineNumber = _currentToken.position.line;
297         // check for var declaration
298         if(_currentToken.isKeyword("var") || _currentToken.isKeyword("let") || _currentToken.isKeyword("const"))
299         {
300             statement = parseVarDeclarationStatement();
301         }
302         // check for {} block
303         else if(_currentToken.type == Token.Type.LBRACE)
304         {
305             // TODO: peek two tokens ahead for a ':' to indicate whether or not this is an object literal expression
306             nextToken();
307             auto statements = parseStatements(Token.Type.RBRACE);
308             nextToken();
309             statement = new BlockStatementNode(lineNumber, statements);
310         }
311         // check for if statement
312         else if(_currentToken.isKeyword("if"))
313         {
314             statement = parseIfStatement();
315         }
316         // check for switch
317         else if(_currentToken.isKeyword("switch"))
318         {
319             statement = parseSwitchStatement();
320         }
321         // check for loops
322         else if(_currentToken.tokenBeginsLoops())
323         {
324             statement = parseLoopStatement();
325         }
326         // break statement?
327         else if(_currentToken.isKeyword("break"))
328         {
329             if(_loopStack == 0 && _switchStack == 0)
330                 throw new ScriptCompileException("Break statements only allowed in loops or switch-case bodies", 
331                     _currentToken);
332             nextToken();
333             string label = "";
334             if(_currentToken.type == Token.Type.IDENTIFIER)
335             {
336                 label = _currentToken.text;
337                 nextToken();
338             }
339             if(_currentToken.type != Token.Type.SEMICOLON)
340                 throw new ScriptCompileException("Expected ';' after break", _currentToken);
341             nextToken();
342             statement = new BreakStatementNode(lineNumber, label);
343         }
344         // continue statement
345         else if(_currentToken.isKeyword("continue"))
346         {
347             if(_loopStack == 0)
348                 throw new ScriptCompileException("Continue statements only allowed in loops", _currentToken);
349             nextToken();
350             string label = "";
351             if(_currentToken.type == Token.Type.IDENTIFIER)
352             {
353                 label = _currentToken.text;
354                 nextToken();
355             }
356             if(_currentToken.type != Token.Type.SEMICOLON)
357                 throw new ScriptCompileException("Expected ';' after continue", _currentToken);
358             nextToken();
359             statement = new ContinueStatementNode(lineNumber, label);
360         }
361         // return statement with optional expression
362         else if(_currentToken.isKeyword("return"))
363         {
364             nextToken();
365             ExpressionNode expression = null;
366             if(_currentToken.type != Token.Type.SEMICOLON)
367                 expression = parseExpression();
368             if(_currentToken.type != Token.Type.SEMICOLON)
369                 throw new ScriptCompileException("Expected ';' after return", _currentToken);
370             nextToken();
371             statement = new ReturnStatementNode(lineNumber, expression);
372         }
373         else if(_currentToken.isKeyword("function"))
374         {
375             statement = parseFunctionDeclarationStatement();
376         }
377         else if(_currentToken.isKeyword("throw"))
378         {
379             nextToken();
380             auto expr = parseExpression();
381             if(_currentToken.type != Token.Type.SEMICOLON)
382                 throw new ScriptCompileException("Expected ';' after throw expression", _currentToken);
383             nextToken();
384             statement = new ThrowStatementNode(lineNumber, expr);
385         }
386         else if(_currentToken.isKeyword("try"))
387         {
388             statement = parseTryCatchBlockStatement();
389         }
390         else if(_currentToken.isKeyword("delete"))
391         {
392             nextToken();
393             auto tok = _currentToken;
394             auto expression = parseExpression();
395             if(cast(MemberAccessNode)expression is null && cast(ArrayIndexNode)expression is null)
396                 throw new ScriptCompileException("Invalid operand for delete operation", tok);
397             statement = new DeleteStatementNode(lineNumber, expression);
398         }
399         else if(_currentToken.isKeyword("class"))
400         {
401             statement = parseClassDeclaration();
402         }
403         else if(_currentToken.isKeyword("super"))
404         {
405             statement = parseSuperCallStatement();
406         }
407         else // for now has to be one expression followed by semicolon or EOF
408         {
409             if(_currentToken.type == Token.Type.SEMICOLON)
410             {
411                 // empty statement
412                 statement = new ExpressionStatementNode(lineNumber, null);
413                 nextToken();
414             }
415             else 
416             {
417                 auto expression = parseExpression();
418                 if(_currentToken.type != Token.Type.SEMICOLON && _currentToken.type != Token.Type.EOF)
419                     throw new ScriptCompileException("Expected semicolon after expression", _currentToken);
420                 nextToken(); // eat semicolon
421                 statement = new ExpressionStatementNode(lineNumber, expression);
422             }
423         }
424         return statement;
425     }
426 
427     ExpressionNode parsePrimaryExpression()
428     {
429         import std.conv: to, ConvException;
430 
431         ExpressionNode left = null;
432         switch(_currentToken.type)
433         {
434             case Token.Type.LPAREN:
435                 nextToken();
436                 left = parseExpression();
437                 if(_currentToken.type != Token.Type.RPAREN)
438                     throw new ScriptCompileException("Missing ')' in primary expression", _currentToken);
439                 nextToken();
440                 break;
441             case Token.Type.LBRACE:
442                 left = parseObjectLiteral();
443                 break;
444             case Token.Type.DOUBLE:
445                 if(_currentToken.literalFlag == Token.LiteralFlag.NONE)
446                     left = new LiteralNode(_currentToken, ScriptAny(to!double(_currentToken.text)));
447                 else
448                     throw new ScriptCompileException("Malformed floating point token detected", _currentToken);
449                 nextToken();
450                 break;
451             case Token.Type.INTEGER:
452                 try 
453                 {
454                     if(_currentToken.literalFlag == Token.LiteralFlag.NONE)
455                         left = new LiteralNode(_currentToken, ScriptAny(to!long(_currentToken.text)));
456                     else if(_currentToken.literalFlag == Token.LiteralFlag.HEXADECIMAL)
457                         left = new LiteralNode(_currentToken, ScriptAny(_currentToken.text[2..$].to!long(16)));
458                     else if(_currentToken.literalFlag == Token.LiteralFlag.OCTAL)
459                         left = new LiteralNode(_currentToken, ScriptAny(_currentToken.text[2..$].to!long(8)));
460                     else if(_currentToken.literalFlag == Token.LiteralFlag.BINARY)
461                         left = new LiteralNode(_currentToken, ScriptAny(_currentToken.text[2..$].to!long(2)));
462                 }
463                 catch(ConvException ex)
464                 {
465                     throw new ScriptCompileException("Integer literal is too long", _currentToken);
466                 }
467                 nextToken();
468                 break;
469             case Token.Type.STRING:
470                 left = new LiteralNode(_currentToken, ScriptAny(_currentToken.text));
471                 nextToken();
472                 break;
473             case Token.Type.KEYWORD:
474                 if(_currentToken.text == "true" || _currentToken.text == "false")
475                 {
476                     left = new LiteralNode(_currentToken, ScriptAny(to!bool(_currentToken.text)));
477                     nextToken();
478                 }
479                 else if(_currentToken.text == "null")
480                 {
481                     left = new LiteralNode(_currentToken, ScriptAny(null));
482                     nextToken();
483                 }
484                 else if(_currentToken.text == "undefined")
485                 {
486                     left = new LiteralNode(_currentToken, ScriptAny.UNDEFINED);
487                     nextToken();
488                 }
489                 else if(_currentToken.text == "function") // function literal
490                 {
491                     nextToken();
492                     if(_currentToken.type != Token.Type.LPAREN)
493                         throw new ScriptCompileException("Argument list expected after anonymous function", 
494                             _currentToken);
495                     nextToken();
496                     string[] argNames = [];
497                     while(_currentToken.type != Token.Type.RPAREN)
498                     {
499                         if(_currentToken.type != Token.Type.IDENTIFIER)
500                             throw new ScriptCompileException("Argument list must be valid identifier", _currentToken);
501                         argNames ~= _currentToken.text;
502                         nextToken();
503                         if(_currentToken.type == Token.Type.COMMA)
504                             nextToken();
505                         else if(_currentToken.type !=  Token.Type.RPAREN)
506                             throw new ScriptCompileException("Missing ')' after argument list", _currentToken);
507                     }
508                     nextToken(); // eat the )
509                     if(_currentToken.type != Token.Type.LBRACE)
510                         throw new ScriptCompileException("Expected '{' before anonymous function body", _currentToken);
511                     nextToken(); // eat the {
512                     auto statements = parseStatements(Token.Type.RBRACE);
513                     nextToken();
514                     // auto func = new ScriptFunction(name, argNames, statements, null);
515                     left = new FunctionLiteralNode(argNames, statements);
516                 }
517                 else if(_currentToken.text == "class")
518                 {
519                     left = parseClassExpression();
520                 }
521                 else if(_currentToken.text == "new")
522                 {
523                     immutable newToken = _currentToken;
524                     nextToken();
525                     auto expression = parseExpression();
526                     auto fcn = cast(FunctionCallNode)expression;
527                     if(fcn is null)
528                     {
529                         // if this isn't a function call, turn it into one
530                         fcn = new FunctionCallNode(expression, [], true);
531                     }
532                     fcn.returnThis = true;
533                     left = new NewExpressionNode(fcn);                    
534                 }
535                 else
536                     throw new ScriptCompileException("Unexpected keyword in primary expression", _currentToken);
537                 break;
538                 // TODO function
539             case Token.Type.IDENTIFIER:
540                 left = new VarAccessNode(_currentToken);
541                 nextToken();
542                 break;
543             case Token.Type.LBRACKET: // an array
544             {
545                 nextToken(); // eat the [
546                 auto values = parseCommaSeparatedExpressions(Token.Type.RBRACKET);
547                 nextToken(); // eat the ]
548                 left = new ArrayLiteralNode(values);
549                 break;
550             }
551             default:
552                 throw new ScriptCompileException("Unexpected token in primary expression", _currentToken);
553         }
554         return left;
555     }
556     
557     /// after class ? extend base this can begin
558     ClassDefinition parseClassDefinition(Token classToken, string className, ExpressionNode baseClass)
559     {
560         if(_currentToken.type != Token.Type.LBRACE)
561             throw new ScriptCompileException("Expected '{' after class", _currentToken);
562         nextToken();
563         FunctionLiteralNode constructor;
564         string[] methodNames;
565         FunctionLiteralNode[] methods;
566         string[] getMethodNames;
567         FunctionLiteralNode[] getMethods;
568         string[] setMethodNames;
569         FunctionLiteralNode[] setMethods;
570         string[] staticMethodNames;
571         FunctionLiteralNode[] staticMethods;
572         enum PropertyType { NONE, GET, SET, STATIC }
573         while(_currentToken.type != Token.Type.RBRACE && _currentToken.type != Token.Type.EOF)
574         {
575             PropertyType ptype = PropertyType.NONE;
576             string currentMethodName = "";
577             // could be a get or set
578             if(_currentToken.isIdentifier("get"))
579             {
580                 ptype = PropertyType.GET;
581                 nextToken();
582             }
583             else if(_currentToken.isIdentifier("set"))
584             {
585                 ptype = PropertyType.SET;
586                 nextToken();
587             }
588             else if(_currentToken.isIdentifier("static"))
589             {
590                 ptype = PropertyType.STATIC;
591                 nextToken();
592             }
593             // then an identifier
594             if(_currentToken.type != Token.Type.IDENTIFIER)
595                 throw new ScriptCompileException("Method names must be valid identifiers", _currentToken);
596             currentMethodName = _currentToken.text;
597             nextToken();
598             // then a (
599             if(_currentToken.type != Token.Type.LPAREN)
600                 throw new ScriptCompileException("Expected '(' after method name", _currentToken);
601             nextToken();
602             string[] argNames;
603             while(_currentToken.type != Token.Type.RPAREN)
604             {
605                 if(_currentToken.type != Token.Type.IDENTIFIER)
606                     throw new ScriptCompileException("Method arguments must be valid identifiers", _currentToken);
607                 argNames ~= _currentToken.text;
608                 nextToken();
609                 if(_currentToken.type == Token.Type.COMMA)
610                     nextToken();
611                 else if(_currentToken.type != Token.Type.RPAREN)
612                     throw new ScriptCompileException("Method arguments must be separated by ','", _currentToken);
613             }
614             nextToken(); // eat the )
615             // then a {
616             if(_currentToken.type != Token.Type.LBRACE)
617                 throw new ScriptCompileException("Method bodies must begin with '{'", _currentToken);
618             nextToken();
619             auto statements = parseStatements(Token.Type.RBRACE);
620             nextToken(); // eat }
621             // now we have a method but if this is the constructor
622             if(currentMethodName == "constructor")
623             {
624                 if(ptype != PropertyType.NONE)
625                     throw new ScriptCompileException("Get and set not allowed for constructor", classToken);
626                 if(constructor !is null)
627                     throw new ScriptCompileException("Classes may only have one constructor", classToken);
628                 // if this is extending a class it MUST have ONE super call
629                 if(baseClass !is null)
630                 {
631                     ulong numSupers = 0;
632                     foreach(stmt ; statements)
633                     {
634                         if(cast(SuperCallStatementNode)stmt)
635                             numSupers++;
636                     }
637                     if(numSupers != 1)
638                         throw new ScriptCompileException("Derived class constructors must have one super call", 
639                                 classToken);
640                 }
641                 constructor = new FunctionLiteralNode(argNames, statements);
642             }
643             else // it's a normal method or getter/setter
644             {
645                 if(ptype == PropertyType.NONE)
646                 {
647                     methods ~= new FunctionLiteralNode(argNames, statements);
648                     methodNames ~= currentMethodName;
649                 }
650                 else if(ptype == PropertyType.GET)
651                 {
652                     getMethods ~= new FunctionLiteralNode(argNames, statements);
653                     getMethodNames ~= currentMethodName;                    
654                 }
655                 else if(ptype == PropertyType.SET)
656                 {
657                     setMethods ~= new FunctionLiteralNode(argNames, statements);
658                     setMethodNames ~= currentMethodName;                    
659                 }
660                 else if(ptype == PropertyType.STATIC)
661                 {
662                     staticMethods ~= new FunctionLiteralNode(argNames, statements);
663                     staticMethodNames ~= currentMethodName;
664                 }
665             }
666         }
667         nextToken(); // eat the class body }
668 
669         // check for duplicate methods
670         bool[string] mnameMap;
671         foreach(mname ; methodNames)
672         {
673             if(mname in mnameMap)
674                 throw new ScriptCompileException("Duplicate methods are not allowed", classToken);
675             mnameMap[mname] = true;
676         }
677 
678         if(baseClass !is null)
679             _baseClassStack = _baseClassStack[0..$-1];
680        	return new ClassDefinition(className, constructor, methodNames, methods, getMethodNames, getMethods, 
681 	   		setMethodNames, setMethods, staticMethodNames, staticMethods, baseClass);
682     }
683 
684     ClassLiteralNode parseClassExpression()
685     {
686         immutable classToken = _currentToken;
687         nextToken();
688         immutable className = "<anonymous class>";
689         ExpressionNode baseClass = null;
690         if(_currentToken.isKeyword("extends"))
691         {
692             nextToken();
693             baseClass = parseExpression(); // let's hope this is an expression that results in a ScriptFunction value
694             _baseClassStack ~= baseClass;
695         }
696         auto classDef = parseClassDefinition(classToken, className, baseClass);
697         return new ClassLiteralNode(classDef);
698     }
699 
700     /// parses multiple statements until reaching stop
701     StatementNode[] parseStatements(in Token.Type stop)
702     {
703         StatementNode[] statements;
704         while(_currentToken.type != stop && _currentToken.type != Token.Type.EOF)
705         {
706             statements ~= parseStatement();
707             // each statement parse should eat the semicolon or } so there's nothing to do here
708         }
709         return statements;
710     }
711 
712     VarDeclarationStatementNode parseVarDeclarationStatement(bool consumeSemicolon = true)
713     {
714         auto specifier = _currentToken;
715         nextToken();
716         auto expressions = parseCommaSeparatedExpressions(Token.Type.SEMICOLON);
717         // make sure all expressions are valid BinaryOpNodes or VarAccessNodes
718         foreach(expression; expressions)
719         {
720             if(auto node = cast(BinaryOpNode)expression)
721             {
722                 if(!cast(VarAccessNode)node.leftNode)
723                     throw new ScriptCompileException("Invalid assignment node", _currentToken);
724             }
725             else if(!cast(VarAccessNode)expression)
726             {
727                 throw new ScriptCompileException("Invalid variable name in declaration", _currentToken);
728             }
729         }
730         if(consumeSemicolon)
731             nextToken(); // eat semicolon
732         return new VarDeclarationStatementNode(specifier, expressions);
733     }
734 
735     IfStatementNode parseIfStatement()
736     {
737         immutable lineNumber = _currentToken.position.line;
738         nextToken();
739         if(_currentToken.type != Token.Type.LPAREN)
740             throw new ScriptCompileException("Expected '(' after if keyword", _currentToken);
741         nextToken();
742         auto condition = parseExpression();
743         if(_currentToken.type != Token.Type.RPAREN)
744             throw new ScriptCompileException("Expected ')' after if condition", _currentToken);
745         nextToken();
746         auto ifTrueStatement = parseStatement();
747         StatementNode elseStatement = null;
748         if(_currentToken.isKeyword("else"))
749         {
750             nextToken();
751             elseStatement = parseStatement();
752         }
753         return new IfStatementNode(lineNumber, condition, ifTrueStatement, elseStatement);
754     }
755 
756     StatementNode parseLoopStatement()
757     {
758         string label = "";
759         if(_currentToken.type == Token.Type.LABEL)
760         {
761             label = _currentToken.text;
762             nextToken();
763         }
764         StatementNode statement;
765         if(_currentToken.isKeyword("while"))
766         {
767             ++_loopStack;
768             statement = parseWhileStatement(label);
769             --_loopStack;
770         }
771         // check for do-while statement TODO check for label
772         else if(_currentToken.isKeyword("do"))
773         {
774             ++_loopStack;
775             statement = parseDoWhileStatement(label);
776             --_loopStack;
777         }
778         // check for for loop TODO check label
779         else if(_currentToken.isKeyword("for"))
780         {
781             ++_loopStack;
782             statement = parseForStatement(label);
783             --_loopStack;
784         }
785         return statement;
786     }
787 
788     WhileStatementNode parseWhileStatement(string label = "")
789     {
790         immutable lineNumber = _currentToken.position.line;
791         nextToken();
792         if(_currentToken.type != Token.Type.LPAREN)
793             throw new ScriptCompileException("Expected '(' after while keyword", _currentToken);
794         nextToken();
795         auto condition = parseExpression();
796         if(_currentToken.type != Token.Type.RPAREN)
797             throw new ScriptCompileException("Expected ')' after while condition", _currentToken);
798         nextToken();
799         auto loopBody = parseStatement();
800         return new WhileStatementNode(lineNumber, condition, loopBody, label);
801     }
802 
803     DoWhileStatementNode parseDoWhileStatement(string label = "")
804     {
805         immutable lineNumber = _currentToken.position.line;
806         nextToken();
807         auto loopBody = parseStatement();
808         if(!_currentToken.isKeyword("while"))
809             throw new ScriptCompileException("Expected while keyword after do statement", _currentToken);
810         nextToken();
811         if(_currentToken.type != Token.Type.LPAREN)
812             throw new ScriptCompileException("Expected '(' before do-while condition", _currentToken);
813         nextToken();
814         auto condition = parseExpression();
815         if(_currentToken.type != Token.Type.RPAREN)
816             throw new ScriptCompileException("Expected ')' after do-while condition", _currentToken);
817         nextToken();
818         if(_currentToken.type != Token.Type.SEMICOLON)
819             throw new ScriptCompileException("Expected ';' after do-while statement", _currentToken);
820         nextToken();
821         return new DoWhileStatementNode(lineNumber, loopBody, condition, label);
822     }
823 
824     StatementNode parseForStatement(string label = "")
825     {
826         immutable lineNumber = _currentToken.position.line;
827         nextToken();
828         if(_currentToken.type != Token.Type.LPAREN)
829             throw new ScriptCompileException("Expected '(' after for keyword", _currentToken);
830         nextToken();
831         VarDeclarationStatementNode decl = null;
832         if(_currentToken.type != Token.Type.SEMICOLON)
833             decl = parseVarDeclarationStatement(false);
834         if(_currentToken.isKeyword("of") || _currentToken.isKeyword("in"))
835         {
836             // first we need to validate the VarDeclarationStatementNode to make sure it only consists
837             // of let or const and VarAccessNodes
838             if(decl is null)
839                 throw new ScriptCompileException("Invalid for of statement", _currentToken);
840             Token qualifier;
841             VarAccessNode[] vans;
842             if(decl.qualifier.text != "const" && decl.qualifier.text != "let")
843                 throw new ScriptCompileException("Global variable declaration invalid in for of statement",
844                     decl.qualifier);
845             foreach(va ; decl.varAccessOrAssignmentNodes)
846             {
847                 auto valid = cast(VarAccessNode)va;
848                 if(valid is null)
849                     throw new ScriptCompileException("Invalid variable declaration in for of statement", 
850                         _currentToken);
851                 vans ~= valid;
852             }
853             nextToken();
854             auto objToIterateExpr = parseExpression();
855             if(_currentToken.type != Token.Type.RPAREN)
856                 throw new ScriptCompileException("Expected ')' after array or object", _currentToken);
857             nextToken();
858             auto bodyStatement = parseStatement();
859             return new ForOfStatementNode(lineNumber, qualifier, vans, objToIterateExpr, bodyStatement, label);
860         }
861         else if(_currentToken.type == Token.Type.SEMICOLON)
862         {
863             nextToken();
864             ExpressionNode condition = null;
865             if(_currentToken.type != Token.Type.SEMICOLON)
866             {
867                 condition = parseExpression();
868                 if(_currentToken.type != Token.Type.SEMICOLON)
869                     throw new ScriptCompileException("Expected ';' after for condition", _currentToken);
870             }
871             else
872             {
873                 condition = new LiteralNode(_currentToken, ScriptAny(true));
874             }
875             nextToken();
876             ExpressionNode increment = null;
877             if(_currentToken.type != Token.Type.RPAREN)
878             {
879                 increment = parseExpression();
880             }
881             else
882             {
883                 increment = new LiteralNode(_currentToken, ScriptAny(true));
884             }
885             if(_currentToken.type != Token.Type.RPAREN)
886                 throw new ScriptCompileException("Expected ')' before for loop body", _currentToken);
887             nextToken();
888             auto bodyNode = parseStatement();
889             return new ForStatementNode(lineNumber, decl, condition, increment, bodyNode, label);
890         }
891         else
892             throw new ScriptCompileException("Invalid for statement", _currentToken);
893     }
894 
895     FunctionDeclarationStatementNode parseFunctionDeclarationStatement()
896     {
897         import std.algorithm: uniq, count;
898         immutable lineNumber = _currentToken.position.line;
899         nextToken();
900         if(_currentToken.type != Token.Type.IDENTIFIER)
901             throw new ScriptCompileException("Expected identifier after function keyword", _currentToken);
902         string name = _currentToken.text;
903         nextToken();
904         if(_currentToken.type != Token.Type.LPAREN)
905             throw new ScriptCompileException("Expected '(' after function name", _currentToken);
906         nextToken();
907         string[] argNames = [];
908         while(_currentToken.type != Token.Type.RPAREN)
909         {
910             if(_currentToken.type != Token.Type.IDENTIFIER)
911                 throw new ScriptCompileException("Function argument names must be valid identifiers", _currentToken);
912             argNames ~= _currentToken.text;
913             nextToken();
914             if(_currentToken.type == Token.Type.COMMA)
915                 nextToken();
916             else if(_currentToken.type != Token.Type.RPAREN)
917                 throw new ScriptCompileException("Function argument names must be separated by comma", _currentToken);
918         }
919         nextToken(); // eat the )
920 
921         // make sure there are no duplicate parameter names
922         if(argNames.uniq.count != argNames.length)
923             throw new ScriptCompileException("Function argument names must be unique", _currentToken);
924 
925         if(_currentToken.type != Token.Type.LBRACE)
926             throw new ScriptCompileException("Function definition must begin with '{'", _currentToken);
927         nextToken();
928         auto statements = parseStatements(Token.Type.RBRACE);
929         nextToken(); // eat the }
930         return new FunctionDeclarationStatementNode(lineNumber, name, argNames, statements);
931     }
932 
933     TryCatchBlockStatementNode parseTryCatchBlockStatement()
934     {
935         immutable lineNumber = _currentToken.position.line;
936         nextToken(); // eat the 'try'
937         auto tryBlock = parseStatement();
938         if(!_currentToken.isKeyword("catch"))
939             throw new ScriptCompileException("Catch block required after try block", _currentToken);
940         nextToken(); // eat the catch
941         if(_currentToken.type != Token.Type.LPAREN)
942             throw new ScriptCompileException("Missing '(' after catch", _currentToken);
943         nextToken(); // eat the '('
944         if(_currentToken.type != Token.Type.IDENTIFIER)
945             throw new ScriptCompileException("Name of exception required in catch block", _currentToken);
946         auto name = _currentToken.text;
947         nextToken();
948         if(_currentToken.type != Token.Type.RPAREN)
949             throw new ScriptCompileException("Missing ')' after exception name", _currentToken);
950         nextToken(); // eat the ')'
951         auto catchBlock = parseStatement();
952         return new TryCatchBlockStatementNode(lineNumber, tryBlock, name, catchBlock);
953     }
954 
955     ObjectLiteralNode parseObjectLiteral()
956     {
957         nextToken(); // eat the {
958         string[] keys = [];
959         ExpressionNode[] valueExpressions = [];
960         while(_currentToken.type != Token.Type.RBRACE)
961         {
962             // first must be an identifier token or string literal token
963             immutable idToken = _currentToken;
964             if(_currentToken.type != Token.Type.IDENTIFIER && _currentToken.type != Token.Type.STRING
965                 && _currentToken.type != Token.Type.LABEL)
966                 throw new ScriptCompileException("Invalid key for object literal", _currentToken);
967             keys ~= _currentToken.text;
968 
969             nextToken();
970             // next must be a :
971             if(idToken.type != Token.Type.LABEL)
972             {
973                 if(_currentToken.type != Token.Type.COLON)
974                     throw new ScriptCompileException("Expected ':' after key in object literal", _currentToken);
975                 nextToken();
976             }
977             // next can be any valid expression
978             valueExpressions ~= parseExpression();
979             // if next is not a comma it must be a closing brace to exit
980             if(_currentToken.type == Token.Type.COMMA)
981                 nextToken();
982             else if(_currentToken.type != Token.Type.RBRACE)
983                 throw new ScriptCompileException("Key value pairs must be separated by ','", _currentToken);
984         }
985         nextToken(); // eat the }
986         if(keys.length != valueExpressions.length)
987             throw new ScriptCompileException("Number of keys must match values in object literal", _currentToken);
988         return new ObjectLiteralNode(keys, valueExpressions);
989     }
990 
991     ClassDeclarationStatementNode parseClassDeclaration()
992     {
993         immutable lineNumber = _currentToken.position.line;
994         immutable classToken = _currentToken;
995         nextToken();
996         if(_currentToken.type != Token.Type.IDENTIFIER)
997             throw new ScriptCompileException("Class name must be valid identifier", _currentToken);
998         auto className = _currentToken.text;
999         nextToken();
1000         ExpressionNode baseClass = null;
1001         if(_currentToken.isKeyword("extends"))
1002         {
1003             nextToken();
1004             baseClass = parseExpression(); // let's hope this is an expression that results in a ScriptFunction value
1005             _baseClassStack ~= baseClass;
1006         }
1007         auto classDef = parseClassDefinition(classToken, className, baseClass);
1008         return new ClassDeclarationStatementNode(lineNumber, classDef);
1009     }
1010 
1011     SuperCallStatementNode parseSuperCallStatement()
1012     {
1013         immutable lineNumber = _currentToken.position.line;
1014         if(_baseClassStack.length == 0)
1015             throw new ScriptCompileException("Super keyword may only be used in constructors of derived classes", 
1016                     _currentToken);
1017         nextToken();
1018         if(_currentToken.type != Token.Type.LPAREN)
1019             throw new ScriptCompileException("Super call parameters must begin with '('", _currentToken);
1020         nextToken();
1021         auto expressions = parseCommaSeparatedExpressions(Token.Type.RPAREN);
1022         nextToken(); // eat the )
1023         if(_currentToken.type != Token.Type.SEMICOLON)
1024             throw new ScriptCompileException("Missing ';' at end of super statement", _currentToken);
1025         nextToken();
1026         size_t topClass = _baseClassStack.length - 1; // @suppress(dscanner.suspicious.length_subtraction)
1027         return new SuperCallStatementNode(lineNumber, _baseClassStack[topClass], expressions);
1028     }
1029 
1030     SwitchStatementNode parseSwitchStatement() 
1031         in { assert(_switchStack >= 0); } do
1032     {
1033         import std.variant: Variant;
1034         import mildew.interpreter: Interpreter;
1035         import mildew.exceptions: ScriptRuntimeException;
1036 
1037         ++_switchStack;
1038         immutable lineNumber = _currentToken.position.line;
1039         immutable switchToken = _currentToken;
1040         nextToken();
1041         if(_currentToken.type != Token.Type.LPAREN)
1042             throw new ScriptCompileException("Expected '(' after switch keyword", _currentToken);
1043         nextToken();
1044         auto expression = parseExpression();
1045         if(_currentToken.type != Token.Type.RPAREN)
1046             throw new ScriptCompileException("Expected ')' after switch expression", _currentToken);
1047         nextToken();
1048         if(_currentToken.type != Token.Type.LBRACE)
1049             throw new ScriptCompileException("Expected '{' to begin switch body", _currentToken);
1050         nextToken();
1051         bool caseStarted = false;
1052         size_t statementCounter = 0;
1053         StatementNode[] statementNodes;
1054         size_t defaultStatementID = size_t.max;
1055         size_t[ScriptAny] jumpTable;
1056         Interpreter interpreter = new Interpreter();
1057         while(_currentToken.type != Token.Type.RBRACE)
1058         {
1059             if(_currentToken.isKeyword("case"))
1060             {
1061                 nextToken();
1062                 caseStarted = true;
1063                 auto caseExpression = parseExpression();
1064                 // it has to be evaluatable at compile time
1065                 auto vr = caseExpression.accept(interpreter).get!(Interpreter.VisitResult);
1066                 if(vr.exception !is null || vr.result == ScriptAny.UNDEFINED)
1067                     throw new ScriptCompileException("Case expression must be determined at compile time", switchToken);
1068                 if(_currentToken.type != Token.Type.COLON)
1069                     throw new ScriptCompileException("Expected ':' after case expression", _currentToken);
1070                 nextToken();
1071                 if(vr.result in jumpTable)
1072                     throw new ScriptCompileException("Duplicate case entries not allowed", switchToken);
1073                 jumpTable[vr.result] = statementCounter;
1074             }
1075             else if(_currentToken.isKeyword("default"))
1076             {
1077                 caseStarted = true;
1078                 nextToken();
1079                 if(_currentToken.type != Token.Type.COLON)
1080                     throw new ScriptCompileException("':' expected after default keyword", _currentToken);
1081                 nextToken();
1082                 defaultStatementID = statementCounter;
1083             }
1084             else
1085             {
1086                 if(!caseStarted)
1087                     throw new ScriptCompileException("Case condition required before any statements", _currentToken);
1088                 statementNodes ~= parseStatement();
1089                 ++statementCounter;
1090             }
1091         }
1092         nextToken(); // consume }
1093         --_switchStack;
1094         return new SwitchStatementNode(lineNumber, expression, new SwitchBody(statementNodes, defaultStatementID, 
1095             jumpTable));
1096     }
1097 
1098     ExpressionNode[] parseCommaSeparatedExpressions(in Token.Type stop)
1099     {
1100         ExpressionNode[] expressions;
1101 
1102         while(_currentToken.type != stop && _currentToken.type != Token.Type.EOF && !_currentToken.isKeyword("of")
1103           && !_currentToken.isKeyword("in"))
1104         {
1105             auto expression = parseExpression();
1106             expressions ~= expression;
1107             if(_currentToken.type == Token.Type.COMMA)
1108                 nextToken();
1109             else if(_currentToken.type != stop && !_currentToken.isKeyword("of")
1110               && !_currentToken.isKeyword("in"))
1111                 throw new ScriptCompileException("Comma separated list items must be separated by ','", _currentToken);
1112         }
1113 
1114         return expressions;
1115     }
1116 
1117     void nextToken()
1118     {
1119         if(_tokenIndex >= _tokens.length)
1120             _currentToken = Token(Token.Type.EOF);
1121         else
1122             _currentToken = _tokens[_tokenIndex++];
1123     }
1124 
1125     Token[] _tokens;
1126     size_t _tokenIndex = 0;
1127     Token _currentToken;
1128     int _loopStack = 0;
1129     int _switchStack = 0;
1130     ExpressionNode[] _baseClassStack; // in case we have nested class declarations
1131 }