src/org/xwt/js/Parser.java

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