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