6 public class Parser extends Lexer {
8 public static void main(String[] s) throws Exception { System.out.println(new Parser(new InputStreamReader(System.in)).parseExpr()); }
10 public Parser(Reader r) throws IOException { super(r); }
11 private Parser skipToken() throws IOException { getToken(); return this; }
13 /** sorta like gcc trees */
14 public static class Expr {
21 Expr next = null; // if this expr is part of a list
26 public String toString() { return toString(0); }
28 public String toString(int indent) {
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;
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);
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; }
50 /** parses a single statement */
51 public Expr parseStatement() throws IOException {
54 switch(tok = peekToken()) {
57 ret = parseBlock(true);
59 case THROW: case RETURN: case ASSERT:
60 ret = new Expr(ASSERT, skipToken().parseExpr());
62 case GOTO: case BREAK: case CONTINUE:
64 if (getToken() == NAME)
65 ret = new Expr(tok, new Expr(string));
67 throw new Error("goto must be followed by a label");
75 if (getToken() != SEMI) throw new Error("expected ;");
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();
87 while(peekToken() != RC)
88 if (head == null) head = tail = parseStatement(); else tail = tail.next = parseStatement();
90 return new Expr(LC, head);
93 static byte[] precedence = new byte[MAX_TOKEN + 1];
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;
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 {
121 int tok = getToken();
123 if (minPrecedence != 0 && tok < precedence.length && precedence[tok] != 0 && precedence[tok] < minPrecedence)
126 // these case arms match the precedence of operators; each arm is a precedence level.
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]));
135 case BITNOT: case INSTANCEOF:
136 return new Expr(tok, parseExpr(null, precedence[tok]));
138 // FIXME: this isn't 100% right
140 return new Expr(tok, prefix, (tok == INC || tok == DEC) ? null : parseExpr());
143 while(peekToken() != RP) {
144 if (head == null) head = tail = parseExpr(); else tail = tail.next = parseExpr();
146 if (tok == RP) break;
147 if (tok != COMMA) throw new Error("expected comma or right paren");
149 return new Expr(LP, prefix, head);
152 if (prefix != null) {
155 if (getToken() != RB) throw new Error("expected a right brace");
156 return new Expr(LB, prefix, e1);
161 if (tok == RB) return new Expr(LB, prefix, head);
162 if (head == null) head = tail = parseExpr(); else tail = tail.next = parseExpr();
164 if (tok != COMMA && tok != RP) throw new Error("expected right bracket or comma");
169 if (prefix != null) throw new Error("didn't expect non-null prefix");
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;
179 if (tok != COMMA && tok != RP) throw new Error("expected right curly or comma");
184 if (getToken() != COLON) throw new Error("expected colon to close ?: expression");
186 return new Expr(HOOK, prefix, e2, e3);
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;
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;
204 if (getToken() == RC) return new Expr(SWITCH, switchExpr, firstExpr);
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;
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; }
218 if (tok == RP) break;
219 if (tok != COMMA) throw new Error("function argument list must consist of alternating NAMEs and COMMAs");
222 return new Expr(tok, formalArgs, parseBlock(true));
226 return new Expr(string);
229 return new Expr(number);
232 if (prefix != null) throw new Error("didn't expect non-null prefix");
234 if (getToken() != NAME) throw new Error("variable declarations must start with a variable name");
235 Expr name = new Expr(NAME, new Expr(string));
240 initVal = parseExpr();
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;
248 return new Expr(VAR, head);
251 if (prefix != null) throw new Error("didn't expect non-null prefix");
252 return new Expr(string);
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);
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);
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);
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));
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);
300 case VOID: case RESERVED:
301 throw new Error("reserved word that you shouldn't be using");
304 throw new Error("WITH not yet implemented"); // FIXME