1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
8 /** parses a stream of lexed tokens into a tree of Expr's */
9 public class Parser extends Lexer {
11 // Constructors //////////////////////////////////////////////////////
13 public Parser(Reader r) throws IOException { super(r); }
15 public static void main(String[] s) throws Exception {
16 Parser p = new Parser(new InputStreamReader(System.in));
18 Expr block = p.parseBlock(false);
19 if (block == null) return;
20 System.out.println(block);
21 if (p.peekToken() == -1) return;
26 // Statics ////////////////////////////////////////////////////////////
28 static byte[] precedence = new byte[MAX_TOKEN + 1];
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;
50 // Parsing Logic /////////////////////////////////////////////////////////
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 {
55 int tok = peekToken();
56 boolean braced = tok == LC;
57 if (requireBraces && !braced) throw new Error("expected {");
58 if (braced) getToken();
64 switch(tok = peekToken()) {
66 case LC: smt = parseBlock(true); break;
67 case THROW: case RETURN: case ASSERT:
69 smt = new Expr(tok, parseMaximalExpr());
70 if (getToken() != SEMI) throw new Error("expected ;");
73 case GOTO: case BREAK: case CONTINUE:
75 if (getToken() == NAME)
76 smt = new Expr(tok, new Expr(string));
78 throw new Error("goto must be followed by a label");
81 if (getToken() != SEMI) throw new Error("expected ;");
85 if (braced) getToken();
90 if (!braced) break OUTER;
94 smt = parseMaximalExpr();
96 if (head == null) throw new Error("empty statement list; next token is " + codeToString[peekToken()]);
101 if (head == null) head = tail = smt; else tail = (tail.next = smt);
103 return new Expr(LC, head);
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();
110 throw new Error("expected " + codeToString[got] + ", got " + (got == -1 ? "EOL" : codeToString[got]));
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 {
117 if (peekToken() == -1) break;
119 prefix = parseSingleExpr(prefix, minPrecedence);
120 if (save == prefix) break;
121 if (prefix == null) throw new Error("parseSingleExpr() returned null");
126 public Expr parseSingleExpr(Expr prefix, int minPrecedence) throws IOException {
127 Expr e1 = null, e2 = null, e3 = null, head = null, tail = null, ret = null;
129 int tok = peekToken();
130 if (minPrecedence > 0 && tok < precedence.length && precedence[tok] != 0 && precedence[tok] <= minPrecedence) return prefix;
133 // these case arms match the precedence of operators; each arm is a precedence level.
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);
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])));
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]));
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);
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]));
164 if (prefix == null) {
166 e1 = parseMaximalExpr(null, precedence[tok]);
167 return new Expr(ASSIGN, e1, new Expr(tok == INC ? ADD : SUB, e1, new Expr(new Integer(1))));
170 return new Expr(tok, prefix);
174 if (prefix == null) { // grouping
175 Expr r = parseMaximalExpr();
176 expect(RP); getToken();
179 } else { // invocation
180 while(peekToken() != RP) {
181 Expr e = parseMaximalExpr();
182 if (head == null) head = tail = e; else tail = tail.next = e;
184 if (tok == RP) { pushBackToken(); break; }
185 if (tok != COMMA) throw new Error("expected comma or right paren, got " + codeToString[tok]);
188 return new Expr(LP, prefix, head);
192 if (prefix != null) {
194 e1 = parseMaximalExpr();
195 if (getToken() != RB) throw new Error("expected a right brace");
196 return new Expr(DOT, prefix, e1);
201 if (tok == RB) return new Expr(LB, prefix, head);
202 if (head == null) head = tail = parseMaximalExpr();
203 else tail = tail.next = parseMaximalExpr();
205 if (tok != COMMA && tok != RP) throw new Error("expected right bracket or comma");
210 if (prefix != null) throw new Error("didn't expect non-null prefix");
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;
221 if (tok != COMMA && tok != RP) throw new Error("expected right curly or comma");
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));
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;
241 if (tok == DEFAULT) {
243 } else if (tok == CASE) {
244 caseExpr = parseMaximalExpr();
246 throw new Error("expected CASE");
248 expect(COLON); getToken();
249 e1 = new Expr(tok, caseExpr, parseBlock(false));
250 if (lastExpr == null) firstExpr = e1;
251 else lastExpr.next = e1;
253 if (getToken() == RC) return new Expr(SWITCH, switchExpr, firstExpr);
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;
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; }
267 if (tok == RP) break;
268 if (tok != COMMA) throw new Error("function argument list must consist of alternating NAMEs and COMMAs");
271 return new Expr(FUNCTION, formalArgs, parseBlock(true));
275 if (prefix != null) throw new Error("didn't expect non-null prefix");
277 if (getToken() != NAME) throw new Error("variable declarations must start with a variable name");
278 Expr name = new Expr(NAME, string);
284 initVal = parseMaximalExpr();
286 e = new Expr(ASSIGN, name, initVal);
288 e = new Expr(NAME, name);
290 if (head == null) head = tail = e; else tail = tail.next = e;
291 if (tok != COMMA) break;
294 return new Expr(VAR, head);
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);
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));
311 if (tok == FINALLY) {
313 e1 = new Expr(FINALLY, parseBlock(false));
314 if (head == null) head = tail = e1; else tail = tail.next = e1;
317 if (head == null) throw new Error("try without catch or finally");
318 return new Expr(TRY, tryBlock, head);
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();
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) {
330 return new Expr(tok, parenExpr, new Expr(ELSE, firstBlock, parseBlock(false)));
332 return new Expr(tok, parenExpr, firstBlock);
335 case IN: return prefix;
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) {
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));
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)));
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);