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