1   // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
3   package jminusminus;
4   
5   import java.util.ArrayList;
6   
7   import static jminusminus.TokenKind.*;
8   
9   /**
10   * A recursive descent parser that, given a lexical analyzer (a LookaheadScanner), parses a j--
11   * compilation unit (program file), taking tokens from the LookaheadScanner, and produces an
12   * abstract syntax tree (AST) for it.
13   */
14  public class Parser {
15      // The lexical analyzer with which tokens are scanned.
16      private LookaheadScanner scanner;
17  
18      // Whether a parser error has been found.
19      private boolean isInError;
20  
21      // Whether we have recovered from a parser error.
22      private boolean isRecovered;
23  
24      /**
25       * Constructs a parser from the given lexical analyzer.
26       *
27       * @param scanner the lexical analyzer with which tokens are scanned.
28       */
29      public Parser(LookaheadScanner scanner) {
30          this.scanner = scanner;
31          isInError = false;
32          isRecovered = true;
33  
34          // Prime the pump.
35          scanner.next();
36      }
37  
38      /**
39       * Returns true if a parser error has occurred up to now, and false otherwise.
40       *
41       * @return true if a parser error has occurred up to now, and false otherwise.
42       */
43      public boolean errorHasOccurred() {
44          return isInError;
45      }
46  
47      /**
48       * Parses a compilation unit (a program file) and returns an AST for it.
49       *
50       * <pre>
51       *     compilationUnit ::= [ PACKAGE qualifiedIdentifier SEMI ]
52       *                         { IMPORT  qualifiedIdentifier SEMI }
53       *                         { typeDeclaration }
54       *                         EOF
55       * </pre>
56       *
57       * @return an AST for a compilation unit.
58       */
59      public JCompilationUnit compilationUnit() {
60          int line = scanner.token().line();
61          String fileName = scanner.fileName();
62          TypeName packageName = null;
63          if (have(PACKAGE)) {
64              packageName = qualifiedIdentifier();
65              mustBe(SEMI);
66          }
67          ArrayList<TypeName> imports = new ArrayList<TypeName>();
68          while (have(IMPORT)) {
69              imports.add(qualifiedIdentifier());
70              mustBe(SEMI);
71          }
72          ArrayList<JAST> typeDeclarations = new ArrayList<JAST>();
73          while (!see(EOF)) {
74              JAST typeDeclaration = typeDeclaration();
75              if (typeDeclaration != null) {
76                  typeDeclarations.add(typeDeclaration);
77              }
78          }
79          mustBe(EOF);
80          return new JCompilationUnit(fileName, line, packageName, imports, typeDeclarations);
81      }
82  
83      /**
84       * Parses and returns a qualified identifier.
85       *
86       * <pre>
87       *   qualifiedIdentifier ::= IDENTIFIER { DOT IDENTIFIER }
88       * </pre>
89       *
90       * @return a qualified identifier.
91       */
92      private TypeName qualifiedIdentifier() {
93          int line = scanner.token().line();
94          mustBe(IDENTIFIER);
95          String qualifiedIdentifier = scanner.previousToken().image();
96          while (have(DOT)) {
97              mustBe(IDENTIFIER);
98              qualifiedIdentifier += "." + scanner.previousToken().image();
99          }
100         return new TypeName(line, qualifiedIdentifier);
101     }
102 
103     /**
104      * Parses a type declaration and returns an AST for it.
105      *
106      * <pre>
107      *   typeDeclaration ::= modifiers classDeclaration
108      * </pre>
109      *
110      * @return an AST for a type declaration.
111      */
112     private JAST typeDeclaration() {
113         ArrayList<String> mods = modifiers();
114         return classDeclaration(mods);
115     }
116 
117     /**
118      * Parses and returns a list of modifiers.
119      *
120      * <pre>
121      *   modifiers ::= { ABSTRACT | PRIVATE | PROTECTED | PUBLIC | STATIC }
122      * </pre>
123      *
124      * @return a list of modifiers.
125      */
126     private ArrayList<String> modifiers() {
127         ArrayList<String> mods = new ArrayList<String>();
128         boolean scannedPUBLIC = false;
129         boolean scannedPROTECTED = false;
130         boolean scannedPRIVATE = false;
131         boolean scannedSTATIC = false;
132         boolean scannedABSTRACT = false;
133         boolean more = true;
134         while (more) {
135             if (have(ABSTRACT)) {
136                 mods.add("abstract");
137                 if (scannedABSTRACT) {
138                     reportParserError("Repeated modifier: abstract");
139                 }
140                 scannedABSTRACT = true;
141             } else if (have(PRIVATE)) {
142                 mods.add("private");
143                 if (scannedPRIVATE) {
144                     reportParserError("Repeated modifier: private");
145                 }
146                 if (scannedPUBLIC || scannedPROTECTED) {
147                     reportParserError("Access conflict in modifiers");
148                 }
149                 scannedPRIVATE = true;
150             } else if (have(PROTECTED)) {
151                 mods.add("protected");
152                 if (scannedPROTECTED) {
153                     reportParserError("Repeated modifier: protected");
154                 }
155                 if (scannedPUBLIC || scannedPRIVATE) {
156                     reportParserError("Access conflict in modifiers");
157                 }
158                 scannedPROTECTED = true;
159             } else if (have(PUBLIC)) {
160                 mods.add("public");
161                 if (scannedPUBLIC) {
162                     reportParserError("Repeated modifier: public");
163                 }
164                 if (scannedPROTECTED || scannedPRIVATE) {
165                     reportParserError("Access conflict in modifiers");
166                 }
167                 scannedPUBLIC = true;
168             } else if (have(STATIC)) {
169                 mods.add("static");
170                 if (scannedSTATIC) {
171                     reportParserError("Repeated modifier: static");
172                 }
173                 scannedSTATIC = true;
174             } else if (have(ABSTRACT)) {
175                 mods.add("abstract");
176                 if (scannedABSTRACT) {
177                     reportParserError("Repeated modifier: abstract");
178                 }
179                 scannedABSTRACT = true;
180             } else {
181                 more = false;
182             }
183         }
184         return mods;
185     }
186 
187     /**
188      * Parses a class declaration and returns an AST for it.
189      *
190      * <pre>
191      *   classDeclaration ::= CLASS IDENTIFIER [ EXTENDS qualifiedIdentifier ] classBody
192      * </pre>
193      *
194      * @param mods the class modifiers.
195      * @return an AST for a class declaration.
196      */
197     private JClassDeclaration classDeclaration(ArrayList<String> mods) {
198         int line = scanner.token().line();
199         mustBe(CLASS);
200         mustBe(IDENTIFIER);
201         String name = scanner.previousToken().image();
202         Type superClass;
203         if (have(EXTENDS)) {
204             superClass = qualifiedIdentifier();
205         } else {
206             superClass = Type.OBJECT;
207         }
208         return new JClassDeclaration(line, mods, name, superClass, null, classBody());
209     }
210 
211     /**
212      * Parses a class body and returns a list of members in the body.
213      *
214      * <pre>
215      *   classBody ::= LCURLY { modifiers memberDecl } RCURLY
216      * </pre>
217      *
218      * @return a list of members in the class body.
219      */
220     private ArrayList<JMember> classBody() {
221         ArrayList<JMember> members = new ArrayList<JMember>();
222         mustBe(LCURLY);
223         while (!see(RCURLY) && !see(EOF)) {
224             ArrayList<String> mods = modifiers();
225             members.add(memberDecl(mods));
226         }
227         mustBe(RCURLY);
228         return members;
229     }
230 
231     /**
232      * Parses a member declaration and returns an AST for it.
233      *
234      * <pre>
235      *   memberDecl ::= IDENTIFIER formalParameters block
236      *                | ( VOID | type ) IDENTIFIER formalParameters ( block | SEMI )
237      *                | type variableDeclarators SEMI
238      * </pre>
239      *
240      * @param mods the class member modifiers.
241      * @return an AST for a member declaration.
242      */
243     private JMember memberDecl(ArrayList<String> mods) {
244         int line = scanner.token().line();
245         JMember memberDecl = null;
246         if (seeIdentLParen()) {
247             // A constructor.
248             mustBe(IDENTIFIER);
249             String name = scanner.previousToken().image();
250             ArrayList<JFormalParameter> params = formalParameters();
251             JBlock body = block();
252             memberDecl = new JConstructorDeclaration(line, mods, name, params, null, body);
253         } else {
254             Type type = null;
255             if (have(VOID)) {
256                 // A void method.
257                 type = Type.VOID;
258                 mustBe(IDENTIFIER);
259                 String name = scanner.previousToken().image();
260                 ArrayList<JFormalParameter> params = formalParameters();
261                 JBlock body = have(SEMI) ? null : block();
262                 memberDecl = new JMethodDeclaration(line, mods, name, type, params, null, body);
263             } else {
264                 type = type();
265                 if (seeIdentLParen()) {
266                     // A non void method.
267                     mustBe(IDENTIFIER);
268                     String name = scanner.previousToken().image();
269                     ArrayList<JFormalParameter> params = formalParameters();
270                     JBlock body = have(SEMI) ? null : block();
271                     memberDecl = new JMethodDeclaration(line, mods, name, type, params, null, body);
272                 } else {
273                     // A field.
274                     memberDecl = new JFieldDeclaration(line, mods, variableDeclarators(type));
275                     mustBe(SEMI);
276                 }
277             }
278         }
279         return memberDecl;
280     }
281 
282     /**
283      * Parses a block and returns an AST for it.
284      *
285      * <pre>
286      *   block ::= LCURLY { blockStatement } RCURLY
287      * </pre>
288      *
289      * @return an AST for a block.
290      */
291     private JBlock block() {
292         int line = scanner.token().line();
293         ArrayList<JStatement> statements = new ArrayList<JStatement>();
294         mustBe(LCURLY);
295         while (!see(RCURLY) && !see(EOF)) {
296             statements.add(blockStatement());
297         }
298         mustBe(RCURLY);
299         return new JBlock(line, statements);
300     }
301 
302     /**
303      * Parses a block statement and returns an AST for it.
304      *
305      * <pre>
306      *   blockStatement ::= localVariableDeclarationStatement
307      *                    | statement
308      * </pre>
309      *
310      * @return an AST for a block statement.
311      */
312     private JStatement blockStatement() {
313         if (seeLocalVariableDeclaration()) {
314             return localVariableDeclarationStatement();
315         } else {
316             return statement();
317         }
318     }
319 
320     /**
321      * Parses a statement and returns an AST for it.
322      *
323      * <pre>
324      *   statement ::= block
325      *               | IF parExpression statement [ ELSE statement ]
326      *               | RETURN [ expression ] SEMI
327      *               | SEMI
328      *               | WHILE parExpression statement
329      *               | statementExpression SEMI
330      * </pre>
331      *
332      * @return an AST for a statement.
333      */
334     private JStatement statement() {
335         int line = scanner.token().line();
336         if (see(LCURLY)) {
337             return block();
338         } else if (have(IF)) {
339             JExpression test = parExpression();
340             JStatement consequent = statement();
341             JStatement alternate = have(ELSE) ? statement() : null;
342             return new JIfStatement(line, test, consequent, alternate);
343         } else if (have(RETURN)) {
344             if (have(SEMI)) {
345                 return new JReturnStatement(line, null);
346             } else {
347                 JExpression expr = expression();
348                 mustBe(SEMI);
349                 return new JReturnStatement(line, expr);
350             }
351         } else if (have(SEMI)) {
352             return new JEmptyStatement(line);
353         } else if (have(WHILE)) {
354             JExpression test = parExpression();
355             JStatement statement = statement();
356             return new JWhileStatement(line, test, statement);
357         } else {
358             // Must be a statementExpression.
359             JStatement statement = statementExpression();
360             mustBe(SEMI);
361             return statement;
362         }
363     }
364 
365     /**
366      * Parses and returns a list of formal parameters.
367      *
368      * <pre>
369      *   formalParameters ::= LPAREN [ formalParameter { COMMA formalParameter } ] RPAREN
370      * </pre>
371      *
372      * @return a list of formal parameters.
373      */
374     private ArrayList<JFormalParameter> formalParameters() {
375         ArrayList<JFormalParameter> parameters = new ArrayList<JFormalParameter>();
376         mustBe(LPAREN);
377         if (have(RPAREN)) {
378             return parameters;
379         }
380         do {
381             parameters.add(formalParameter());
382         } while (have(COMMA));
383         mustBe(RPAREN);
384         return parameters;
385     }
386 
387     /**
388      * Parses a formal parameter and returns an AST for it.
389      *
390      * <pre>
391      *   formalParameter ::= type IDENTIFIER
392      * </pre>
393      *
394      * @return an AST for a formal parameter.
395      */
396     private JFormalParameter formalParameter() {
397         int line = scanner.token().line();
398         Type type = type();
399         mustBe(IDENTIFIER);
400         String name = scanner.previousToken().image();
401         return new JFormalParameter(line, name, type);
402     }
403 
404     /**
405      * Parses a parenthesized expression and returns an AST for it.
406      *
407      * <pre>
408      *   parExpression ::= LPAREN expression RPAREN
409      * </pre>
410      *
411      * @return an AST for a parenthesized expression.
412      */
413     private JExpression parExpression() {
414         mustBe(LPAREN);
415         JExpression expr = expression();
416         mustBe(RPAREN);
417         return expr;
418     }
419 
420     /**
421      * Parses a local variable declaration statement and returns an AST for it.
422      *
423      * <pre>
424      *   localVariableDeclarationStatement ::= type variableDeclarators SEMI
425      * </pre>
426      *
427      * @return an AST for a local variable declaration statement.
428      */
429     private JVariableDeclaration localVariableDeclarationStatement() {
430         int line = scanner.token().line();
431         Type type = type();
432         ArrayList<JVariableDeclarator> vdecls = variableDeclarators(type);
433         mustBe(SEMI);
434         return new JVariableDeclaration(line, vdecls);
435     }
436 
437     /**
438      * Parses and returns a list of variable declarators.
439      *
440      * <pre>
441      *   variableDeclarators ::= variableDeclarator { COMMA variableDeclarator }
442      * </pre>
443      *
444      * @param type type of the variables.
445      * @return a list of variable declarators.
446      */
447     private ArrayList<JVariableDeclarator> variableDeclarators(Type type) {
448         ArrayList<JVariableDeclarator> variableDeclarators = new ArrayList<JVariableDeclarator>();
449         do {
450             variableDeclarators.add(variableDeclarator(type));
451         } while (have(COMMA));
452         return variableDeclarators;
453     }
454 
455     /**
456      * Parses a variable declarator and returns an AST for it.
457      *
458      * <pre>
459      *   variableDeclarator ::= IDENTIFIER [ ASSIGN variableInitializer ]
460      * </pre>
461      *
462      * @param type type of the variable.
463      * @return an AST for a variable declarator.
464      */
465     private JVariableDeclarator variableDeclarator(Type type) {
466         int line = scanner.token().line();
467         mustBe(IDENTIFIER);
468         String name = scanner.previousToken().image();
469         JExpression initial = have(ASSIGN) ? variableInitializer(type) : null;
470         return new JVariableDeclarator(line, name, type, initial);
471     }
472 
473     /**
474      * Parses a variable initializer and returns an AST for it.
475      *
476      * <pre>
477      *   variableInitializer ::= arrayInitializer | expression
478      * </pre>
479      *
480      * @param type type of the variable.
481      * @return an AST for a variable initializer.
482      */
483     private JExpression variableInitializer(Type type) {
484         if (see(LCURLY)) {
485             return arrayInitializer(type);
486         }
487         return expression();
488     }
489 
490     /**
491      * Parses an array initializer and returns an AST for it.
492      *
493      * <pre>
494      *   arrayInitializer ::= LCURLY [ variableInitializer { COMMA variableInitializer }
495      *                                 [ COMMA ] ] RCURLY
496      * </pre>
497      *
498      * @param type type of the array.
499      * @return an AST for an array initializer.
500      */
501     private JArrayInitializer arrayInitializer(Type type) {
502         int line = scanner.token().line();
503         ArrayList<JExpression> initials = new ArrayList<JExpression>();
504         mustBe(LCURLY);
505         if (have(RCURLY)) {
506             return new JArrayInitializer(line, type, initials);
507         }
508         initials.add(variableInitializer(type.componentType()));
509         while (have(COMMA)) {
510             initials.add(see(RCURLY) ? null : variableInitializer(type.componentType()));
511         }
512         mustBe(RCURLY);
513         return new JArrayInitializer(line, type, initials);
514     }
515 
516     /**
517      * Parses and returns a list of arguments.
518      *
519      * <pre>
520      *   arguments ::= LPAREN [ expression { COMMA expression } ] RPAREN
521      * </pre>
522      *
523      * @return a list of arguments.
524      */
525     private ArrayList<JExpression> arguments() {
526         ArrayList<JExpression> args = new ArrayList<JExpression>();
527         mustBe(LPAREN);
528         if (have(RPAREN)) {
529             return args;
530         }
531         do {
532             args.add(expression());
533         } while (have(COMMA));
534         mustBe(RPAREN);
535         return args;
536     }
537 
538     /**
539      * Parses and returns a type.
540      *
541      * <pre>
542      *   type ::= referenceType | basicType
543      * </pre>
544      *
545      * @return a type.
546      */
547     private Type type() {
548         if (seeReferenceType()) {
549             return referenceType();
550         }
551         return basicType();
552     }
553 
554     /**
555      * Parses and returns a basic type.
556      *
557      * <pre>
558      *   basicType ::= BOOLEAN | CHAR | INT
559      * </pre>
560      *
561      * @return a basic type.
562      */
563     private Type basicType() {
564         if (have(BOOLEAN)) {
565             return Type.BOOLEAN;
566         } else if (have(CHAR)) {
567             return Type.CHAR;
568         } else if (have(INT)) {
569             return Type.INT;
570         } else {
571             reportParserError("Type sought where %s found", scanner.token().image());
572             return Type.ANY;
573         }
574     }
575 
576     /**
577      * Parses and returns a reference type.
578      *
579      * <pre>
580      *   referenceType ::= basicType LBRACK RBRACK { LBRACK RBRACK }
581      *                   | qualifiedIdentifier { LBRACK RBRACK }
582      * </pre>
583      *
584      * @return a reference type.
585      */
586     private Type referenceType() {
587         Type type = null;
588         if (!see(IDENTIFIER)) {
589             type = basicType();
590             mustBe(LBRACK);
591             mustBe(RBRACK);
592             type = new ArrayTypeName(type);
593         } else {
594             type = qualifiedIdentifier();
595         }
596         while (seeDims()) {
597             mustBe(LBRACK);
598             mustBe(RBRACK);
599             type = new ArrayTypeName(type);
600         }
601         return type;
602     }
603 
604     /**
605      * Parses a statement expression and returns an AST for it.
606      *
607      * <pre>
608      *   statementExpression ::= expression
609      * </pre>
610      *
611      * @return an AST for a statement expression.
612      */
613     private JStatement statementExpression() {
614         int line = scanner.token().line();
615         JExpression expr = expression();
616         if (expr instanceof JAssignment
617                 || expr instanceof JPreIncrementOp
618                 || expr instanceof JPreDecrementOp
619                 || expr instanceof JPostIncrementOp
620                 || expr instanceof JPostDecrementOp
621                 || expr instanceof JMessageExpression
622                 || expr instanceof JSuperConstruction
623                 || expr instanceof JThisConstruction
624                 || expr instanceof JNewOp
625                 || expr instanceof JNewArrayOp) {
626             // So as not to save on stack.
627             expr.isStatementExpression = true;
628         } else {
629             reportParserError("Invalid statement expression; it does not have a side-effect");
630         }
631         return new JStatementExpression(line, expr);
632     }
633 
634     /**
635      * Parses an expression and returns an AST for it.
636      *
637      * <pre>
638      *   expression ::= assignmentExpression
639      * </pre>
640      *
641      * @return an AST for an expression.
642      */
643     private JExpression expression() {
644         return assignmentExpression();
645     }
646 
647     /**
648      * Parses an assignment expression and returns an AST for it.
649      *
650      * <pre>
651      *   assignmentExpression ::= conditionalAndExpression
652      *                                [ ( ASSIGN | PLUS_ASSIGN ) assignmentExpression ]
653      * </pre>
654      *
655      * @return an AST for an assignment expression.
656      */
657     private JExpression assignmentExpression() {
658         int line = scanner.token().line();
659         JExpression lhs = conditionalAndExpression();
660         if (have(ASSIGN)) {
661             return new JAssignOp(line, lhs, assignmentExpression());
662         } else if (have(PLUS_ASSIGN)) {
663             return new JPlusAssignOp(line, lhs, assignmentExpression());
664         } else {
665             return lhs;
666         }
667     }
668 
669     /**
670      * Parses a conditional-and expression and returns an AST for it.
671      *
672      * <pre>
673      *   conditionalAndExpression ::= equalityExpression { LAND equalityExpression }
674      * </pre>
675      *
676      * @return an AST for a conditional-and expression.
677      */
678     private JExpression conditionalAndExpression() {
679         int line = scanner.token().line();
680         boolean more = true;
681         JExpression lhs = equalityExpression();
682         while (more) {
683             if (have(LAND)) {
684                 lhs = new JLogicalAndOp(line, lhs, equalityExpression());
685             } else {
686                 more = false;
687             }
688         }
689         return lhs;
690     }
691 
692     /**
693      * Parses an equality expression and returns an AST for it.
694      *
695      * <pre>
696      *   equalityExpression ::= relationalExpression { EQUAL relationalExpression }
697      * </pre>
698      *
699      * @return an AST for an equality expression.
700      */
701     private JExpression equalityExpression() {
702         int line = scanner.token().line();
703         boolean more = true;
704         JExpression lhs = relationalExpression();
705         while (more) {
706             if (have(EQUAL)) {
707                 lhs = new JEqualOp(line, lhs, relationalExpression());
708             } else {
709                 more = false;
710             }
711         }
712         return lhs;
713     }
714 
715     /**
716      * Parses a relational expression and returns an AST for it.
717      *
718      * <pre>
719      *   relationalExpression ::= additiveExpression [ ( GT | LE ) additiveExpression
720      *                                               | INSTANCEOF referenceType ]
721      * </pre>
722      *
723      * @return an AST for a relational expression.
724      */
725     private JExpression relationalExpression() {
726         int line = scanner.token().line();
727         JExpression lhs = additiveExpression();
728         if (have(GT)) {
729             return new JGreaterThanOp(line, lhs, additiveExpression());
730         } else if (have(LE)) {
731             return new JLessEqualOp(line, lhs, additiveExpression());
732         } else if (have(INSTANCEOF)) {
733             return new JInstanceOfOp(line, lhs, referenceType());
734         } else {
735             return lhs;
736         }
737     }
738 
739     /**
740      * Parses an additive expression and returns an AST for it.
741      *
742      * <pre>
743      *   additiveExpression ::= multiplicativeExpression { MINUS multiplicativeExpression }
744      * </pre>
745      *
746      * @return an AST for an additive expression.
747      */
748     private JExpression additiveExpression() {
749         int line = scanner.token().line();
750         boolean more = true;
751         JExpression lhs = multiplicativeExpression();
752         while (more) {
753             if (have(MINUS)) {
754                 lhs = new JSubtractOp(line, lhs, multiplicativeExpression());
755             } else if (have(PLUS)) {
756                 lhs = new JPlusOp(line, lhs, multiplicativeExpression());
757             } else {
758                 more = false;
759             }
760         }
761         return lhs;
762     }
763 
764     /**
765      * Parses a multiplicative expression and returns an AST for it.
766      *
767      * <pre>
768      *   multiplicativeExpression ::= unaryExpression { STAR unaryExpression }
769      * </pre>
770      *
771      * @return an AST for a multiplicative expression.
772      */
773     private JExpression multiplicativeExpression() {
774         int line = scanner.token().line();
775         boolean more = true;
776         JExpression lhs = unaryExpression();
777         while (more) {
778             if (have(STAR)) {
779                 lhs = new JMultiplyOp(line, lhs, unaryExpression());
780             } else {
781                 more = false;
782             }
783         }
784         return lhs;
785     }
786 
787     /**
788      * Parses an unary expression and returns an AST for it.
789      *
790      * <pre>
791      *   unaryExpression ::= INC unaryExpression
792      *                     | MINUS unaryExpression
793      *                     | simpleUnaryExpression
794      * </pre>
795      *
796      * @return an AST for an unary expression.
797      */
798     private JExpression unaryExpression() {
799         int line = scanner.token().line();
800         if (have(INC)) {
801             return new JPreIncrementOp(line, unaryExpression());
802         } else if (have(MINUS)) {
803             return new JNegateOp(line, unaryExpression());
804         } else {
805             return simpleUnaryExpression();
806         }
807     }
808 
809     /**
810      * Parses a simple unary expression and returns an AST for it.
811      *
812      * <pre>
813      *   simpleUnaryExpression ::= LNOT unaryExpression
814      *                           | LPAREN basicType RPAREN unaryExpression
815      *                           | LPAREN referenceType RPAREN simpleUnaryExpression
816      *                           | postfixExpression
817      * </pre>
818      *
819      * @return an AST for a simple unary expression.
820      */
821     private JExpression simpleUnaryExpression() {
822         int line = scanner.token().line();
823         if (have(LNOT)) {
824             return new JLogicalNotOp(line, unaryExpression());
825         } else if (seeCast()) {
826             mustBe(LPAREN);
827             boolean isBasicType = seeBasicType();
828             Type type = type();
829             mustBe(RPAREN);
830             JExpression expr = isBasicType ? unaryExpression() : simpleUnaryExpression();
831             return new JCastOp(line, type, expr);
832         } else {
833             return postfixExpression();
834         }
835     }
836 
837     /**
838      * Parses a postfix expression and returns an AST for it.
839      *
840      * <pre>
841      *   postfixExpression ::= primary { selector } { DEC }
842      * </pre>
843      *
844      * @return an AST for a postfix expression.
845      */
846     private JExpression postfixExpression() {
847         int line = scanner.token().line();
848         JExpression primaryExpr = primary();
849         while (see(DOT) || see(LBRACK)) {
850             primaryExpr = selector(primaryExpr);
851         }
852         while (have(DEC)) {
853             primaryExpr = new JPostDecrementOp(line, primaryExpr);
854         }
855         return primaryExpr;
856     }
857 
858     /**
859      * Parses a selector and returns an AST for it.
860      *
861      * <pre>
862      *   selector ::= DOT qualifiedIdentifier [ arguments ]
863      *              | LBRACK expression RBRACK
864      * </pre>
865      *
866      * @param target the target expression for this selector.
867      * @return an AST for a selector.
868      */
869     private JExpression selector(JExpression target) {
870         int line = scanner.token().line();
871         if (have(DOT)) {
872             // target.selector.
873             mustBe(IDENTIFIER);
874             String name = scanner.previousToken().image();
875             if (see(LPAREN)) {
876                 ArrayList<JExpression> args = arguments();
877                 return new JMessageExpression(line, target, name, args);
878             } else {
879                 return new JFieldSelection(line, target, name);
880             }
881         } else {
882             mustBe(LBRACK);
883             JExpression index = expression();
884             mustBe(RBRACK);
885             return new JArrayExpression(line, target, index);
886         }
887     }
888 
889     /**
890      * Parses a primary expression and returns an AST for it.
891      *
892      * <pre>
893      *   primary ::= parExpression
894      *             | NEW creator
895      *             | THIS [ arguments ]
896      *             | SUPER ( arguments | DOT IDENTIFIER [ arguments ] )
897      *             | qualifiedIdentifier [ arguments ]
898      *             | literal
899      * </pre>
900      *
901      * @return an AST for a primary expression.
902      */
903     private JExpression primary() {
904         int line = scanner.token().line();
905         if (see(LPAREN)) {
906             return parExpression();
907         } else if (have(NEW)) {
908             return creator();
909         } else if (have(THIS)) {
910             if (see(LPAREN)) {
911                 ArrayList<JExpression> args = arguments();
912                 return new JThisConstruction(line, args);
913             } else {
914                 return new JThis(line);
915             }
916         } else if (have(SUPER)) {
917             if (!have(DOT)) {
918                 ArrayList<JExpression> args = arguments();
919                 return new JSuperConstruction(line, args);
920             } else {
921                 mustBe(IDENTIFIER);
922                 String name = scanner.previousToken().image();
923                 JExpression newTarget = new JSuper(line);
924                 if (see(LPAREN)) {
925                     ArrayList<JExpression> args = arguments();
926                     return new JMessageExpression(line, newTarget, null, name, args);
927                 } else {
928                     return new JFieldSelection(line, newTarget, name);
929                 }
930             }
931         } else if (see(IDENTIFIER)) {
932             TypeName id = qualifiedIdentifier();
933             if (see(LPAREN)) {
934                 // ambiguousPart.messageName(...).
935                 ArrayList<JExpression> args = arguments();
936                 return new JMessageExpression(line, null, ambiguousPart(id), id.simpleName(), args);
937             } else if (ambiguousPart(id) == null) {
938                 // A simple name.
939                 return new JVariable(line, id.simpleName());
940             } else {
941                 // ambiguousPart.fieldName.
942                 return new JFieldSelection(line, ambiguousPart(id), null, id.simpleName());
943             }
944         } else {
945             return literal();
946         }
947     }
948 
949     /**
950      * Parses a creator and returns an AST for it.
951      *
952      * <pre>
953      *   creator ::= ( basicType | qualifiedIdentifier )
954      *                   ( arguments
955      *                   | LBRACK RBRACK { LBRACK RBRACK } [ arrayInitializer ]
956      *                   | newArrayDeclarator
957      *                   )
958      * </pre>
959      *
960      * @return an AST for a creator.
961      */
962     private JExpression creator() {
963         int line = scanner.token().line();
964         Type type = seeBasicType() ? basicType() : qualifiedIdentifier();
965         if (see(LPAREN)) {
966             ArrayList<JExpression> args = arguments();
967             return new JNewOp(line, type, args);
968         } else if (see(LBRACK)) {
969             if (seeDims()) {
970                 Type expected = type;
971                 while (have(LBRACK)) {
972                     mustBe(RBRACK);
973                     expected = new ArrayTypeName(expected);
974                 }
975                 return arrayInitializer(expected);
976             } else {
977                 return newArrayDeclarator(line, type);
978             }
979         } else {
980             reportParserError("( or [ sought where %s found", scanner.token().image());
981             return new JWildExpression(line);
982         }
983     }
984 
985     /**
986      * Parses a new array declarator and returns an AST for it.
987      *
988      * <pre>
989      *   newArrayDeclarator ::= LBRACK expression RBRACK
990      *                              { LBRACK expression RBRACK } { LBRACK RBRACK }
991      * </pre>
992      *
993      * @param line line in which the declarator occurred.
994      * @param type type of the array.
995      * @return an AST for a new array declarator.
996      */
997     private JNewArrayOp newArrayDeclarator(int line, Type type) {
998         ArrayList<JExpression> dimensions = new ArrayList<JExpression>();
999         mustBe(LBRACK);
1000        dimensions.add(expression());
1001        mustBe(RBRACK);
1002        type = new ArrayTypeName(type);
1003        while (have(LBRACK)) {
1004            if (have(RBRACK)) {
1005                // We're done with dimension expressions.
1006                type = new ArrayTypeName(type);
1007                while (have(LBRACK)) {
1008                    mustBe(RBRACK);
1009                    type = new ArrayTypeName(type);
1010                }
1011                return new JNewArrayOp(line, type, dimensions);
1012            } else {
1013                dimensions.add(expression());
1014                type = new ArrayTypeName(type);
1015                mustBe(RBRACK);
1016            }
1017        }
1018        return new JNewArrayOp(line, type, dimensions);
1019    }
1020
1021    /**
1022     * Parses a literal and returns an AST for it.
1023     *
1024     * <pre>
1025     *   literal ::= CHAR_LITERAL | FALSE | INT_LITERAL | NULL | STRING_LITERAL | TRUE
1026     * </pre>
1027     *
1028     * @return an AST for a literal.
1029     */
1030    private JExpression literal() {
1031        int line = scanner.token().line();
1032        if (have(CHAR_LITERAL)) {
1033            return new JLiteralChar(line, scanner.previousToken().image());
1034        } else if (have(FALSE)) {
1035            return new JLiteralBoolean(line, scanner.previousToken().image());
1036        } else if (have(INT_LITERAL)) {
1037            return new JLiteralInt(line, scanner.previousToken().image());
1038        } else if (have(NULL)) {
1039            return new JLiteralNull(line);
1040        } else if (have(STRING_LITERAL)) {
1041            return new JLiteralString(line, scanner.previousToken().image());
1042        } else if (have(TRUE)) {
1043            return new JLiteralBoolean(line, scanner.previousToken().image());
1044        } else {
1045            reportParserError("Literal sought where %s found", scanner.token().image());
1046            return new JWildExpression(line);
1047        }
1048    }
1049
1050    //////////////////////////////////////////////////
1051    // Parsing Support
1052    // ////////////////////////////////////////////////
1053
1054    // Returns true if the current token equals sought, and false otherwise.
1055    private boolean see(TokenKind sought) {
1056        return (sought == scanner.token().kind());
1057    }
1058
1059    // If the current token equals sought, scans it and returns true. Otherwise, returns false
1060    // without scanning the token.
1061    private boolean have(TokenKind sought) {
1062        if (see(sought)) {
1063            scanner.next();
1064            return true;
1065        } else {
1066            return false;
1067        }
1068    }
1069
1070    // Attempts to match a token we're looking for with the current input token. On success,
1071    // scans the token and goes into a "Recovered" state. On failure, what happens next depends
1072    // on whether or not the parser is currently in a "Recovered" state: if so, it reports the
1073    // error and goes into an "Unrecovered" state; if not, it repeatedly scans tokens until it
1074    // finds the one it is looking for (or EOF) and then returns to a "Recovered" state. This
1075    // gives us a kind of poor man's syntactic error recovery, a strategy due to David Turner and
1076    // Ron Morrison.
1077    private void mustBe(TokenKind sought) {
1078        if (scanner.token().kind() == sought) {
1079            scanner.next();
1080            isRecovered = true;
1081        } else if (isRecovered) {
1082            isRecovered = false;
1083            reportParserError("%s found where %s sought", scanner.token().image(), sought.image());
1084        } else {
1085            // Do not report the (possibly spurious) error, but rather attempt to recover by
1086            // forcing a match.
1087            while (!see(sought) && !see(EOF)) {
1088                scanner.next();
1089            }
1090            if (see(sought)) {
1091                scanner.next();
1092                isRecovered = true;
1093            }
1094        }
1095    }
1096
1097    // Pulls out and returns the ambiguous part of a name.
1098    private AmbiguousName ambiguousPart(TypeName name) {
1099        String qualifiedName = name.toString();
1100        int i = qualifiedName.lastIndexOf('.');
1101        return i == -1 ? null : new AmbiguousName(name.line(), qualifiedName.substring(0, i));
1102    }
1103
1104    // Reports a syntax error.
1105    private void reportParserError(String message, Object... args) {
1106        isInError = true;
1107        isRecovered = false;
1108        System.err.printf("%s:%d: error: ", scanner.fileName(), scanner.token().line());
1109        System.err.printf(message, args);
1110        System.err.println();
1111    }
1112
1113    //////////////////////////////////////////////////
1114    // Lookahead Methods
1115    //////////////////////////////////////////////////
1116
1117    // Returns true if we are looking at an IDENTIFIER followed by a LPAREN, and false otherwise.
1118    private boolean seeIdentLParen() {
1119        scanner.recordPosition();
1120        boolean result = have(IDENTIFIER) && see(LPAREN);
1121        scanner.returnToPosition();
1122        return result;
1123    }
1124
1125    // Returns true if we are looking at a cast (basic or reference), and false otherwise.
1126    private boolean seeCast() {
1127        scanner.recordPosition();
1128        if (!have(LPAREN)) {
1129            scanner.returnToPosition();
1130            return false;
1131        }
1132        if (seeBasicType()) {
1133            scanner.returnToPosition();
1134            return true;
1135        }
1136        if (!see(IDENTIFIER)) {
1137            scanner.returnToPosition();
1138            return false;
1139        } else {
1140            scanner.next();
1141            // A qualified identifier is ok.
1142            while (have(DOT)) {
1143                if (!have(IDENTIFIER)) {
1144                    scanner.returnToPosition();
1145                    return false;
1146                }
1147            }
1148        }
1149        while (have(LBRACK)) {
1150            if (!have(RBRACK)) {
1151                scanner.returnToPosition();
1152                return false;
1153            }
1154        }
1155        if (!have(RPAREN)) {
1156            scanner.returnToPosition();
1157            return false;
1158        }
1159        scanner.returnToPosition();
1160        return true;
1161    }
1162
1163    // Returns true if we are looking at a local variable declaration, and false otherwise.
1164    private boolean seeLocalVariableDeclaration() {
1165        scanner.recordPosition();
1166        if (have(IDENTIFIER)) {
1167            // A qualified identifier is ok.
1168            while (have(DOT)) {
1169                if (!have(IDENTIFIER)) {
1170                    scanner.returnToPosition();
1171                    return false;
1172                }
1173            }
1174        } else if (seeBasicType()) {
1175            scanner.next();
1176        } else {
1177            scanner.returnToPosition();
1178            return false;
1179        }
1180        while (have(LBRACK)) {
1181            if (!have(RBRACK)) {
1182                scanner.returnToPosition();
1183                return false;
1184            }
1185        }
1186        if (!have(IDENTIFIER)) {
1187            scanner.returnToPosition();
1188            return false;
1189        }
1190        while (have(LBRACK)) {
1191            if (!have(RBRACK)) {
1192                scanner.returnToPosition();
1193                return false;
1194            }
1195        }
1196        scanner.returnToPosition();
1197        return true;
1198    }
1199
1200    // Returns true if we are looking at a basic type, and false otherwise.
1201    private boolean seeBasicType() {
1202        return (see(BOOLEAN) || see(CHAR) || see(INT));
1203    }
1204
1205    // Returns true if we are looking at a reference type, and false otherwise.
1206    private boolean seeReferenceType() {
1207        if (see(IDENTIFIER)) {
1208            return true;
1209        } else {
1210            scanner.recordPosition();
1211            if (have(BOOLEAN) || have(CHAR) || have(INT)) {
1212                if (have(LBRACK) && see(RBRACK)) {
1213                    scanner.returnToPosition();
1214                    return true;
1215                }
1216            }
1217            scanner.returnToPosition();
1218        }
1219        return false;
1220    }
1221
1222    // Returns true if we are looking at a [] pair, and false otherwise.
1223    private boolean seeDims() {
1224        scanner.recordPosition();
1225        boolean result = have(LBRACK) && see(RBRACK);
1226        scanner.returnToPosition();
1227        return result;
1228    }
1229}
1230