Zenn
🌟

Parolというパーサ生成ツールがすごい

2022/11/27に公開
Rust
構文解析
パーサ
tech

parolというLL(k)パーサを生成するcrateがあるのですが、とにかくすごいので紹介します。
parolを知って、Rustでパーサをつくることに関して新しい時代が始まったなと思いました。

パーサコンビネータ

Rustでパーサといえばnomやchumskyといったパーサコンビネータが主流の印象です。
これはjsonのように既に文法が定義されている場合やプログラミング言語のプロトタイピングに向いていると思います。
nomのREADMEにも後者について以下のように言及されています。

While programming language parsers are usually written manually for more flexibility and performance, nom can be (and has been successfully) used as a prototyping parser for a language.

DeepL訳: プログラミング言語のパーサーは通常、より柔軟で高性能なものを求めて人手で書かれますが、nomは言語のプロトタイピングパーサーとして使用することができます（これまでも成功しています）。

逆に新しく実用的なフォーマットやプロトコルを作りたい場合や本格的にプログラミング言語の開発をする場合には向いていない場合があると思います。理由は主に以下です。

  1. 完成したパーサの時間計算量や空間計算量といった性質が簡単にはわからないこと[1]
  2. コーナーケースの時にどういう挙動をするかが予測しずらく、実装の中身の知識が必要になる場合があること
  3. 意図せず複雑な文法を作ってしまう危険性があること[2]
  4. 文法定義を提供したい場合、ソースコードとは別に文法定義を保守する必要があること

これらの問題を回避・軽減する方法として有名なのはLL(k)やLR(k)の文法を作ってそこから適切な生成アルゴリズムでパーサを生成することでしょう[3]。
1についてはいくつかのアルゴリズムについて計算量が分かっているため解決できます。
2についても適切なアルゴリズムと適切な実装を選択すれば問題ないです。
3については少なくともLLパーサやLRパーサにとって読めない文法は排除することができます[4]。
4については多くの生成ソフトウェアの入力が文法ファイルであるため解決されます。

Parol以外の選択肢

私が知っている限り大きいものだと以下の選択肢があります。

どちらも使えそうではありますが、個人的には実用するとなるといろいろな覚悟や割り切りが必要だと感じました。以下私の感想です。

lalrpop

  • parolをのぞけば、正直これ以外の選択肢はないのは事実だが……
  • 今後も開発が継続するか怪しく、また最悪の場合に自分で保守するには少し大きすぎる
  • 文法定義の仕様が自分にとっては複雑すぎて、読むのも書くのも苦労しそう
  • ドキュメントをざっくりみた限りでは、正しく使う方法が自分にはよくわからなかった[5]

antlr4rust

  • まだ成熟しておらず、また、どの程度の機能が実装されているかがよくわからない[6]
  • ANTLRという外部依存ができてしまうことに不満を感じる
  • ビルドをcargoの中で完結させるのに苦労しそう
  • 正直ANTLRの仕組みがよく分かってない（すごいらしい）

Parolの特徴

READMEから三箇所を抜粋してDeepLにかけたのが以下です。
ちょっと多いので、飛ばしてその下の私の感想だけ読んでいただくだけでも問題なく概要がわかると思います。

生成されるパーサーは

  • プッシュダウン・オートマトン（PDA）によって実装された真のLL(k)パーサーです。
  • また、PDAは予測型であり、バックトラックのない解析技術を実装しています。これにより、多くの場合、より高速なパーザが得られます。
  • クリーンで読みやすい
  • 特定の非終端記号（0～k）に対して必要なだけの先読みを使用します。
  • 1つの文法記述ファイルから生成される
  • 文法のASTに類似した型を自動的に生成できる。そして、これらの型を使って意味づけされたアクションが呼び出される。これにより、開発プロセスが大幅に改善され、エラーが起こりにくくなる。

その他のparolの特性

  • 生成の選択は、各非終端に対して決定論的有限ルックアヘッドオートマトンによって行われる。
  • 空のデフォルト実装を持つ意味作用は、trait として生成されます。このtraitを文法処理項目に実装し、必要なアクションのみを実装することができます。これにより、言語定義と言語処理との間の緩やかな結合が実現される。
  • その結果、Bisonとは異なり、セマンティックアクションは文法定義から厳密に分離されます。意味作用の実装を変更するだけであれば、パーサーの生成ステップは必要ありません。
  • 文法記述は、グループ化、オプション要素、繰り返しなど、EBNFで知られる機能を追加したYacc/Bisonのようなスタイルで提供されます。
  • 複数のスキャナ状態（別名、開始条件）を定義し、それらの間のスイッチを文法のプロダクションで直接定義することができる。
  • 各スキャナー状態に対して、空白と改行のデフォルト処理を個別に選択することができる。
  • 文法記述は、各スキャナー状態の %line_comment および %block_comment 宣言による言語コメントの定義に対応しています。
  • このクレートは、文法解析、変換、解析ツリー可視化のためのツールを提供し、文法の実装をサポートします。
  • パーサ・ジェネレータは，文法記述に含まれる直接・間接の左再帰を検出します．
  • parol のパーサは parol 自身によって生成されます。
  • parol を使用する独自の crate を作成するには、parol new を使用します。

なぜ parol を使う必要があるのでしょうか？

  • parol はシンプルです。構文解析の理論的な知識がなくても、すべての部分を理解することができます。
  • parolは速いです。決定論的オートマトンを使うので、パース中のオーバーヘッドが少なく、バックトラックも不要です。
  • parolは真のLL(k)パーサーです。LL(k)パーサーはあまり見かけません。
  • parolは美しいコードを生成し、読みやすく、デバッグを容易にします。
  • parol は若いです。特にAPIの安定性で問題になることがありますが、これからが本番です。
  • parolは活発に開発されています。そのため、必要に応じて新しい機能が追加される可能性があります。

以下私の感想です。

  • （バックトラックのない）本物のLL(k)パーサを生成できるだけでも嬉しいのに、再帰下降型でないのでスタックオバーフローの心配もいらなさそう
  • まだ若いのにドキュメントがしっかり整備されていて、全体の文字量は少ないまま実用に必要なほとんどの知識が理解できるものになっている
  • めちゃくちゃアクティブかつコンスタントに開発されている（issueでの改善要望の解決も迅速）
  • コードベースが小さいかつリーダブルなので、もし自分がメンテナになったとしても問題なさそう
  • ベストプラクティスが既に洗練されていて、しかもparol newコマンドだけで開発環境が整う
  • パーサを生成する前に自動的に、文法に不正がないかのチェックやkが意図したものより大きくないかのチェックをしてくれるのが心強すぎる
  • パーサの生成中や実際のパース中に何が起こるかの理解がすぐできた
  • BNFを知ってる人なら誰でも簡単に理解できるような形式で文法を定義できる
  • 文法定義と意味論の記述が分離されていて美しい（文法定義の中にコードが含まれたりしない）
  • （lexerについて）自動でwhitespaceや改行などを処理しつつ、特定の場面（文字列リテラルやコメントなど）のみ手動で処理するという機能が当たり前のようについていて感動した
  • すでにlanguage serverが提供されていて、文法定義がシンタックスハイライトできる

初見時はlexerとparserを別にできないことに不満を感じましたが、その不満がどうでも良くなるくらいに全てが良いと感じました。
それ以外にも細かい不満がいろいろとあったのですが、全部プルリクを出して解決しました。

LL(k)やLR(1)やPEGなどについて

LLやLRとかPEGとかどれを使えばいいかわからないという質問がありました。以下わたしの回答です。

1000文字分くらい語りたい欲を抑えて、短くまとめてみます。
まずはLL(k)もしくはLR(1)の文法を考えるのが良いです。
LLかLRかはほとんど好みの問題です。LRの方が扱える言語の集合はでかいのですが一番良い効率のアルゴリズムを使ってたとしても空間計算量がそれなりに大きいです。LL(k)はLR(1)に比べて理論上は扱える言語が少ないですが、実用的なプログラミングを作る分にはLL(k)で十分なことが多いです。
それ以外にも構文エラーのでる場所が変わってきたりとか色々な違いがありますが、その辺りは頑張ればどうにでもなります。
もし、LL(k)やLR(1)の文法では表現できない言語だと分かれば、いよいよCFGやPEGの出番になります。CFGとPEGは多くの側面で全然違うものですが、好みで決めたとしてもあからさまに困ることはないと思います。

上で「LR(1)文法が扱える言語集合はLL(k)文法の扱える言語集合のスーパーセット」みたいなことを言ってますが、これはいくつかの事実から直感的に推論しただけなので、真なのか自信なくなってきました。正しく推論するのって難しい……

おわり

使ってみるとさらに良さがわかると思うので、ぜひ皆さんも試してみてください。

脚注

  1. 小さいファイルしか実用的に使われないケースではこれは無視してもよさそう ↩︎

  2. 実用上問題ない場合が多いが…… ↩︎

  3. LL(1)は手書きでも簡単に書けますが、コードと文法の二重管理が発生することやコードが正しく書かれているかの保証が大変といった問題があるため、適切な生成ツールが存在するのであれば使うに越したことはないと思います ↩︎

  4. いくらでも複雑な文法を作ることができることは変わりません ↩︎

  5. 例：デフォルトでは（全く実用的でない）LR(1)を出力するらしいが、LALRに切り替える方法がチュートリアルには載っていない ↩︎

  6. 成熟すればparolとともに二大勢力になりそう ↩︎

Discussion