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