src/org/xwt/js/Parser.java

   1 // Copyright 2002 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 Expr's */
   8 public class Parser extends Lexer {
   9
  10     // Constructors //////////////////////////////////////////////////////
  11
  12     public Parser(Reader r) throws IOException { super(r); }
  13
  14     public static void main(String[] s) throws Exception {
  15         Parser p = new Parser(new InputStreamReader(System.in));
  16         while(true) {
  17             Expr block = p.parseBlock(false);
  18             if (block == null) return;
  19             System.out.println(block);
  20             if (p.peekToken() == -1) return;
  21         }
  22     }
  23
  24
  25     // Statics ////////////////////////////////////////////////////////////
  26
  27     static byte[] precedence = new byte[MAX_TOKEN + 1];
  28     static {
  29         precedence[COMMA] = 1;
  30         precedence[ASSIGN] = 2;
  31         precedence[GT] = precedence[GE] = 3;
  32         precedence[OR] = precedence[AND] = 4;
  33         precedence[BITOR] = 5;
  34         precedence[BITXOR] = 6;
  35         precedence[BITAND] = 7;
  36         precedence[EQ] = precedence[NE] = 8;
  37         precedence[LT] = precedence[LE] = 9;
  38         precedence[SHEQ] = precedence[SHNE] = 10;
  39         precedence[LSH] = precedence[RSH] = precedence[URSH] = 11;
  40         precedence[ADD] = precedence[SUB] = 12;
  41         precedence[MUL] = precedence[DIV] = precedence[MOD] = 13;
  42         precedence[BITNOT] = precedence[INSTANCEOF] = 14;
  43         precedence[INC] = precedence[DEC] = 15;
  44         precedence[LP] = 16;
  45         precedence[DOT] = 17;
  46     }
  47
  48
  49     // Useful Types /////////////////////////////////////////////////////////
  50
  51     /** sorta like gcc trees */
  52     public static class Expr {
  53
  54         int code = -1;
  55
  56         Expr left = null;
  57         Expr right = null;
  58         Expr next = null;   // if this expr is part of a list
  59
  60         String string = null;
  61         Number number = null;
  62
  63         public String toString() { return toString(0); }
  64         public String toString(int indent) {
  65             String ret = "";
  66             for(int i=0; i<indent; i++) ret += " ";
  67             ret += codeToString[code];
  68             if (code == NUMBER) ret += " " + number;
  69             else if (string != null) ret += " \"" + string + "\"";
  70             ret += "\n";
  71             if (left != null) ret += left.toString(indent + 2);
  72             if (right != null) ret += right.toString(indent + 2);
  73             if (next != null) ret += next.toString(indent);
  74             return ret;
  75         }
  76
  77         public Expr(String s) { code = STRING; this.string = s; }  // an identifier or label
  78         public Expr(Number n) { code = NUMBER; this.number = n; }  // an identifier or label
  79         public Expr(int code) { this(code, null, null); }
  80         public Expr(int code, String s) { this.code = code; string = s; }
  81         public Expr(int code, Expr left) { this(code, left, null); }
  82         public Expr(int code, Expr left, Expr right) { this.code = code; this.left = left; this.right = right; }
  83     }
  84
  85     /** a block is either a single statement or a list of statements surrounded by curly braces; all expressions are also statements */
  86     public Expr parseBlock(boolean requireBraces) throws IOException {
  87         Expr ret = null;
  88         int tok = peekToken();
  89         boolean braced = tok == LC;
  90         if (requireBraces && !braced) throw new Error("expected {");
  91         if (braced) getToken();
  92         Expr head = null;
  93         Expr tail = null;
  94         OUTER: while(true) {
  95             Expr smt;
  96             switch(tok = peekToken()) {
  97             case -1: break OUTER;
  98             case LC: smt = parseBlock(true); break;
  99             case THROW: case RETURN: case ASSERT:
 100                 getToken();
 101                 smt = new Expr(tok, parseMaximalExpr());
 102                 if (getToken() != SEMI) throw new Error("expected ;");
 103                 break;
 104             case GOTO: case BREAK: case CONTINUE:
 105                 getToken();
 106                 if (getToken() == NAME)
 107                     smt = new Expr(tok, new Expr(string));
 108                 else if (tok == GOTO)
 109                     throw new Error("goto must be followed by a label");
 110                 else
 111                     smt = new Expr(tok);
 112                 if (getToken() != SEMI) throw new Error("expected ;");
 113                 break;
 114
 115             case RC:
 116                 if (braced) getToken();
 117                 break OUTER;
 118
 119             case SEMI:
 120                 getToken();
 121                 if (!braced) break OUTER;
 122                 continue;
 123
 124             default:
 125                 smt = parseMaximalExpr();
 126                 if (smt == null) {
 127                     if (head == null) throw new Error("empty statement list");
 128                     break OUTER;
 129                 }
 130                 break;
 131             }
 132             if (head == null) head = tail = smt; else tail = (tail.next = smt);
 133         }
 134         return new Expr(LC, head);
 135     }
 136
 137     /** throws an error if the next token is not <tt>code</tt> */
 138     public void expect(int code) throws IOException {
 139         int got = peekToken();
 140         if (got != code)
 141             throw new Error("expected " + codeToString[got] + ", got " + (got == -1 ? "EOL" : codeToString[got]));
 142     }
 143
 144     /** parses the largest possible expression */
 145     public Expr parseMaximalExpr() throws IOException { return parseMaximalExpr(null, -1); }
 146     public Expr parseMaximalExpr(Expr prefix, int minPrecedence) throws IOException {
 147         Expr save = null;
 148         do {
 149             save = prefix;
 150             if (peekToken() == -1) break;
 151             prefix = parseSingleExpr(prefix, minPrecedence);
 152             if (prefix == null) throw new Error("parseSingleExpr_() returned null");
 153         } while (save != prefix);
 154         return prefix;
 155     }
 156
 157     /** parses the smallest possible complete expression */
 158     public Expr parseSingleExpr() throws IOException { return parseSingleExpr(null, 0); }
 159
 160     /** parses the smallest possible complete expression beginning with prefix and only using operators with at least minPrecedence */
 161     public Expr parseSingleExpr(Expr prefix, int minPrecedence) throws IOException {
 162         Expr e1 = null, e2 = null, e3 = null, head = null, tail = null, ret = null;
 163
 164         int tok = peekToken();
 165         if (minPrecedence > 0 && tok < precedence.length && precedence[tok] != 0 && precedence[tok] <= minPrecedence) return prefix;
 166         getToken();
 167
 168         // these case arms match the precedence of operators; each arm is a precedence level.
 169         switch (tok) {
 170
 171         case WITH: throw new Error("XWT does not allow the WITH keyword");
 172         case VOID: case RESERVED: throw new Error("reserved word that you shouldn't be using");
 173         case NAME: if (prefix != null) { pushBackToken(); return prefix; } else return parseMaximalExpr(new Expr(NAME, string), minPrecedence);
 174         case STRING: if (prefix != null) { pushBackToken(); return prefix; } else return new Expr(string);
 175         case NUMBER: if (prefix != null) { pushBackToken(); return prefix; } else return new Expr(number);
 176         case NULL: case TRUE: case FALSE: case NOP: if (prefix != null) { pushBackToken(); return prefix; } else return new Expr(tok);
 177
 178         case COMMA: case ASSIGN: case GT: case GE: case OR: case AND:
 179         case BITOR: case BITXOR: case BITAND: case EQ: case NE: case LT:
 180         case LE: case SHEQ: case SHNE: case LSH: case RSH: case URSH:
 181         case ADD: case SUB: case MUL: case DIV: case MOD: case DOT:
 182             return new Expr(tok, prefix, parseMaximalExpr(null, precedence[tok]));
 183
 184         case BITNOT: case INSTANCEOF:
 185             if (prefix != null) throw new Error("didn't expect non-null prefix!");
 186             return new Expr(tok, parseMaximalExpr(null, precedence[tok]));
 187
 188         case INC: case DEC:
 189             if (prefix == null) {
 190                 // prefix
 191                 return new Expr(tok, parseMaximalExpr(null, precedence[tok]));
 192             } else {
 193                 // postfix
 194                 return new Expr(tok, null, prefix);
 195             }
 196
 197         case LP:
 198             if (prefix == null) {  // grouping
 199                 Expr r = parseMaximalExpr();
 200                 expect(RP);
 201                 return r;
 202
 203             } else {  // invocation
 204                 while(peekToken() != RP) {
 205                     Expr e = parseMaximalExpr(null, precedence[COMMA]);
 206                     if (head == null) head = tail = e; else tail = tail.next = e;
 207                     tok = getToken();
 208                     if (tok == RP) { pushBackToken(); break; }
 209                     if (tok != COMMA) throw new Error("expected comma or right paren, got " + codeToString[tok]);
 210                 }
 211                 getToken();
 212                 return new Expr(LP, prefix, head);
 213             }
 214
 215         case LB:
 216             if (prefix != null) {
 217                 // subscripting
 218                 e1 = parseSingleExpr();
 219                 if (getToken() != RB) throw new Error("expected a right brace");
 220                 return new Expr(LB, prefix, e1);
 221             } else {
 222                 // array ctor
 223                 tok = getToken();
 224                 while(true) {
 225                     if (tok == RB) return new Expr(LB, prefix, head);
 226                     if (head == null) head = tail = parseSingleExpr(); else tail = tail.next = parseSingleExpr();
 227                     tok = getToken();
 228                     if (tok != COMMA && tok != RP) throw new Error("expected right bracket or comma");
 229                 }
 230             }
 231
 232         case LC:
 233             if (prefix != null) throw new Error("didn't expect non-null prefix");
 234             tok = getToken();
 235             while(true) {
 236                 if (tok == RC) return new Expr(LC, head);
 237                 if (tok != NAME) throw new Error("expecting name");
 238                 Expr name = parseSingleExpr();
 239                 if (tok != COLON) throw new Error("expecting colon");
 240                 e1 = new Expr(COLON, name, parseSingleExpr());
 241                 if (head == null) head = tail = e1; else tail = tail.next = e1;
 242                 tok = getToken();
 243                 if (tok != COMMA && tok != RP) throw new Error("expected right curly or comma");
 244             }
 245
 246         case HOOK:
 247             e2 = parseSingleExpr();
 248             if (getToken() != COLON) throw new Error("expected colon to close ?: expression");
 249             e3 = parseSingleExpr();
 250             e2.next = e3;
 251             return new Expr(HOOK, prefix, e2);
 252
 253         case SWITCH: {
 254             if (prefix != null) throw new Error("didn't expect non-null prefix");
 255             if (getToken() != LP) throw new Error("expected left paren");
 256             Expr switchExpr = parseSingleExpr();
 257             if (getToken() != RP) throw new Error("expected left paren");
 258             if (getToken() != LC) throw new Error("expected left brace");
 259             Expr firstExpr = null;
 260             Expr lastExpr = null;
 261             while(true) {
 262                 if (getToken() != CASE) throw new Error("expected CASE");
 263                 Expr caseExpr = parseSingleExpr();
 264                 if (getToken() != COLON) throw new Error("expected COLON");
 265                 Expr e = new Expr(CASE, caseExpr, parseBlock(false));
 266                 if (lastExpr == null) firstExpr = e;
 267                 else lastExpr.next = e;
 268                 lastExpr = e;
 269                 if (getToken() == RC) return new Expr(SWITCH, switchExpr, firstExpr);
 270             }
 271         }
 272
 273         case FUNCTION: {
 274             if (prefix != null) throw new Error("didn't expect non-null prefix");
 275             if (getToken() != LP) throw new Error("function keyword must be followed by a left paren");
 276             Expr formalArgs = null, cur = null;
 277             tok = getToken();
 278             while(tok != RP) {
 279                 if (tok != NAME) throw new Error("expected a variable name");
 280                 if (cur == null) { formalArgs = cur = new Expr(string); }
 281                 else { cur.next = new Expr(NAME, string); cur = cur.next; }
 282                 tok = getToken();
 283                 if (tok == RP) break;
 284                 if (tok != COMMA) throw new Error("function argument list must consist of alternating NAMEs and COMMAs");
 285                 tok = getToken();
 286             }
 287             return new Expr(FUNCTION, formalArgs, parseBlock(true));
 288         }
 289
 290         case VAR:
 291             if (prefix != null) throw new Error("didn't expect non-null prefix");
 292             while(true) {
 293                 if (getToken() != NAME) throw new Error("variable declarations must start with a variable name");
 294                 Expr name = new Expr(NAME, string);
 295                 Expr initVal = null;
 296                 tok = peekToken();
 297                 Expr e = null;
 298                 if (tok == ASSIGN) {
 299                     getToken();
 300                     initVal = parseSingleExpr();
 301                     tok = peekToken();
 302                     e = new Expr(ASSIGN, name, initVal);
 303                 } else {
 304                     e = new Expr(NAME, name);
 305                 }
 306                 if (head == null) head = tail = e; else tail = tail.next = e;
 307                 if (tok != COMMA) break;
 308                 getToken();
 309             }
 310             return new Expr(VAR, head);
 311
 312         case TRY: {
 313             // We deliberately allow you to omit braces in catch{}/finally{} if they are single statements...
 314             if (prefix != null) throw new Error("didn't expect non-null prefix");
 315             Expr tryBlock = parseBlock(true);
 316             while ((tok = peekToken()) == CATCH || tok == FINALLY) {
 317                 getToken();
 318                 if (getToken() != LP) throw new Error("expected (");
 319                 if (getToken() != NAME) throw new Error("expected name");
 320                 Expr name = new Expr(NAME, string);
 321                 if (getToken() != RP) throw new Error("expected )");
 322                 e1 = new Expr(tok, name, parseBlock(false));
 323                 if (head == null) head = tail = e1; else tail = tail.next = e1;
 324             }
 325             if (head == null) throw new Error("try without catch or finally");
 326             return new Expr(TRY, tryBlock, head);
 327         }
 328
 329         case IF: case WHILE: {
 330             if (prefix != null) throw new Error("didn't expect non-null prefix");
 331             if (getToken() != LP) throw new Error("expected left paren");
 332             Expr parenExpr = parseMaximalExpr(null, -1);
 333             int t;
 334             if ((t = getToken()) != RP) throw new Error("expected right paren, but got " + codeToString[t]);
 335             Expr firstBlock = parseBlock(false);
 336             if (tok == IF && peekToken() == ELSE) {
 337                 getToken();
 338                 firstBlock.next = parseBlock(false);
 339                 return new Expr(tok, parenExpr, firstBlock);
 340             }
 341             return new Expr(tok, parenExpr, firstBlock);
 342         }
 343
 344         case IN: return prefix;
 345         case FOR:
 346             if (prefix != null) throw new Error("didn't expect non-null prefix");
 347             if (getToken() != LP) throw new Error("expected left paren");
 348             e1 = parseMaximalExpr(null, -1);
 349             if (e1.code == NAME && peekToken() == IN) {
 350                 getToken();
 351                 e2 = parseMaximalExpr(null, -1);
 352                 if (getToken() != RP) throw new Error("expected right paren");
 353                 return new Expr(FOR, new Expr(IN, e1, e2), parseBlock(false));
 354
 355             } else {
 356                 if (getToken() != SEMI) throw new Error("expected ;");
 357                 e2 = parseMaximalExpr(null, -1);
 358                 if (getToken() != SEMI) throw new Error("expected ;");
 359                 e3 = parseMaximalExpr(null, -1);
 360                 if (getToken() != RP) throw new Error("expected right paren");
 361                 return new Expr(LC, e1, new Expr(WHILE, e2, new Expr(LC, parseBlock(false), e3)));
 362             }
 363
 364         case DO: {
 365             if (prefix != null) throw new Error("didn't expect non-null prefix");
 366             Expr firstBlock = parseBlock(false);
 367             if (getToken() != WHILE) throw new Error("expecting WHILE");
 368             if (getToken() != LP) throw new Error("expected left paren");
 369             Expr whileExpr = parseSingleExpr();
 370             if (getToken() != RP) throw new Error("expected right paren");
 371             if (getToken() != SEMI) throw new Error("semicolon");
 372             return new Expr(DO, firstBlock, whileExpr);
 373         }
 374
 375         default:
 376             pushBackToken();
 377             return prefix;
 378         }
 379     }
 380
 381 }
 382