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