2014年1月27日月曜日

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


yacc, bisonなどのLALR(1)パーサの基礎をまとめておく。


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

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

大文字は終端記号(terminal symbol)、スキャナから送られてくる記号とする。
小文字は非終端記号(non-terminal symbol)とする。スキャナから送られてこない、パーサだけに存在する左辺に出てくる記号である。

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

LR法の、入力を左(Left)から右に読んでいき、右端導出(Rightmost derivation)する過程がわかる。

よく使う慣用表現

・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 item                      itemをシフト
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


現在位置を_で表す。非終端記号のcの前である。シフトできるのは非終端記号だけだが、非終端記号はその規則を使って展開しても良いので、
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 '(' ')'
        | IDENT args

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

エラー出力用アウトプットファイルは以下のように出てくる。
ちなみにこれはraccの出力である。ruby用のyaccである。

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が優先される。

さて、どこでshiftとreduceが衝突しているか探ってみる。
shiftの方は規則6の通りで明らかである。
reduceされる条件は、「スタックの末尾がある規則に一致したら即還元(reduce)ではなく、還元後にシフトできそうだったら還元(reduce)」であったことを思いだそう。
還元した後に、","でシフトできるルール(function ",")があるということである。

下記のような規則を作っていた。一見そのようなルールはなさそうに見えるため、複数の規則にまたがって存在しているのだろう。

funcall : (略)
        | IDENT args

args    : primary
        | args ',' primary

primary : (略)
        | funcall

先読みする","に目をつけ、展開していく。
args : args "," primary
         ↓
args : primary "," primary
         ↓
args : funcall "," primary

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

stmp    : primary
        | assign
        | IDENT args

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


・reduce/reduce conflict エラー

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

funcall : IDENT '(' args ')'
        | IDENT '(' ')'
        | 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 : /* 空規則 */
        {
            ~
        }