test

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

優先度

衝突を解決する規則が不十分である状況が 1 つあります。それは、算術式の構文解析における状況です。一般に使用される算術式の構成のほとんどは、演算子の優先度の概念と、左または右の結合規則に関する情報によって自然に表現できます。適切なあいまいさ解決規則を伴ったあいまいな文法を使用すれば、あいまいでない文法で構築されたパーサーよりも高速かつ容易に書き込めるパーサーを作成できます。基本的な概念は、必要なすべての二項演算子と単項演算子について、以下の形式で構文規則を作成するということです。

expr : expr OP expr

次に : 

expr : UNARY expr

これにより、構文解析の衝突を多数伴った、非常にあいまいな文法が作成されます。

あいまいさ解決規則として、すべての演算子の優先度または結合の強さ、および二項演算子の結合規則を指定します。この情報によって、yacc がこれらの規則に従って構文解析の衝突を解決し、必要な優先度と結合規則を認識するパーサーを構築することができます。

優先度と結合規則は、宣言セクションでトークンに関連付けられます。この処理は、yacc キーワードの %left、%right、または %nonassoc の後にトークンのリストが続く一連の行によって行われます。同じ行にあるトークンは、すべて同じ優先度レベルと結合規則を持っているとみなされます。各行は、優先度または結合が強いものから順に記述されます。以下にその例を示します。

%left '+' '-' 
%left '*' '/'

この例では、4 つの算術演算子の優先度と結合規則が記述されています。+ と - は、左結合で、* と / よりも低い優先度を持っています。* と / も左結合です。キーワード %right は、右結合の演算子を表すために使用します。キーワード %nonassoc は、FORTRAN の演算子 .LT. などのような、互いに結合できない演算子を表すために使用します。つまり、以下の記述は FORTRAN では無効なので、.LT. は yacc ではキーワード %nonassoc を使用して表すことになります。

A .LT.  B .LT.  C

これらの宣言の例を以下に示します。

%right '=' 
%left '+' '- 
%left '*' '/' 

%% 

expr    : expr '=' expr    
        | expr '+' expr 
        | expr '-' expr 
        | expr '*' expr 
        | expr '/' expr 
        | NAME 
        ;

この記述を以下の入力に対して使用すると、

a = b = c * d - e - f * g

演算子の正しい優先度を実現するために、以下のように構成されます。

a = ( b = ( ((c * d) - e) - (f * g) ) )

このメカニズムを使用するときには、通常は単項演算子にも優先度を与える必要があります。単項演算子と二項演算子は、記号表現が同一の場合がありますが、優先度は必ず異なります。たとえば、単項演算子の - と二項演算子の - とでは、優先度が異なります。

単項演算子の - には、* (乗算) と同じか、それよりも高い優先度を与えることができますが、二項演算子の - は * よりも低い優先度になります。キーワード %prec は、特定の構文規則に関連付けられている優先度を変更します。この %prec は、構文規則の本体の直後の、アクションや終端のセミコロンの前に記述します。%prec の後にはトークン名またはリテラルを記述します。これにより、その構文規則の優先度は、後続のトークン名またはリテラルと同じ優先度になります。たとえば、以下の規則を使用すれば、単項演算子の - を * と同じ優先度にできます。

%left '+' '-' 
%left '*' '/' 

%% 

expr     : expr '+' expr 
         | expr '-' expr 
         | expr '*' expr 
         | expr '/' expr 
         | '-' expr %prec '*' 
         | NAME 
         ;

%left、%right、%nonassoc によって宣言されたトークンは、再度 %token によって宣言する必要はありません。ただし、宣言しても構いません。

優先度と結合規則は、構文解析の衝突を解決する際に yacc によって使用されます。優先度と結合規則によって、以下のようなあいまいさ解決規則が生成されます。

  1. 優先度と結合規則を持ったトークンやリテラルの優先度と結合規則が記録されます。

  2. ある 1 組の優先度と結合規則が、各構文規則に関連付けられます。これらは、規則の本体にある最終的なトークンまたはリテラルの優先度と結合規則です。%prec 構文を使用した場合には、このデフォルト値はその構文の値に置換されます。その構文規則に関連付けられた優先度と結合規則を持っていない構文規則もあります。

  3. reduce-reduce または shift-reduce 衝突が生じていて、入力シンボルまたは構文規則が優先度と結合規則を持っていない場合には、前節で示した 2 つのデフォルトのあいまいさ解決規則が使用され、その衝突が報告されます。

  4. shift-reduce 衝突が生じていて、構文規則と入力文字の両方が共にそれぞれに関連付けられた優先度と結合規則を持っている場合には、さらに高い優先度に関連付けられたアクション (shift または reduce) を選択して、その衝突を解決します。優先度が等しい場合には、結合規則が使用されます。左結合は reduce、右結合は shift、非結合は error を意味します。

    優先度によって解決された衝突は、yacc が報告する shift-reduce と reduce-reduce 衝突の数には加えられません。これは、優先度の仕様が間違っていると、入力構文のエラーを検出できなくなる可能性があることを意味しています。ある程度慣れるまでは優先度の使用を控えることも 1 つの方法です。y.output ファイルは、実際にパーサーが指定通りに動作しているかどうかを判定する際に利用できます。

優先度キーワードを使用して shift-reduce 衝突を解決する方法をさらに詳しく説明するため、前節の例と類似した例を取り上げます。以下の C 言語の文について考えます。

if (flag) if (anotherflag) x = 1; 
    else x = 2;

パーサーにとっての問題は、else に対応するのは最初の if なのか、それとも 2 番目の if なのかということです。C プログラマであれば、この字下げに惑わされることなく、else は 2 番目の if に対応していると判断するでしょう。if-then-else 構成の以下の yacc 文法では、この問題を抽象化しています。つまり、入力 iises (if-if.statement.else-statment) によってこれらの C の文を形成します。

%{ 
#include <stdio.h> 
%} 
%token SIMPLE IF ELSE 
%% 
S          ;  stmnt
           ;
stmnt      : SIMPLE
           | if_stmnt 
           ; 
if_stmnt   : IF stmnt
                { printf("simple if¥n");} 
           | IF stmnt ELSE stmnt 
                { printf("if_then_else¥n");} 
           ; 
%% 
int 
yylex() { 
        int c; 
        c=getchar(); 
        if (c= =EOF) return 0; 
        else switch(c) { 
            case 'i': return IF; 
            case 's': return SIMPLE; 
            case 'e': return ELSE; 
            default: return c; 
        } 
}

この仕様が yacc に渡されると、以下のメッセージが表示されます。

conflicts: 1 shift/reduce

問題なのは、yacc が iises と照合するために iis を読み取ったときに、選択肢が 2 つあるということです。つまり、is を文として認識する (reduce) 場合と、さらに入力を読み取って (shift)、最終的に ises を文として認識する場合があります。

この問題を解決する方法の 1 つとして、新しいトークン REDUCE を作成して解決する方法があります。この REDUCE の用途は、正しい優先度を規則に与えることです。

%{ 
#include <stdio.h> 
%} 
%token SIMPLE IF 
%nonassoc REDUCE 
%nonassoc ELSE 
%% 
S       : stmnt '¥n' 
        ; 
stmnt   : SIMPLE 
        | if_stmnt 
        ; 
if_stmnt : IF stmnt %prec REDUCE 
            { printf("simple if");} 
        | IF stmnt ELSE stmnt 
            { printf("if_then_else");} 
        ; 
%%

if_stmnt の 2 番目の形式に関連付けられている優先度が高くなっているので、yacc は最初にその規則との照合を試み、衝突も報告されません。

この単純な例では、実際には新しいトークンは必要ありません。

%nonassoc IF 

%nonassoc ELSE

上記の 2 つも機能します。また、shift-reduce 衝突では yacc はデフォルトで shift を行うので、実際には上記のような方法で衝突を解決する必要はありません。ただし、正しい仕様ならば診断メッセージは表示されないという点では、衝突を解決するのも良い方法です。