1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
7 /** Parses a stream of lexed tokens into a tree of ByteCodeBlock's */
8 class Parser extends Lexer implements ByteCodes {
11 // Constructors //////////////////////////////////////////////////////
13 public Parser(Reader r, String sourceName, int line) throws IOException {
15 this.sourceName = sourceName;
20 public static void main(String[] s) throws Exception {
21 Parser p = new Parser(new InputStreamReader(System.in), "stdin", 0);
23 ByteCodeBlock block = new ByteCodeBlock(0, "stdin");
24 p.parseStatement(false, block);
25 if (block == null) return;
26 System.out.println(block);
27 if (p.peekToken() == -1) return;
32 // Statics ////////////////////////////////////////////////////////////
34 static byte[] precedence = new byte[MAX_TOKEN + 1];
35 static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
37 isRightAssociative[ASSIGN] = true;
39 precedence[ASSIGN] = 1;
41 precedence[COMMA] = 3;
42 precedence[OR] = precedence[AND] = 4;
43 precedence[GT] = precedence[GE] = 5;
44 precedence[BITOR] = 6;
45 precedence[BITXOR] = 7;
46 precedence[BITAND] = 8;
47 precedence[EQ] = precedence[NE] = 9;
48 precedence[LT] = precedence[LE] = 10;
49 precedence[SHEQ] = precedence[SHNE] = 11;
50 precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
51 precedence[ADD] = precedence[SUB] = 13;
52 precedence[MUL] = precedence[DIV] = precedence[MOD] = 14;
53 precedence[BITNOT] = precedence[INSTANCEOF] = 15;
54 precedence[INC] = precedence[DEC] = 16;
61 // Parsing Logic /////////////////////////////////////////////////////////
63 /** gets a token and throws an exception if it is not <tt>code</tt> */
64 public void consume(int code) throws IOException {
65 if (getToken() != code)
66 throw new ParserException("expected " + codeToString[code] + ", got " + (op == -1 ? "EOL" : codeToString[op]));
69 /** append the largest expression beginning with prefix containing no operators of precedence below <tt>minPrecedence</tt> */
70 public ByteCodeBlock startExpr() throws IOException { return startExpr(-1); }
71 public void startExpr(ByteCodeBlock block) throws IOException { startExpr(-1, block); }
72 public ByteCodeBlock startExpr(int minPrecedence) throws IOException {
73 ByteCodeBlock ret = new ByteCodeBlock(line, sourceName);
74 startExpr(minPrecedence, ret);
75 return ret.size() == 0 ? null : ret;
78 public void startExpr(int minPrecedence, ByteCodeBlock appendTo) throws IOException {
81 if (tok == -1) return;
82 if (minPrecedence > 0 && precedence[tok] != 0)
83 if (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))
84 { pushBackToken(); return; }
86 ByteCodeBlock b = appendTo;
89 case NUMBER: continueExpr(b.add(ByteCodeBlock.LITERAL, number), minPrecedence); return;
90 case STRING: continueExpr(b.add(ByteCodeBlock.LITERAL, string), minPrecedence); return;
91 case THIS: continueExpr(b.add(TOPSCOPE, null), minPrecedence); return;
92 case NULL: continueExpr(b.add(ByteCodeBlock.LITERAL, null), minPrecedence); return;
93 case TRUE: case FALSE: continueExpr(b.add(ByteCodeBlock.LITERAL, new Boolean(tok == TRUE)), minPrecedence); return;
95 b.add(ARRAY, new Integer(0));
100 if (size == b.size())
101 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
102 b.add(LITERAL, new Integer(i++));
103 if (size == b.size()) b.add(LITERAL, null);
106 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
112 continueExpr(b.add(ByteCodeBlock.LITERAL, new Double(number.doubleValue() * -1)), minPrecedence);
118 continueExpr(b, minPrecedence);
121 case INC: case DEC: {
123 startExpr(precedence[tok], b);
124 b.set(b.size() - 1, tok, new Boolean(true));
125 continueExpr(b, minPrecedence);
128 case BANG: case BITNOT: case INSTANCEOF: case TYPEOF: {
129 startExpr(precedence[tok], b);
131 continueExpr(b, minPrecedence);
136 if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
138 if (peekToken() != NAME && peekToken() != STRING) throw new Error("expected NAME or STRING");
140 b.add(LITERAL, string);
145 if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
147 if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
151 String name = string;
152 if (peekToken() == ASSIGN) {
155 b.add(ByteCodeBlock.LITERAL, name);
156 startExpr(minPrecedence, b);
157 b.add(ByteCodeBlock.PUT);
158 b.add(ByteCodeBlock.SWAP);
159 b.add(ByteCodeBlock.POP);
162 b.add(ByteCodeBlock.LITERAL, name);
163 b.add(ByteCodeBlock.GET);
165 continueExpr(b, minPrecedence);
171 ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
174 b2.add(LITERAL, "arguments");
175 b2.add(LITERAL, "arguments");
181 if (peekToken() == RP) consume(RP);
183 if (peekToken() == COMMA) {
190 b2.add(LITERAL, string);
193 // retrieve it from the arguments array
194 b2.add(LITERAL, new Integer(numArgs));
195 b2.add(GET_PRESERVE);
199 // put it to the current scope
202 b2.add(LITERAL, string);
210 if (peekToken() == RP) { consume(RP); break; }
215 // pop off the arguments array
217 parseStatement(true, b2);
218 b2.add(LITERAL, null);
220 continueExpr(b.add(NEWFUNCTION, b2), minPrecedence);
223 default: pushBackToken(); return;
227 public void continueExpr(ByteCodeBlock prefix, int minPrecedence) throws IOException {
228 int tok = getToken();
230 if (tok == -1) return;
231 if (minPrecedence > 0 && precedence[tok] != 0)
232 if (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))
233 { pushBackToken(); return; }
235 if (prefix == null) throw new Error("got null prefix");
236 ByteCodeBlock b = prefix;
240 case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
241 case ASSIGN_ADD: case ASSIGN_SUB: case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: {
242 prefix.set(prefix.size() - 1, b.GET_PRESERVE, new Boolean(true));
243 startExpr(precedence[tok - 1], b);
248 continueExpr(b, minPrecedence);
252 case INC: case DEC: {
254 b.set(b.size() - 1, tok, new Boolean(false));
255 continueExpr(b, minPrecedence);
262 while(peekToken() != RP) {
265 if (peekToken() == RP) break;
269 b.add(CALL, new Integer(i));
270 continueExpr(b, minPrecedence);
274 case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
275 case RSH: case URSH: case ADD: case MUL: case DIV: case MOD:
276 case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
277 startExpr(precedence[tok], b);
279 continueExpr(b, minPrecedence);
284 b.add(tok == AND ? b.JF : b.JT, new Integer(0));
286 startExpr(precedence[tok], b);
287 b.arg[size - 1] = new Integer(b.size() - size + 2);
288 b.add(JMP, new Integer(2));
289 b.add(LITERAL, tok == AND ? new Boolean(false) : new Boolean(true));
290 continueExpr(b, minPrecedence);
296 String target = string;
297 if (peekToken() == ASSIGN) {
299 b.add(LITERAL, target);
305 b.add(LITERAL, target);
308 continueExpr(b, minPrecedence);
315 if (peekToken() == ASSIGN) {
324 continueExpr(b, minPrecedence);
329 b.add(JF, new Integer(0));
332 b.arg[size - 1] = new Integer(b.size() - size + 2);
333 b.add(JMP, new Integer(0));
337 b.arg[size - 1] = new Integer(b.size() - size + 1);
338 continueExpr(b, minPrecedence);
342 default: { pushBackToken(); return; }
346 /** a block is either a single statement or a list of statements surrounded by curly braces; all expressions are also statements */
347 public ByteCodeBlock parseStatement() throws IOException {
348 ByteCodeBlock ret = new ByteCodeBlock(line, sourceName);
349 ret.add(ret.LITERAL, null);
350 parseStatement(false, ret);
351 if (ret.size() == 1) return null;
355 public void parseStatement(boolean requireBraces) throws IOException {
356 parseStatement(requireBraces, new ByteCodeBlock(line, sourceName));
358 public void parseStatement(boolean requireBraces, ByteCodeBlock b) throws IOException {
359 int tok = peekToken();
360 if (tok == -1) return;
361 boolean braced = tok == LC;
362 if (requireBraces && !braced) throw new ParserException("expected {, got " + codeToString[tok]);
363 if (braced) consume(LC);
366 switch(tok = peekToken()) {
368 case THROW: case RETURN: case ASSERT: {
370 if (tok == RETURN && peekToken() == SEMI) b.add(LITERAL, null);
377 case BREAK: case CONTINUE: {
379 if (peekToken() == NAME) consume(NAME);
392 b.add(TOPSCOPE); // push the current scope
395 String name = string;
396 b.add(LITERAL, name); // push the name to be declared
397 b.add(DECLARE); // declare it
398 if (peekToken() == ASSIGN) { // if there is an '=' after the variable name
399 b.add(LITERAL, name); // put the var name back on the stack
405 if (peekToken() != COMMA) break;
409 if (peekToken() == SEMI) consume(SEMI);
419 b.add(JF, new Integer(0));
421 parseStatement(false, b);
423 if (peekToken() == ELSE) {
425 b.arg[size - 1] = new Integer(2 + b.size() - size);
426 b.add(JMP, new Integer(0));
428 parseStatement(false, b);
430 b.arg[size - 1] = new Integer(1 + b.size() - size);
437 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
442 loop.add(JT, new Integer(2));
445 parseStatement(false, loop);
447 // if we fall out of the end, definately continue
455 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
461 if (peekToken() == CASE) {
467 loop.add(JF, new Integer(0));
468 int size = loop.size();
469 while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
470 int size2 = loop.size();
471 parseStatement(false, loop);
472 if (size2 == loop.size()) break;
474 loop.arg[size - 1] = new Integer(1 + loop.size() - size);
475 } else if (peekToken() == DEFAULT) {
478 while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
479 int size2 = loop.size();
480 parseStatement(false, loop);
481 if (size2 == loop.size()) break;
483 } else if (peekToken() == RC) {
488 throw new ParserException("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
495 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
498 parseStatement(false, loop);
502 loop.add(JT, new Integer(2));
511 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
513 parseStatement(true, b);
515 if (peekToken() == CATCH) {
520 parseStatement(); // just discard the catchblock
523 if (peekToken() == FINALLY) {
525 parseStatement(false, b);
535 if (tok == VAR) tok = getToken();
536 String varName = string;
537 boolean forIn = peekToken() == IN;
538 pushBackToken(tok, varName);
545 b.add(LITERAL, "length");
548 ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
550 b2.add(LITERAL, new Integer(1));
553 b2.add(LITERAL, new Integer(0));
555 b2.add(JT, new Integer(7));
556 b2.add(GET_PRESERVE);
557 b2.add(LITERAL, varName);
558 b2.add(LITERAL, varName);
561 parseStatement(false, b2);
565 ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
569 int size = b2.size();
571 if (b2.size() - size > 0) b2.add(POP);
573 ByteCodeBlock e2 = startExpr();
575 if (e2 == null) e2 = new ByteCodeBlock(curLine, sourceName, b.LITERAL, null);
577 ByteCodeBlock b3 = new ByteCodeBlock(curLine, sourceName);
579 b2.add(LITERAL, null);
581 b3.add(JT, new Integer(0));
585 if (b3.size() - size > 0) b3.add(POP);
586 b3.arg[size - 1] = new Integer(b3.size() - size + 1);
589 b3.add(JT, new Integer(2));
591 parseStatement(false, b3);
599 String name = string;
600 if (peekToken() == COLON) {
602 b.add(ByteCodeBlock.LABEL, string);
605 pushBackToken(NAME, name);
606 // fall through to default case
611 if (tok == RC && braced) { consume(RC); return; }
616 if (size == b.size()) return;
618 if (peekToken() == SEMI) consume(SEMI);
627 class ParserException extends RuntimeException {
628 public ParserException(String s) { super(sourceName + ":" + line + " " + s); }