Contents | Prev | Next | Index

CHAPTER 19

LALR(1) Grammar

This chapter presents a grammar for Java. The grammar has been mechanically checked to insure that it is LALR(1).

The grammar for Java presented piecemeal in the preceding chapters is much better for exposition, but it cannot be parsed left-to-right with one token of lookahead because of certain syntactic peculiarities, some of them inherited from C and C++. These problems and the solutions adopted for the LALR(1) grammar are presented below, followed by the grammar itself.

19.1 Grammatical Difficulties

There are five problems with the grammar presented in preceding chapters.

19.1.1 Problem #1: Names Too Specific

Consider the two groups of productions:

and:

Now consider the partial input: 

class Problem1 { int m() { hayden.
When the parser is considering the token hayden, with one-token lookahead to symbol ".", it cannot yet tell whether hayden should be a PackageName that qualifies a type name, as in: 

hayden.Dinosaur rex = new hayden.Dinosaur(2);
or an AmbiguousName that qualifies a method name, as in: 

hayden.print("Dinosaur Rex!");
Therefore, the productions shown above result in a grammar that is not LALR(1). There are also other problems with drawing distinctions among different kinds of names in the grammar.

The solution is to eliminate the nonterminals PackageName, TypeName, ExpressionName, MethodName, and AmbiguousName, replacing them all with a single nonterminal Name:

A later stage of compiler analysis then sorts out the precise role of each name or name qualifier.

For related reasons, these productions in §4.3:

were changed to:

19.1.2 Problem #2: Modifiers Too Specific

Consider the two groups of productions:

and:

Now consider the partial input: 

class Problem2 { public static int
When the parser is considering the token static, with one-token lookahead to symbol int-or, worse yet, considering the token public with lookahead to static-it cannot yet tell whether this will be a field declaration such as: 

public static int maddie = 0;
or a method declaration such as: 

public static int maddie(String art) { return art.length(); }
Therefore, the parser cannot tell with only one-token lookahead whether static (or, similarly, public) should be reduced to FieldModifier or MethodModifier. Therefore, the productions shown above result in a grammar that is not LALR(1). There are also other problems with drawing distinctions among different kinds of modifiers in the grammar.

While not all contexts provoke the problem, the simplest solution is to combine all contexts in which such modifiers are used, eliminating all six of the nonterminals ClassModifiers (§8.1.2), FieldModifiers (§8.3.1), MethodModifiers (§8.4.3), ConstructorModifiers (§8.6.3), InterfaceModifiers (§9.1.2), and ConstantModifiers (§9.3) from the grammar, replacing them all with a single nonterminal Modifiers:

A later stage of compiler analysis then sorts out the precise role of each modifier and whether it is permitted in a given context.

19.1.3 Problem #3: Field Declaration versus Method Declaration

Consider the two productions (shown after problem #2 has been corrected):

and:

where ResultType is defined as:

Now consider the partial input: 

class Problem3 { int julie
Note that, in this simple example, no Modifiers are present. When the parser is considering the token int, with one-token lookahead to symbol julie, it cannot yet tell whether this will be a field declaration such as: 

int julie = 14;
or a method declaration such as: 

int julie(String art) { return art.length(); }
Therefore, after the parser reduces int to the nonterminal Type, it cannot tell with only one-token lookahead whether Type should be further reduced to ResultType (for a method declaration) or left alone (for a field declaration). Therefore, the productions shown above result in a grammar that is not LALR(1).

The solution is to eliminate the ResultType production and to have separate alternatives for MethodHeader:

This allows the parser to reduce int to Type and then leave it as is, delaying the decision as to whether a field declaration or method declaration is in progress.

19.1.4 Problem #4: Array Type versus Array Access

Consider the productions (shown after problem #1 has been corrected):

and:

Now consider the partial input: 

class Problem4 { Problem4() { peter[
When the parser is considering the token peter, with one-token lookahead to symbol [, it cannot yet tell whether peter will be part of a type name, as in: 

peter[] team;
or part of an array access, as in: 

peter[3] = 12;
Therefore, after the parser reduces peter to the nonterminal Name, it cannot tell with only one-token lookahead whether Name should be reduced ultimately to Type (for an array type) or left alone (for an array access). Therefore, the productions shown above result in a grammar that is not LALR(1).

The solution is to have separate alternatives for ArrayType:

This allows the parser to reduce peter to Name and then leave it as is, delaying the decision as to whether an array type or array access is in progress.

19.1.5 Problem #5: Cast versus Parenthesized Expression

Consider the production:

Now consider the partial input: 

class Problem5 { Problem5() { super((matthew)
When the parser is considering the token matthew, with one-token lookahead to symbol ), it cannot yet tell whether (matthew) will be a parenthesized expression, as in: 

super((matthew), 9);
or a cast, as in: 

super((matthew)baz, 9);
Therefore, after the parser reduces matthew to the nonterminal Name, it cannot tell with only one-token lookahead whether Name should be further reduced to PostfixExpression and ultimately to Expression (for a parenthesized expression) or to ClassOrInterfaceType and then to ReferenceType (for a cast). Therefore, the productions shown above result in a grammar that is not LALR(1).

The solution is to eliminate the use of the nonterminal ReferenceType in the definition of CastExpression, which requires some reworking of both alternatives to avoid other ambiguities:

This allows the parser to reduce matthew to Expression and then leave it there, delaying the decision as to whether a parenthesized expression or a cast is in progress. Inappropriate variants such as: 

(int[])+3
and: 

(matthew+1)baz
must then be weeded out and rejected by a later stage of compiler analysis.

The remaining sections of this chapter constitute a LALR(1) grammar for Java syntax, in which the five problems described above have been solved.

19.2 Productions from §2.3: The Syntactic Grammar

19.3 Productions from §3: Lexical Structure

19.4 Productions from §4: Types, Values, and Variables

19.5 Productions from §6: Names

19.6 Productions from §7: Packages

19.7 Productions Used Only in the LALR(1) Grammar

19.8 Productions from §8: Classes

19.8.1 Productions from §8.1: Class Declaration

19.8.2 Productions from §8.3: Field Declarations

19.8.3 Productions from §8.4: Method Declarations

19.8.4 Productions from §8.5: Static Initializers

19.8.5 Productions from §8.6: Constructor Declarations

19.9 Productions from §9: Interfaces

19.9.1 Productions from §9.1: Interface Declarations

19.10 Productions from §10: Arrays

19.11 Productions from §14: Blocks and Statements

19.12 Productions from §15: Expressions

Contents | Prev | Next | Index

Java Language Specification (HTML generated by dkramer on August 01, 1996)
Copyright © 1996 Sun Microsystems, Inc. All rights reserved
Please send any comments or corrections to doug.kramer@sun.com