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