src/org/xwt/js/Parser.java

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