GLL parsing をちょっと調べたのだが、 これは Earley parsing に近いと思った。
まぁ、lookahead で枝刈りするのは Earley にはないから、ちょっと違うか。
演算子の優先順位というのは、式の中に ... op1 e op2 ... という部分があったとき、つまり式 e が演算子 op1 と演算子 op2 ではさまれていたときに、 その式 e が優先順位の高い方の演算子の引数となるということである。 綱引きみたいな感じ。
ここでいう演算子は二項演算子や単項演算子だけとはかぎらない。 一般には、式の導出規則で式が左右の端に出現するものは、その端に出現する式を他の演算子とではさむことができるので、その式がどちらに属するかを優先順位によって指定することができる。
yacc とかの優先順位は、衝突があったときに shift と reduce のどちらかを選ぶ、と実装される。 SDF では (SGLR により曖昧なものも含めてすべての構文木を生成する仕掛けなので) 導出の抑制を指定するという話になっている。
ただ、SDF の導出抑制は抑制しすぎて受け付ける言語が小さくなってしまう場合があるようで、よろしくない。
ということで、そういうことが起きない (受け付ける言語が変わらない) ように、 文法を優先順位を反映するように変形する、という話がある。
前者の著者の D論が後者で、Chapter 4 に前者の Safe Specification of Operator Precedence Rules が入っている。 (D論のほうが後で書かれているだろうから、修正がおこなわれているかもしれない)
ここであげられているアルゴリズムで以下のように文法を変形できるという例が記述されている。
入力として以下の文法が与えられる。 (E + E が左結合というのが (left) という記述で指定され、E + E よりも i E と a のほうが優先順位が低いというのが不等号 > で指定されている。 )
E ::= E + E (left)
> i E
| a
出力として以下の文法が生成される。
E ::= E1 + E2 | i E | a E1 ::= E1 + E3 | a E2 ::= i E | a E3 ::= a
この文法は、以下のような足し算と OCaml スタイルの if 式を表現している。 (区別しやすくするため、トークンを double quote でくくってある)
E ::= E "+" E
| "if" E "then" E "else" E
| "a"
i E というのは i と E の連結で、i は "if" E "then" E "else" に対応している。 OCaml スタイルの if 式は "if" E "then" E "else" E だが、"if" から "else" までは両端がトークンなので、かっこみたいなものとみなせる。 そのため優先順位には関係しないので、i としてまとめている。 こうやってまとめると、i は前置単項演算子とみなせる。
ということで、二項演算子 + と、前置単項演算子 i からなる式で、後者のほうが優先順位が低いという文法を考えていることになる。 (二項演算子よりも前置単項演算子の優先順位が高いなら、単項演算子のプラスやマイナスと同じになるので、単項演算子の優先順位が低いというのがこの例の面白く難しい点である。)
さて、変形された文法を少し展開して単純にすると、以下のようになる。
E ::= E1 + E2 | i E | a E1 ::= E1 + a | a E2 ::= i E | a
これを眺めてしばらく考える。
まぁ、なんとかわかった気がする。 ... i a + ... という列があったときに、a は (優先順位が i よりも高い) + の引数になるようになっていると思う。
でも、この文法はわかりやすくはないよな。+ が 2箇所、i が 2箇所、a が 4箇所出現していて、(優先順位で記述されていた文法と違って) 重複があるし。
優先順位を使った文法のほうが、意図を素直に表現できていると思う。
なお、件のD論の Chapter 5 Operator Precedence for Data-dependent Grammars では、 (Chapter 3 で説明されている) data-dependent grammar というものを使って、そういう重複を起こさずに優先順位を実装する方法を述べている。 これは GLL ベースで、attributed grammar ぽいことをやって、優先順位に反する構文木を除去していくというものだと思う。 ただ、これって決定的な動作をするかどうかいまいち確信できないような気がする。
[latest]