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