🙆

驚異的な拡張性と表現力を持つ Programmable Pratt Parser

2024/04/24に公開

コンパイラ

構文解析

パーサー

tech

はじめに

Lean4のパーサーにインスピレーションを得て、任意の構文をプログラマブルに埋め込めるパーサーを考案し、実装した。 P3（Programmable Pratt Parser）と呼んでいる。

https://github.com/ksrky/p3/tree/master

Pratt parser は、演算子の優先順位を扱う再帰下降構文解析法の一種である。これを使うと、前置演算子や中置演算子だけでなく、if式や配列の添字などの複雑な構文も同じロジックでパースできるようになる。これはユーザー定義演算子をサポートするプログラミング言語で有用である。例えばHaskellでは、ユーザー定義演算子をサポートしているが、GHCのパーサーは通常の構文のパースと演算子のパースを2フェーズに分けている。これを一つのパスで実装できれば、コンパイラの実装がよりシンプルになるだろう^[1]。

このブログではP3がどんな式をパースできて、それをどのようなアルゴリズムで実現したかを説明していく。ただ、私もなぜこれでうまく行くのかはっきりと分かっていないところが多い。それは、私がロジックを実装に移すというより、エンジニアリング的直感に基づいてアルゴリズムを抽象化し、コードを修正してきたためだと思う。
驚くべきことにP3はclocカウントで300行そこそこで書かれている。そのため、このブログを読むより、コードを実際に読むほうが理解が早いかもしれない。

初めは以下のようなブログやコードを参考にしていたが、抽象化するにつれてどんどん見た目が変わってきた。P3は以下のいずれで示されている方法よりもパースできる式の種類が多い。

Pratt parserの実装方法は恐らくいろいろな形があり、このブログで解説しているものはあくまでP3の実装でしかない。特に、原論文^[2]を参照したわけではないので、どこからどこまでがPrattの考案なのかは把握していない。

前置演算子・中置演算子・後置演算子のパース

このあたりは上に挙げたブログでも解説されているので、簡単に説明する。オリジナルのPratt parserでは、演算子の結合性の優先順位（Precedence）ではなく、演算子の左右の式（被演算子）の結合力（Binding power）を考える。そのため、例えば、+は左結合でPrecedenceが65というような言い方ではなく、+の左のBinding powerが65、右のBinding powerが66などという表現をする。

また、Pratt parserは2つのメイン関数が相互再帰するようなアルゴリズムで実装される。一方がLeadingパーサーで、もう一方がTrailingパーサーである。このあたりの用語はLean4のパーサーを参照している。leadingとtrailingがどういう風に用いられるのかを言葉で説明するのは難しいが、例えば-3 * 2という式では、以下のようにトークン上を動く。ネストはその関数の中で呼び出されたことを意味する。

-   leading
      3  trailing
*   trailing
      2   leading
      eof trailing

P3では以下のようにトークンでインデックス付けされたパーサーテーブルを持っている。型自体は同じであるが、leadingとtrailingは区別する必要がある。

data ParserTable t m = ParserTable
    { _leadingParsers   :: M.Map t [Parser t m]
    , _trailingParsers  :: M.Map t [Parser t m]
    }

3種類の演算子の一般化

前置演算子、中置演算子、後置演算子を一般化した表現を考えて、if式や配列の添字なども同じロジックでパースしたい。そのために、私は以下のようなデータ構造を考えた。型パラメータtはトークンのことで、トークンには任意の表現を持たせられる。

type BindingPower = Int

data Oper t
    = Operator t
    | Operand BindingPower

data MixfixOp t = MixfixOp
    { name  :: Name
    , opers :: [Oper t]
    }

Mixfix演算子は、演算子と被演算子の並びであると考えられる。例えば、if式は以下のように表現できる。

ifExpr :: MixfixOp String
ifExpr = MixfixOp "If" 
        [ Operator "if", Operand 30
        , Operator "then", Operand 30
        , Operator "else", Operand 30
        ]

Haskellのユニットを表現することもできる。

unitExpr :: MixfixOp String
unitExpr = MixfixOp "Unit" [Operator "(", Operator ")"]

ただし、演算子が先頭か2番目に来ないOperの列は正しくパーサーに変換できない。なぜなら、Pratt parserは一文字の先読みしかできないからである。

バックトラック

トップダウンパーサーの弱点は、そのままではバックトラックができないことである。バックトラックができないと、例えばif-then式をパースするときに、if-then-else式との区別がつかない。ただ、バックトラックを導入するのはそれほど難しくはない。先頭のトークン（例えばif）に対して複数のパーサーが登録されている場合は、それらすべてを実行して、最長一致したものを選択するという方法である。Lean4.Parser.Basicのコメントが非常に参考になった。
バックトラックが可能になったことによって、例えば、if 1 == 2 then if 4 then 5 else 6のような式が、if 1 == 2 then (if 3 then 4 else 5)としてパースできるようになった。if 1 == 2 then (if 3 then 4) else 5ではない。

ここまでのまとめ

p3-testにいくつか具体例がある。ここでは、特に字句解析をせず、トークンをただの文字列としたときの例を示す。QuasiQuoteを使うことで、以下のように宣言的にパーサーを定義することができる。

以下からいくつかのテストケースを確認できる。

面白い点としては、予約語がないので、if * let + thenのような式をパースできることだ。トークンの型はパラメータ化されているため、字句解析で予約語と識別子の表現を分けることはできるが、P3自体は予約語という概念を持っていない。

Let式やラムダ式のパース

自然な流れとして、次はLet式やラムダ式をパースしたいと考えるだろう。しかし、Let式やラムダ式は、変数束縛を含むため、変数束縛のためのパーサーをどうやって組み込むかが問題である。私が考えたのはパーサージェネレータの非終端記号のようなものを各被演算子に持たせることである。そのために、ParserCategoryというものを導入して、先程のOper型を書き換える。

type ParserCatgory = Int

data Oper t
    = Operator t
    | Operand ParserCategory BindingPower

これを使うと例えば、Let式は以下のように表現できる。ただし、式のParserCategoryを0、変数を1とする。実際には、ParserCategoryはもっとわかりやすい識別子にして、それをマップするデータを保持しておくのが良いだろう。

letExpr :: MixfixOp String
letExpr = MixfixOp "Let" 
        [ Operator "let", Operand 1 0
        , Operator "=", Operand 0 10
        , Operator "in", Operand 0 10
        ]

終端記号のパース

ここまでは特に終端記号の扱いについて述べてこなかった。これは単に文字列にしてしまえば良いからである。だが、xのような識別子はAST上ではしっかりVar "x"のように表現したい。このようなパーサーはleadingパーサーやtrailingパーサーでは実現できない。そこで、ParserTableを書き換える。

data ParserTable t m = ParserTable
    { _leadingParsers   :: M.Map t [Parser t m]
    , _trailingParsers  :: M.Map t [Parser t m]
    , _terminalParsers  :: [t -> Parser t m]
    }

実装の都合上、terminalParsersはトークンを受け取ってパーサーを返す関数となっているが、それよりトークンでインデックス付けされていないことに注意が必要である。terminalパーサーはleadingパーサーに失敗した場合にすべて試される。

関数適用のパース

最後に、悪名高い？スペースで区切られた関数適用の構文を実現する。これはトップダウンパーサーで実装するときには無限再帰が起こるなどして罠になりがちである。ボトムアップのLRパーサーの場合は左再帰させれば良いから簡単なのだが。

関数適用は目印となるトークンがないため、同じようにleadingでもtrailingでも実現できない。したがって、更にParserTableを拡張する必要がある。

data ParserTable t m = ParserTable
    { _leadingParsers   :: M.Map t [Parser t m]
    , _trailingParsers  :: M.Map t [Parser t m]
    , _terminalParsers  :: [t -> Parser t m]
    , _unindexedParsers :: [Parser t m]
    }

この新たに追加したunindexedParsersは、トークンでインデックス付けされていないパーサーである。terminalパーサーとは異なって、今度はtrailingパーサーが失敗したときに試される。

しかし、これだけでは、いくつか問題が発生する。まずは、演算子のトークンの問題である。例えば、f + 1という式は、fと1の足し算であってほしいが、fに+と1という式が適用されていると解釈されてしまう可能性がある。これを回避するには、fや1のようなトークンと、識別子になりえない+のようなトークンに字句解析の時点で別の表現を割り当てる必要がある。
次も似たような問題だが、今度は識別子になりうる演算子（thenやin）が誤って関数適用として解釈されてしまう点である。結局、残念なことに関数適用のパースをするために予約語という概念を導入することになった。だが、予約語のスコープを限定することで、パースできなくなる式は特に見当たらなかったのでそんなに問題もなさそうである。予約後のスコープというのは、if式をパースするときに一時的にthenとelseを予約語として扱うといったようなことである。

終わりに

以上の機能をフルに使ってパーサーテーブルを書くと以下のようになる。

文法規則に互いにオーバーラップがあっても、正しくパースできていることがわかる。

今後の拡張としては

字句解析時に行頭のスペースを記録してオフサイドルールのようなものを実現する。
同じトークン列を再びパースしないように、キャッシュを使って効率化する。

などを考えている。APIを整理して、ライブラリとして使えるようにもしたい。

脚注

Haskellの場合は演算子の結合性の宣言を演算子の定義後に書くことができるため、仮にすべての式をPratt parserでパースできたとしても、厳密にはワンパスにならないかもしれない ↩︎
https://dl.acm.org/doi/pdf/10.1145/512927.512931 ↩︎