CHAPTER 19
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.
PackageName:and:
Identifier
PackageName.
Identifier TypeName:
Identifier
PackageName.
Identifier
MethodName:Now consider the partial input:
Identifier
AmbiguousName.
Identifier AmbiguousName:
Identifier
AmbiguousName.
Identifier
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:
Name:A later stage of compiler analysis then sorts out the precise role of each name or name qualifier.
SimpleName
QualifiedName SimpleName:
Identifier QualifiedName:
Name.
Identifier
For related reasons, these productions in §4.3:
ClassOrInterfaceType:were changed to:
ClassType
InterfaceType ClassType:
TypeName InterfaceType:
TypeName
ClassOrInterfaceType:
Name ClassType:
ClassOrInterfaceType InterfaceType:
ClassOrInterfaceType
FieldDeclaration:and:
FieldModifiersoptType
VariableDeclarators
;
FieldModifiers:
FieldModifier
FieldModifiersFieldModifier FieldModifier: one of
public
protected
private
final static transient volatile
MethodHeader:Now consider the partial input:
MethodModifiersoptResultType
MethodDeclarator
Throwsopt MethodModifiers:
MethodModifier
MethodModifiersMethodModifier MethodModifier: one of
public
protected
private
static
abstract final native synchronized
class Problem2 { public static intWhen 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:
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.
Modifier
ModifiersModifier Modifier: one of
public protected private
static
abstract final native synchronized transient volatile
FieldDeclaration:and:
ModifiersoptType
VariableDeclarators
;
MethodHeader:where ResultType is defined as:
ModifiersoptResultType
MethodDeclarator
Throwsopt
ResultType:Now consider the partial input:
Type
void
class Problem3 { int julieNote 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:
MethodHeader:This allows the parser to reduce
ModifiersoptType
MethodDeclarator
Throwsopt
Modifiersoptvoid
MethodDeclaratorThrowsopt
int
to Type and then leave it as is, delaying the decision as to whether a field declaration or method declaration is in progress.ArrayType:and:
Type
[ ]
ArrayAccess:Now consider the partial input:
Name[
Expression]
PrimaryNoNewArray
[
Expression]
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:
ArrayType:This allows the parser to reduce
PrimitiveType
[ ]
Name
[ ]
ArrayType
[ ]
peter
to Name and then leave it as is, delaying
the decision as to whether an array type or array access is in progress.
CastExpression:Now consider the partial input:
(
PrimitiveType)
UnaryExpression
(
ReferenceType)
UnaryExpressionNotPlusMinus
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:
CastExpression:This allows the parser to reduce
(
PrimitiveTypeDimsopt
)
UnaryExpression
(
Expression)
UnaryExpressionNotPlusMinus
(
NameDims
)
UnaryExpressionNotPlusMinus
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[])+3and:
(matthew+1)bazmust 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.
Goal:
CompilationUnit
Literal:
IntegerLiteral
FloatingPointLiteral
BooleanLiteral
CharacterLiteral
StringLiteral
NullLiteral
Type:
PrimitiveType
ReferenceType PrimitiveType:
NumericType
boolean
NumericType:
IntegralType
FloatingPointType IntegralType: one of
byte short int long char
FloatingPointType: one of
float double
ReferenceType:
ClassOrInterfaceType
ArrayType ClassOrInterfaceType:
Name ClassType:
ClassOrInterfaceType InterfaceType:
ClassOrInterfaceType ArrayType:
PrimitiveType
[ ]
Name
[ ]
ArrayType
[ ]
Name:
SimpleName
QualifiedName SimpleName:
Identifier QualifiedName:
Name.
Identifier
CompilationUnit:
PackageDeclarationoptImportDeclarationsopt
TypeDeclarationsopt ImportDeclarations:
ImportDeclaration
ImportDeclarationsImportDeclaration TypeDeclarations:
TypeDeclaration
TypeDeclarationsTypeDeclaration PackageDeclaration:
package
Name;
ImportDeclaration:
SingleTypeImportDeclaration
TypeImportOnDemandDeclaration SingleTypeImportDeclaration:
import
Name;
TypeImportOnDemandDeclaration:
import
Name. * ;
TypeDeclaration:
ClassDeclaration
InterfaceDeclaration
;
Modifiers:
Modifier
ModifiersModifier Modifier: one of
public protected private
static
abstract final native synchronized transient volatile
ClassDeclaration:
Modifiersoptclass
IdentifierSuperopt
Interfacesopt
ClassBody Super:
extends
ClassType Interfaces:
implements
InterfaceTypeList InterfaceTypeList:
InterfaceType
InterfaceTypeList,
InterfaceType ClassBody:
{
ClassBodyDeclarationsopt}
ClassBodyDeclarations:
ClassBodyDeclaration
ClassBodyDeclarationsClassBodyDeclaration ClassBodyDeclaration:
ClassMemberDeclaration
StaticInitializer
ConstructorDeclaration ClassMemberDeclaration:
FieldDeclaration
MethodDeclaration
FieldDeclaration:
ModifiersoptType
VariableDeclarators
;
VariableDeclarators:
VariableDeclarator
VariableDeclarators,
VariableDeclarator VariableDeclarator:
VariableDeclaratorId
VariableDeclaratorId=
VariableInitializer VariableDeclaratorId:
Identifier
VariableDeclaratorId[ ]
VariableInitializer:
Expression
ArrayInitializer
MethodDeclaration:
MethodHeaderMethodBody MethodHeader:
ModifiersoptType
MethodDeclarator
Throwsopt
Modifiersoptvoid
MethodDeclaratorThrowsopt MethodDeclarator:
Identifier(
FormalParameterListopt)
MethodDeclarator
[ ]
FormalParameterList:
FormalParameter
FormalParameterList,
FormalParameter FormalParameter:
TypeVariableDeclaratorId Throws:
throws
ClassTypeList ClassTypeList:
ClassType
ClassTypeList,
ClassType MethodBody:
Block
;
StaticInitializer:
static
Block
ConstructorDeclaration:
ModifiersoptConstructorDeclarator
Throwsopt
ConstructorBody ConstructorDeclarator:
SimpleName
(
FormalParameterListopt)
ConstructorBody:
{
ExplicitConstructorInvocationoptBlockStatementsopt
}
ExplicitConstructorInvocation:
this (
ArgumentListopt) ;
super (
ArgumentListopt) ;
InterfaceDeclaration:
Modifiersoptinterface
IdentifierExtendsInterfacesopt
InterfaceBody ExtendsInterfaces:
extends
InterfaceType
ExtendsInterfaces,
InterfaceType InterfaceBody:
{
InterfaceMemberDeclarationsopt}
InterfaceMemberDeclarations:
InterfaceMemberDeclaration
InterfaceMemberDeclarationsInterfaceMemberDeclaration InterfaceMemberDeclaration:
ConstantDeclaration
AbstractMethodDeclaration ConstantDeclaration:
FieldDeclaration AbstractMethodDeclaration:
MethodHeader;
ArrayInitializer:
{
VariableInitializersopt,
opt}
VariableInitializers:
VariableInitializer
VariableInitializers,
VariableInitializer
Block:
{
BlockStatementsopt}
BlockStatements:
BlockStatement
BlockStatements
BlockStatement BlockStatement:
LocalVariableDeclarationStatement
Statement LocalVariableDeclarationStatement:
LocalVariableDeclaration;
LocalVariableDeclaration:
TypeVariableDeclarators Statement:
StatementWithoutTrailingSubstatement
LabeledStatement
IfThenStatement
IfThenElseStatement
WhileStatement
ForStatement StatementNoShortIf:
StatementWithoutTrailingSubstatement
LabeledStatementNoShortIf
IfThenElseStatementNoShortIf
WhileStatementNoShortIf
ForStatementNoShortIf StatementWithoutTrailingSubstatement:
Block
EmptyStatement
ExpressionStatement
SwitchStatement
DoStatement
BreakStatement
ContinueStatement
ReturnStatement
SynchronizedStatement
ThrowStatement
TryStatement EmptyStatement:
;
LabeledStatement:
Identifier:
Statement LabeledStatementNoShortIf:
Identifier:
StatementNoShortIf ExpressionStatement:
StatementExpression;
StatementExpression:
Assignment
PreIncrementExpression
PreDecrementExpression
PostIncrementExpression
PostDecrementExpression
MethodInvocation
ClassInstanceCreationExpression
IfThenStatement:
if (
Expression)
Statement IfThenElseStatement:
if (
Expression)
StatementNoShortIfelse
Statement IfThenElseStatementNoShortIf:
if (
Expression)
StatementNoShortIfelse
StatementNoShortIf SwitchStatement:
switch (
Expression)
SwitchBlock SwitchBlock:
{
SwitchBlockStatementGroupsoptSwitchLabelsopt
}
SwitchBlockStatementGroups:
SwitchBlockStatementGroup
SwitchBlockStatementGroups
SwitchBlockStatementGroup SwitchBlockStatementGroup:
SwitchLabelsBlockStatements SwitchLabels:
SwitchLabel
SwitchLabelsSwitchLabel SwitchLabel:
case
ConstantExpression:
WhileStatement:
default :
while (
Expression)
Statement WhileStatementNoShortIf:
while (
Expression)
StatementNoShortIf DoStatement:
do
Statementwhile (
Expression) ;
ForStatement:
for (
ForInitopt;
Expressionopt;
ForUpdateopt)
Statement ForStatementNoShortIf:
for (
ForInitopt;
Expressionopt;
ForUpdateopt)
StatementNoShortIf ForInit:
StatementExpressionList
LocalVariableDeclaration ForUpdate:
StatementExpressionList StatementExpressionList:
StatementExpression
StatementExpressionList,
StatementExpression BreakStatement:
break
Identifieropt;
ContinueStatement:
continu
e Identifieropt;
ReturnStatement:
return
Expressionopt;
ThrowStatement:
throw
Expression;
SynchronizedStatement:
synchronized (
Expression)
Block TryStatement:
try
BlockCatches
try
BlockCatchesopt
Finally Catches:
CatchClause
CatchesCatchClause CatchClause:
catch (
FormalParameter)
Block Finally:
finally
Block
Primary:
PrimaryNoNewArray
ArrayCreationExpression PrimaryNoNewArray:
Literal
this
(
Expression)
ClassInstanceCreationExpression
FieldAccess
MethodInvocation
ArrayAccess ClassInstanceCreationExpression:
new
ClassType(
ArgumentListopt)
ArgumentList:
Expression
ArgumentList,
Expression ArrayCreationExpression:
new
PrimitiveTypeDimExprs
Dimsopt
new
ClassOrInterfaceTypeDimExprs
Dimsopt DimExprs:
DimExpr
DimExprsDimExpr DimExpr:
[
Expression]
Dims:
[ ]
Dims
[ ]
FieldAccess:
Primary.
Identifier
super .
Identifier MethodInvocation:
Name(
ArgumentListopt)
Primary
.
Identifier(
ArgumentListopt)
Identifier
super .(
ArgumentListopt)
ArrayAccess:
Name[
Expression]
PrimaryNoNewArray
[
Expression]
PostfixExpression:
Primary
Name
PostIncrementExpression
PostDecrementExpression PostIncrementExpression:
PostfixExpression++
PostDecrementExpression:
PostfixExpression--
UnaryExpression:
PreIncrementExpression
PreDecrementExpression
+
UnaryExpression
-
UnaryExpression
UnaryExpressionNotPlusMinus PreIncrementExpression:
++
UnaryExpression PreDecrementExpression:
--
UnaryExpression UnaryExpressionNotPlusMinus:
PostfixExpression
~
UnaryExpression
!
UnaryExpression
CastExpression CastExpression:
(
PrimitiveTypeDimsopt
)
UnaryExpression
(
Expression)
UnaryExpressionNotPlusMinus
(
NameDims
)
UnaryExpressionNotPlusMinus MultiplicativeExpression:
UnaryExpression
MultiplicativeExpression*
UnaryExpression
MultiplicativeExpression/
UnaryExpression
MultiplicativeExpression%
UnaryExpression AdditiveExpression:
MultiplicativeExpression
AdditiveExpression+
MultiplicativeExpression
AdditiveExpression
-
MultiplicativeExpression ShiftExpression:
AdditiveExpression
ShiftExpression<<
AdditiveExpression
ShiftExpression>>
AdditiveExpression
ShiftExpression>>>
AdditiveExpression RelationalExpression:
ShiftExpression
RelationalExpression<
ShiftExpression
RelationalExpression>
ShiftExpression
RelationalExpression<=
ShiftExpression
RelationalExpression>=
ShiftExpression
RelationalExpressioninstanceof
ReferenceType EqualityExpression:
RelationalExpression
EqualityExpression==
RelationalExpression
EqualityExpression!=
RelationalExpression AndExpression:
EqualityExpression
AndExpression&
EqualityExpression ExclusiveOrExpression:
AndExpression
ExclusiveOrExpression^
AndExpression InclusiveOrExpression:
ExclusiveOrExpression
InclusiveOrExpression|
ExclusiveOrExpression ConditionalAndExpression:
InclusiveOrExpression
ConditionalAndExpression&&
InclusiveOrExpression ConditionalOrExpression:
ConditionalAndExpression
ConditionalOrExpression||
ConditionalAndExpression ConditionalExpression:
ConditionalOrExpression
ConditionalOrExpression?
Expression:
ConditionalExpression AssignmentExpression:
ConditionalExpression
Assignment Assignment:
LeftHandSideAssignmentOperator
AssignmentExpression LeftHandSide:
Name
FieldAccess
ArrayAccess AssignmentOperator: one of
= *= /= %= += -= <<= >>= >>>= &= ^= |=
Expression:
AssignmentExpression ConstantExpression:
Expression
Contents | Prev | Next | Index
Java Language Specification (HTML generated by Suzette Pelouch on February 24, 1998)
Copyright © 1996 Sun Microsystems, Inc.
All rights reserved
Please send any comments or corrections to doug.kramer@sun.com