Comparison of Rust Parser generators

Rustでパーサージェネレーターを探していたときに、
その特徴や、今回の最終目的に必要な機能が備わってかどうかで主観的に比較をした時のメモ

構文解析の方式
Indentation(Pythonのようなインデントセンシティブな文法をパースできそうか)
曖昧な文法が可能か
その他気になる点

結論

〇 = OK
× = NG

パーサー	lalrpop	ANTLR(antlr-rust)	pest
Left recursion	〇	〇	×
Indentation	〇	×	〇
曖昧な文法	×	〇	〇

2021-02-02時点

以下お気持ち

lalrpop

GitHub - lalrpop/lalrpop: LR(1) parser generator for Rust

Rustのパーサージェネレーターを調べるとすぐに出てくる有名そうなパーサー。

構文解析の方式

LR(1)かLALR(1)というものらしい。
将来的には他の方式にも対応していくとある。

Despite its name, LALRPOP in fact uses LR(1) by default (though you can opt for LALR(1)), and really I hope to eventually move to something general that can handle all CFGs (like GLL, GLR, LL(*), etc).

構文解析とかそういう分野にはあまり詳しくないが、wikipediaによると

多くのプログラミング言語がLR法（およびそれを一部改変したもの）で構文解析できる。例外として、C++とPerlがある。

なので多くの場合はlalrpopでも事足りるのではないかと思う。
簡単に試用した感じだと文法ファイル中に自分の定義するASTの生成まで書けるので便利かもしれない。
(他のパーサーは内部のコンテキストからASTへ変換する必要があることが多そう)

e-tipsmemo.hatenablog.com

Left recursionの問題が無い(?)ことで簡単に書ける文法もある。

Indentation

インデントでブロックを区切ったりするような言語は簡単に設計しやすい？からよくありがちなのかもしれない。(設定ファイルとか?)
RustPython/python.lalrpop at master · RustPython/RustPython · GitHub

RustPythonはこれを使っているらしいのでインデントセンシティブな文法もパースすることが可能だと思われる。(試してはいない)

曖昧な文法が可能か

https://github.com/lalrpop/lalrpop/issues/193
たとえばこのような文法があったとして、

UnsignedInt: '0' | PosInt;
SignedInt: ( '+' | '-') PosInt;
fragment PosInt: [1-9] ( Digit)*
fragment Digit: [0-9];

先駆者によると、これが許されない/なんとかするのはめんどくさいらしい。

その他

build.rsにごちゃごちゃ書かなくても事前に用意されたcrateとセットで使うことで勝手にパーサーが生成される。
https://crates.io/crates/lalrpop
https://crates.io/crates/lalrpop-util

文法が少し複雑感ある。(その分短くかけるのかもしれない)

ANTLR

https://ja.wikipedia.org/wiki/ANTLR
ANTLR4の文法ファイルが存在していれば、それを利用できれば簡単だと考えた。
ANTLRは様々な言語に対してパーサーを生成することができる。
GitHub - antlr/antlr4: ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.
公式の対応している言語は
Java, C#, Python (2 and 3), JavaScript, Go, C++, Swift, PHP, Dartらしく
Rustが無いが、作っている人がいた
GitHub - rrevenantt/antlr4rust: ANTLR4 parser generator runtime for Rust programming laguage
これでひとまず適当なANTLR4 CalculatorのサンプルなどからASTを作ることはできた。

構文解析の方式

LL(*)というものらしい
https://www.antlr.org/papers/LL-star-PLDI11.pdf
しかしながら、Left recursion問題を回避しているらしい。
antlr4/left-recursion.md at master · antlr/antlr4 · GitHub

とある言語の文法ファイルには以下のようなものもあるので可能ということはわかる。

exp:
|id         //Ref
|exp "." id //Sub-field
|.....;

Indentation

インデントをハンドリングする機能はANTLR4にそもそも備わっているわけではなく、
ANTLRの文法ファイル内でINDENT/DEDENTトークンを定義し、一部ANTLR4の動作をoverwriteすることで、可能となるよう。
GitHub - yshavit/antlr-denter: Helper class for generating python-like INDENT/DEDENT tokens with antlr4.

Indentation Helperで具体的に何をしているのかというのは完全に理解していないので
Parsing indentation-based languages in Rust? : rust
によると。

Generally for indent based languages the first step is to run a tokeniser to pull out the tokens and convert the indentation into explicit "INDENT" and "DEDENT" tokens. Then you can parse them with a normal parser like lalrpop.
Keep a stack of indent levels. On each line count the indent and compare to top of stack. If the level is greater, push it to the stack and emit "INDENT" token. If it's less, pop from the stack and emit "DEDENT" tokens until you find the matching level. If it's equal, do nothing.
Tools like nom which do tokenise and parse in one go (ie. they parse characters/bytes not tokens) will be difficult to get working.

これをantlr-rustで可能かどうかを考えたが、簡単に試したところ、
antlr-rustが生成する関数をoverwriteすることが(今のところ)出来ないのではないかという気持ちになった。

(ANTLR4のg4ファイル中に @lexer::members を書くが、その中の Rustの文法がANTLR4の文法エラーになる(?え?)、
@lexer::membersの関数を呼んでくれない。など)

曖昧な文法が可能か

可能

その他

build.rsのおかげで「文法ファイルが更新されたら、再コンパイルする」といったことも簡単にできる。
VscodeにSyntax Highlightもformatterもあり便利。
ANTLR自体が様々な多くの言語をターゲットにできるので利用者は多く情報も多いと思う。

ASTを生成する方法として、ListenerパターンとVisitorパターンの2つの書き方がある。
Listenerパターンでは、パース操作が行われている最中、構文のノードから出るときにexit_[token名]という関数が呼ばれるようになっているらしく、
その時、子ノードのASTをスタックからpopして、そのノードのASTを作って、スタックにpushすることでASTを構築できる(末端の場合はただ単にpushする)。
Visitorパターンではパース操作が行われ、完了するとTreeができるので、それを辿ることでASTに変換する。
という理解。