| Parser.java |
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