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