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 { super(r, sourceName, line); }
  14
  15     /** for debugging */
  16     public static void main(String[] s) throws Exception {
  17         Parser p = new Parser(new InputStreamReader(System.in), "stdin", 0);
  18         while(true) {
  19             ByteCodeBlock block = new ByteCodeBlock(0, "stdin");
  20             p.parseStatement(false, block);
  21             if (block == null) return;
  22             System.out.println(block);
  23             if (p.peekToken() == -1) return;
  24         }
  25     }
  26
  27
  28     // Statics ////////////////////////////////////////////////////////////
  29
  30     static byte[] precedence = new byte[MAX_TOKEN + 1];
  31     static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
  32     static {
  33         isRightAssociative[ASSIGN] = true;
  34
  35         precedence[ASSIGN] = 1;
  36         precedence[HOOK] = 2;
  37         precedence[COMMA] = 3;
  38         precedence[OR] = precedence[AND] = 4;
  39         precedence[GT] = precedence[GE] = 5;
  40         precedence[BITOR] = 6;
  41         precedence[BITXOR] = 7;
  42         precedence[BITAND] = 8;
  43         precedence[EQ] = precedence[NE] = 9;
  44         precedence[LT] = precedence[LE] = 10;
  45         precedence[SHEQ] = precedence[SHNE] = 11;
  46         precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
  47         precedence[ADD] = precedence[SUB] = 13;
  48         precedence[MUL] = precedence[DIV] = precedence[MOD] = 14;
  49         precedence[BITNOT] =  15;
  50         precedence[INC] = precedence[DEC] = 16;
  51         precedence[LP] = 17;
  52         precedence[LB] = 18;
  53         precedence[DOT] = 19;
  54     }
  55
  56
  57     // Parsing Logic /////////////////////////////////////////////////////////
  58
  59     private ByteCodeBlock newbb(int line) { return new ByteCodeBlock(line, sourceName); }
  60
  61     /** gets a token and throws an exception if it is not <tt>code</tt> */
  62     public void consume(int code) throws IOException {
  63         if (getToken() != code)
  64             throw new ParserException("expected " + codeToString[code] + ", got " + (op == -1 ? "EOF" : codeToString[op]));
  65     }
  66
  67     /** append the largest expression beginning with prefix containing no operators of precedence below <tt>minPrecedence</tt> */
  68     public void startExpr(ByteCodeBlock block) throws IOException { startExpr(-1, block); }
  69     /*
  70     public ByteCodeBlock startExpr(int minPrecedence) throws IOException {
  71         ByteCodeBlock ret = new ByteCodeBlock(line, sourceName);
  72         startExpr(minPrecedence, ret);
  73         return ret.size() == 0 ? null : ret;
  74     }
  75     */
  76
  77     public void startExpr(int minPrecedence, ByteCodeBlock appendTo) throws IOException {
  78         int tok = getToken();
  79         int curLine = line;
  80         if (tok == -1) return;
  81
  82         ByteCodeBlock b = appendTo;
  83
  84         switch (tok) {
  85         case NUMBER: continueExpr(b.add(ByteCodeBlock.LITERAL, number), minPrecedence); return;
  86         case STRING: continueExpr(b.add(ByteCodeBlock.LITERAL, string), minPrecedence); return;
  87         case THIS: continueExpr(b.add(TOPSCOPE, null), minPrecedence); return;
  88         case NULL: continueExpr(b.add(ByteCodeBlock.LITERAL, null), minPrecedence); return;
  89         case TRUE: case FALSE: continueExpr(b.add(ByteCodeBlock.LITERAL, new Boolean(tok == TRUE)), minPrecedence); return;
  90         case LB: {
  91             b.add(ARRAY, new Integer(0));
  92             int i = 0;
  93             while(true) {
  94                 int size = b.size();
  95                 startExpr(b);
  96                 if (size == b.size())
  97                     if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
  98                 b.add(LITERAL, new Integer(i++));
  99                 if (size == b.size()) b.add(LITERAL, null);
 100                 b.add(PUT);
 101                 b.add(POP);
 102                 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
 103                 consume(COMMA);
 104             }
 105         }
 106         case SUB: {
 107             consume(NUMBER);
 108             b.add(ByteCodeBlock.LITERAL, new Double(number.doubleValue() * -1));
 109             continueExpr(b, minPrecedence);
 110             return;
 111         }
 112         case LP: {
 113             startExpr(b);
 114             consume(RP);
 115             continueExpr(b, minPrecedence);
 116             return;
 117         }
 118         case INC: case DEC: {
 119             // prefix
 120             startExpr(precedence[tok], b);
 121             b.set(b.size() - 1, tok, new Boolean(true));
 122             continueExpr(b, minPrecedence);
 123             return;
 124         }
 125         case BANG: case BITNOT: case TYPEOF: {
 126             startExpr(precedence[tok], b);
 127             b.add(tok);
 128             continueExpr(b, minPrecedence);
 129             return;
 130         }
 131         case LC: {
 132             b.add(OBJECT, null);
 133             if (peekToken() != RC) while(true) {
 134                 if (peekToken() != NAME && peekToken() != STRING) throw new Error("expected NAME or STRING");
 135                 getToken();
 136                 b.add(LITERAL, string);
 137                 consume(COLON);
 138                 startExpr(b);
 139                 b.add(PUT);
 140                 b.add(POP);
 141                 if (peekToken() == RC) break;
 142                 consume(COMMA);
 143                 if (peekToken() == RC) break;
 144             }
 145             consume(RC);
 146             continueExpr(b, minPrecedence);
 147             return;
 148         }
 149         case NAME: {
 150             String name = string;
 151             if (peekToken() == ASSIGN) {
 152                 consume(ASSIGN);
 153                 b.add(TOPSCOPE);
 154                 b.add(ByteCodeBlock.LITERAL, name);
 155                 startExpr(minPrecedence, b);
 156                 b.add(ByteCodeBlock.PUT);
 157                 b.add(ByteCodeBlock.SWAP);
 158                 b.add(ByteCodeBlock.POP);
 159             } else {
 160                 b.add(TOPSCOPE);
 161                 b.add(ByteCodeBlock.LITERAL, name);
 162                 b.add(ByteCodeBlock.GET);
 163             }
 164             continueExpr(b, minPrecedence);
 165             return;
 166         }
 167         case FUNCTION: {
 168             consume(LP);
 169             int numArgs = 0;
 170             ByteCodeBlock b2 = newbb(curLine);
 171             b2.add(TOPSCOPE);
 172             b2.add(SWAP);
 173             b2.add(LITERAL, "arguments");
 174             b2.add(LITERAL, "arguments");
 175             b2.add(DECLARE);
 176             b2.add(SWAP);
 177             b2.add(PUT);
 178             b2.add(SWAP);
 179             b2.add(POP);
 180             if (peekToken() == RP) consume(RP);
 181             else while(true) {
 182                 if (peekToken() == COMMA) {
 183                     consume(COMMA);
 184
 185                 } else {
 186                     consume(NAME);
 187
 188                     // declare the name
 189                     b2.add(LITERAL, string);
 190                     b2.add(DECLARE);
 191
 192                     // retrieve it from the arguments array
 193                     b2.add(LITERAL, new Integer(numArgs));
 194                     b2.add(GET_PRESERVE);
 195                     b2.add(SWAP);
 196                     b2.add(POP);
 197
 198                     // put it to the current scope
 199                     b2.add(TOPSCOPE);
 200                     b2.add(SWAP);
 201                     b2.add(LITERAL, string);
 202                     b2.add(SWAP);
 203                     b2.add(PUT);
 204
 205                     // clean the stack
 206                     b2.add(POP);
 207                     b2.add(POP);
 208
 209                     if (peekToken() == RP) { consume(RP); break; }
 210                     consume(COMMA);
 211                 }
 212                 numArgs++;
 213             }
 214             // pop off the arguments array
 215             b2.add(POP);
 216             parseStatement(true, b2);
 217             b2.add(LITERAL, null);
 218             b2.add(RETURN);
 219             continueExpr(b.add(NEWFUNCTION, b2), minPrecedence);
 220             return;
 221         }
 222         default: pushBackToken(); return;
 223         }
 224     }
 225
 226     public void continueExpr(ByteCodeBlock prefix, int minPrecedence) throws IOException {
 227         int tok = getToken();
 228         int curLine = line;
 229         if (tok == -1) return;
 230         if (minPrecedence > 0 && precedence[tok] != 0)
 231             if (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))
 232                 { pushBackToken(); return; }
 233
 234         if (prefix == null) throw new Error("got null prefix");
 235         ByteCodeBlock b = prefix;
 236
 237         switch (tok) {
 238
 239         case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
 240         case ASSIGN_ADD: case ASSIGN_SUB: case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: {
 241             prefix.set(prefix.size() - 1, b.GET_PRESERVE, new Boolean(true));
 242             startExpr(precedence[tok - 1], b);
 243             prefix.add(tok - 1);
 244             prefix.add(PUT);
 245             prefix.add(SWAP);
 246             prefix.add(POP);
 247             continueExpr(b, minPrecedence);
 248             return;
 249         }
 250
 251         case INC: case DEC: {
 252             // postfix
 253             b.set(b.size() - 1, tok, new Boolean(false));
 254             continueExpr(b, minPrecedence);
 255             return;
 256         }
 257
 258         case LP: {
 259             // invocation
 260             int i = 0;
 261             while(peekToken() != RP) {
 262                 i++;
 263                 startExpr(b);
 264                 if (peekToken() == RP) break;
 265                 consume(COMMA);
 266             }
 267             consume(RP);
 268             b.add(CALL, new Integer(i));
 269             continueExpr(b, minPrecedence);
 270             return;
 271         }
 272
 273         case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
 274         case RSH: case URSH: case ADD: case MUL: case DIV: case MOD:
 275         case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
 276             startExpr(precedence[tok], b);
 277             b.add(tok);
 278             continueExpr(b, minPrecedence);
 279             return;
 280         }
 281
 282         case OR: case AND: {
 283             b.add(tok == AND ? b.JF : b.JT, new Integer(0));
 284             int size = b.size();
 285             startExpr(precedence[tok], b);
 286             b.set(size - 1, new Integer(b.size() - size + 2));
 287             b.add(JMP, new Integer(2));
 288             b.add(LITERAL, tok == AND ? new Boolean(false) : new Boolean(true));
 289             continueExpr(b, minPrecedence);
 290             return;
 291         }
 292
 293         case DOT: {
 294             consume(NAME);
 295             String target = string;
 296             if (peekToken() == ASSIGN) {
 297                 consume(ASSIGN);
 298                 b.add(LITERAL, target);
 299                 startExpr(b);
 300                 b.add(PUT);
 301                 b.add(SWAP);
 302                 b.add(POP);
 303             } else {
 304                 b.add(LITERAL, target);
 305                 b.add(GET);
 306             }
 307             continueExpr(b, minPrecedence);
 308             return;
 309         }
 310
 311         case LB: {
 312             startExpr(b);
 313             consume(RB);
 314             if (peekToken() == ASSIGN) {
 315                 consume(ASSIGN);
 316                 startExpr(b);
 317                 b.add(PUT);
 318                 b.add(SWAP);
 319                 b.add(POP);
 320             } else {
 321                 b.add(GET);
 322             }
 323             continueExpr(b, minPrecedence);
 324             return;
 325         }
 326
 327         case HOOK: {
 328             b.add(JF, new Integer(0));
 329             int size = b.size();
 330             startExpr(b);
 331             b.set(size - 1, new Integer(b.size() - size + 2));
 332             b.add(JMP, new Integer(0));
 333             consume(COLON);
 334             size = b.size();
 335             startExpr(b);
 336             b.set(size - 1, new Integer(b.size() - size + 1));
 337             continueExpr(b, minPrecedence);
 338             return;
 339         }
 340
 341         default: { pushBackToken(); return; }
 342         }
 343     }
 344
 345     /** a block is either a single statement or a list of statements surrounded by curly braces; all expressions are also statements */
 346
 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, ByteCodeBlock b) throws IOException {
 356         int tok = peekToken();
 357         if (tok == -1) return;
 358         boolean braced = tok == LC;
 359         if (requireBraces && !braced) throw new ParserException("expected {, got " + codeToString[tok]);
 360         if (braced) consume(LC);
 361         int curLine = line;
 362         while(true) {
 363             switch(tok = peekToken()) {
 364
 365             case THROW: case RETURN: case ASSERT: {
 366                 getToken();
 367                 if (tok == RETURN && peekToken() == SEMI) b.add(LITERAL, null);
 368                 else startExpr(b);
 369                 consume(SEMI);
 370                 b.add(tok);
 371                 break;
 372             }
 373
 374             case BREAK: case CONTINUE: {
 375                 getToken();
 376                 if (peekToken() == NAME) consume(NAME);
 377                 b.add(tok, string);
 378                 consume(SEMI);
 379                 break;
 380             }
 381
 382             case SEMI:
 383                 consume(SEMI);
 384                 if (!braced) return;
 385                 break;
 386
 387             case VAR: {
 388                 consume(VAR);
 389                 b.add(TOPSCOPE);                               // push the current scope
 390                 while(true) {
 391                     consume(NAME);
 392                     String name = string;
 393                     b.add(LITERAL, name);                // push the name to be declared
 394                     b.add(DECLARE);                      // declare it
 395                     if (peekToken() == ASSIGN) {           // if there is an '=' after the variable name
 396                         b.add(LITERAL, name);            // put the var name back on the stack
 397                         consume(ASSIGN);
 398                         startExpr(b);
 399                         b.add(PUT);
 400                         b.add(POP);
 401                     }
 402                     if (peekToken() != COMMA) break;
 403                     consume(COMMA);
 404                 }
 405                 b.add(POP);
 406                 if (peekToken() == SEMI) consume(SEMI);
 407                 break;
 408             }
 409
 410             case IF: {
 411                 consume(IF);
 412                 consume(LP);
 413                 startExpr(b);
 414                 consume(RP);
 415
 416                 b.add(JF, new Integer(0));
 417                 int size = b.size();
 418                 parseStatement(false, b);
 419
 420                 if (peekToken() == ELSE) {
 421                     consume(ELSE);
 422                     b.set(size - 1, new Integer(2 + b.size() - size));
 423                     b.add(JMP, new Integer(0));
 424                     size = b.size();
 425                     parseStatement(false, b);
 426                 }
 427                 b.set(size - 1, new Integer(1 + b.size() - size));
 428                 break;
 429             }
 430
 431             case WHILE: {
 432                 consume(WHILE);
 433                 consume(LP);
 434                 b.add(LOOP);
 435                 int size = b.size();
 436                 b.add(POP);
 437                 startExpr(b);
 438                 b.add(JT, new Integer(2));
 439                 b.add(BREAK);
 440                 consume(RP);
 441                 parseStatement(false, b);
 442                 b.add(CONTINUE);                                    // if we fall out of the end, definately continue
 443                 b.set(size - 1, new Integer(b.size() - size + 1));  // end of the loop
 444                 break;
 445             }
 446
 447             case SWITCH: {
 448                 consume(SWITCH);
 449                 consume(LP);
 450                 b.add(LOOP);
 451                 int size0 = b.size();
 452                 startExpr(b);
 453                 consume(RP);
 454                 consume(LC);
 455                 while(true)
 456                     if (peekToken() == CASE) {
 457                         consume(CASE);
 458                         b.add(DUP);
 459                         startExpr(b);
 460                         consume(COLON);
 461                         b.add(EQ);
 462                         b.add(JF, new Integer(0));
 463                         int size = b.size();
 464                         while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
 465                             int size2 = b.size();
 466                             parseStatement(false, b);
 467                             if (size2 == b.size()) break;
 468                         }
 469                         b.set(size - 1, new Integer(1 + b.size() - size));
 470                     } else if (peekToken() == DEFAULT) {
 471                         consume(DEFAULT);
 472                         consume(COLON);
 473                         while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
 474                             int size2 = b.size();
 475                             parseStatement(false, b);
 476                             if (size2 == b.size()) break;
 477                         }
 478                     } else if (peekToken() == RC) {
 479                         consume(RC);
 480                         b.add(BREAK);
 481                         break;
 482                     } else {
 483                         throw new ParserException("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 484                     }
 485                 b.add(BREAK);
 486                 b.set(size0 - 1, new Integer(b.size() - size0 + 1));      // end of the loop
 487                 break;
 488             }
 489
 490             case DO: {
 491                 consume(DO);
 492                 b.add(LOOP);
 493                 int size = b.size();
 494                 parseStatement(false, b);
 495                 consume(WHILE);
 496                 consume(LP);
 497                 startExpr(b);
 498                 b.add(JT, new Integer(2));
 499                 b.add(BREAK);
 500                 b.add(CONTINUE);
 501                 consume(RP);
 502                 consume(SEMI);
 503                 b.set(size - 1, new Integer(b.size() - size + 1));      // end of the loop
 504                 break;
 505             }
 506
 507             case TRY: {
 508                 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
 509                 consume(TRY);
 510                 parseStatement(true, b);
 511
 512                 if (peekToken() == CATCH) {
 513                     getToken();
 514                     consume(LP);
 515                     consume(NAME);
 516                     consume(RP);
 517                     parseStatement();   // just discard the catchblock
 518                 }
 519
 520                 if (peekToken() == FINALLY) {
 521                     consume(FINALLY);
 522                     parseStatement(false, b);
 523                 }
 524                 break;
 525             }
 526
 527         case FOR: {
 528             consume(FOR);
 529             consume(LP);
 530
 531             tok = getToken();
 532             boolean hadVar = false;
 533             if (tok == VAR) { hadVar = true; tok = getToken(); }
 534             String varName = string;
 535             boolean forIn = peekToken() == IN;
 536             pushBackToken(tok, varName);
 537
 538             if (forIn) {
 539                 // FIXME: break needs to work in here
 540                 consume(NAME);
 541                 consume(IN);
 542                 startExpr(b);
 543                 b.add(PUSHKEYS);
 544                 b.add(LITERAL, "length");
 545                 b.add(GET);
 546                 consume(RP);
 547                 ByteCodeBlock b2 = newbb(curLine);
 548
 549                 b.add(PUSHSCOPE);
 550
 551                 b.add(LITERAL, new Integer(1));
 552                 b.add(SUB);
 553                 b.add(DUP);
 554                 b.add(LITERAL, new Integer(0));
 555                 b.add(LT);
 556                 b.add(JT, new Integer(7));
 557                 b.add(GET_PRESERVE);
 558                 b.add(LITERAL, varName);
 559                 b.add(LITERAL, varName);
 560                 b.add(DECLARE);
 561                 b.add(PUT);
 562                 parseStatement(false, b);
 563
 564                 b.add(POPSCOPE);
 565
 566                 break;
 567
 568             } else {
 569                 if (hadVar) pushBackToken(VAR, null);
 570                 b.add(PUSHSCOPE);
 571
 572                 parseStatement(false, b);
 573                 ByteCodeBlock e2 = new ByteCodeBlock(line, sourceName);
 574                 startExpr(e2);
 575                 consume(SEMI);
 576                 if (e2 == null) e2 = newbb(curLine).add(b.LITERAL, Boolean.TRUE);
 577
 578                 b.add(LOOP);
 579                 int size2 = b.size();
 580
 581                 b.add(JT, new Integer(0));
 582                 int size = b.size();
 583                 startExpr(b);
 584                 if (b.size() > size) b.add(POP);
 585                 b.set(size - 1, new Integer(b.size() - size + 1));
 586                 consume(RP);
 587
 588                 b.paste(e2);
 589                 b.add(JT, new Integer(2));
 590                 b.add(BREAK);
 591                 parseStatement(false, b);
 592                 b.add(CONTINUE);
 593                 b.set(size2 - 1, new Integer(b.size() - size2 + 1));      // end of the loop
 594
 595                 b.add(POPSCOPE);
 596                 break;
 597             }
 598         }
 599
 600             case NAME: {
 601                 consume(NAME);
 602                 String name = string;
 603                 if (peekToken() == COLON) {
 604                     consume(COLON);
 605                     b.add(ByteCodeBlock.LABEL, string);
 606                     break;
 607                 } else {
 608                     pushBackToken(NAME, name);
 609                     // fall through to default case
 610                 }
 611             }
 612             // fall through
 613             case RC:
 614                 if (tok == RC && braced) { consume(RC); return; }
 615             // fall through
 616             default: {
 617                 int size = b.size();
 618                 startExpr(b);
 619                 if (size == b.size()) return;
 620                 b.add(POP);
 621                 if (peekToken() == SEMI) consume(SEMI);
 622                 break;
 623             }
 624             }
 625
 626             if (!braced) return;
 627         }
 628     }
 629
 630     class ParserException extends RuntimeException {
 631         public ParserException(String s) { super(sourceName + ":" + line + " " + s); }
 632     }
 633
 634 }
 635