src/org/xwt/js/Parser.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.js;
   3
   4 import org.xwt.util.*;
   5 import java.io.*;
   6
   7 /** Parses a stream of lexed tokens into a tree of ByteCodeBlock's */
   8 class Parser extends Lexer implements ByteCodes {
   9
  10
  11     // Constructors //////////////////////////////////////////////////////
  12
  13     public Parser(Reader r, String sourceName, int line) throws IOException {
  14         super(r);
  15         this.sourceName = sourceName;
  16         this.line = line;
  17     }
  18
  19     /** for debugging */
  20     public static void main(String[] s) throws Exception {
  21         Parser p = new Parser(new InputStreamReader(System.in), "stdin", 0);
  22         while(true) {
  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;
  28         }
  29     }
  30
  31
  32     // Statics ////////////////////////////////////////////////////////////
  33
  34     static byte[] precedence = new byte[MAX_TOKEN + 1];
  35     static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
  36     static {
  37         isRightAssociative[ASSIGN] = true;
  38
  39         precedence[ASSIGN] = 1;
  40         precedence[HOOK] = 2;
  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;
  55         precedence[LP] = 17;
  56         precedence[LB] = 18;
  57         precedence[DOT] = 19;
  58     }
  59
  60
  61     // Parsing Logic /////////////////////////////////////////////////////////
  62
  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]));
  67     }
  68
  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;
  76     }
  77
  78     public void startExpr(int minPrecedence, ByteCodeBlock appendTo) throws IOException {
  79         int tok = getToken();
  80         int curLine = line;
  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; }
  85
  86         ByteCodeBlock b = appendTo;
  87
  88         switch (tok) {
  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;
  94         case LB: {
  95             b.add(ARRAY, new Integer(0));
  96             int i = 0;
  97             while(true) {
  98                 int size = b.size();
  99                 startExpr(b);
 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);
 104                 b.add(PUT);
 105                 b.add(POP);
 106                 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
 107                 consume(COMMA);
 108             }
 109         }
 110         case SUB: {
 111             consume(NUMBER);
 112             continueExpr(b.add(ByteCodeBlock.LITERAL, new Double(number.doubleValue() * -1)), minPrecedence);
 113             return;
 114         }
 115         case LP: {
 116             startExpr(b);
 117             consume(RP);
 118             continueExpr(b, minPrecedence);
 119             return;
 120         }
 121         case INC: case DEC: {
 122             // prefix
 123             startExpr(precedence[tok], b);
 124             b.set(b.size() - 1, tok, new Boolean(true));
 125             continueExpr(b, minPrecedence);
 126             return;
 127         }
 128         case BANG: case BITNOT: case INSTANCEOF: case TYPEOF: {
 129             startExpr(precedence[tok], b);
 130             b.add(tok);
 131             continueExpr(b, minPrecedence);
 132             return;
 133         }
 134         case LC: {
 135             b.add(OBJECT, null);
 136             if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
 137             while(true) {
 138                 if (peekToken() != NAME && peekToken() != STRING) throw new Error("expected NAME or STRING");
 139                 getToken();
 140                 b.add(LITERAL, string);
 141                 consume(COLON);
 142                 startExpr(b);
 143                 b.add(PUT);
 144                 b.add(POP);
 145                 if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
 146                 consume(COMMA);
 147                 if (peekToken() == RC) { consume(RC); continueExpr(b, minPrecedence); return; }
 148             }
 149         }
 150         case NAME: {
 151             String name = string;
 152             if (peekToken() == ASSIGN) {
 153                 consume(ASSIGN);
 154                 b.add(TOPSCOPE);
 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);
 160             } else {
 161                 b.add(TOPSCOPE);
 162                 b.add(ByteCodeBlock.LITERAL, name);
 163                 b.add(ByteCodeBlock.GET);
 164             }
 165             continueExpr(b, minPrecedence);
 166             return;
 167         }
 168         case FUNCTION: {
 169             consume(LP);
 170             int numArgs = 0;
 171             ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
 172             b2.add(TOPSCOPE);
 173             b2.add(SWAP);
 174             b2.add(LITERAL, "arguments");
 175             b2.add(LITERAL, "arguments");
 176             b2.add(DECLARE);
 177             b2.add(SWAP);
 178             b2.add(PUT);
 179             b2.add(SWAP);
 180             b2.add(POP);
 181             if (peekToken() == RP) consume(RP);
 182             else while(true) {
 183                 if (peekToken() == COMMA) {
 184                     consume(COMMA);
 185
 186                 } else {
 187                     consume(NAME);
 188
 189                     // declare the name
 190                     b2.add(LITERAL, string);
 191                     b2.add(DECLARE);
 192
 193                     // retrieve it from the arguments array
 194                     b2.add(LITERAL, new Integer(numArgs));
 195                     b2.add(GET_PRESERVE);
 196                     b2.add(SWAP);
 197                     b2.add(POP);
 198
 199                     // put it to the current scope
 200                     b2.add(TOPSCOPE);
 201                     b2.add(SWAP);
 202                     b2.add(LITERAL, string);
 203                     b2.add(SWAP);
 204                     b2.add(PUT);
 205
 206                     // clean the stack
 207                     b2.add(POP);
 208                     b2.add(POP);
 209
 210                     if (peekToken() == RP) { consume(RP); break; }
 211                     consume(COMMA);
 212                 }
 213                 numArgs++;
 214             }
 215             // pop off the arguments array
 216             b2.add(POP);
 217             parseStatement(true, b2);
 218             b2.add(LITERAL, null);
 219             b2.add(RETURN);
 220             continueExpr(b.add(NEWFUNCTION, b2), minPrecedence);
 221             return;
 222         }
 223         default: pushBackToken(); return;
 224         }
 225     }
 226
 227     public void continueExpr(ByteCodeBlock prefix, int minPrecedence) throws IOException {
 228         int tok = getToken();
 229         int curLine = line;
 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; }
 234
 235         if (prefix == null) throw new Error("got null prefix");
 236         ByteCodeBlock b = prefix;
 237
 238         switch (tok) {
 239
 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);
 244             prefix.add(tok - 1);
 245             prefix.add(PUT);
 246             prefix.add(SWAP);
 247             prefix.add(POP);
 248             continueExpr(b, minPrecedence);
 249             return;
 250         }
 251
 252         case INC: case DEC: {
 253             // postfix
 254             b.set(b.size() - 1, tok, new Boolean(false));
 255             continueExpr(b, minPrecedence);
 256             return;
 257         }
 258
 259         case LP: {
 260             // invocation
 261             int i = 0;
 262             while(peekToken() != RP) {
 263                 startExpr(b);
 264                 i++;
 265                 if (peekToken() == RP) break;
 266                 consume(COMMA);
 267             }
 268             consume(RP);
 269             b.add(CALL, new Integer(i));
 270             continueExpr(b, minPrecedence);
 271             return;
 272         }
 273
 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);
 278             b.add(tok);
 279             continueExpr(b, minPrecedence);
 280             return;
 281         }
 282
 283         case OR: case AND: {
 284             b.add(tok == AND ? b.JF : b.JT, new Integer(0));
 285             int size = b.size();
 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);
 291             return;
 292         }
 293
 294         case DOT: {
 295             consume(NAME);
 296             String target = string;
 297             if (peekToken() == ASSIGN) {
 298                 consume(ASSIGN);
 299                 b.add(LITERAL, target);
 300                 startExpr(b);
 301                 b.add(PUT);
 302                 b.add(SWAP);
 303                 b.add(POP);
 304             } else {
 305                 b.add(LITERAL, target);
 306                 b.add(GET);
 307             }
 308             continueExpr(b, minPrecedence);
 309             return;
 310         }
 311
 312         case LB: {
 313             startExpr(b);
 314             consume(RB);
 315             if (peekToken() == ASSIGN) {
 316                 consume(ASSIGN);
 317                 startExpr(b);
 318                 b.add(PUT);
 319                 b.add(SWAP);
 320                 b.add(POP);
 321             } else {
 322                 b.add(GET);
 323             }
 324             continueExpr(b, minPrecedence);
 325             return;
 326         }
 327
 328         case HOOK: {
 329             b.add(JF, new Integer(0));
 330             int size = b.size();
 331             startExpr(b);
 332             b.arg[size - 1] = new Integer(b.size() - size + 2);
 333             b.add(JMP, new Integer(0));
 334             consume(COLON);
 335             size = b.size();
 336             startExpr(b);
 337             b.arg[size - 1] = new Integer(b.size() - size + 1);
 338             continueExpr(b, minPrecedence);
 339             return;
 340         }
 341
 342         default: { pushBackToken(); return; }
 343         }
 344     }
 345
 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;
 352         return ret;
 353     }
 354
 355     public void parseStatement(boolean requireBraces) throws IOException {
 356         parseStatement(requireBraces, new ByteCodeBlock(line, sourceName));
 357     }
 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);
 364         int curLine = line;
 365         while(true) {
 366             switch(tok = peekToken()) {
 367
 368             case THROW: case RETURN: case ASSERT: {
 369                 getToken();
 370                 if (tok == RETURN && peekToken() == SEMI) b.add(LITERAL, null);
 371                 else startExpr(b);
 372                 consume(SEMI);
 373                 b.add(tok);
 374                 break;
 375             }
 376
 377             case BREAK: case CONTINUE: {
 378                 getToken();
 379                 if (peekToken() == NAME) consume(NAME);
 380                 b.add(tok, string);
 381                 consume(SEMI);
 382                 break;
 383             }
 384
 385             case SEMI:
 386                 consume(SEMI);
 387                 if (!braced) return;
 388                 break;
 389
 390             case VAR: {
 391                 consume(VAR);
 392                 b.add(TOPSCOPE);                               // push the current scope
 393                 while(true) {
 394                     consume(NAME);
 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
 400                         consume(ASSIGN);
 401                         startExpr(b);
 402                         b.add(PUT);
 403                         b.add(POP);
 404                     }
 405                     if (peekToken() != COMMA) break;
 406                     consume(COMMA);
 407                 }
 408                 b.add(POP);
 409                 if (peekToken() == SEMI) consume(SEMI);
 410                 break;
 411             }
 412
 413             case IF: {
 414                 consume(IF);
 415                 consume(LP);
 416                 startExpr(b);
 417                 consume(RP);
 418
 419                 b.add(JF, new Integer(0));
 420                 int size = b.size();
 421                 parseStatement(false, b);
 422
 423                 if (peekToken() == ELSE) {
 424                     consume(ELSE);
 425                     b.arg[size - 1] = new Integer(2 + b.size() - size);
 426                     b.add(JMP, new Integer(0));
 427                     size = b.size();
 428                     parseStatement(false, b);
 429                 }
 430                 b.arg[size - 1] = new Integer(1 + b.size() - size);
 431                 break;
 432             }
 433
 434             case WHILE: {
 435                 consume(WHILE);
 436                 consume(LP);
 437                 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
 438                 b.add(LOOP, loop);
 439
 440                 loop.add(POP);
 441                 startExpr(loop);
 442                 loop.add(JT, new Integer(2));
 443                 loop.add(BREAK);
 444                 consume(RP);
 445                 parseStatement(false, loop);
 446
 447                 // if we fall out of the end, definately continue
 448                 loop.add(CONTINUE);
 449                 break;
 450             }
 451
 452             case SWITCH: {
 453                 consume(SWITCH);
 454                 consume(LP);
 455                 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
 456                 b.add(LOOP, loop);
 457                 startExpr(loop);
 458                 consume(RP);
 459                 consume(LC);
 460                 while(true)
 461                     if (peekToken() == CASE) {
 462                         consume(CASE);
 463                         loop.add(DUP);
 464                         startExpr(loop);
 465                         consume(COLON);
 466                         loop.add(EQ);
 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;
 473                         }
 474                         loop.arg[size - 1] = new Integer(1 + loop.size() - size);
 475                     } else if (peekToken() == DEFAULT) {
 476                         consume(DEFAULT);
 477                         consume(COLON);
 478                         while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
 479                             int size2 = loop.size();
 480                             parseStatement(false, loop);
 481                             if (size2 == loop.size()) break;
 482                         }
 483                     } else if (peekToken() == RC) {
 484                         consume(RC);
 485                         loop.add(BREAK);
 486                         break;
 487                     } else {
 488                         throw new ParserException("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 489                     }
 490                 break;
 491             }
 492
 493             case DO: {
 494                 consume(DO);
 495                 ByteCodeBlock loop = new ByteCodeBlock(curLine, sourceName);
 496                 b.add(LOOP, loop);
 497
 498                 parseStatement(false, loop);
 499                 consume(WHILE);
 500                 consume(LP);
 501                 startExpr(loop);
 502                 loop.add(JT, new Integer(2));
 503                 loop.add(BREAK);
 504                 loop.add(CONTINUE);
 505                 consume(RP);
 506                 consume(SEMI);
 507                 break;
 508             }
 509
 510             case TRY: {
 511                 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
 512                 consume(TRY);
 513                 parseStatement(true, b);
 514
 515                 if (peekToken() == CATCH) {
 516                     getToken();
 517                     consume(LP);
 518                     consume(NAME);
 519                     consume(RP);
 520                     parseStatement();   // just discard the catchblock
 521                 }
 522
 523                 if (peekToken() == FINALLY) {
 524                     consume(FINALLY);
 525                     parseStatement(false, b);
 526                 }
 527                 break;
 528             }
 529
 530         case FOR: {
 531             consume(FOR);
 532             consume(LP);
 533
 534             tok = getToken();
 535             if (tok == VAR) tok = getToken();
 536             String varName = string;
 537             boolean forIn = peekToken() == IN;
 538             pushBackToken(tok, varName);
 539
 540             if (forIn) {
 541                 consume(NAME);
 542                 consume(IN);
 543                 startExpr(b);
 544                 b.add(PUSHKEYS);
 545                 b.add(LITERAL, "length");
 546                 b.add(GET);
 547                 consume(RP);
 548                 ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
 549                 b.add(SCOPE, b2);
 550                 b2.add(LITERAL, new Integer(1));
 551                 b2.add(SUB);
 552                 b2.add(DUP);
 553                 b2.add(LITERAL, new Integer(0));
 554                 b2.add(LT);
 555                 b2.add(JT, new Integer(7));
 556                 b2.add(GET_PRESERVE);
 557                 b2.add(LITERAL, varName);
 558                 b2.add(LITERAL, varName);
 559                 b2.add(DECLARE);
 560                 b2.add(PUT);
 561                 parseStatement(false, b2);
 562                 break;
 563
 564             } else {
 565                 ByteCodeBlock b2 = new ByteCodeBlock(curLine, sourceName);
 566                 b.add(SCOPE, b2);
 567                 b.add(POP);
 568
 569                 int size = b2.size();
 570                 startExpr(b2);
 571                 if (b2.size() - size > 0) b2.add(POP);
 572                 consume(SEMI);
 573                 ByteCodeBlock e2 = startExpr();
 574                 consume(SEMI);
 575                 if (e2 == null) e2 = new ByteCodeBlock(curLine, sourceName, b.LITERAL, null);
 576
 577                 ByteCodeBlock b3 = new ByteCodeBlock(curLine, sourceName);
 578                 b2.add(LOOP, b3);
 579                 b2.add(LITERAL, null);
 580
 581                 b3.add(JT, new Integer(0));
 582                 size = b3.size();
 583                 startExpr(b3);
 584                 consume(RP);
 585                 if (b3.size() - size > 0) b3.add(POP);
 586                 b3.arg[size - 1] = new Integer(b3.size() - size + 1);
 587
 588                 b3.paste(e2);
 589                 b3.add(JT, new Integer(2));
 590                 b3.add(BREAK);
 591                 parseStatement(false, b3);
 592                 b3.add(BREAK);
 593                 break;
 594             }
 595         }
 596
 597             case NAME: {
 598                 consume(NAME);
 599                 String name = string;
 600                 if (peekToken() == COLON) {
 601                     consume(COLON);
 602                     b.add(ByteCodeBlock.LABEL, string);
 603                     break;
 604                 } else {
 605                     pushBackToken(NAME, name);
 606                     // fall through to default case
 607                 }
 608             }
 609             // fall through
 610             case RC:
 611                 if (tok == RC && braced) { consume(RC); return; }
 612             // fall through
 613             default: {
 614                 int size = b.size();
 615                 startExpr(b);
 616                 if (size == b.size()) return;
 617                 b.add(POP);
 618                 if (peekToken() == SEMI) consume(SEMI);
 619                 break;
 620             }
 621             }
 622
 623             if (!braced) return;
 624         }
 625     }
 626
 627     class ParserException extends RuntimeException {
 628         public ParserException(String s) { super(sourceName + ":" + line + " " + s); }
 629     }
 630
 631 }
 632