19. LALR(1) 文法

Javaの文法を19.に示す。文法は，LALR(1) 文法であることが機械的に検査されている。

これまでに示したJavaの文法は，説明には適しているが，C及びC++から継承された一部の構文的特異性のために，1トークンの先読みではLR(left-to-right)技法で解析できない。次に，この問題及びLALR(1)文法で採用された解決を示し，その後の節で文法自体を規定する。

19.1 文法上の困難

これまでに示した文法には，五つの問題が存在する。

19.1.1 問題点１: 明瞭すぎる名前

次の二つの生成規則を考える。

_PackageName:        Identifier
        PackageName . Identifier

TypeName:

        Identifier
        PackageName . Identifier

及び

MethodName:

        Identifier
        AmbiguousName . Identifier

AmbiguousName:

        Identifier
        AmbiguousName . Identifier

次の部分的な入力を考える。

class Problem1 { int m() { hayden.

パーサが記号 "." まで 1トークン先読みしてトークンhaydenを検討するとき，パーサは，haydenが次のとおり型名を限定するPackageNameでなければならないか

hayden.Dinosaur rex = new hayden.Dinosaur(2);

又は次のとおりメソッド名を限定するAmbiguousNameでなければならないか，まだ判定できない。

hayden.print("Dinosaur Rex!");

したがって，前述の生成規則は，LALR(1)の文法ではないことになる。この文法には，各種の名前の区別に関する別の問題も存在する。

これを解決するには，非終端記号のPackageName，TypeName，ExpressionName，MethodName，及びAmbiguousNameを削除し，これらを単一の非終端記号Nameで置き換える。

Name:

        SimpleName
        QualifiedName

SimpleName:

        Identifier

QualifiedName:

        Name . Identifier

コンパイラ解析の後の段階で，各名前又は名前限定子の正確な役割を分類する。

関連した理由により，4.3の次の生成規則

ClassOrInterfaceType:

        ClassType
        InterfaceType

ClassType:

        TypeName

InterfaceType:

        TypeName

は，次のとおりに置き換える。

ClassOrInterfaceType:

        Name

ClassType:

        ClassOrInterfaceType

InterfaceType:

        ClassOrInterfaceType

19.1.2 問題点２: 明瞭すぎる修飾子

次の二つの生成規則を考える。


FieldDeclaration:

        FieldModifiers opt Type VariableDeclarators ;

FieldModifiers:

        FieldModifier
        FieldModifiers FieldModifier

FieldModifier: one of

        public protected private
        final static transient volatile

及び

MethodHeader:

        MethodModifiers_opt ResultType MethodDeclarator Throws_optMethodModifiers:

        MethodModifier
        MethodModifiers MethodModifier

MethodModifier: one of

        public protected private
        static
        abstract final native synchronized

次の部分的な入力を考える。

class Problem2 { public static int

パーサが記号intまで 1トークン先読みしてトークンstaticを検討するとき，又はさらに悪い状況として，staticまで1トークン先読みしてトークンpublicを検討するとき，これが次のとおりフィールド宣言なのか

public static int maddie = 0;

次のとおりメソッド宣言なのか判定できない。

public static int maddie(String art) { return art.length(); }

したがって，パーサは1トークンの先読みだけでは，static（又は同様にpublic）をFieldModifierとして還元すべきか，MethodModifierとして還元すべきか判定できない。したがって，前述の生成規則は，LALR(1)の文法ではないことになる。この文法には，各種の修飾子の区別に関する別の問題も存在する。

すべての文脈で問題が起きるわけではないが，最も簡単に解決するには，これらの修飾子が使用されているすべての文脈を統合し，非終端記号ClassModifiers(8.1.2)，FieldModifiers(8.3.1)，MethodModifiers(8.4.3)，ConstructorModifiers(8.6.3)，InterfaceModifiers(9.1.2)，ConstantModifiers(9.3)の六つすべてを削除し，単一の非終端記号Modifiersで置き換える。

Modifiers:

        Modifier
        Modifiers Modifier

Modifier: one of

        public protected private
        static
        abstract final native synchronized transient volatile

コンパイラ解析の後の段階で，各修飾子の正確な役割を分類し，及びそれが与えられた文脈で許されるかどうかを解析する。

19.1.3 問題点３: フィールド宣言及びメソッド宣言の競合

次の二つの生成規則（問題点2の修正を施した生成規則）を考える。

FieldDeclaration:

        Modifiers_opt Type VariableDeclarators ;

及び

MethodHeader:

        Modifiers_opt ResultType MethodDeclarator Throws_opt

ここで，ResultTypeは次のとおり定義される。

ResultType:

        Type
        void

次の部分的な入力を考える。

class Problem3 { int julie

この簡単な例は，Modifiersが存在しないことに注意すること。パーサが１トークン先読みして記号julieまで行き，トークンintを検討するとき，これが次のとおりフィールド宣言なのか

int julie = 14;

次のとおりメソッド宣言なのか判定できない。

int julie(String art) { return art.length(); }

したがって，パーサは，intを非終端記号のTypeとして還元した後で，TypeをさらにResultTypeとして還元しなければならない（メソッド宣言の場合）か，そのままにしておく（フィールド宣言の場合）のか，1トークンの先読みだけでは判定できない。したがって，前述の生成規則は，LALR(1)の文法ではないことになる。

これを解決するには，ResultTypeの生成規則を削除して，MethodHeaderに別の選択肢を用意する。

MethodHeader:

        Modifiers_opt Type MethodDeclarator Throws_opt        Modifiers_opt void MethodDeclarator Throws_opt

これで，パーサはintをTypeとして還元してそのままにしておき，フィールド宣言又はメソッド宣言の判定を遅らせることができる。

19.1.4 問題点４: 配列型及び配列アクセスの競合

次の生成規則（問題点１の訂正を施した生成規則）を考える。

ArrayType:

        Type [ ]

及び

ArrayAccess:

        Name [ Expression ]
        PrimaryNoNewArray [ Expression ]

次の部分的な入力を考える。

class Problem4 { Problem4() { peter[

パーサが記号 [ まで1トークン先読みしてトークンpeterを解析するとき，peterが次のとおり型名の一部なのか

peter[] team;

又は次のとおり配列アクセスの一部なのか

peter[3] = 12;

判定できない。したがって，パーサは，peterを非終端記号のNameとして還元した後で，Nameを最終的にTypeとして還元する（配列型の場合）のか，又はそのままにしておく（配列アクセスの場合）のか，1トークンの先読みでは判定できない。したがって，前述の生成規則は，LALR(1)の文法ではないことになる。

これを解決するには，ArrayTypeに別の選択肢を用意する。

ArrayType:

        PrimitiveType [ ]
        Name [ ]
        ArrayType [ ]

これで，パーサは，peterをNameとして還元してそのままにしておき，配列型又は配列アクセスの判定を遅らせることができる。

19.1.5 問題点５: キャスト及び括弧付き式の競合

次の生成規則を考える。

CastExpression:

        ( PrimitiveType ) UnaryExpression
        ( ReferenceType ) UnaryExpressionNotPlusMinus

次の部分的な入力を考える。

class Problem5 { Problem5() { super((matthew)

パーサが記号 ) まで1トークン先読みしてトークンmatthewを解析するとき，(matthew) が次のとおり括弧付き式なのか:

super((matthew), 9);

又は次のとおりキャストなのか，

super((matthew)baz, 9);

判定できない。したがって，パーサは，matthewを非終端記号のNameとして還元した後で，NameをさらにPostfixExpressionとして還元し，最終的にExpressionとして還元する（括弧付きの式の場合）のか，ClassOrInterfaceTypeとして還元し，次にReferenceTypeとして還元する（キャストの場合）のか，1トークンの先読みでは判定できない。したがって，前述の生成規則は，LALR(1)の文法ではないことになる。

これを解決するには，CastExpressionの定義内の非終端記号ReferenceTypeを削除する。これは，別のあいまいさを回避するために，両選択肢の多少の変更が必要となる。

CastExpression:

        ( PrimitiveType Dims_opt ) UnaryExpression
        ( Expression ) UnaryExpressionNotPlusMinus
        ( Name Dims ) UnaryExpressionNotPlusMinus

これで，パーサはmatthewをExpressionとして還元してそのままにしておき，括弧付き式又はキャストの判定を遅らせることができる。さらに，

(int[])+3

及び

(matthew+1)baz

のような不適切な書式は，コンパイラ解析の後の段階で削除及び拒否しなければならない。

以降の節では，Java構文の LALR(1) 文法を構成する。この文法では，前述の五つの問題は解決されている。

19.2　構文文法(2.3)からの生成規則

Goal:

        CompilationUnit

19.3　字句構造(3)からの生成規則

Literal:

        IntegerLiteral
        FloatingPointLiteral
        BooleanLiteral
        CharacterLiteral
        StringLiteral
        NullLiteral

19.4　型，値，及び変数(4)からの生成規則

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 [ ]

19.5　名前(6)からの生成規則

Name:

        SimpleName
        QualifiedName

SimpleName:

        Identifier

QualifiedName:

        Name . Identifier

19.6　パッケージ(7)からの生成規則

CompilationUnit:

        PackageDeclaration_opt ImportDeclarations_opt TypeDeclarations_optImportDeclarations:

        ImportDeclaration
        ImportDeclarations ImportDeclaration

TypeDeclarations:

        TypeDeclaration
        TypeDeclarations TypeDeclaration

PackageDeclaration:

        package Name ;

ImportDeclaration:

        SingleTypeImportDeclaration
        TypeImportOnDemandDeclaration

SingleTypeImportDeclaration:

        import Name ;

TypeImportOnDemandDeclaration:

        import Name . * ;

TypeDeclaration:

        ClassDeclaration
        InterfaceDeclaration
        ;

19.7　LALR(1)文法でだけ使用される生成規則

Modifiers:

        Modifier
        Modifiers Modifier

Modifier: one of

        public protected private
        static
        abstract final native synchronized transient volatile

19.8　クラス(8)からの生成規則

19.8.1　クラス宣言(8.1)からの生成規則

ClassDeclaration:

        Modifiers_opt class Identifier Super_opt Interfaces_opt ClassBody

Super:

        extends ClassType

Interfaces:

        implements InterfaceTypeList

InterfaceTypeList:

        InterfaceType
        InterfaceTypeList , InterfaceType

ClassBody:

        { ClassBodyDeclarations_opt }

ClassBodyDeclarations:

        ClassBodyDeclaration
        ClassBodyDeclarations ClassBodyDeclaration

ClassBodyDeclaration:

        ClassMemberDeclaration
        StaticInitializer
        ConstructorDeclaration

ClassMemberDeclaration:

        FieldDeclaration
        MethodDeclaration

19.8.2　フィールド宣言(8.3)からの生成規則

FieldDeclaration:

        Modifiers_opt Type VariableDeclarators ;

VariableDeclarators:

        VariableDeclarator
        VariableDeclarators , VariableDeclarator

VariableDeclarator:

        VariableDeclaratorId
        VariableDeclaratorId = VariableInitializer

VariableDeclaratorId:

        Identifier
        VariableDeclaratorId [ ]

VariableInitializer:

        Expression
        ArrayInitializer

19.8.3　メソッド宣言(8.4)からの生成規則

MethodDeclaration:

        MethodHeader MethodBody

MethodHeader:

        Modifiers_opt Type MethodDeclarator Throws_opt        Modifiers_opt void MethodDeclarator Throws_optMethodDeclarator:

        Identifier ( FormalParameterList_opt )
        MethodDeclarator [ ]

FormalParameterList:

        FormalParameter
        FormalParameterList , FormalParameter

FormalParameter:

        Type VariableDeclaratorId

Throws:

        throws ClassTypeList

ClassTypeList:

        ClassType
        ClassTypeList , ClassType

MethodBody:

        Block 
        ;

19.8.4　静的初期化子(8.5)からの生成規則

StaticInitializer:

        static Block

19.8.5　コンストラクタ宣言(8.6)からの生成規則

ConstructorDeclaration:

        Modifiers_opt ConstructorDeclarator Throwsopt ConstructorBody

ConstructorDeclarator:

        SimpleName ( FormalParameterList_opt )

ConstructorBody:

        { ExplicitConstructorInvocation_opt BlockStatements_opt }

ExplicitConstructorInvocation:

        this ( ArgumentList_opt ) ;
        super ( ArgumentList_opt ) ;

19.9　インタフェース(9)からの生成規則

19.9.1　インタフェース宣言(9.1)からの生成規則

InterfaceDeclaration:

        Modifiers_opt interface Identifier ExtendsInterfaces_opt InterfaceBody

ExtendsInterfaces:

        extends InterfaceType
        ExtendsInterfaces , InterfaceType

InterfaceBody:

        { InterfaceMemberDeclarations_opt }

InterfaceMemberDeclarations:

        InterfaceMemberDeclaration
        InterfaceMemberDeclarations InterfaceMemberDeclaration

InterfaceMemberDeclaration:

        ConstantDeclaration
        AbstractMethodDeclaration

ConstantDeclaration:

        FieldDeclaration

AbstractMethodDeclaration:

        MethodHeader ;

19.10　配列(10)からの生成規則

ArrayInitializer:

        { VariableInitializers_opt ,_opt }

VariableInitializers:

        VariableInitializer
        VariableInitializers , VariableInitializer

19.11　ブロック及び文(14)からの生成規則

Block:

        { BlockStatements_opt }

BlockStatements:

        BlockStatement
        BlockStatements BlockStatement

BlockStatement:

        LocalVariableDeclarationStatement
        Statement

LocalVariableDeclarationStatement:

        LocalVariableDeclaration ;

LocalVariableDeclaration:

        Type VariableDeclarators

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 ) StatementNoShortIf else Statement

IfThenElseStatementNoShortIf:

        if ( Expression ) StatementNoShortIf else StatementNoShortIf

SwitchStatement:

        switch ( Expression ) SwitchBlock

SwitchBlock:

        { SwitchBlockStatementGroups_opt SwitchLabels_opt }

SwitchBlockStatementGroups:

        SwitchBlockStatementGroup
        SwitchBlockStatementGroups SwitchBlockStatementGroup

SwitchBlockStatementGroup:

        SwitchLabels BlockStatements

SwitchLabels:

        SwitchLabel
        SwitchLabels SwitchLabel

SwitchLabel:

        case ConstantExpression :
        default :

WhileStatement:

        while ( Expression ) Statement

WhileStatementNoShortIf:

        while ( Expression ) StatementNoShortIf

DoStatement:

        do Statement while ( Expression ) ;

ForStatement:

        for ( ForInit_opt ; Expression_opt ; ForUpdate_opt )
                Statement

ForStatementNoShortIf:

        for ( ForInit_opt ; Expression_opt ; ForUpdate_opt )
                StatementNoShortIf

ForInit:

        StatementExpressionList
        LocalVariableDeclaration

ForUpdate:

        StatementExpressionList

StatementExpressionList:

        StatementExpression
        StatementExpressionList , StatementExpression

BreakStatement:

        break Identifier_opt ;

ContinueStatement:

        continue Identifier_opt ;

ReturnStatement:

        return Expression_opt ;

ThrowStatement:

        throw Expression ;

SynchronizedStatement:

        synchronized ( Expression ) Block

TryStatement:

        try Block Catches
        try Block Catches_opt Finally

Catches:

        CatchClause
        Catches CatchClause

CatchClause:

        catch ( FormalParameter ) Block

Finally:

        finally Block

19.12　式(15)からの生成規則

Primary:

        PrimaryNoNewArray
        ArrayCreationExpression

PrimaryNoNewArray:

        Literal
        this
        ( Expression )
        ClassInstanceCreationExpression
        FieldAccess
        MethodInvocation
        ArrayAccess

ClassInstanceCreationExpression:

        new ClassType ( ArgumentList_opt )

ArgumentList:

        Expression
        ArgumentList , Expression

ArrayCreationExpression:

new PrimitiveType DimExprs Dims_opt        new ClassOrInterfaceType DimExprs Dims_optDimExprs:

        DimExpr
        DimExprs DimExpr

DimExpr:

        [ Expression ]

Dims:

        [ ]
        Dims [ ]

FieldAccess:

        Primary . Identifier
        super . Identifier

MethodInvocation:

        Name ( ArgumentList_opt )
        Primary . Identifier ( ArgumentList_opt )
        super . Identifier ( ArgumentList_opt )

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:

        ( PrimitiveType Dims_opt ) UnaryExpression
        ( Expression ) UnaryExpressionNotPlusMinus
        ( Name Dims ) 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
        RelationalExpression instanceof 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:

        LeftHandSide AssignmentOperator AssignmentExpression

LeftHandSide:

        Name
        FieldAccess
        ArrayAccess

AssignmentOperator: one of

        = *= /= %= += -= <<= >>= >>>= &= ^= |=

Expression:

        AssignmentExpression

ConstantExpression:

        Expression

目次 | 前 | 次

19. LALR(1) 文法

19.1 文法上の困難

19.1.1 問題点１: 明瞭すぎる名前

19.1.2 問題点２: 明瞭すぎる修飾子

19.1.3 問題点３: フィールド宣言及びメソッド宣言の競合

19.1.4 問題点４: 配列型及び配列アクセスの競合

19.1.5 問題点５: キャスト及び括弧付き式の競合

19.2 構文文法(2.3)からの生成規則

19.3 字句構造(3)からの生成規則

19.4 型，値，及び変数(4)からの生成規則

19.5 名前(6)からの生成規則

19.6 パッケージ(7)からの生成規則

19.7 LALR(1)文法でだけ使用される生成規則

19.8 クラス(8)からの生成規則

19.8.1 クラス宣言(8.1)からの生成規則

19.8.2 フィールド宣言(8.3)からの生成規則

19.8.3 メソッド宣言(8.4)からの生成規則

19.8.4 静的初期化子(8.5)からの生成規則

19.8.5 コンストラクタ宣言(8.6)からの生成規則

19.9 インタフェース(9)からの生成規則

19.9.1 インタフェース宣言(9.1)からの生成規則

19.10 配列(10)からの生成規則

19.11 ブロック及び文(14)からの生成規則

19.12 式(15)からの生成規則

19.2　構文文法(2.3)からの生成規則

19.3　字句構造(3)からの生成規則

19.4　型，値，及び変数(4)からの生成規則

19.5　名前(6)からの生成規則

19.6　パッケージ(7)からの生成規則

19.7　LALR(1)文法でだけ使用される生成規則

19.8　クラス(8)からの生成規則

19.8.1　クラス宣言(8.1)からの生成規則

19.8.2　フィールド宣言(8.3)からの生成規則

19.8.3　メソッド宣言(8.4)からの生成規則

19.8.4　静的初期化子(8.5)からの生成規則

19.8.5　コンストラクタ宣言(8.6)からの生成規則

19.9　インタフェース(9)からの生成規則

19.9.1　インタフェース宣言(9.1)からの生成規則

19.10　配列(10)からの生成規則

19.11　ブロック及び文(14)からの生成規則

19.12　式(15)からの生成規則