test

プログラミングユーティリティ

あいまいさと衝突

入力文字列が 2 種類以上の方法で構成できる場合には、構文規則のセットはあいまいになります。たとえば、2 つの式の間にマイナス記号を置いたものが算術式の 1 つであることを表す場合は、普通は以下の構文規則を使用します。 

expr : expr '-' expr

この構文規則では、複雑な入力のすべてを構成する方法は完全には指定されていないので注意してください。たとえば、以下のような入力の場合には、

expr - expr - expr

この規則では以下のいずれかでその入力を構成できます。

( expr - expr ) - expr
expr - ( expr - expr )

最初のものは左結合、2 番目のものは右結合と呼ばれています。

yacc は、パーサーを構築する際にこのようなあいまいさを検出します。以下のような入力を与えられたときにパーサーが直面する問題について考えます。

expr - expr - expr

パーサーが 2 番目の expr を読み取ったときには、この入力は以下のように認識されます。

expr - expr

これは、前述の構文規則の右側と一致します。パーサーは、この規則を適用することによって入力を還元 (reduce) できます。この規則を適用すると、入力は還元されて expr (規則の左側) になります。その後、パーサーは入力の最後の部分 (その部分を以下に示します) を読み取って、再度 reduce を実行します。

- expr

この結果、入力は左結合であるとみなされます。

あるいは、以下の入力を認識した場合に、

expr - expr

パーサーは、すぐにその規則を適用しないで、以下の入力を認識するまで読み取りを継続することもできます。

expr - expr - expr

この入力を認識した後で、パーサーは右端の 3 つのシンボルに対して規則を適用し、それを expr に還元できます。その結果、以下の入力が残ります。

expr - expr

これで、この規則をもう一度還元することが可能になります。この結果、入力は右結合であるとみなされます。したがって、以下の入力を読み取ったパーサーは、shift または reduce のいずれかの正当なアクションを実行できます。

expr - expr

shift と reduce を選択する方法はありません。これは、shift-reduce 衝突と呼ばれています。また、正当な 2 つの還元の選択肢をパーサーが持っている可能性もあります。これは、reduce-reduce 衝突と呼ばれています。shift-shift 衝突というものは存在しません。

shift-reduce 衝突や reduce-reduce 衝突が生じた場合でも、yacc はパーサーを生成します。yacc は、選択肢がある場所で有効なステップの 1 つを選択することによって、パーサーの生成を行います。所定の状況において行う選択を表した規則は、あいまいさ解決規則と呼ばれます。

yacc は、デフォルトの 2 つのあいまいさ解決規則を呼び出します。

  1. shift-reduce 衝突の場合は、デフォルトは shift になります。

  2. reduce-reduce 衝突の場合は、デフォルトは、読み込まれた yacc 仕様中で先に定義された文法規則による reduce になります。

    規則 1 は、選択肢があるところでは還元はシフトの方に従うことを意味しています。規則 2 では、ユーザーがこの状況において行えるパーサーの動作の制御は多少おおまかなものになりますが、reduce-reduce 衝突は可能なかぎり避ける必要があります。

    衝突は、入力や論理に誤りがあるとき、または yacc では構築できない複雑なパーサーが (矛盾のない) 構文規則で必要になったときに発生します。また、どの規則を認識しているのかをパーサーが確認する前にアクションを実行する必要がある場合には、規則内のアクションを使用すると衝突が発生することがあります。

    これらの場合にあいまいさ解決規則を適用するのは不適切であり、パーサーも不正なものになります。そのため、yacc は上記の規則 1 と規則 2 によって解決された shift-reduce 衝突と reduce-reduce 衝突の数を常に報告します。

    一般に、あいまいさ解決規則を適用して正しいパーサーを生成できるときには、構文規則を書き直して同じ入力を読み取るようにすることもできます。構文規則を書き直した場合には、衝突は発生しません。そのため、初期のパーサージェネレータでは、衝突は重大なエラーとして扱われていました。

    このような書き直しは、やや不自然である上に、低速のパーサーが生成されることになります。そのため、yacc は衝突が存在している場合であってもパーサーを生成します。

あいまいさ解決規則の効果を表した例を以下に示します。

stat    : IF '(' cond ')' stat 
        | IF '(' cond ')' stat ELSE stat 
        ;

これは、if-then-else 文を含んだプログラミング言語のコードの一部です。これらの規則では、IF と ELSE はトークン、cond は条件 (論理) 式を表す非終端記号、stat は文を表す非終端記号になっています。最初の規則は単純 if 規則、2 番目の規則は if-else 規則と呼ばれます。

この 2 つの規則は、あいまいな構造を生じます。その理由は、以下のような形式の入力は、

IF ( C1 ) IF ( C2 ) S1 ELSE S2

その 2 つの規則に従った場合に以下の 2 つの方法で構成できるからです。

IF ( C1 ) 
{ 
     IF ( C2 ) 
         S1 
}
ELSE 
     S2
IF ( C1 ) 
{ 
    IF ( C2 ) 
        S1 
    ELSE 
        S2 
}

後者の解釈は、この構造を持った大部分のプログラミング言語で用いられる解釈です。つまり、各 ELSE は、ELSE に関連付けられていない直前の IF と関連付けられます。この例で、パーサーが以下の入力を認識してから ELSE を探す場合について考えます。

IF ( C1 ) IF ( C2 ) S1

この入力は、単純 if 規則によってすぐに以下のように還元されます。

IF ( C1 ) stat

そして、以下に示す残りの入力が読み取られます。

ELSE S2

次に、if-else 規則によって以下の入力が還元されます。

IF ( C1 ) stat ELSE S2

この結果、前述した前者の方の入力のグループ化が行われます。

一方、ELSE をシフトして、S2 を読み取ってから、以下の右側の部分に if-else 規則を適用すると、

IF ( C1 ) IF ( C2 ) S1 ELSE S2

以下のように還元できます。

IF ( C1 ) stat

これは、単純 if 規則で還元できます。

この結果、前述した後者の方の入力のグループ化が行われます。通常はこちらが望ましい方法です。

パーサーが行うことができる有効な処理が 2 つあるので、shift-reduce 衝突が存在します。この場合にあいまいさ解決規則 1 を適用すると、パーサーは shift を実行し、その結果目的のグループ化が行われます。この shift-reduce 衝突は、現在の入力シンボルが ELSE で、以下のような特定の入力が認識済みのときにだけ発生します。

IF ( C1 ) IF ( C2 ) S1

一般に、衝突は多数発生する可能性があり、各衝突は入力シンボルと以前に読み取った入力のセットに関連付けられます。以前に読み取った入力は、パーサーの状態によって特徴づけられます。

yacc の衝突メッセージの内容は、-v を指定した場合の出力を検討するとよくわかります。例として、上記の衝突状態に相当する出力を以下に示します。

23: shift-reduce conflict (shift 45, reduce 18) on ELSE 

state 23 
      stat :   IF ( cond ) stat_ (18) 
      stat :   IF ( cond ) stat_ELSE stat 
     
      ELSE     shift 45 
           .   reduce 18

最初の行は、衝突に関する説明で、状態と入力シンボルが表示されています。通常の状態の場合には、その状態でアクティブな構文規則とパーサーのアクションが表示されます。下線記号はすでに認識されている構文規則の一部を表しています。

したがって、state 23 のこの例では、パーサーは以下に対応する入力をすでに認識しています。

IF ( cond ) stat

また、この時点では、表示されている 2 つの構文規則はアクティブです。パーサーは 2 通りの処理を行うことができます。入力シンボルが ELSE の場合には、state 45 にシフトできます。

ELSE は state 45 においてすでにシフトされているので、state 45 にはその記述の一部として以下の行が含まれています。

stat : IF ( cond ) stat ELSE_stat

state 23 では、入力シンボルがアクションの中に明示的に記述されていない場合には、代替アクション (. によって指定されたアクション) が実行されます。つまり、入力シンボルが ELSE 以外の場合には、パーサーは構文規則 18 によって以下のように還元を行います。

stat : IF '(' cond ')' stat

shift コマンドの後の数字は別の状態を参照しており、reduce コマンドの後の数字は構文規則番号を参照しています。y.output ファイルでは、規則番号は還元可能な規則の後の括弧内に出力されます。大部分の状態では、reduce が使用可能であり、reduce がデフォルトのコマンドになっています。予期しない shift-reduce が発生した場合には、-v オプションによる出力を調べて、デフォルトのアクションが適切かどうかを判断してください。