1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
7 /** parses a stream of lexed tokens into a tree of Expr's */
8 public class Parser extends Lexer {
10 // Constructors //////////////////////////////////////////////////////
12 public Parser(Reader r) throws IOException { super(r); }
14 public static void main(String[] s) throws Exception {
15 Parser p = new Parser(new InputStreamReader(System.in));
17 Expr block = p.parseBlock(false);
18 if (block == null) return;
19 System.out.println(block);
20 if (p.peekToken() == -1) return;
25 // Statics ////////////////////////////////////////////////////////////
27 static byte[] precedence = new byte[MAX_TOKEN + 1];
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;
49 // Useful Types /////////////////////////////////////////////////////////
51 /** sorta like gcc trees */
52 public static class Expr {
58 Expr next = null; // if this expr is part of a list
63 public String toString() { return toString(0); }
64 public String toString(int indent) {
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 + "\"";
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);
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; }
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 {
88 int tok = peekToken();
89 boolean braced = tok == LC;
90 if (requireBraces && !braced) throw new Error("expected {");
91 if (braced) getToken();
96 switch(tok = peekToken()) {
98 case LC: smt = parseBlock(true); break;
99 case THROW: case RETURN: case ASSERT:
101 smt = new Expr(tok, parseMaximalExpr());
102 if (getToken() != SEMI) throw new Error("expected ;");
104 case GOTO: case BREAK: case CONTINUE:
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");
112 if (getToken() != SEMI) throw new Error("expected ;");
116 if (braced) getToken();
121 if (!braced) break OUTER;
125 smt = parseMaximalExpr();
127 if (head == null) throw new Error("empty statement list");
132 if (head == null) head = tail = smt; else tail = (tail.next = smt);
134 return new Expr(LC, head);
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();
141 throw new Error("expected " + codeToString[got] + ", got " + (got == -1 ? "EOL" : codeToString[got]));
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 {
150 if (peekToken() == -1) break;
151 prefix = parseSingleExpr(prefix, minPrecedence);
152 if (prefix == null) throw new Error("parseSingleExpr_() returned null");
153 } while (save != prefix);
157 /** parses the smallest possible complete expression */
158 public Expr parseSingleExpr() throws IOException { return parseSingleExpr(null, 0); }
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;
164 int tok = peekToken();
165 if (minPrecedence > 0 && tok < precedence.length && precedence[tok] != 0 && precedence[tok] <= minPrecedence) return prefix;
168 // these case arms match the precedence of operators; each arm is a precedence level.
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);
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]));
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]));
189 if (prefix == null) {
191 return new Expr(tok, parseMaximalExpr(null, precedence[tok]));
194 return new Expr(tok, null, prefix);
198 if (prefix == null) { // grouping
199 Expr r = parseMaximalExpr();
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;
208 if (tok == RP) { pushBackToken(); break; }
209 if (tok != COMMA) throw new Error("expected comma or right paren, got " + codeToString[tok]);
212 return new Expr(LP, prefix, head);
216 if (prefix != null) {
218 e1 = parseSingleExpr();
219 if (getToken() != RB) throw new Error("expected a right brace");
220 return new Expr(LB, prefix, e1);
225 if (tok == RB) return new Expr(LB, prefix, head);
226 if (head == null) head = tail = parseSingleExpr(); else tail = tail.next = parseSingleExpr();
228 if (tok != COMMA && tok != RP) throw new Error("expected right bracket or comma");
233 if (prefix != null) throw new Error("didn't expect non-null prefix");
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;
243 if (tok != COMMA && tok != RP) throw new Error("expected right curly or comma");
247 e2 = parseSingleExpr();
248 if (getToken() != COLON) throw new Error("expected colon to close ?: expression");
249 e3 = parseSingleExpr();
251 return new Expr(HOOK, prefix, e2);
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;
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;
269 if (getToken() == RC) return new Expr(SWITCH, switchExpr, firstExpr);
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;
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; }
283 if (tok == RP) break;
284 if (tok != COMMA) throw new Error("function argument list must consist of alternating NAMEs and COMMAs");
287 return new Expr(FUNCTION, formalArgs, parseBlock(true));
291 if (prefix != null) throw new Error("didn't expect non-null prefix");
293 if (getToken() != NAME) throw new Error("variable declarations must start with a variable name");
294 Expr name = new Expr(NAME, string);
300 initVal = parseSingleExpr();
302 e = new Expr(ASSIGN, name, initVal);
304 e = new Expr(NAME, name);
306 if (head == null) head = tail = e; else tail = tail.next = e;
307 if (tok != COMMA) break;
310 return new Expr(VAR, head);
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) {
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;
325 if (head == null) throw new Error("try without catch or finally");
326 return new Expr(TRY, tryBlock, head);
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);
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) {
338 firstBlock.next = parseBlock(false);
339 return new Expr(tok, parenExpr, firstBlock);
341 return new Expr(tok, parenExpr, firstBlock);
344 case IN: return prefix;
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) {
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));
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)));
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);