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