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 CompiledFunction'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         CompiledFunction block = new CompiledFunction("stdin", 0, new InputStreamReader(System.in), null);
  18         if (block == null) return;
  19         System.out.println(block);
  20     }
  21
  22
  23     // Statics ////////////////////////////////////////////////////////////
  24
  25     static byte[] precedence = new byte[MAX_TOKEN + 1];
  26     static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
  27     static {
  28         isRightAssociative[ASSIGN] = true;
  29
  30         precedence[ASSIGN] = 1;
  31         precedence[HOOK] = 2;
  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;
  46         precedence[LP] = 17;
  47         precedence[LB] = 18;
  48         precedence[DOT] = 19;
  49     }
  50
  51
  52     // Parsing Logic /////////////////////////////////////////////////////////
  53
  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]));
  58     }
  59
  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 {
  62         int tok = getToken();
  63         CompiledFunction b = appendTo;
  64
  65         switch (tok) {
  66         case -1: return;
  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;
  72         case LB: {
  73             b.add(line, ARRAY, new Integer(0));
  74             int i = 0;
  75             while(true) {
  76                 int size = b.size();
  77                 startExpr(-1, b);
  78                 if (size == b.size())
  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);
  82                 b.add(line, PUT);
  83                 b.add(line, POP);
  84                 if (peekToken() == RB) { consume(RB); continueExpr(b, minPrecedence); return; }
  85                 consume(COMMA);
  86             }
  87         }
  88         case SUB: {
  89             consume(NUMBER);
  90             b.add(line, CompiledFunction.LITERAL, new Double(number.doubleValue() * -1));
  91             continueExpr(b, minPrecedence);
  92             return;
  93         }
  94         case LP: {
  95             startExpr(-1, b);
  96             consume(RP);
  97             continueExpr(b, minPrecedence);
  98             return;
  99         }
 100         case INC: case DEC: {
 101             // prefix
 102             startExpr(precedence[tok], b);
 103             b.set(b.size() - 1, tok, new Boolean(true));
 104             continueExpr(b, minPrecedence);
 105             return;
 106         }
 107         case BANG: case BITNOT: case TYPEOF: {
 108             startExpr(precedence[tok], b);
 109             b.add(line, tok);
 110             continueExpr(b, minPrecedence);
 111             return;
 112         }
 113         case LC: {
 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");
 117                 getToken();
 118                 b.add(line, LITERAL, string);
 119                 consume(COLON);
 120                 startExpr(-1, b);
 121                 b.add(line, PUT);
 122                 b.add(line, POP);
 123                 if (peekToken() == RC) break;
 124                 consume(COMMA);
 125                 if (peekToken() == RC) break;
 126             }
 127             consume(RC);
 128             continueExpr(b, minPrecedence);
 129             return;
 130         }
 131         case NAME: {
 132             String name = string;
 133             if (peekToken() == ASSIGN) {
 134                 consume(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);
 141             } else {
 142                 b.add(line, TOPSCOPE);
 143                 b.add(line, CompiledFunction.LITERAL, name);
 144                 b.add(line, CompiledFunction.GET);
 145             }
 146             continueExpr(b, minPrecedence);
 147             return;
 148         }
 149         case FUNCTION: {
 150             consume(LP);
 151             int numArgs = 0;
 152             CompiledFunction b2 = new CompiledFunction(sourceName, line, null);
 153             b2.add(line, TOPSCOPE);
 154             b2.add(line, SWAP);
 155             b2.add(line, LITERAL, "arguments");
 156             b2.add(line, LITERAL, "arguments");
 157             b2.add(line, DECLARE);
 158             b2.add(line, SWAP);
 159             b2.add(line, PUT);
 160             b2.add(line, SWAP);
 161             b2.add(line, POP);
 162             if (peekToken() == RP) consume(RP);
 163             else while(true) {
 164                 if (peekToken() == COMMA) {
 165                     consume(COMMA);
 166
 167                 } else {
 168                     consume(NAME);
 169
 170                     // declare the name
 171                     b2.add(line, LITERAL, string);
 172                     b2.add(line, DECLARE);
 173
 174                     // retrieve it from the arguments array
 175                     b2.add(line, LITERAL, new Integer(numArgs));
 176                     b2.add(line, GET_PRESERVE);
 177                     b2.add(line, SWAP);
 178                     b2.add(line, POP);
 179
 180                     // put it to the current scope
 181                     b2.add(line, TOPSCOPE);
 182                     b2.add(line, SWAP);
 183                     b2.add(line, LITERAL, string);
 184                     b2.add(line, SWAP);
 185                     b2.add(line, PUT);
 186
 187                     // clean the stack
 188                     b2.add(line, POP);
 189                     b2.add(line, POP);
 190
 191                     if (peekToken() == RP) { consume(RP); break; }
 192                     consume(COMMA);
 193                 }
 194                 numArgs++;
 195             }
 196             // pop off the arguments array
 197             b2.add(line, POP);
 198             parseStatement(true, b2);
 199             b2.add(line, LITERAL, null);
 200             b2.add(line, RETURN);
 201             continueExpr(b.add(line, NEWFUNCTION, b2), minPrecedence);
 202             return;
 203         }
 204         default: pushBackToken(); return;
 205         }
 206     }
 207
 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;
 216
 217         switch (tok) {
 218
 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);
 228             return;
 229         }
 230
 231         case INC: case DEC: {
 232             // postfix
 233             b.set(b.size() - 1, tok, new Boolean(false));
 234             continueExpr(b, minPrecedence);
 235             return;
 236         }
 237
 238         case LP: {
 239             // invocation
 240             int i = 0;
 241             while(peekToken() != RP) {
 242                 i++;
 243                 startExpr(-1, b);
 244                 if (peekToken() == RP) break;
 245                 consume(COMMA);
 246             }
 247             consume(RP);
 248             b.add(line, CALL, new Integer(i));
 249             continueExpr(b, minPrecedence);
 250             return;
 251         }
 252
 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);
 257             b.add(line, tok);
 258             continueExpr(b, minPrecedence);
 259             return;
 260         }
 261
 262         case OR: case AND: {
 263             b.add(line, tok == AND ? b.JF : b.JT, new Integer(0));
 264             int size = b.size();
 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);
 270             return;
 271         }
 272
 273         case DOT: {
 274             consume(NAME);
 275             String target = string;
 276             if (peekToken() == ASSIGN) {
 277                 consume(ASSIGN);
 278                 b.add(line, LITERAL, target);
 279                 startExpr(-1, b);
 280                 b.add(line, PUT);
 281                 b.add(line, SWAP);
 282                 b.add(line, POP);
 283             } else {
 284                 b.add(line, LITERAL, target);
 285                 b.add(line, GET);
 286             }
 287             continueExpr(b, minPrecedence);
 288             return;
 289         }
 290
 291         case LB: {
 292             startExpr(-1, b);
 293             consume(RB);
 294             if (peekToken() == ASSIGN) {
 295                 consume(ASSIGN);
 296                 startExpr(-1, b);
 297                 b.add(line, PUT);
 298                 b.add(line, SWAP);
 299                 b.add(line, POP);
 300             } else {
 301                 b.add(line, GET);
 302             }
 303             continueExpr(b, minPrecedence);
 304             return;
 305         }
 306
 307         case HOOK: {
 308             b.add(line, JF, new Integer(0));
 309             int size = b.size();
 310             startExpr(-1, b);
 311             b.set(size - 1, new Integer(b.size() - size + 2));
 312             b.add(line, JMP, new Integer(0));
 313             consume(COLON);
 314             size = b.size();
 315             startExpr(-1, b);
 316             b.set(size - 1, new Integer(b.size() - size + 1));
 317             continueExpr(b, minPrecedence);
 318             return;
 319         }
 320
 321         default: { pushBackToken(); return; }
 322         }
 323     }
 324
 325     /**
 326      *  a block is either a single statement or a list of statements surrounded by curly braces;
 327      *  all expressions are also statements
 328      */
 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;
 334         return ret;
 335     }
 336
 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);
 345         while(true) {
 346             switch(tok = peekToken()) {
 347
 348             case THROW: case RETURN: case ASSERT: {
 349                 getToken();
 350                 if (tok == RETURN && peekToken() == SEMI) b.add(line, LITERAL, null);
 351                 else startExpr(-1, b);
 352                 consume(SEMI);
 353                 b.add(line, tok);
 354                 break;
 355             }
 356
 357             case BREAK: case CONTINUE: {
 358                 getToken();
 359                 if (peekToken() == NAME) consume(NAME);
 360                 b.add(line, tok, string);
 361                 consume(SEMI);
 362                 break;
 363             }
 364
 365             case SEMI: {
 366                 consume(SEMI);
 367                 if (!braced) return;
 368                 break;
 369             }
 370
 371             case VAR: {
 372                 consume(VAR);
 373                 b.add(line, TOPSCOPE);                               // push the current scope
 374                 while(true) {
 375                     consume(NAME);
 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
 381                         consume(ASSIGN);
 382                         startExpr(-1, b);
 383                         b.add(line, PUT);
 384                         b.add(line, POP);
 385                     }
 386                     if (peekToken() != COMMA) break;
 387                     consume(COMMA);
 388                 }
 389                 b.add(line, POP);
 390                 if (peekToken() == SEMI) consume(SEMI);
 391                 break;
 392             }
 393
 394             case IF: {
 395                 consume(IF);
 396                 consume(LP);
 397                 startExpr(-1, b);
 398                 consume(RP);
 399
 400                 b.add(line, JF, new Integer(0));
 401                 int size = b.size();
 402                 parseStatement(false, b);
 403
 404                 if (peekToken() == ELSE) {
 405                     consume(ELSE);
 406                     b.set(size - 1, new Integer(2 + b.size() - size));
 407                     b.add(line, JMP, new Integer(0));
 408                     size = b.size();
 409                     parseStatement(false, b);
 410                 }
 411                 b.set(size - 1, new Integer(1 + b.size() - size));
 412                 break;
 413             }
 414
 415             case WHILE: {
 416                 consume(WHILE);
 417                 consume(LP);
 418                 if (label != null) b.add(line, LABEL, label);
 419                 b.add(line, LOOP);
 420                 int size = b.size();
 421                 b.add(line, POP);
 422                 startExpr(-1, b);
 423                 b.add(line, JT, new Integer(2));
 424                 b.add(line, BREAK);
 425                 consume(RP);
 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
 429                 break;
 430             }
 431
 432             case SWITCH: {
 433                 consume(SWITCH);
 434                 consume(LP);
 435                 if (label != null) b.add(line, LABEL, label);
 436                 b.add(line, LOOP);
 437                 int size0 = b.size();
 438                 startExpr(-1, b);
 439                 consume(RP);
 440                 consume(LC);
 441                 while(true)
 442                     if (peekToken() == CASE) {
 443                         consume(CASE);
 444                         b.add(line, DUP);
 445                         startExpr(-1, b);
 446                         consume(COLON);
 447                         b.add(line, EQ);
 448                         b.add(line, JF, new Integer(0));
 449                         int size = b.size();
 450                         while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
 451                             int size2 = b.size();
 452                             parseStatement(false, b);
 453                             if (size2 == b.size()) break;
 454                         }
 455                         b.set(size - 1, new Integer(1 + b.size() - size));
 456                     } else if (peekToken() == DEFAULT) {
 457                         consume(DEFAULT);
 458                         consume(COLON);
 459                         while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) {
 460                             int size2 = b.size();
 461                             parseStatement(false, b);
 462                             if (size2 == b.size()) break;
 463                         }
 464                     } else if (peekToken() == RC) {
 465                         consume(RC);
 466                         b.add(line, BREAK);
 467                         break;
 468                     } else {
 469                         throw new ParserException("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
 470                     }
 471                 b.add(line, BREAK);
 472                 b.set(size0 - 1, new Integer(b.size() - size0 + 1));      // end of the loop
 473                 break;
 474             }
 475
 476             case DO: {
 477                 consume(DO);
 478                 if (label != null) b.add(line, LABEL, label);
 479                 b.add(line, LOOP);
 480                 int size = b.size();
 481                 parseStatement(false, b);
 482                 consume(WHILE);
 483                 consume(LP);
 484                 startExpr(-1, b);
 485                 b.add(line, JT, new Integer(2));
 486                 b.add(line, BREAK);
 487                 b.add(line, CONTINUE);
 488                 consume(RP);
 489                 consume(SEMI);
 490                 b.set(size - 1, new Integer(b.size() - size + 1));      // end of the loop
 491                 break;
 492             }
 493
 494             case TRY: {
 495                 // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
 496                 consume(TRY);
 497                 b.add(line, TRY);
 498                 int size = b.size();
 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
 504
 505                 if (peekToken() == CATCH) {
 506                     getToken();
 507                     consume(LP);
 508                     consume(NAME);
 509                     consume(RP);
 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
 512                     b.add(line, SWAP);
 513                     b.add(line, LITERAL);
 514                     b.add(line, SWAP);
 515                     b.add(line, PUT);
 516                     b.add(line, POP);
 517                     b.add(line, POP);
 518                     parseStatement(false, b);
 519                 }
 520
 521                 b.set(size2 - 1, new Integer(b.size() - size2 + 1)); // jump here if no exception was thrown
 522
 523                       // FIXME: not implemented correctly
 524                 if (peekToken() == FINALLY) {
 525                     consume(FINALLY);
 526                     parseStatement(false, b);
 527                 }
 528                 break;
 529             }
 530
 531             case FOR: {
 532                 consume(FOR);
 533                 consume(LP);
 534
 535                 tok = getToken();
 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);
 541
 542                 if (forIn) {
 543                     // FIXME: break needs to work in here
 544                     consume(NAME);
 545                     consume(IN);
 546                     startExpr(-1, b);
 547                     b.add(line, PUSHKEYS);
 548                     b.add(line, LITERAL, "length");
 549                     b.add(line, GET);
 550                     consume(RP);
 551                     CompiledFunction b2 = new CompiledFunction(sourceName, line, null);
 552
 553                     b.add(line, NEWSCOPE);
 554
 555                     b.add(line, LITERAL, new Integer(1));
 556                     b.add(line, SUB);
 557                     b.add(line, DUP);
 558                     b.add(line, LITERAL, new Integer(0));
 559                     b.add(line, LT);
 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);
 565                     b.add(line, PUT);
 566                     parseStatement(false, b);
 567
 568                     b.add(line, OLDSCOPE);
 569
 570                     break;
 571
 572                 } else {
 573                     if (hadVar) pushBackToken(VAR, null);
 574                     b.add(line, NEWSCOPE);
 575
 576                     parseStatement(false, b);
 577                     CompiledFunction e2 = new CompiledFunction(sourceName, line, null);
 578                     startExpr(-1, e2);
 579                     consume(SEMI);
 580                     if (e2 == null) e2 = new CompiledFunction(sourceName, line, null).add(line, b.LITERAL, Boolean.TRUE);
 581
 582                     if (label != null) b.add(line, LABEL, label);
 583                     b.add(line, LOOP);
 584                     int size2 = b.size();
 585
 586                     b.add(line, JT, new Integer(0));
 587                     int size = b.size();
 588                     startExpr(-1, b);
 589                     if (b.size() > size) b.add(line, POP);
 590                     b.set(size - 1, new Integer(b.size() - size + 1));
 591                     consume(RP);
 592
 593                     b.paste(e2);
 594                     b.add(line, JT, new Integer(2));
 595                     b.add(line, BREAK);
 596                     parseStatement(false, b);
 597                     b.add(line, CONTINUE);
 598                     b.set(size2 - 1, new Integer(b.size() - size2 + 1));      // end of the loop
 599
 600                     b.add(line, OLDSCOPE);
 601                     break;
 602                 }
 603             }
 604
 605             case NAME: {
 606                 consume(NAME);
 607                 String possiblyTheLabel = string;
 608                 if (peekToken() == COLON) {
 609                     consume(COLON);
 610                     label = possiblyTheLabel;
 611                     System.out.println("label == " + label);
 612                     parseStatement(false, b, label);
 613                     break;
 614                 } else {
 615                     pushBackToken(NAME, possiblyTheLabel);
 616                     // fall through to default case
 617                 }
 618             }
 619             // fall through
 620             case RC:
 621                 if (tok == RC && braced) { consume(RC); return; }
 622             // fall through
 623             default: {
 624                 int size = b.size();
 625                 startExpr(-1, b);
 626                 if (size == b.size()) return;
 627                 b.add(line, POP);
 628                 if (peekToken() == SEMI) consume(SEMI);
 629                 break;
 630             }
 631             }
 632
 633             if (!braced) return;
 634         }
 635     }
 636
 637     private class ParserException extends RuntimeException {
 638         public ParserException(String s) { super(sourceName + ":" + line + " " + s); }
 639     }
 640
 641 }
 642