目次 | |



19. LALR(1) 文法

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

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

19.1 文法上の困難

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

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

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

及び

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

class Problem1 { int m() { hayden.

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

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

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

hayden.print("Dinosaur Rex!");

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

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

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

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

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

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

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

及び

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

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で置き換える。

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

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

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

及び

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

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

class Problem3 { int julie

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

int julie = 14;

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

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

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

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

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

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

次の生成規則(問題点1の訂正を施した生成規則)を考える。

及び

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

class Problem4 { Problem4() { peter[

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

peter[] team;

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

peter[3] = 12;

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

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

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

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

次の生成規則を考える。

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

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を削除する。これは,別のあいまいさを回避するために,両選択肢の多少の変更が必要となる。

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

(int[])+3

及び

(matthew+1)baz

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

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

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)からの生成規則


目次 | |