1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
7 /** parses a stream of lexed tokens into ForthBlock's */
8 public class Parser extends Lexer implements OpCodes {
10 // Constructors //////////////////////////////////////////////////////
12 public Parser(Reader r, String sourceName, int line) throws IOException {
14 this.sourceName = sourceName;
19 public static void main(String[] s) throws Exception {
20 Parser p = new Parser(new InputStreamReader(System.in), "stdin", 0);
22 ForthBlock block = p.parseStatement(false);
23 if (block == null) return;
24 System.out.println(block);
25 if (p.peekToken() == -1) return;
30 // Statics ////////////////////////////////////////////////////////////
32 static byte[] precedence = new byte[MAX_TOKEN + 1];
33 static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
35 precedence[ASSIGN] = 1;
36 isRightAssociative[ASSIGN] = true;
38 precedence[COMMA] = 3;
39 precedence[OR] = precedence[AND] = 4;
40 precedence[GT] = precedence[GE] = 5;
41 precedence[BITOR] = 6;
42 precedence[BITXOR] = 7;
43 precedence[BITAND] = 8;
44 precedence[EQ] = precedence[NE] = 9;
45 precedence[LT] = precedence[LE] = 10;
46 precedence[SHEQ] = precedence[SHNE] = 11;
47 precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
48 precedence[ADD] = precedence[SUB] = 13;
49 precedence[MUL] = precedence[DIV] = precedence[MOD] = 14;
50 precedence[BITNOT] = precedence[INSTANCEOF] = 15;
51 precedence[INC] = precedence[DEC] = 16;
58 // Parsing Logic /////////////////////////////////////////////////////////
60 public void consume(int code) throws IOException {
61 if (getToken() != code)
62 throw new ParserException("expected " + codeToString[code] + ", got " + (op == -1 ? "EOL" : codeToString[op]));
65 /** parses the largest possible expression */
66 public ForthBlock parseMaximalForthBlock() throws IOException { return parseMaximalForthBlock(null, -1); }
67 public ForthBlock parseMaximalForthBlock(ForthBlock prefix, int minPrecedence) throws IOException {
69 if (peekToken() == -1) break;
70 ForthBlock save = prefix;
71 prefix = parseSingleForthBlock(prefix, minPrecedence);
72 if (save == prefix) break;
73 if (prefix == null) throw new ParserException("parseSingleForthBlock() returned null");
78 public ForthBlock parseSingleForthBlock(ForthBlock prefix, int minPrecedence) throws IOException {
79 ForthBlock e1 = null, e2 = null, e3 = null, head = null, tail = null, ret = null;
81 int tok = peekToken();
82 if (minPrecedence > 0 && tok < precedence.length && precedence[tok] != 0 &&
83 (isRightAssociative[tok] ? (precedence[tok] < minPrecedence) : (precedence[tok] <= minPrecedence)))
92 if (prefix != null) { pushBackToken(); return prefix; }
93 ForthBlock b = new ForthBlock(curLine, sourceName);
98 b.add(b.LITERAL, name);
100 if (peekToken() == ASSIGN) {
101 b.add(b.LITERAL, name);
103 b.add(b.EXPR, parseMaximalForthBlock());
107 if (peekToken() != COMMA) break;
110 return parseSingleForthBlock(b, minPrecedence);
113 case IN: pushBackToken(); return prefix;
116 if (prefix != null) { pushBackToken(); return prefix; }
117 ForthBlock b = new ForthBlock(curLine, sourceName);
119 b.add(b.EXPR, parseMaximalForthBlock());
121 b.add(b.JF, new Integer(3));
122 b.add(b.EXPR, parseStatement(false));
123 b.add(b.JMP, new Integer(2));
124 if (peekToken() != ELSE) return parseSingleForthBlock(b.add(b.LITERAL, null), minPrecedence);
126 b.add(b.EXPR, parseStatement(false));
127 return parseSingleForthBlock(b, minPrecedence);
130 // FIXME: ugly hack!!
131 case ASSIGN_BITOR: if (tok == ASSIGN_BITOR) tok = BITOR;
132 case ASSIGN_BITXOR: if (tok == ASSIGN_BITXOR) tok = BITXOR;
133 case ASSIGN_BITAND: if (tok == ASSIGN_BITAND) tok = BITAND;
134 case ASSIGN_LSH: if (tok == ASSIGN_LSH) tok = LSH;
135 case ASSIGN_RSH: if (tok == ASSIGN_RSH) tok = RSH;
136 case ASSIGN_URSH: if (tok == ASSIGN_URSH) tok = URSH;
137 case ASSIGN_ADD: if (tok == ASSIGN_ADD) tok = ADD;
138 case ASSIGN_SUB: if (tok == ASSIGN_SUB) tok = SUB;
139 case ASSIGN_MUL: if (tok == ASSIGN_MUL) tok = MUL;
140 case ASSIGN_DIV: if (tok == ASSIGN_DIV) tok = DIV;
141 case ASSIGN_MOD: if (tok == ASSIGN_MOD) tok = MOD;
143 ForthBlock b = (ForthBlock)prefix;
144 b.set(b.size() - 1, b.GET_PRESERVE, new Boolean(true));
145 b.add(b.EXPR, parseMaximalForthBlock(null, precedence[tok]));
150 return parseSingleForthBlock(b, minPrecedence);
154 if (prefix == null) {
156 ForthBlock b = (ForthBlock)parseMaximalForthBlock(null, precedence[tok]);
157 b.set(b.size() - 1, tok, new Boolean(true));
158 return parseSingleForthBlock(b, minPrecedence);
161 ForthBlock b = (ForthBlock)prefix;
162 b.set(b.size() - 1, tok, new Boolean(false));
163 return parseSingleForthBlock(b, minPrecedence);
167 if (prefix == null) { // grouping
168 ForthBlock b = new ForthBlock(curLine, sourceName, ForthBlock.EXPR, parseMaximalForthBlock());
170 return parseSingleForthBlock(b, minPrecedence);
172 } else { // invocation
173 ForthBlock b = new ForthBlock(curLine, sourceName);
175 b.add(b.EXPR, prefix);
176 while(peekToken() != RP) {
177 b.add(b.EXPR, parseMaximalForthBlock());
179 if (peekToken() == RP) break;
183 b.add(b.CALL, new Integer(i));
184 return parseSingleForthBlock(b, minPrecedence);
187 case BANG: case BITNOT: case INSTANCEOF: case TYPEOF: {
188 if (prefix != null) { pushBackToken(); return prefix; }
189 ForthBlock b = new ForthBlock(curLine, sourceName);
190 b.add(b.EXPR, parseMaximalForthBlock(null, precedence[tok]));
192 return parseSingleForthBlock(b, minPrecedence);
196 if (prefix == null && peekToken() == NUMBER) {
198 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, ForthBlock.LITERAL, new Double(number.doubleValue() * -1)), minPrecedence);
199 } // else fall through
200 case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
201 case RSH: case URSH: case ADD: case MUL: case DIV: case MOD:
202 case GT: case GE: case EQ: case NE: case LT: case LE: {
203 if (prefix == null) throw new ParserException("the " + codeToString[tok] + " token cannot start an expression");
204 ForthBlock b = new ForthBlock(curLine, sourceName);
205 b.add(b.EXPR, prefix);
206 b.add(b.EXPR, parseMaximalForthBlock(null, precedence[tok]));
208 return parseSingleForthBlock(b, minPrecedence);
211 // includes short-circuit logic
213 if (prefix == null) throw new ParserException("the " + codeToString[tok] + " token cannot start an expression");
214 ForthBlock b = new ForthBlock(curLine, sourceName);
215 b.add(b.LITERAL, tok == AND ? new Boolean(false) : new Boolean(true));
216 b.add(b.EXPR, prefix);
217 b.add(tok == AND ? b.JF : b.JT, new Integer(3));
219 b.add(b.EXPR, parseMaximalForthBlock(null, precedence[tok]));
220 return parseSingleForthBlock(b, minPrecedence);
223 case WITH: throw new ParserException("XWT does not allow the WITH keyword");
224 case VOID: case RESERVED: throw new ParserException("reserved word that you shouldn't be using");
227 if (prefix != null) { pushBackToken(); return prefix; }
228 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, ForthBlock.LITERAL, number), minPrecedence);
231 if (prefix != null) { pushBackToken(); return prefix; }
232 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, ForthBlock.LITERAL, string), minPrecedence);
234 case NULL: case TRUE: case FALSE: case NOP:
235 if (prefix != null) { pushBackToken(); return prefix; }
236 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, ForthBlock.LITERAL, (tok == NULL || tok == NOP) ? null : new Boolean(tok == TRUE)), minPrecedence);
238 case COMMA: pushBackToken(); return prefix;
241 if (prefix != null) { pushBackToken(); return prefix; }
242 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, OpCodes.THIS, null), minPrecedence);
245 if (prefix != null) { pushBackToken(); return prefix; }
246 String name = string;
247 ForthBlock b = new ForthBlock(curLine, sourceName);
248 if (peekToken() == ASSIGN) {
251 b.add(ForthBlock.LITERAL, name);
252 b.add(ForthBlock.EXPR, parseMaximalForthBlock(null, minPrecedence));
253 b.add(ForthBlock.PUT);
254 b.add(ForthBlock.SWAP);
255 b.add(ForthBlock.POP);
256 return parseSingleForthBlock(b, minPrecedence);
259 b.add(ForthBlock.LITERAL, name);
260 b.add(ForthBlock.GET);
261 return parseSingleForthBlock(parseMaximalForthBlock(b, minPrecedence), minPrecedence);
267 String target = string;
268 ForthBlock b = new ForthBlock(curLine, sourceName);
269 b.add(b.EXPR, prefix);
270 if (peekToken() == ASSIGN) {
272 ForthBlock val = parseMaximalForthBlock();
273 b.add(b.LITERAL, target);
279 b.add(b.LITERAL, target);
282 return parseSingleForthBlock(b, minPrecedence);
286 ForthBlock b = new ForthBlock(curLine, sourceName);
287 if (prefix == null) {
288 b.add(b.ARRAY, new Integer(0));
291 ForthBlock e = parseMaximalForthBlock();
292 if (e == null && peekToken() == RB) { consume(RB); return parseSingleForthBlock(b, minPrecedence); }
293 b.add(b.LITERAL, new Integer(i++));
294 if (e == null) b.add(b.LITERAL, null);
295 else b.add(b.EXPR, e);
298 if (peekToken() == RB) { consume(RB); return parseSingleForthBlock(b, minPrecedence); }
302 b.add(b.EXPR, prefix);
303 b.add(b.EXPR, parseMaximalForthBlock());
305 if (peekToken() == ASSIGN) {
307 b.add(b.EXPR, parseMaximalForthBlock());
314 return parseSingleForthBlock(b, minPrecedence);
319 if (prefix != null) { pushBackToken(); return prefix; }
320 ForthBlock b = new ForthBlock(curLine, sourceName);
321 b.add(b.OBJECT, null);
322 if (peekToken() == RC) { consume(RC); return parseSingleForthBlock(b, minPrecedence); }
324 if (peekToken() != NAME && peekToken() != STRING) throw new Error("expected NAME or STRING");
326 b.add(b.LITERAL, string);
328 b.add(b.EXPR, parseMaximalForthBlock());
331 if (peekToken() == RC) { consume(RC); return parseSingleForthBlock(b, minPrecedence); }
333 if (peekToken() == RC) { consume(RC); return parseSingleForthBlock(b, minPrecedence); }
338 ForthBlock b = new ForthBlock(curLine, sourceName);
339 b.add(b.EXPR, prefix);
340 b.add(b.JF, new Integer(3));
341 b.add(b.EXPR, parseMaximalForthBlock());
342 b.add(b.JMP, new Integer(2));
344 b.add(b.EXPR, parseMaximalForthBlock());
345 return parseSingleForthBlock(b, minPrecedence);
348 case Tokens.FUNCTION: {
349 if (prefix != null) { pushBackToken(); return prefix; }
351 ForthBlock b = new ForthBlock(curLine, sourceName);
355 b.add(b.LITERAL, "arguments");
356 b.add(b.LITERAL, "arguments");
362 if (peekToken() == RP) consume(RP);
364 if (peekToken() == COMMA) {
370 b.add(b.LITERAL, string);
373 // retrieve it from the arguments array
374 b.add(b.LITERAL, new Integer(numArgs));
375 b.add(b.GET_PRESERVE);
379 // put it to the current scope
382 b.add(b.LITERAL, string);
390 if (peekToken() == RP) { consume(RP); break; }
395 // pop off the arguments array
397 parseStatement(true, b);
398 return parseSingleForthBlock(new ForthBlock(curLine, sourceName, OpCodes.FUNCTION, b), minPrecedence);
402 if (prefix != null) { pushBackToken(); return prefix; }
404 ForthBlock r = new ForthBlock(curLine, sourceName);
405 ForthBlock loop = new ForthBlock(curLine, sourceName);
406 r.add(loop.LOOP, loop);
407 r.add(r.LITERAL, null);
409 loop.add(loop.EXPR, parseMaximalForthBlock());
410 loop.add(loop.JT, new Integer(2));
411 loop.add(Lexer.BREAK);
413 parseStatement(false, loop);
415 // if we fall out of the end, definately continue
417 return parseSingleForthBlock(r, minPrecedence);
421 if (prefix != null) { pushBackToken(); return prefix; }
423 ForthBlock r = new ForthBlock(curLine, sourceName);
424 ForthBlock loop = new ForthBlock(curLine, sourceName);
425 r.add(loop.LOOP, loop);
426 r.add(r.LITERAL, null);
427 loop.add(loop.EXPR, parseMaximalForthBlock());
431 ForthBlock caseForthBlock;
435 loop.add(loop.EXPR, parseMaximalForthBlock());
437 loop.add(loop.JF, new Integer(2));
438 } else if (tok != DEFAULT) throw new ParserException("expected CASE or DEFAULT");
440 ForthBlock b = new ForthBlock(curLine, sourceName);
441 while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
442 if ((e1 = parseStatement(false)) == null) break;
445 loop.add(loop.EXPR, b);
446 if (peekToken() == RC) {
449 return parseSingleForthBlock(r, minPrecedence);
455 if (prefix != null) { pushBackToken(); return prefix; }
456 ForthBlock r = new ForthBlock(curLine, sourceName);
457 ForthBlock loop = new ForthBlock(curLine, sourceName);
458 r.add(loop.LOOP, loop);
459 r.add(r.LITERAL, null);
461 parseStatement(false, loop);
464 loop.add(loop.EXPR, parseMaximalForthBlock());
465 loop.add(loop.JT, new Integer(2));
466 loop.add(Lexer.BREAK);
467 loop.add(Lexer.CONTINUE);
470 return parseSingleForthBlock(r, minPrecedence);
474 // FIXME: don't just ignore this!
475 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
476 if (prefix != null) { pushBackToken(); return prefix; }
477 ForthBlock tryBlock = parseStatement(true);
482 if (getToken() != LP) throw new ParserException("expected (");
483 if (getToken() != NAME) throw new ParserException("expected name");
484 if (getToken() != RP) throw new ParserException("expected )");
487 if (tok == FINALLY) getToken();
489 return parseSingleForthBlock(tryBlock, minPrecedence);
493 if (prefix != null) { pushBackToken(); return prefix; }
494 if (getToken() != LP) throw new ParserException("expected left paren");
497 if (tok == VAR) tok = getToken();
498 String varName = string;
499 boolean forIn = peekToken() == IN;
500 pushBackToken(tok, varName);
502 ForthBlock b = new ForthBlock(curLine, sourceName);
506 b.add(b.EXPR, parseMaximalForthBlock());
508 b.add(b.LITERAL, "length");
511 ForthBlock b2 = new ForthBlock(curLine, sourceName);
513 b2.add(b.LITERAL, new Integer(1));
516 b2.add(b.LITERAL, new Integer(0));
518 b2.add(b.JT, new Integer(7));
519 b2.add(b.GET_PRESERVE);
520 b2.add(b.LITERAL, varName);
521 b2.add(b.LITERAL, varName);
524 b2.add(b.EXPR, parseStatement(false));
525 b2.add(b.LITERAL, null);
526 return parseSingleForthBlock(b, minPrecedence);
529 ForthBlock b2 = new ForthBlock(curLine, sourceName);
532 e1 = parseMaximalForthBlock();
533 if (e1 == null) e1 = new ForthBlock(curLine, sourceName, b.LITERAL, null);
538 e2 = parseMaximalForthBlock();
540 e3 = parseMaximalForthBlock();
543 if (e2 == null) e2 = new ForthBlock(curLine, sourceName, b.LITERAL, null);
544 if (e3 == null) e3 = new ForthBlock(curLine, sourceName, b.LITERAL, null);
546 ForthBlock b3 = new ForthBlock(curLine, sourceName);
548 b2.add(b.LITERAL, null);
549 b3.add(b.JT, new Integer(3));
553 b3.add(b.JT, new Integer(2));
555 parseStatement(false, b3);
556 return parseSingleForthBlock(b, minPrecedence);
566 /** a block is either a single statement or a list of statements surrounded by curly braces; all expressions are also statements */
567 public ForthBlock parseStatement(boolean requireBraces) throws IOException { return parseStatement(requireBraces, null); }
568 public ForthBlock parseStatement(boolean requireBraces, ForthBlock b) throws IOException {
569 ForthBlock smt = null;
570 int tok = peekToken();
571 if (tok == -1) return null;
572 boolean braced = tok == LC;
573 if (requireBraces && !braced) throw new ParserException("expected {, got " + codeToString[tok]);
574 if (braced) consume(LC);
576 ForthBlock ret = new ForthBlock(curLine, sourceName);
577 ForthBlock block = b == null ? new ForthBlock(curLine, sourceName) : b;
578 block.add(ret.LITERAL, Boolean.TRUE);
579 ret.add(block.SCOPE, block);
581 switch(tok = peekToken()) {
583 case LC: smt = parseStatement(true); break;
584 case GOTO: throw new ParserException("goto not supported");
586 case THROW: case RETURN: case ASSERT: {
588 ForthBlock r = new ForthBlock(curLine, sourceName);
589 if (tok == RETURN && peekToken() == SEMI) r.add(b.LITERAL, null);
590 else r.add(b.EXPR, parseMaximalForthBlock());
597 case BREAK: case CONTINUE: {
599 if (peekToken() == NAME) consume(NAME);
600 smt = new ForthBlock(curLine, sourceName, tok, string);
606 if (braced) consume(RC);
607 return block.size() == 0 ? null : ret;
611 if (!braced) return block.size() == 0 ? null : ret;
615 String name = string;
617 if (peekToken() == COLON) {
619 smt = new ForthBlock(curLine, sourceName, ForthBlock.LABEL, string);
622 pushBackToken(NAME, name);
623 // fall through to default case
629 smt = parseMaximalForthBlock();
630 if (smt == null) return block.size() == 0 ? null : ret;
631 if (peekToken() == SEMI) getToken();
635 if (!braced) return smt;
636 block.add(block.EXPR, smt);
637 block.add(block.POP);
641 class ParserException extends RuntimeException {
642 public ParserException(String s) { super(sourceName + ":" + line + " " + s); }