1/*
2 * Javassist, a Java-bytecode translator toolkit.
3 * Copyright (C) 1999-2007 Shigeru Chiba. All Rights Reserved.
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License.  Alternatively, the contents of this file may be used under
8 * the terms of the GNU Lesser General Public License Version 2.1 or later.
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 */
15
16package javassist.compiler;
17
18import javassist.compiler.ast.*;
19
20public final class Parser implements TokenId {
21    private Lex lex;
22
23    public Parser(Lex lex) {
24        this.lex = lex;
25    }
26
27    public boolean hasMore() { return lex.lookAhead() >= 0; }
28
29    /* member.declaration
30     * : method.declaration | field.declaration
31     */
32    public ASTList parseMember(SymbolTable tbl) throws CompileError {
33        ASTList mem = parseMember1(tbl);
34        if (mem instanceof MethodDecl)
35            return parseMethod2(tbl, (MethodDecl)mem);
36        else
37            return mem;
38    }
39
40    /* A method body is not parsed.
41     */
42    public ASTList parseMember1(SymbolTable tbl) throws CompileError {
43        ASTList mods = parseMemberMods();
44        Declarator d;
45        boolean isConstructor = false;
46        if (lex.lookAhead() == Identifier && lex.lookAhead(1) == '(') {
47            d = new Declarator(VOID, 0);
48            isConstructor = true;
49        }
50        else
51            d = parseFormalType(tbl);
52
53        if (lex.get() != Identifier)
54            throw new SyntaxError(lex);
55
56        String name;
57        if (isConstructor)
58            name = MethodDecl.initName;
59        else
60            name = lex.getString();
61
62        d.setVariable(new Symbol(name));
63        if (isConstructor || lex.lookAhead() == '(')
64            return parseMethod1(tbl, isConstructor, mods, d);
65        else
66            return parseField(tbl, mods, d);
67    }
68
69    /* field.declaration
70     *  : member.modifiers
71     *    formal.type Identifier
72     *    [ "=" expression ] ";"
73     */
74    private FieldDecl parseField(SymbolTable tbl, ASTList mods,
75                                Declarator d) throws CompileError
76    {
77        ASTree expr = null;
78        if (lex.lookAhead() == '=') {
79            lex.get();
80            expr = parseExpression(tbl);
81        }
82
83        int c = lex.get();
84        if (c == ';')
85            return new FieldDecl(mods, new ASTList(d, new ASTList(expr)));
86        else if (c == ',')
87            throw new CompileError(
88                "only one field can be declared in one declaration", lex);
89        else
90            throw new SyntaxError(lex);
91    }
92
93    /* method.declaration
94     *  : member.modifiers
95     *    [ formal.type ]
96     *    Identifier "(" [ formal.parameter ( "," formal.parameter )* ] ")"
97     *    array.dimension
98     *    [ THROWS class.type ( "," class.type ) ]
99     *    ( block.statement | ";" )
100     *
101     * Note that a method body is not parsed.
102     */
103    private MethodDecl parseMethod1(SymbolTable tbl, boolean isConstructor,
104                                    ASTList mods, Declarator d)
105        throws CompileError
106    {
107        if (lex.get() != '(')
108            throw new SyntaxError(lex);
109
110        ASTList parms = null;
111        if (lex.lookAhead() != ')')
112            while (true) {
113                parms = ASTList.append(parms, parseFormalParam(tbl));
114                int t = lex.lookAhead();
115                if (t == ',')
116                    lex.get();
117                else if (t == ')')
118                    break;
119            }
120
121        lex.get();      // ')'
122        d.addArrayDim(parseArrayDimension());
123        if (isConstructor && d.getArrayDim() > 0)
124            throw new SyntaxError(lex);
125
126        ASTList throwsList = null;
127        if (lex.lookAhead() == THROWS) {
128            lex.get();
129            while (true) {
130                throwsList = ASTList.append(throwsList, parseClassType(tbl));
131                if (lex.lookAhead() == ',')
132                    lex.get();
133                else
134                    break;
135            }
136        }
137
138        return new MethodDecl(mods, new ASTList(d,
139                                ASTList.make(parms, throwsList, null)));
140    }
141
142    /* Parses a method body.
143     */
144    public MethodDecl parseMethod2(SymbolTable tbl, MethodDecl md)
145        throws CompileError
146    {
147        Stmnt body = null;
148        if (lex.lookAhead() == ';')
149            lex.get();
150        else {
151            body = parseBlock(tbl);
152            if (body == null)
153                body = new Stmnt(BLOCK);
154        }
155
156        md.sublist(4).setHead(body);
157        return md;
158    }
159
160    /* member.modifiers
161     *  : ( FINAL | SYNCHRONIZED | ABSTRACT
162     *    | PUBLIC | PROTECTED | PRIVATE | STATIC
163     *    | VOLATILE | TRANSIENT | STRICT )*
164     */
165    private ASTList parseMemberMods() {
166        int t;
167        ASTList list = null;
168        while (true) {
169            t = lex.lookAhead();
170            if (t == ABSTRACT || t == FINAL || t == PUBLIC || t == PROTECTED
171                || t == PRIVATE || t == SYNCHRONIZED || t == STATIC
172                || t == VOLATILE || t == TRANSIENT || t == STRICT)
173                list = new ASTList(new Keyword(lex.get()), list);
174            else
175                break;
176        }
177
178        return list;
179    }
180
181    /* formal.type : ( build-in-type | class.type ) array.dimension
182     */
183    private Declarator parseFormalType(SymbolTable tbl) throws CompileError {
184        int t = lex.lookAhead();
185        if (isBuiltinType(t) || t == VOID) {
186            lex.get();  // primitive type
187            int dim = parseArrayDimension();
188            return new Declarator(t, dim);
189        }
190        else {
191            ASTList name = parseClassType(tbl);
192            int dim = parseArrayDimension();
193            return new Declarator(name, dim);
194        }
195    }
196
197    private static boolean isBuiltinType(int t) {
198        return (t == BOOLEAN || t == BYTE || t == CHAR || t == SHORT
199                || t == INT || t == LONG || t == FLOAT || t == DOUBLE);
200    }
201
202    /* formal.parameter : formal.type Identifier array.dimension
203     */
204    private Declarator parseFormalParam(SymbolTable tbl)
205        throws CompileError
206    {
207        Declarator d = parseFormalType(tbl);
208        if (lex.get() != Identifier)
209            throw new SyntaxError(lex);
210
211        String name = lex.getString();
212        d.setVariable(new Symbol(name));
213        d.addArrayDim(parseArrayDimension());
214        tbl.append(name, d);
215        return d;
216    }
217
218    /* statement : [ label ":" ]* labeled.statement
219     *
220     * labeled.statement
221     *          : block.statement
222     *          | if.statement
223     *          | while.statement
224     *          | do.statement
225     *          | for.statement
226     *          | switch.statement
227     *          | try.statement
228     *          | return.statement
229     *          | thorw.statement
230     *          | break.statement
231     *          | continue.statement
232     *          | declaration.or.expression
233     *          | ";"
234     *
235     * This method may return null (empty statement).
236     */
237    public Stmnt parseStatement(SymbolTable tbl)
238        throws CompileError
239    {
240        int t = lex.lookAhead();
241        if (t == '{')
242            return parseBlock(tbl);
243        else if (t == ';') {
244            lex.get();
245            return new Stmnt(BLOCK);    // empty statement
246        }
247        else if (t == Identifier && lex.lookAhead(1) == ':') {
248            lex.get();  // Identifier
249            String label = lex.getString();
250            lex.get();  // ':'
251            return Stmnt.make(LABEL, new Symbol(label), parseStatement(tbl));
252        }
253        else if (t == IF)
254            return parseIf(tbl);
255        else if (t == WHILE)
256            return parseWhile(tbl);
257        else if (t == DO)
258            return parseDo(tbl);
259        else if (t == FOR)
260            return parseFor(tbl);
261        else if (t == TRY)
262            return parseTry(tbl);
263        else if (t == SWITCH)
264            return parseSwitch(tbl);
265        else if (t == SYNCHRONIZED)
266            return parseSynchronized(tbl);
267        else if (t == RETURN)
268            return parseReturn(tbl);
269        else if (t == THROW)
270            return parseThrow(tbl);
271        else if (t == BREAK)
272            return parseBreak(tbl);
273        else if (t == CONTINUE)
274            return parseContinue(tbl);
275        else
276            return parseDeclarationOrExpression(tbl, false);
277    }
278
279    /* block.statement : "{" statement* "}"
280     */
281    private Stmnt parseBlock(SymbolTable tbl) throws CompileError {
282        if (lex.get() != '{')
283            throw new SyntaxError(lex);
284
285        Stmnt body = null;
286        SymbolTable tbl2 = new SymbolTable(tbl);
287        while (lex.lookAhead() != '}') {
288            Stmnt s = parseStatement(tbl2);
289            if (s != null)
290                body = (Stmnt)ASTList.concat(body, new Stmnt(BLOCK, s));
291        }
292
293        lex.get();      // '}'
294        if (body == null)
295            return new Stmnt(BLOCK);    // empty block
296        else
297            return body;
298    }
299
300    /* if.statement : IF "(" expression ")" statement
301     *                [ ELSE statement ]
302     */
303    private Stmnt parseIf(SymbolTable tbl) throws CompileError {
304        int t = lex.get();      // IF
305        ASTree expr = parseParExpression(tbl);
306        Stmnt thenp = parseStatement(tbl);
307        Stmnt elsep;
308        if (lex.lookAhead() == ELSE) {
309            lex.get();
310            elsep = parseStatement(tbl);
311        }
312        else
313            elsep = null;
314
315        return new Stmnt(t, expr, new ASTList(thenp, new ASTList(elsep)));
316    }
317
318    /* while.statement : WHILE "(" expression ")" statement
319     */
320    private Stmnt parseWhile(SymbolTable tbl)
321        throws CompileError
322    {
323        int t = lex.get();      // WHILE
324        ASTree expr = parseParExpression(tbl);
325        Stmnt body = parseStatement(tbl);
326        return new Stmnt(t, expr, body);
327    }
328
329    /* do.statement : DO statement WHILE "(" expression ")" ";"
330     */
331    private Stmnt parseDo(SymbolTable tbl) throws CompileError {
332        int t = lex.get();      // DO
333        Stmnt body = parseStatement(tbl);
334        if (lex.get() != WHILE || lex.get() != '(')
335            throw new SyntaxError(lex);
336
337        ASTree expr = parseExpression(tbl);
338        if (lex.get() != ')' || lex.get() != ';')
339            throw new SyntaxError(lex);
340
341        return new Stmnt(t, expr, body);
342    }
343
344    /* for.statement : FOR "(" decl.or.expr expression ";" expression ")"
345     *                 statement
346     */
347    private Stmnt parseFor(SymbolTable tbl) throws CompileError {
348        Stmnt expr1, expr3;
349        ASTree expr2;
350        int t = lex.get();      // FOR
351
352        SymbolTable tbl2 = new SymbolTable(tbl);
353
354        if (lex.get() != '(')
355            throw new SyntaxError(lex);
356
357        if (lex.lookAhead() == ';') {
358            lex.get();
359            expr1 = null;
360        }
361        else
362            expr1 = parseDeclarationOrExpression(tbl2, true);
363
364        if (lex.lookAhead() == ';')
365            expr2 = null;
366        else
367            expr2 = parseExpression(tbl2);
368
369        if (lex.get() != ';')
370            throw new CompileError("; is missing", lex);
371
372        if (lex.lookAhead() == ')')
373            expr3 = null;
374        else
375            expr3 = parseExprList(tbl2);
376
377        if (lex.get() != ')')
378            throw new CompileError(") is missing", lex);
379
380        Stmnt body = parseStatement(tbl2);
381        return new Stmnt(t, expr1, new ASTList(expr2,
382                                               new ASTList(expr3, body)));
383    }
384
385    /* switch.statement : SWITCH "(" expression ")" "{" switch.block "}"
386     *
387     * swtich.block : ( switch.label statement* )*
388     *
389     * swtich.label : DEFAULT ":"
390     *              | CASE const.expression ":"
391     */
392    private Stmnt parseSwitch(SymbolTable tbl) throws CompileError {
393        int t = lex.get();	// SWITCH
394        ASTree expr = parseParExpression(tbl);
395        Stmnt body = parseSwitchBlock(tbl);
396        return new Stmnt(t, expr, body);
397    }
398
399    private Stmnt parseSwitchBlock(SymbolTable tbl) throws CompileError {
400        if (lex.get() != '{')
401            throw new SyntaxError(lex);
402
403        SymbolTable tbl2 = new SymbolTable(tbl);
404        Stmnt s = parseStmntOrCase(tbl2);
405        if (s == null)
406            throw new CompileError("empty switch block", lex);
407
408        int op = s.getOperator();
409        if (op != CASE && op != DEFAULT)
410            throw new CompileError("no case or default in a switch block",
411                                   lex);
412
413        Stmnt body = new Stmnt(BLOCK, s);
414        while (lex.lookAhead() != '}') {
415            Stmnt s2 = parseStmntOrCase(tbl2);
416            if (s2 != null) {
417                int op2 = s2.getOperator();
418                if (op2 == CASE || op2 == DEFAULT) {
419                    body = (Stmnt)ASTList.concat(body, new Stmnt(BLOCK, s2));
420                    s = s2;
421                }
422                else
423                    s = (Stmnt)ASTList.concat(s, new Stmnt(BLOCK, s2));
424            }
425        }
426
427        lex.get();      // '}'
428        return body;
429    }
430
431    private Stmnt parseStmntOrCase(SymbolTable tbl) throws CompileError {
432        int t = lex.lookAhead();
433        if (t != CASE && t != DEFAULT)
434            return parseStatement(tbl);
435
436        lex.get();
437        Stmnt s;
438        if (t == CASE)
439            s = new Stmnt(t, parseExpression(tbl));
440        else
441            s = new Stmnt(DEFAULT);
442
443        if (lex.get() != ':')
444            throw new CompileError(": is missing", lex);
445
446        return s;
447    }
448
449    /* synchronized.statement :
450     *     SYNCHRONIZED "(" expression ")" block.statement
451     */
452    private Stmnt parseSynchronized(SymbolTable tbl) throws CompileError {
453        int t = lex.get();	// SYNCHRONIZED
454        if (lex.get() != '(')
455            throw new SyntaxError(lex);
456
457        ASTree expr = parseExpression(tbl);
458        if (lex.get() != ')')
459            throw new SyntaxError(lex);
460
461        Stmnt body = parseBlock(tbl);
462        return new Stmnt(t, expr, body);
463    }
464
465    /* try.statement
466     * : TRY block.statement
467     *   [ CATCH "(" class.type Identifier ")" block.statement ]*
468     *   [ FINALLY block.statement ]*
469     */
470    private Stmnt parseTry(SymbolTable tbl) throws CompileError {
471        lex.get();      // TRY
472        Stmnt block = parseBlock(tbl);
473        ASTList catchList = null;
474        while (lex.lookAhead() == CATCH) {
475            lex.get();  // CATCH
476            if (lex.get() != '(')
477                throw new SyntaxError(lex);
478
479            SymbolTable tbl2 = new SymbolTable(tbl);
480            Declarator d = parseFormalParam(tbl2);
481            if (d.getArrayDim() > 0 || d.getType() != CLASS)
482                throw new SyntaxError(lex);
483
484            if (lex.get() != ')')
485                throw new SyntaxError(lex);
486
487            Stmnt b = parseBlock(tbl2);
488            catchList = ASTList.append(catchList, new Pair(d, b));
489        }
490
491        Stmnt finallyBlock = null;
492        if (lex.lookAhead() == FINALLY) {
493            lex.get();  // FINALLY
494            finallyBlock = parseBlock(tbl);
495        }
496
497        return Stmnt.make(TRY, block, catchList, finallyBlock);
498    }
499
500    /* return.statement : RETURN [ expression ] ";"
501     */
502    private Stmnt parseReturn(SymbolTable tbl) throws CompileError {
503        int t = lex.get();      // RETURN
504        Stmnt s = new Stmnt(t);
505        if (lex.lookAhead() != ';')
506            s.setLeft(parseExpression(tbl));
507
508        if (lex.get() != ';')
509            throw new CompileError("; is missing", lex);
510
511        return s;
512    }
513
514    /* throw.statement : THROW expression ";"
515     */
516    private Stmnt parseThrow(SymbolTable tbl) throws CompileError {
517        int t = lex.get();      // THROW
518        ASTree expr = parseExpression(tbl);
519        if (lex.get() != ';')
520            throw new CompileError("; is missing", lex);
521
522        return new Stmnt(t, expr);
523    }
524
525    /* break.statement : BREAK [ Identifier ] ";"
526     */
527    private Stmnt parseBreak(SymbolTable tbl)
528        throws CompileError
529    {
530        return parseContinue(tbl);
531    }
532
533    /* continue.statement : CONTINUE [ Identifier ] ";"
534     */
535    private Stmnt parseContinue(SymbolTable tbl)
536        throws CompileError
537    {
538        int t = lex.get();      // CONTINUE
539        Stmnt s = new Stmnt(t);
540        int t2 = lex.get();
541        if (t2 == Identifier) {
542            s.setLeft(new Symbol(lex.getString()));
543            t2 = lex.get();
544        }
545
546        if (t2 != ';')
547            throw new CompileError("; is missing", lex);
548
549        return s;
550    }
551
552    /* declaration.or.expression
553     *      : [ FINAL ] built-in-type array.dimension declarators
554     *      | [ FINAL ] class.type array.dimension declarators
555     *      | expression ';'
556     *      | expr.list ';'             if exprList is true
557     *
558     * Note: FINAL is currently ignored.  This must be fixed
559     * in future.
560     */
561    private Stmnt parseDeclarationOrExpression(SymbolTable tbl,
562                                               boolean exprList)
563        throws CompileError
564    {
565        int t = lex.lookAhead();
566        while (t == FINAL) {
567            lex.get();
568            t = lex.lookAhead();
569        }
570
571        if (isBuiltinType(t)) {
572            t = lex.get();
573            int dim = parseArrayDimension();
574            return parseDeclarators(tbl, new Declarator(t, dim));
575        }
576        else if (t == Identifier) {
577            int i = nextIsClassType(0);
578            if (i >= 0)
579                if (lex.lookAhead(i) == Identifier) {
580                    ASTList name = parseClassType(tbl);
581                    int dim = parseArrayDimension();
582                    return parseDeclarators(tbl, new Declarator(name, dim));
583                }
584        }
585
586        Stmnt expr;
587        if (exprList)
588            expr = parseExprList(tbl);
589        else
590            expr = new Stmnt(EXPR, parseExpression(tbl));
591
592        if (lex.get() != ';')
593            throw new CompileError("; is missing", lex);
594
595        return expr;
596    }
597
598    /* expr.list : ( expression ',')* expression
599     */
600    private Stmnt parseExprList(SymbolTable tbl) throws CompileError {
601        Stmnt expr = null;
602        for (;;) {
603            Stmnt e = new Stmnt(EXPR, parseExpression(tbl));
604            expr = (Stmnt)ASTList.concat(expr, new Stmnt(BLOCK, e));
605            if (lex.lookAhead() == ',')
606                lex.get();
607            else
608                return expr;
609        }
610    }
611
612    /* declarators : declarator [ ',' declarator ]* ';'
613     */
614    private Stmnt parseDeclarators(SymbolTable tbl, Declarator d)
615        throws CompileError
616    {
617        Stmnt decl = null;
618        for (;;) {
619            decl = (Stmnt)ASTList.concat(decl,
620                                new Stmnt(DECL, parseDeclarator(tbl, d)));
621            int t = lex.get();
622            if (t == ';')
623                return decl;
624            else if (t != ',')
625                throw new CompileError("; is missing", lex);
626        }
627    }
628
629    /* declarator : Identifier array.dimension [ '=' initializer ]
630     */
631    private Declarator parseDeclarator(SymbolTable tbl, Declarator d)
632        throws CompileError
633    {
634        if (lex.get() != Identifier || d.getType() == VOID)
635            throw new SyntaxError(lex);
636
637        String name = lex.getString();
638        Symbol symbol = new Symbol(name);
639        int dim = parseArrayDimension();
640        ASTree init = null;
641        if (lex.lookAhead() == '=') {
642            lex.get();
643            init = parseInitializer(tbl);
644        }
645
646        Declarator decl = d.make(symbol, dim, init);
647        tbl.append(name, decl);
648        return decl;
649    }
650
651    /* initializer : expression | array.initializer
652     */
653    private ASTree parseInitializer(SymbolTable tbl) throws CompileError {
654        if (lex.lookAhead() == '{')
655            return parseArrayInitializer(tbl);
656        else
657            return parseExpression(tbl);
658    }
659
660    /* array.initializer :
661     *  '{' (( array.initializer | expression ) ',')* '}'
662     */
663    private ArrayInit parseArrayInitializer(SymbolTable tbl)
664        throws CompileError
665    {
666        lex.get();      // '{'
667        ASTree expr = parseExpression(tbl);
668        ArrayInit init = new ArrayInit(expr);
669        while (lex.lookAhead() == ',') {
670            lex.get();
671            expr = parseExpression(tbl);
672            ASTList.append(init, expr);
673        }
674
675        if (lex.get() != '}')
676            throw new SyntaxError(lex);
677
678        return init;
679    }
680
681    /* par.expression : '(' expression ')'
682     */
683    private ASTree parseParExpression(SymbolTable tbl) throws CompileError {
684        if (lex.get() != '(')
685            throw new SyntaxError(lex);
686
687        ASTree expr = parseExpression(tbl);
688        if (lex.get() != ')')
689            throw new SyntaxError(lex);
690
691        return expr;
692    }
693
694    /* expression : conditional.expr
695     *            | conditional.expr assign.op expression (right-to-left)
696     */
697    public ASTree parseExpression(SymbolTable tbl) throws CompileError {
698        ASTree left = parseConditionalExpr(tbl);
699        if (!isAssignOp(lex.lookAhead()))
700            return left;
701
702        int t = lex.get();
703        ASTree right = parseExpression(tbl);
704        return AssignExpr.makeAssign(t, left, right);
705    }
706
707    private static boolean isAssignOp(int t) {
708        return t == '=' || t == MOD_E || t == AND_E
709                || t == MUL_E || t == PLUS_E || t == MINUS_E || t == DIV_E
710                || t == EXOR_E || t == OR_E || t == LSHIFT_E
711                || t == RSHIFT_E || t == ARSHIFT_E;
712    }
713
714    /* conditional.expr                 (right-to-left)
715     *     : logical.or.expr [ '?' expression ':' conditional.expr ]
716     */
717    private ASTree parseConditionalExpr(SymbolTable tbl) throws CompileError {
718        ASTree cond = parseBinaryExpr(tbl);
719        if (lex.lookAhead() == '?') {
720            lex.get();
721            ASTree thenExpr = parseExpression(tbl);
722            if (lex.get() != ':')
723                throw new CompileError(": is missing", lex);
724
725            ASTree elseExpr = parseExpression(tbl);
726            return new CondExpr(cond, thenExpr, elseExpr);
727        }
728        else
729            return cond;
730    }
731
732    /* logical.or.expr          10 (operator precedence)
733     * : logical.and.expr
734     * | logical.or.expr OROR logical.and.expr          left-to-right
735     *
736     * logical.and.expr         9
737     * : inclusive.or.expr
738     * | logical.and.expr ANDAND inclusive.or.expr
739     *
740     * inclusive.or.expr        8
741     * : exclusive.or.expr
742     * | inclusive.or.expr "|" exclusive.or.expr
743     *
744     * exclusive.or.expr        7
745     *  : and.expr
746     * | exclusive.or.expr "^" and.expr
747     *
748     * and.expr                 6
749     * : equality.expr
750     * | and.expr "&" equality.expr
751     *
752     * equality.expr            5
753     * : relational.expr
754     * | equality.expr (EQ | NEQ) relational.expr
755     *
756     * relational.expr          4
757     * : shift.expr
758     * | relational.expr (LE | GE | "<" | ">") shift.expr
759     * | relational.expr INSTANCEOF class.type ("[" "]")*
760     *
761     * shift.expr               3
762     * : additive.expr
763     * | shift.expr (LSHIFT | RSHIFT | ARSHIFT) additive.expr
764     *
765     * additive.expr            2
766     * : multiply.expr
767     * | additive.expr ("+" | "-") multiply.expr
768     *
769     * multiply.expr            1
770     * : unary.expr
771     * | multiply.expr ("*" | "/" | "%") unary.expr
772     */
773    private ASTree parseBinaryExpr(SymbolTable tbl) throws CompileError {
774        ASTree expr = parseUnaryExpr(tbl);
775        for (;;) {
776            int t = lex.lookAhead();
777            int p = getOpPrecedence(t);
778            if (p == 0)
779                return expr;
780            else
781                expr = binaryExpr2(tbl, expr, p);
782        }
783    }
784
785    private ASTree parseInstanceOf(SymbolTable tbl, ASTree expr)
786        throws CompileError
787    {
788        int t = lex.lookAhead();
789        if (isBuiltinType(t)) {
790            lex.get();  // primitive type
791            int dim = parseArrayDimension();
792            return new InstanceOfExpr(t, dim, expr);
793        }
794        else {
795            ASTList name = parseClassType(tbl);
796            int dim = parseArrayDimension();
797            return new InstanceOfExpr(name, dim, expr);
798        }
799    }
800
801    private ASTree binaryExpr2(SymbolTable tbl, ASTree expr, int prec)
802        throws CompileError
803    {
804        int t = lex.get();
805        if (t == INSTANCEOF)
806            return parseInstanceOf(tbl, expr);
807
808        ASTree expr2 = parseUnaryExpr(tbl);
809        for (;;) {
810            int t2 = lex.lookAhead();
811            int p2 = getOpPrecedence(t2);
812            if (p2 != 0 && prec > p2)
813                expr2 = binaryExpr2(tbl, expr2, p2);
814            else
815                return BinExpr.makeBin(t, expr, expr2);
816        }
817    }
818
819    // !"#$%&'(    )*+,-./0    12345678    9:;<=>?
820    private static final int[] binaryOpPrecedence
821        =  { 0, 0, 0, 0, 1, 6, 0, 0,
822             0, 1, 2, 0, 2, 0, 1, 0,
823             0, 0, 0, 0, 0, 0, 0, 0,
824             0, 0, 0, 4, 0, 4, 0 };
825
826    private int getOpPrecedence(int c) {
827        if ('!' <= c && c <= '?')
828            return binaryOpPrecedence[c - '!'];
829        else if (c == '^')
830            return 7;
831        else if (c == '|')
832            return 8;
833        else if (c == ANDAND)
834            return 9;
835        else if (c == OROR)
836            return 10;
837        else if (c == EQ || c == NEQ)
838            return 5;
839        else if (c == LE || c == GE || c == INSTANCEOF)
840            return 4;
841        else if (c == LSHIFT || c == RSHIFT || c == ARSHIFT)
842            return 3;
843        else
844            return 0;   // not a binary operator
845    }
846
847    /* unary.expr : "++"|"--" unary.expr
848                  | "+"|"-" unary.expr
849                  | "!"|"~" unary.expr
850                  | cast.expr
851                  | postfix.expr
852
853       unary.expr.not.plus.minus is a unary expression starting without
854       "+", "-", "++", or "--".
855     */
856    private ASTree parseUnaryExpr(SymbolTable tbl) throws CompileError {
857        int t;
858        switch (lex.lookAhead()) {
859        case '+' :
860        case '-' :
861        case PLUSPLUS :
862        case MINUSMINUS :
863        case '!' :
864        case '~' :
865            t = lex.get();
866            if (t == '-') {
867                int t2 = lex.lookAhead();
868                switch (t2) {
869                case LongConstant :
870                case IntConstant :
871                case CharConstant :
872                    lex.get();
873                    return new IntConst(-lex.getLong(), t2);
874                case DoubleConstant :
875                case FloatConstant :
876                    lex.get();
877                    return new DoubleConst(-lex.getDouble(), t2);
878                default :
879                    break;
880                }
881            }
882
883            return Expr.make(t, parseUnaryExpr(tbl));
884        case '(' :
885            return parseCast(tbl);
886        default :
887            return parsePostfix(tbl);
888        }
889    }
890
891    /* cast.expr : "(" builtin.type ("[" "]")* ")" unary.expr
892                 | "(" class.type ("[" "]")* ")" unary.expr2
893
894       unary.expr2 is a unary.expr beginning with "(", NULL, StringL,
895       Identifier, THIS, SUPER, or NEW.
896
897       Either "(int.class)" or "(String[].class)" is a not cast expression.
898     */
899    private ASTree parseCast(SymbolTable tbl) throws CompileError {
900        int t = lex.lookAhead(1);
901        if (isBuiltinType(t) && nextIsBuiltinCast()) {
902            lex.get();  // '('
903            lex.get();  // primitive type
904            int dim = parseArrayDimension();
905            if (lex.get() != ')')
906                throw new CompileError(") is missing", lex);
907
908            return new CastExpr(t, dim, parseUnaryExpr(tbl));
909        }
910        else if (t == Identifier && nextIsClassCast()) {
911            lex.get();  // '('
912            ASTList name = parseClassType(tbl);
913            int dim = parseArrayDimension();
914            if (lex.get() != ')')
915                throw new CompileError(") is missing", lex);
916
917            return new CastExpr(name, dim, parseUnaryExpr(tbl));
918        }
919        else
920            return parsePostfix(tbl);
921    }
922
923    private boolean nextIsBuiltinCast() {
924        int t;
925        int i = 2;
926        while ((t = lex.lookAhead(i++)) == '[')
927            if (lex.lookAhead(i++) != ']')
928                return false;
929
930        return lex.lookAhead(i - 1) == ')';
931    }
932
933    private boolean nextIsClassCast() {
934        int i = nextIsClassType(1);
935        if (i < 0)
936            return false;
937
938        int t = lex.lookAhead(i);
939        if (t != ')')
940            return false;
941
942        t = lex.lookAhead(i + 1);
943        return t == '(' || t == NULL || t == StringL
944               || t == Identifier || t == THIS || t == SUPER || t == NEW
945               || t == TRUE || t == FALSE || t == LongConstant
946               || t == IntConstant || t == CharConstant
947               || t == DoubleConstant || t == FloatConstant;
948    }
949
950    private int nextIsClassType(int i) {
951        int t;
952        while (lex.lookAhead(++i) == '.')
953            if (lex.lookAhead(++i) != Identifier)
954                return -1;
955
956        while ((t = lex.lookAhead(i++)) == '[')
957            if (lex.lookAhead(i++) != ']')
958                return -1;
959
960        return i - 1;
961    }
962
963    /* array.dimension : [ "[" "]" ]*
964     */
965    private int parseArrayDimension() throws CompileError {
966        int arrayDim = 0;
967        while (lex.lookAhead() == '[') {
968            ++arrayDim;
969            lex.get();
970            if (lex.get() != ']')
971                throw new CompileError("] is missing", lex);
972        }
973
974        return arrayDim;
975    }
976
977    /* class.type : Identifier ( "." Identifier )*
978     */
979    private ASTList parseClassType(SymbolTable tbl) throws CompileError {
980        ASTList list = null;
981        for (;;) {
982            if (lex.get() != Identifier)
983                throw new SyntaxError(lex);
984
985            list = ASTList.append(list, new Symbol(lex.getString()));
986            if (lex.lookAhead() == '.')
987                lex.get();
988            else
989                break;
990        }
991
992        return list;
993    }
994
995    /* postfix.expr : number.literal
996     *              | primary.expr
997     *              | method.expr
998     *              | postfix.expr "++" | "--"
999     *              | postfix.expr "[" array.size "]"
1000     *              | postfix.expr "." Identifier
1001     *              | postfix.expr ( "[" "]" )* "." CLASS
1002     *              | postfix.expr "#" Identifier
1003     *
1004     * "#" is not an operator of regular Java.  It separates
1005     * a class name and a member name in an expression for static member
1006     * access.  For example,
1007     *     java.lang.Integer.toString(3)        in regular Java
1008     * can be written like this:
1009     *     java.lang.Integer#toString(3)        for this compiler.
1010     */
1011    private ASTree parsePostfix(SymbolTable tbl) throws CompileError {
1012        int token = lex.lookAhead();
1013        switch (token) {    // see also parseUnaryExpr()
1014        case LongConstant :
1015        case IntConstant :
1016        case CharConstant :
1017            lex.get();
1018            return new IntConst(lex.getLong(), token);
1019        case DoubleConstant :
1020        case FloatConstant :
1021            lex.get();
1022            return new DoubleConst(lex.getDouble(), token);
1023        default :
1024            break;
1025        }
1026
1027        String str;
1028        ASTree index;
1029        ASTree expr = parsePrimaryExpr(tbl);
1030        int t;
1031        while (true) {
1032            switch (lex.lookAhead()) {
1033            case '(' :
1034                expr = parseMethodCall(tbl, expr);
1035                break;
1036            case '[' :
1037                if (lex.lookAhead(1) == ']') {
1038                    int dim = parseArrayDimension();
1039                    if (lex.get() != '.' || lex.get() != CLASS)
1040                        throw new SyntaxError(lex);
1041
1042                    expr = parseDotClass(expr, dim);
1043                }
1044                else {
1045                    index = parseArrayIndex(tbl);
1046                    if (index == null)
1047                        throw new SyntaxError(lex);
1048
1049                    expr = Expr.make(ARRAY, expr, index);
1050                }
1051                break;
1052            case PLUSPLUS :
1053            case MINUSMINUS :
1054                t = lex.get();
1055                expr = Expr.make(t, null, expr);
1056                break;
1057            case '.' :
1058                lex.get();
1059                t = lex.get();
1060                if (t == CLASS) {
1061                    expr = parseDotClass(expr, 0);
1062                }
1063                else if (t == Identifier) {
1064                    str = lex.getString();
1065                    expr = Expr.make('.', expr, new Member(str));
1066                }
1067                else
1068                    throw new CompileError("missing member name", lex);
1069                break;
1070            case '#' :
1071                lex.get();
1072                t = lex.get();
1073                if (t != Identifier)
1074                    throw new CompileError("missing static member name", lex);
1075
1076                str = lex.getString();
1077                expr = Expr.make(MEMBER, new Symbol(toClassName(expr)),
1078                                 new Member(str));
1079                break;
1080            default :
1081                return expr;
1082            }
1083        }
1084    }
1085
1086    /* Parse a .class expression on a class type.  For example,
1087     * String.class   => ('.' "String" "class")
1088     * String[].class => ('.' "[LString;" "class")
1089     */
1090    private ASTree parseDotClass(ASTree className, int dim)
1091        throws CompileError
1092    {
1093        String cname = toClassName(className);
1094        if (dim > 0) {
1095            StringBuffer sbuf = new StringBuffer();
1096            while (dim-- > 0)
1097                sbuf.append('[');
1098
1099            sbuf.append('L').append(cname.replace('.', '/')).append(';');
1100            cname = sbuf.toString();
1101        }
1102
1103        return Expr.make('.', new Symbol(cname), new Member("class"));
1104    }
1105
1106    /* Parses a .class expression on a built-in type.  For example,
1107     * int.class   => ('#' "java.lang.Integer" "TYPE")
1108     * int[].class => ('.' "[I", "class")
1109     */
1110    private ASTree parseDotClass(int builtinType, int dim)
1111        throws CompileError
1112    {
1113        if (dim > 0) {
1114            String cname = CodeGen.toJvmTypeName(builtinType, dim);
1115            return Expr.make('.', new Symbol(cname), new Member("class"));
1116        }
1117        else {
1118            String cname;
1119            switch(builtinType) {
1120            case BOOLEAN :
1121                cname = "java.lang.Boolean";
1122                break;
1123            case BYTE :
1124                cname = "java.lang.Byte";
1125                break;
1126            case CHAR :
1127                cname = "java.lang.Character";
1128                break;
1129            case SHORT :
1130                cname = "java.lang.Short";
1131                break;
1132            case INT :
1133                cname = "java.lang.Integer";
1134                break;
1135            case LONG :
1136                cname = "java.lang.Long";
1137                break;
1138            case FLOAT :
1139                cname = "java.lang.Float";
1140                break;
1141            case DOUBLE :
1142                cname = "java.lang.Double";
1143                break;
1144            case VOID :
1145                cname = "java.lang.Void";
1146                break;
1147            default :
1148                throw new CompileError("invalid builtin type: "
1149                                       + builtinType);
1150            }
1151
1152            return Expr.make(MEMBER, new Symbol(cname), new Member("TYPE"));
1153        }
1154    }
1155
1156    /* method.call : method.expr "(" argument.list ")"
1157     * method.expr : THIS | SUPER | Identifier
1158     *             | postfix.expr "." Identifier
1159     *             | postfix.expr "#" Identifier
1160     */
1161    private ASTree parseMethodCall(SymbolTable tbl, ASTree expr)
1162        throws CompileError
1163    {
1164        if (expr instanceof Keyword) {
1165            int token = ((Keyword)expr).get();
1166            if (token != THIS && token != SUPER)
1167                throw new SyntaxError(lex);
1168        }
1169        else if (expr instanceof Symbol)        // Identifier
1170            ;
1171        else if (expr instanceof Expr) {
1172            int op = ((Expr)expr).getOperator();
1173            if (op != '.' && op != MEMBER)
1174                throw new SyntaxError(lex);
1175        }
1176
1177        return CallExpr.makeCall(expr, parseArgumentList(tbl));
1178    }
1179
1180    private String toClassName(ASTree name)
1181        throws CompileError
1182    {
1183        StringBuffer sbuf = new StringBuffer();
1184        toClassName(name, sbuf);
1185        return sbuf.toString();
1186    }
1187
1188    private void toClassName(ASTree name, StringBuffer sbuf)
1189        throws CompileError
1190    {
1191        if (name instanceof Symbol) {
1192            sbuf.append(((Symbol)name).get());
1193            return;
1194        }
1195        else if (name instanceof Expr) {
1196            Expr expr = (Expr)name;
1197            if (expr.getOperator() == '.') {
1198                toClassName(expr.oprand1(), sbuf);
1199                sbuf.append('.');
1200                toClassName(expr.oprand2(), sbuf);
1201                return;
1202            }
1203        }
1204
1205        throw new CompileError("bad static member access", lex);
1206    }
1207
1208    /* primary.expr : THIS | SUPER | TRUE | FALSE | NULL
1209     *              | StringL
1210     *              | Identifier
1211     *              | NEW new.expr
1212     *              | "(" expression ")"
1213     *              | builtin.type ( "[" "]" )* "." CLASS
1214     *
1215     * Identifier represents either a local variable name, a member name,
1216     * or a class name.
1217     */
1218    private ASTree parsePrimaryExpr(SymbolTable tbl) throws CompileError {
1219        int t;
1220        String name;
1221        Declarator decl;
1222        ASTree expr;
1223
1224        switch (t = lex.get()) {
1225        case THIS :
1226        case SUPER :
1227        case TRUE :
1228        case FALSE :
1229        case NULL :
1230            return new Keyword(t);
1231        case Identifier :
1232            name = lex.getString();
1233            decl = tbl.lookup(name);
1234            if (decl == null)
1235                return new Member(name);        // this or static member
1236            else
1237                return new Variable(name, decl); // local variable
1238        case StringL :
1239            return new StringL(lex.getString());
1240        case NEW :
1241            return parseNew(tbl);
1242        case '(' :
1243            expr = parseExpression(tbl);
1244            if (lex.get() == ')')
1245                return expr;
1246            else
1247                throw new CompileError(") is missing", lex);
1248        default :
1249            if (isBuiltinType(t) || t == VOID) {
1250                int dim = parseArrayDimension();
1251                if (lex.get() == '.' && lex.get() == CLASS)
1252                    return parseDotClass(t, dim);
1253            }
1254
1255            throw new SyntaxError(lex);
1256        }
1257    }
1258
1259    /* new.expr : class.type "(" argument.list ")"
1260     *          | class.type     array.size [ array.initializer ]
1261     *          | primitive.type array.size [ array.initializer ]
1262     */
1263    private NewExpr parseNew(SymbolTable tbl) throws CompileError {
1264        ArrayInit init = null;
1265        int t = lex.lookAhead();
1266        if (isBuiltinType(t)) {
1267            lex.get();
1268            ASTList size = parseArraySize(tbl);
1269            if (lex.lookAhead() == '{')
1270                init = parseArrayInitializer(tbl);
1271
1272            return new NewExpr(t, size, init);
1273        }
1274        else if (t == Identifier) {
1275            ASTList name = parseClassType(tbl);
1276            t = lex.lookAhead();
1277            if (t == '(') {
1278                ASTList args = parseArgumentList(tbl);
1279                return new NewExpr(name, args);
1280            }
1281            else if (t == '[') {
1282                ASTList size = parseArraySize(tbl);
1283                if (lex.lookAhead() == '{')
1284                    init = parseArrayInitializer(tbl);
1285
1286                return NewExpr.makeObjectArray(name, size, init);
1287            }
1288        }
1289
1290        throw new SyntaxError(lex);
1291    }
1292
1293    /* array.size : [ array.index ]*
1294     */
1295    private ASTList parseArraySize(SymbolTable tbl) throws CompileError {
1296        ASTList list = null;
1297        while (lex.lookAhead() == '[')
1298            list = ASTList.append(list, parseArrayIndex(tbl));
1299
1300        return list;
1301    }
1302
1303    /* array.index : "[" [ expression ] "]"
1304     */
1305    private ASTree parseArrayIndex(SymbolTable tbl) throws CompileError {
1306        lex.get();      // '['
1307        if (lex.lookAhead() == ']') {
1308            lex.get();
1309            return null;
1310        }
1311        else {
1312            ASTree index = parseExpression(tbl);
1313            if (lex.get() != ']')
1314                throw new CompileError("] is missing", lex);
1315
1316            return index;
1317        }
1318    }
1319
1320    /* argument.list : "(" [ expression [ "," expression ]* ] ")"
1321     */
1322    private ASTList parseArgumentList(SymbolTable tbl) throws CompileError {
1323        if (lex.get() != '(')
1324            throw new CompileError("( is missing", lex);
1325
1326        ASTList list = null;
1327        if (lex.lookAhead() != ')')
1328            for (;;) {
1329                list = ASTList.append(list, parseExpression(tbl));
1330                if (lex.lookAhead() == ',')
1331                    lex.get();
1332                else
1333                    break;
1334            }
1335
1336        if (lex.get() != ')')
1337            throw new CompileError(") is missing", lex);
1338
1339        return list;
1340    }
1341}
1342
1343