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.
余談ですが、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を変更したり、レポートファイルをみることで確認しました。