Ruby Parser開発日誌 (17) - 演算子の優先度はいつ使われるのか

AWKの式でa + bが構文解析でa (+b)ではなくて、(a) + (b)と解釈されるのはなぜでしょうかという質問をいただきました。 私はAWKに詳しいわけではないですが、LR parser なかでもBison用に書かれた文法定義ファイルであれば解説できると思うので、少し踏み込んで解説をしてみたいと思います。

質問者の方は https://pubs.opengroup.org/onlinepubs/9699919799/utilities/awk.html の"Expressions in awk"を読んで、+ expr (Unary plus)の方がexpr + expr (Addition)よりも優先度が高いのであるからa + bはa (+b)と解釈されるのではないかと考えていました。とても良い質問だと思います。

結論を先にいうと、ここで問題になるのは加算(Addition)と文字列結合(String concatenation)の優先度であり、加算(Addition)のほうが優先度が高いのでa + bは(a) + (b)と解釈されます。

awkの構文解析の様子

下準備

まずはgawkのソースコードをレポジトリからcloneしてきます。 今回はtag gawk-5.3.0 (5efd1487e16e68a1bb52fa5ca997d2d51182bff2)を使って解説をしていきます。

Bisonを使っている場合yydebugという変数に0以外を設定することで構文解析の詳細なlogが出力されます。 "main.c"を眺めるとYYDEBUGというマクロが有効であればYオプションでyydebugを有効化できることがわかります。 また"configure.ac"をDYYDEBUGで検索すると$srcdir/.developingというファイルがあるときにdebugモードでビルドしてくれそうです。

$ touch .developing
$ ./configure
$ make
$ ./gawk -Y '{ a + b }'
Starting parse
Entering state 0
Stack now 0
Reducing stack by rule 1 (line 235):
-> $$ = nterm program ()
Entering state 1
...

無事にパーサーのlogがでるようになったので、このlogを調べていきましょう。

a + b の解析

ShiftについてはShifting token NAME ()のようにShifting token ...と表示されている行をみればわかります。 ReduceについてはReducing stack by rule 194 (line 2156):のようにReducing stack by rule ...と表示されている行とその後に続くメッセージをみればわかります。 たとえば以下のような出力であれば、simp_exp: simp_exp '+' simp_expのルールによってReduceしていることがわかります。

Reducing stack by rule 153 (line 1807):
   $1 = nterm simp_exp ()
   $2 = token '+' ()
   $3 = nterm simp_exp ()
-> $$ = nterm simp_exp ()
Entering state 36
Stack now 0 1 29 81 155 36

'{ a + b }'の中でもとくにa + bの部分について、構文解析が進んでいく様子をまとめたものが以下の図です。

awkgram.yという文法ファイルをみてみましょう。 String concatenationはcommon_expで、Additionはsimp_expでそれぞれ定義されています。Unary plus(単項演算のプラス)はnon_post_simp_expで定義されています。

また式に関する文法は

• simple_stmt: exp
  • exp: common_exp

という構造になっているので、ここではcommon_exp以下の構造を調べていきます。

common_exp: simp_exp
          | common_exp simp_exp %prec CONCAT_OP /* String concatenation */

simp_exp: simp_exp '+' simp_exp /* Addition */
        | non_post_simp_exp

non_post_simp_exp: variable
                 | '+' simp_exp /* Unary plus */

今回の質問は、下図1のような動きになるのではないかという質問です。 つまりaをcommon_expとし、+bをnon_post_simp_exp -> simp_expとして、全体をString concatenationのcommon_expとして解釈しないのだろうかということになります。

パーサーの気持ちになって考える

以前 Ruby Parser開発日誌 (14) - LR parser完全に理解した - かねこにっき で解説したとおり、LR parserというのはBNFのルールに1:1対応するオートマトンを用意し、それを1つのオートマトンに合成してつくります。

ここではa + bをパースしているときのパーサーの状態について詳しくみていきましょう。

いま問題になっているのはaをパースして、次のtokenが+という状況です。 aがsimp_expであることと次のトークンが+であることを考慮すると、この時点では2つの可能性があります。ひとつはcommon_exp: simp_expの解析中であり、かつsimp_exp: simp_exp '+' simp_expの解析中であるというケースです。

もうひとつはcommon_exp: common_exp simp_expの解析中であり、かつcommon_exp: simp_expの解析がちょうどいま終わろうとしているケースです。

ケース1では+をShiftして処理を進めることになりますし、ケース2では+をShiftせずにcommon_exp: simp_expのルールでReduceをすることになります。これはShift/Reduce Conflictと呼ばれるもので、1つの状態のときにShiftとReduceの両方が成立しうる状態です。Conflictというのはパーサーからするとどうしていいのか決められないので、パーサーの開発者が決めてあげる必要があります。このケースではAddition (ケース1)とString concatenation (ケース2)のどちらを優先するかという話であり、仕様ではAdditionを優先することになっています。なのでケース1が選択されます。

ケース1を選択したので、+をShiftして処理を続けてみましょう。 つぎのトークンがNAMEであり、NAMEは何回かのReduceによってvariableになることを加味すると、non_post_simp_exp: variableをパースする状態にいると考えることができます。non_post_simp_exp: '+' simp_expという単項演算のルールもありますが、+はすでに上位のオートマトンで考慮されているため、ここではこのルールは該当しません。

gawkのパーサーの状態を調べてみる

ここまでの説明と実際のgawkのパーサーの状態が一致しているのか確認してみましょう。 ここではBisonの出力するレポートファイルを使うので、まずはレポートファイルを生成します。

$ make clean
$ make YFLAGS="--report=states,itemsets,lookaheads,solved"

を実行するとawkgram.outputというファイルが生成されます。 これにはパーサーの状態に関する様々な情報が記載されています。 今回問題になっているのは+をShiftするかどうかという点なので、./gawk -Y '{ a + b }'のlogのうち+をShiftしている前後をみます。

Stack now 0 1 29 81 155 36
Next token is token '+' ()
Shifting token '+' ()
Entering state 100
Stack now 0 1 29 81 155 36 100
Reading a token

State 36のときに+をShiftしてState 100に遷移していることがわかります。 レポートファイルを見てみましょう。

State 36

  145 common_exp: simp_exp •  [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, IO_OUT, IO_IN, MATCHOP, LEX_GETLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, NEWLINE, SLASH_BEFORE_EQUAL, '?', ':', ',', '<', '>', '+', '-', '/', '!', '$', '(', ')', '@', ']', '{', ';']
  149 simp_exp: simp_exp • '^' simp_exp
  150         | simp_exp • '*' simp_exp
  151         | simp_exp • '/' simp_exp
  152         | simp_exp • '%' simp_exp
  153         | simp_exp • '+' simp_exp
  154         | simp_exp • '-' simp_exp

    '+'  shift, and go to state 100
    '-'  shift, and go to state 101
    '*'  shift, and go to state 102
    '/'  shift, and go to state 103
    '%'  shift, and go to state 104
    '^'  shift, and go to state 105

    '+'       [reduce using rule 145 (common_exp)]
    '-'       [reduce using rule 145 (common_exp)]
    '/'       [reduce using rule 145 (common_exp)]
    $default  reduce using rule 145 (common_exp)

145 common_exp: simp_exp •というのがさきほどのケース2のことです。 下のほうに'+' [reduce using rule 145 (common_exp)]と書いてあるとおり、Reduceをすることになります。

153 | simp_exp • '+' simp_expというのがケース1に該当します。 '+' shift, and go to state 100と書いてあるように、こちらは+をShiftします。

[reduce using rule 145 (common_exp)]と[]で囲ってあるのはReduceではなくShiftを選択したという意味です。

BisonはS/R Conflictがあり、演算子の優先度を考慮しても決定できないときにShiftを選択するという挙動をします。 なのでState 36では仕様の通り優先度の高いAdditionが選択されています。

Bison is designed to resolve these conflicts by choosing to shift, unless otherwise directed by operator precedence declarations.

Shift/Reduce (Bison 3.8.1)

余談ですが、BisonのS/R Conflict解消の挙動に依存したくない場合、以下のようにcommon_exp: simp_expのルールに優先度を明示することで解決できます。

diff --git a/awkgram.y b/awkgram.y
index 5f0697b0..cbce0f6a 100644
--- a/awkgram.y
+++ b/awkgram.y
@@ -1733,7 +1733,7 @@ a_relop
        ;

 common_exp
-       : simp_exp
+       : simp_exp %prec CONCAT_OP
          { $$ = $1; }
        | simp_exp_nc
          { $$ = $1; }

State 36

  145 common_exp: simp_exp •  [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, IO_OUT, IO_IN, MATCHOP, LEX_GETLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, NEWLINE, SLASH_BEFORE_EQUAL, '?', ':', ',', '<', '>', '!', '$', '(', ')', '@', ']', '{', ';']
  149 simp_exp: simp_exp • '^' simp_exp
  150         | simp_exp • '*' simp_exp
  151         | simp_exp • '/' simp_exp
  152         | simp_exp • '%' simp_exp
  153         | simp_exp • '+' simp_exp
  154         | simp_exp • '-' simp_exp

    '+'  shift, and go to state 100
    '-'  shift, and go to state 101
    '*'  shift, and go to state 102
    '/'  shift, and go to state 103
    '%'  shift, and go to state 104
    '^'  shift, and go to state 105

    $default  reduce using rule 145 (common_exp)

    Conflict between rule 145 and token '+' resolved as shift (CONCAT_OP < '+').
    Conflict between rule 145 and token '-' resolved as shift (CONCAT_OP < '-').
    Conflict between rule 145 and token '/' resolved as shift (CONCAT_OP < '/').

UNARY 優先度の役割

awkgram.yの優先度定義をみると単項演算子のためにUNARYという優先度が定義されています。 これがどのような役割を担っているか確認しておきましょう。

diff --git a/awkgram.y b/awkgram.y
index 5f0697b0..3d271a7d 100644
--- a/awkgram.y
+++ b/awkgram.y
@@ -1983,7 +1983,7 @@ non_post_simp_exp
                        $$ = list_append($2, $1);
                }
          }
-       | '+' simp_exp    %prec UNARY
+       | '+' simp_exp
          {
                if ($2->lasti->opcode == Op_push_i
                        && ($2->lasti->memory->flags & STRING) == 0

という変更をいれて、その前後でレポートファイルを比較することで、単項演算子+に対するUNARY優先度の役割がわかります。

State 62が影響を受けます。この状態はnon_post_simp_exp: '+' simp_exp •とあるようにまさしく単項演算子を含む式に関するルールです。単項演算子の対象の式もまたsimp_expなので、このsimp_expがa * bであったりします。つまり+ a * bを+ (a * b)とするのか(+ a) * bとするのかを決める必要があります。仕様によるとUnary plusはMultiplication, Division, Modulusよりも優先度が高いので、(+ a) * bと解釈するのが正しく、ここではReduceをする必要があります。'+' simp_exp %prec UNARYの%prec UNARYは、このルールの優先度を*, /, %よりも高くするために必要であることがわかります。もし%prec UNARYがないと、+と*の優先度の比較が行われ*のほうが優先度が高いので、+ (a * b)と解釈されてしまいます。

diff --git a/awkgram.output.before b/awkgram.output.after
index fab379f2..6f001b66 100644
--- a/awkgram.output.before
+++ b/awkgram.output.after
@@ -2151,18 +2151,21 @@ State 62
   152         | simp_exp • '%' simp_exp
   153         | simp_exp • '+' simp_exp
   154         | simp_exp • '-' simp_exp
-  179 non_post_simp_exp: '+' simp_exp •  [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, IO_OUT, IO_IN, ASSIGNOP, ASSIGN, MATCHOP, LEX_GETLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, NEWLINE, SLASH_BEFORE_EQUAL, '?', ':', ',', '<', '>', '+', '-', '*', '/', '%', '!', '$', '(', ')', '@', ']', '{', ';']
+  179 non_post_simp_exp: '+' simp_exp •  [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, IO_OUT, IO_IN, ASSIGNOP, ASSIGN, MATCHOP, LEX_GETLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, NEWLINE, SLASH_BEFORE_EQUAL, '?', ':', ',', '<', '>', '+', '-', '!', '$', '(', ')', '@', ']', '{', ';']

+    '*'  shift, and go to state 102
+    '/'  shift, and go to state 103
+    '%'  shift, and go to state 104
     '^'  shift, and go to state 105

     $default  reduce using rule 179 (non_post_simp_exp)

-    Conflict between rule 179 and token '+' resolved as reduce ('+' < UNARY).
-    Conflict between rule 179 and token '-' resolved as reduce ('-' < UNARY).
-    Conflict between rule 179 and token '*' resolved as reduce ('*' < UNARY).
-    Conflict between rule 179 and token '/' resolved as reduce ('/' < UNARY).
-    Conflict between rule 179 and token '%' resolved as reduce ('%' < UNARY).
-    Conflict between rule 179 and token '^' resolved as shift (UNARY < '^').
+    Conflict between rule 179 and token '+' resolved as reduce (%left '+').
+    Conflict between rule 179 and token '-' resolved as reduce (%left '-').
+    Conflict between rule 179 and token '*' resolved as shift ('+' < '*').
+    Conflict between rule 179 and token '/' resolved as shift ('+' < '/').
+    Conflict between rule 179 and token '%' resolved as shift ('+' < '%').
+    Conflict between rule 179 and token '^' resolved as shift ('+' < '^').

このように演算子の優先度というのはLR parserの状態を計算し、コンフリクトがあったときにそれを解消するために使われます。

まとめ

AWKにおいてa + bを構文解析上a (+b)と解釈するのか(a) + (b)と解釈するのかという質問を受けたので調べてみました。 今回のケースでは単項演算(Unary plus)と加算(Addition)の優先度ではなく、加算(Addition)と文字列結合(String concatenation)の優先度を考える必要がありました。gawkでは仕様にあるとおり加算(Addition)を優先する実装になっていました。

演算子の優先度はtableなどに切り出されていることが多く、一見すると広い範囲で使われているように思えますが、実際はLR parserの各状態でコンフリクトが発生したときにコンフリクトを解消するために使われます。このことをawkgram.yを変更したり、レポートファイルをみることで確認しました。