2014年1月27日月曜日

パーサジェネレータの最速理解


yacc, bisonを使ったパーサジェネレータの基礎をまとめておく。

きっかけは、rubyのパーサ部分を読んでいる際に混乱したため。
rubyの場合、簡易で直感に従える文法規則を実装するため、
状態付きスキャナも複雑に絡んでおり一筋縄ではいかないことは承知済みである。

ただし、基礎としてのパーサ処理の理解が乏しいこともまた、
コードリーディングが難しくなっている理由でもあると素直に省みたわけである。
ここではrubyのパース処理を追いかけるものではないので肩肘張れず理解できるはずだ。


スタック内のシフトと還元の動作をトレース

以下のような規則に従った文法をパースする。

小文字は非終端記号。
大文字は終端記号とする。

program :
        | program stmt EOL

stmp    : primary
        | assign

funcall : IDENT '(' args ')'
        | IDENT '(' ')'

args    : primary
        | args ',' primary

assign  : IDENT '=' primary

primary : IDENT
        | NUMBER
        | STRING
        | funcall


スキャナからの入力を以下と仮定してスタックの様子をトレースする。
IDENT '(' STRING ',' NUMBER ')' EOF

program ← スタックは最初空なので空規則に一致する
program IDENT
program IDENT '('
program IDENT '(' STRING
program IDENT '(' primary
program IDENT '(' args
program IDENT '(' args ','
program IDENT '(' args ',' NUMBER
program IDENT '(' args ',' primary
program IDENT '(' args '
program IDENT '(' args ')'
program funcall
program stmt
program stmt EOF
program



よく使う慣用表現
・0個以上のitemのリスト
list:
    | list item


・1個以上のitemのリスト
list: item
    | list item


ところで、
list item

item list
と左右を逆にした場合どうなるのか。
0個以上のitemのリストを使って違いを見てみる。
例として、入力としてitemを3つpushして、
最後に空規則(END_ITEM)を追加して終わるとする。


・左再帰(left recursion)の場合
0個以上のitemのリストの再掲。

list:
    | list item

list                           最初は空(空規則にマッチ)
list item                      itemをシフト
list list                      listで還元
list list item                 itemをシフト
list list                      listで還元
list list item                 itemをシフト
list list                      listで還元


・右再帰(right recursion)の場合
list :
     | item list    ← ここを逆転させる

list                           最初は空
list item                      itemをシフト
list item item                 itemをシフト
list item item item            itemをシフト
list item item item END_ITEM   空規則をシフト
list item item list            listで還元
list item list                 listで還元
list list                      listで還元


リストの表現としては決定的な違いはないがアクションさせる場合、
その実行のされ方が変わる。
右再帰ではitemから順番にアクションが実行されていく。

この違いをどういう時に使うかは、実コード内から例をとったほうが参考になるだろう。
左再帰と右再帰あたりを参照。



シフトと還元の動作についてもう少し詳しく

このような規則があったとする。
target : A B c D
c      : C
       | C E


現在位置を_で表す。

target : A B _ c D
c      : C
       | C E

target : A B c D
c      : _ C
       | _ C E


(規則1)
トークンを入れ込むスタックの末尾がある規則に一致したら還元
というのが基本原則。


yaccではLALR(1)というアルゴリズムを使っているので1つだけトークンの先読みができる。
そのため、先の規則をより正確に言うと、
(規則1')
スタックの末尾がある規則に一致したら即還元ではなく、
還元後にシフトできそうだったら還元

例えば、次のトークンがDの場合、Cをcへ還元する。
次のトークンがEならシフトすることになる。

target : A B c D
c      :  C _
       |  C _ E


(規則2)
シフトできそうであればシフト

例えば、次のトークンがEの場合である。

target : A B c D
c      : C _
       | C _ E



シフトと還元のエラー例
・shift/reduce conflict エラー
還元前でもシフトできる場合である。

例えば次の規則でDが来た場合。

target : A B c D
c      : C _
       | C _ D
       | C _ E

※このエラー時、ディフォルトではshiftが優先される。


・reduce/reduce conflict エラー
同時に二つの規則が末尾と一致する場合である。

例えば次の規則でDが来た場合。

target : A B c D
c      : C _
       | C _ E
       | C _



エラー時の原因解析
・shift/reduce conflict エラー

一番最初に例示した規則に、
括弧なしで引数を呼べる関数規則を追加する。

funcall : IDENT '(' args ')'
        | IDENT '(' args ')'
        | IDENT args

するとshift/reduce conflict エラーが出る。

エラー出力用アウトプットファイルは以下のように出てくる。
ちなみにこれはraccの出力である。
raccは知っている人は知っているか。
yaccの学習に関しては、最適なのはオライリー以上にRubyを256倍使うための本 無道編だ。

state 10
  5) funcall : IDENT args _    ← reduceできる
  6) args : args _ "," primary ←  shiftできる

","             shift, and go to state 20       ←","が来た場合こちらを優先
","             [reduce using rule 5 (funcall)] ←[]は捨てられたrule(規則)
$default        reduce using rule 5 (funcall)   ←","以外のrule


shiftとreduceが衝突した場合はがshiftが優先される。

ところで、規則5と規則6は同じに見えない。
本当に衝突しているのか、という疑問がわかないだろうか。
こういう場合は、規則を展開して考えればよい。

このような規則を作っていた。
funcall : (略)
        | IDENT args

args    : primary
        | args ',' primary

primary : (略)

        | funcall

展開していく。
args : args "," primary
args : primary "," primary
args : funcall "," primary
args : IDENT args "," primary

これで納得いくだろう。
還元しようと思っていた規則の後に、先読みしたトークンが現れシフトもできるというわけである。


対策はいろいろあるが、一番簡単なのは、
トップレベルの関数呼び出しだけは括弧を省略可能にすることだろう。
もちろん手段は多々ある。

stmp    : primary
        | assign
        | IDENT args

funcall : IDENT '(' args ')'
        | IDENT '('  ')'


・reduce/reduce conflict エラー

括弧なしで引数のない関数の規則を追加する。

funcall : IDENT '(' args ')'
        | IDENT '(' args ')'
        | IDENT args
        | IDENT


エラー出力用アウトプットファイル例。

state 11 contains 3 reduce/reduce conflicts
rule 13 (primary) never reduced

state 11
  6) funcall : IDENT _ "(" args ")"
  7) funcall : IDENT _ "("")"
  8) funcall : IDENT _
 13) primary : IDENT _

  "("           shift, and go to state 12
  EOL           [reduce using rule 13 (primary)]
  ")"           [reduce using rule 13 (primary)]
  ","           [reduce using rule 13 (primary)]
  $default      reduce using rule 8 (funcall)]


つまり規則13は一切合財、規則8に上書きされる。
関数呼び出しと変数参照の区別がつかなくなり、
このままではすべて関数呼び出しになってしまう。


文法規則での解決は難しそうである。
必ずしも規則で解決する必要はない。
こういった場合は、規則13のアクションを使う。
存在しない変数だったら関数呼び出しにするようにすればいい。

こんな感じだろうか。
変数テーブル[var] || var 

変数テーブル[var] があればこちらを呼び出し、
なければ、varを実行。

これも対策は一つではない。



アクション内での引数の受け渡し

アクションで生成された値を手に入れる場合、
シフトされた値を左から順番に、$1、$2、...で参照できる。

次の規則とこの規則が還元される際にフックされるアクションがあるとする。
program  :  A  B { $1 + $2 }

この場合、$1にはA、$2にはBの値が入る。


ここまではいいだろう。

では、ある規則内で実施したあるアクションの結果を、
その規則内の別アクションで使うにはどうすればいいだろうか。

次の規則を見てみる。
Aを受け取りアクションした結果を
Bを受け取った際のアクションの値として使えるだろうか。

program  :  A
           {
             $$ =10
           }
            B
           {
              x = $2
              y = $3
           }


$2で10を参照できる。
意図したことは実現できそうなのだが、
それはなぜなのだろうか。なぜ$2なのだろうか。

アクションも一つのスタックに積まれる記号であることが分かれば疑問は解消する。

program : A  {~}   B {~}
          $1  $2    $3  $4

アクションは規則の最後にしか書けないわけではなく、
実は、規則の途中でも書くことができるのである。

埋め込まれたアクションは次のような記述の単なるシンタックスシュガーということである。

program: A { ~ } B { ~ }

は以下と同じである。

program: A dummy B dummy
dummy : /* 空規則 */
        {
            ~
        }




0 件のコメント:

コメントを投稿