1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
7 /** Parses a stream of lexed tokens into a tree of CompiledFunction's */
8 class Parser extends Lexer implements ByteCodes {
11 // Constructors //////////////////////////////////////////////////////
13 public Parser(Reader r, String sourceName, int line) throws IOException { super(r, sourceName, line); }
16 public static void main(String[] s) throws Exception {
17 CompiledFunction block = new CompiledFunction("stdin", 0, new InputStreamReader(System.in), null);
18 if (block == null) return;
19 System.out.println(block);
23 // Statics ////////////////////////////////////////////////////////////
25 static byte[] precedence = new byte[MAX_TOKEN + 1];
26 static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
28 isRightAssociative[ASSIGN] = true;
30 precedence[ASSIGN] = 1;
32 precedence[COMMA] = 3;
33 precedence[OR] = precedence[AND] = 4;
34 precedence[GT] = precedence[GE] = 5;
35 precedence[BITOR] = 6;
36 precedence[BITXOR] = 7;
37 precedence[BITAND] = 8;
38 precedence[EQ] = precedence[NE] = 9;
39 precedence[LT] = precedence[LE] = 10;
40 precedence[SHEQ] = precedence[SHNE] = 11;
41 precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
42 precedence[ADD] = precedence[SUB] = 13;
43 precedence[MUL] = precedence[DIV] = precedence[MOD] = 14;
44 precedence[BITNOT] = 15;
45 precedence[INC] = precedence[DEC] = 16;
52 // Parsing Logic /////////////////////////////////////////////////////////
54 /** gets a token and throws an exception if it is not <tt>code</tt> */
55 public void consume(int code) throws IOException {
56 if (getToken() != code)
57 throw new ParserException("expected " + codeToString[code] + ", got " + (op == -1 ? "EOF" : codeToString[op]));
60 /** append the largest possible expression containing no operators of precedence below <tt>minPrecedence</tt> */
61 public void startExpr(int minPrecedence, CompiledFunction appendTo) throws IOException {
63 CompiledFunction b = appendTo;
67 case NUMBER: continueExpr(b.add(line, CompiledFunction.LITERAL, number), minPrecedence); return;
68 case STRING: continueExpr(b.add(line, CompiledFunction.LITERAL, string), minPrecedence); return;
69 case THIS: continueExpr(b.add(line, TOPSCOPE, null), minPrecedence); return;
70 case NULL: continueExpr(b.add(line, CompiledFunction.LITERAL, null), minPrecedence); return;
71 case TRUE: case FALSE: continueExpr(b.add(line, CompiledFunction.LITERAL, new Boolean(tok == TRUE)), minPrecedence); return;
73 b.add(line, ARRAY, new Integer(0));
79 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
80 b.add(line, LITERAL, new Integer(i++));
81 if (size == b.size()) b.add(line, LITERAL, null);
84 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
90 b.add(line, CompiledFunction.LITERAL, new Double(number.doubleValue() * -1));
91 continueExpr(b, minPrecedence);
97 continueExpr(b, minPrecedence);
100 case INC: case DEC: {
102 startExpr(precedence[tok], b);
103 b.set(b.size() - 1, tok, new Boolean(true));
104 continueExpr(b, minPrecedence);
107 case BANG: case BITNOT: case TYPEOF: {
108 startExpr(precedence[tok], b);
110 continueExpr(b, minPrecedence);
114 b.add(line, OBJECT, null);
115 if (peekToken() != RC) while(true) {
116 if (peekToken() != NAME && peekToken() != STRING) throw new Error("expected NAME or STRING");
118 b.add(line, LITERAL, string);
123 if (peekToken() == RC) break;
125 if (peekToken() == RC) break;
128 continueExpr(b, minPrecedence);
132 String name = string;
133 if (peekToken() == ASSIGN) {
135 b.add(line, TOPSCOPE);
136 b.add(line, CompiledFunction.LITERAL, name);
137 startExpr(minPrecedence, b);
138 b.add(line, CompiledFunction.PUT);
139 b.add(line, CompiledFunction.SWAP);
140 b.add(line, CompiledFunction.POP);
142 b.add(line, TOPSCOPE);
143 b.add(line, CompiledFunction.LITERAL, name);
144 b.add(line, CompiledFunction.GET);
146 continueExpr(b, minPrecedence);
152 CompiledFunction b2 = new CompiledFunction(sourceName, line, null);
153 b2.add(line, TOPSCOPE);
155 b2.add(line, LITERAL, "arguments");
156 b2.add(line, LITERAL, "arguments");
157 b2.add(line, DECLARE);
162 if (peekToken() == RP) consume(RP);
164 if (peekToken() == COMMA) {
171 b2.add(line, LITERAL, string);
172 b2.add(line, DECLARE);
174 // retrieve it from the arguments array
175 b2.add(line, LITERAL, new Integer(numArgs));
176 b2.add(line, GET_PRESERVE);
180 // put it to the current scope
181 b2.add(line, TOPSCOPE);
183 b2.add(line, LITERAL, string);
191 if (peekToken() == RP) { consume(RP); break; }
196 // pop off the arguments array
198 parseStatement(true, b2);
199 b2.add(line, LITERAL, null);
200 b2.add(line, RETURN);
201 continueExpr(b.add(line, NEWFUNCTION, b2), minPrecedence);
204 default: pushBackToken(); return;
208 public void continueExpr(CompiledFunction prefix, int minPrecedence) throws IOException {
209 int tok = getToken();
210 if (tok == -1) return;
211 if (minPrecedence > 0 && precedence[tok] != 0)
212 if (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))
213 { pushBackToken(); return; }
214 if (prefix == null) throw new Error("got null prefix");
215 CompiledFunction b = prefix;
219 case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
220 case ASSIGN_ADD: case ASSIGN_SUB: case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: {
221 prefix.set(prefix.size() - 1, b.GET_PRESERVE, new Boolean(true));
222 startExpr(precedence[tok - 1], b);
223 prefix.add(line, tok - 1);
224 prefix.add(line, PUT);
225 prefix.add(line, SWAP);
226 prefix.add(line, POP);
227 continueExpr(b, minPrecedence);
231 case INC: case DEC: {
233 b.set(b.size() - 1, tok, new Boolean(false));
234 continueExpr(b, minPrecedence);
241 while(peekToken() != RP) {
244 if (peekToken() == RP) break;
248 b.add(line, CALL, new Integer(i));
249 continueExpr(b, minPrecedence);
253 case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
254 case RSH: case URSH: case ADD: case MUL: case DIV: case MOD:
255 case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
256 startExpr(precedence[tok], b);
258 continueExpr(b, minPrecedence);
263 b.add(line, tok == AND ? b.JF : b.JT, new Integer(0));
265 startExpr(precedence[tok], b);
266 b.set(size - 1, new Integer(b.size() - size + 2));
267 b.add(line, JMP, new Integer(2));
268 b.add(line, LITERAL, tok == AND ? new Boolean(false) : new Boolean(true));
269 continueExpr(b, minPrecedence);
275 String target = string;
276 if (peekToken() == ASSIGN) {
278 b.add(line, LITERAL, target);
284 b.add(line, LITERAL, target);
287 continueExpr(b, minPrecedence);
294 if (peekToken() == ASSIGN) {
303 continueExpr(b, minPrecedence);
308 b.add(line, JF, new Integer(0));
311 b.set(size - 1, new Integer(b.size() - size + 2));
312 b.add(line, JMP, new Integer(0));
316 b.set(size - 1, new Integer(b.size() - size + 1));
317 continueExpr(b, minPrecedence);
321 default: { pushBackToken(); return; }
326 * a block is either a single statement or a list of statements surrounded by curly braces;
327 * all expressions are also statements
329 public CompiledFunction parseStatement() throws IOException {
330 CompiledFunction ret = new CompiledFunction(sourceName, line, null);
331 ret.add(line, ret.LITERAL, null);
332 parseStatement(false, ret);
333 if (ret.size() == 1) return null;
337 public void parseStatement(boolean r, CompiledFunction b) throws IOException { parseStatement(r, b, null); }
338 public void parseStatement(boolean requireBraces, CompiledFunction b, String label) throws IOException {
339 int tok = peekToken();
340 if (tok == -1) return;
341 int line = this.line;
342 boolean braced = tok == LC;
343 if (requireBraces && !braced) throw new ParserException("expected {, got " + codeToString[tok]);
344 if (braced) consume(LC);
346 switch(tok = peekToken()) {
348 case THROW: case RETURN: case ASSERT: {
350 if (tok == RETURN && peekToken() == SEMI) b.add(line, LITERAL, null);
351 else startExpr(-1, b);
357 case BREAK: case CONTINUE: {
359 if (peekToken() == NAME) consume(NAME);
360 b.add(line, tok, string);
373 b.add(line, TOPSCOPE); // push the current scope
376 String name = string;
377 b.add(line, LITERAL, name); // push the name to be declared
378 b.add(line, DECLARE); // declare it
379 if (peekToken() == ASSIGN) { // if there is an '=' after the variable name
380 b.add(line, LITERAL, name); // put the var name back on the stack
386 if (peekToken() != COMMA) break;
390 if (peekToken() == SEMI) consume(SEMI);
400 b.add(line, JF, new Integer(0));
402 parseStatement(false, b);
404 if (peekToken() == ELSE) {
406 b.set(size - 1, new Integer(2 + b.size() - size));
407 b.add(line, JMP, new Integer(0));
409 parseStatement(false, b);
411 b.set(size - 1, new Integer(1 + b.size() - size));
418 if (label != null) b.add(line, LABEL, label);
423 b.add(line, JT, new Integer(2));
426 parseStatement(false, b);
427 b.add(line, CONTINUE); // if we fall out of the end, definately continue
428 b.set(size - 1, new Integer(b.size() - size + 1)); // end of the loop
435 if (label != null) b.add(line, LABEL, label);
437 int size0 = b.size();
442 if (peekToken() == CASE) {
448 b.add(line, JF, new Integer(0));
450 while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
451 int size2 = b.size();
452 parseStatement(false, b);
453 if (size2 == b.size()) break;
455 b.set(size - 1, new Integer(1 + b.size() - size));
456 } else if (peekToken() == DEFAULT) {
459 while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
460 int size2 = b.size();
461 parseStatement(false, b);
462 if (size2 == b.size()) break;
464 } else if (peekToken() == RC) {
469 throw new ParserException("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
472 b.set(size0 - 1, new Integer(b.size() - size0 + 1)); // end of the loop
478 if (label != null) b.add(line, LABEL, label);
481 parseStatement(false, b);
485 b.add(line, JT, new Integer(2));
487 b.add(line, CONTINUE);
490 b.set(size - 1, new Integer(b.size() - size + 1)); // end of the loop
495 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
499 parseStatement(true, b);
500 b.add(line, POP); // pop the TryMarker
501 b.add(line, JMP); // jump forward to the end of the catch block
502 int size2 = b.size();
503 b.set(size - 1, new Integer(b.size() - size + 1));// the TRY argument points at the start of the CATCH block
505 if (peekToken() == CATCH) {
510 // FIXME, we need an extra scope here
511 b.add(line, TOPSCOPE); // the exception is on top of the stack; put it to the variable
513 b.add(line, LITERAL);
518 parseStatement(false, b);
521 b.set(size2 - 1, new Integer(b.size() - size2 + 1)); // jump here if no exception was thrown
523 // FIXME: not implemented correctly
524 if (peekToken() == FINALLY) {
526 parseStatement(false, b);
536 boolean hadVar = false;
537 if (tok == VAR) { hadVar = true; tok = getToken(); }
538 String varName = string;
539 boolean forIn = peekToken() == IN;
540 pushBackToken(tok, varName);
543 // FIXME: break needs to work in here
547 b.add(line, PUSHKEYS);
548 b.add(line, LITERAL, "length");
551 CompiledFunction b2 = new CompiledFunction(sourceName, line, null);
553 b.add(line, NEWSCOPE);
555 b.add(line, LITERAL, new Integer(1));
558 b.add(line, LITERAL, new Integer(0));
560 b.add(line, JT, new Integer(7));
561 b.add(line, GET_PRESERVE);
562 b.add(line, LITERAL, varName);
563 b.add(line, LITERAL, varName);
564 b.add(line, DECLARE);
566 parseStatement(false, b);
568 b.add(line, OLDSCOPE);
573 if (hadVar) pushBackToken(VAR, null);
574 b.add(line, NEWSCOPE);
576 parseStatement(false, b);
577 CompiledFunction e2 = new CompiledFunction(sourceName, line, null);
580 if (e2 == null) e2 = new CompiledFunction(sourceName, line, null).add(line, b.LITERAL, Boolean.TRUE);
582 if (label != null) b.add(line, LABEL, label);
584 int size2 = b.size();
586 b.add(line, JT, new Integer(0));
589 if (b.size() > size) b.add(line, POP);
590 b.set(size - 1, new Integer(b.size() - size + 1));
594 b.add(line, JT, new Integer(2));
596 parseStatement(false, b);
597 b.add(line, CONTINUE);
598 b.set(size2 - 1, new Integer(b.size() - size2 + 1)); // end of the loop
600 b.add(line, OLDSCOPE);
607 String possiblyTheLabel = string;
608 if (peekToken() == COLON) {
610 label = possiblyTheLabel;
611 System.out.println("label == " + label);
612 parseStatement(false, b, label);
615 pushBackToken(NAME, possiblyTheLabel);
616 // fall through to default case
621 if (tok == RC && braced) { consume(RC); return; }
626 if (size == b.size()) return;
628 if (peekToken() == SEMI) consume(SEMI);
637 private class ParserException extends RuntimeException {
638 public ParserException(String s) { super(sourceName + ":" + line + " " + s); }