Python の (形式言語の) 字句/構文解析ライブラリ (2014.11初調査、2021.02 一部追記)

注意

ここで調べているのは形式言語の解析器です。自然言語のそれではありません。

2019-10-06 追記

左再帰は扱えないけど，最近はPEGパーサも結構流行っています．
Pythonだと https://github.com/erikrose/parsimonious とか https://github.com/KuramitsuLab/pegpy があります．
pyparsing もたぶんPEGパーサと言っていいはず。

調査の動機

Coq (https://coq.inria.fr/) という定理証明支援系で使われる式の構文解析をしたいと思った。
そこで Python の形式言語の字句/構文解析ツールについて、いくつかざっと調べてみた。

評価基準

Coqの式の文法はなかなか複雑 (文法定義によると左再帰文法¹であるうえ、先読み (lookahead) が必要) である。
そこで以下を選択の際のポイントとした。他の文法を扱いたい場合は、これとは異なった判断基準となる。

• 目的は Python のプログラムを構文解析することか
  • もしそうなら標準ライブラリに ast モジュールがあるのでそれを使うとよい。
• 左再帰文法を扱いたいか
• 先読みが必要な複雑な文法であるか
• 文法をDSLで記述するか、パーサコンビネータとして定義するか

構文解析には大まかには2種類のアプローチ、ボトムアップ構文解析とトップダウン構文解析、がある。

• PEGパーサなど、パーサコンビネータに基づくもの、およびLL系パーサはトップダウン構文解析
• LR系パーサはボトムアップ構文解析

以下調査結果である。

新しいもの

Lark (lark-parser 0.11.2) 2021/02

まだ調べてない。Earleyパーサ (CYKパーサ) のようなチャート・パーサによる解析、および LALR(1) 解析の両者が使用できるようだ。曖昧な文法に強いことをウリにしている模様。
本家: https://github.com/lark-parser/lark
参考: https://qiita.com/k5trismegistus/items/358d58bcd50eb3f67fe8 (ご紹介ありがとうございます)

ANTLR v4.9.1 (antlr4-python3-runtime 4.9.1) 2021/01

LL(*) に基づくトップダウン構文解析器。構文解析はパワフルで、左再帰文法も使える。ただし、ANTLR は Python とは独立したツールなので、一度 ANTLR を実行して構文解析を行う Python ソースファイルを生成する必要があり、試行錯誤には不便かもしれない。
本家 (ANTLR 自身の): https://www.antlr.org/
参考: https://qiita.com/osamunmun/items/54a00e963d1a7db0cf59

pyparsing (2.4.7) 2020/04

構文解析ライブラリ。パーサコンビネータをベースとしたトップダウン解析器である。OneOfやOptional、Groupといったクラスを組み合わせて構文解析ルールを作成する仕組み。プログラミング言語の文法設計で面倒な「ネストしたコメント」の定義が非常に簡単。言語クラスの指定や解析結果を利用したプログラミングは非常に容易であるが、左再帰文法をそのままでは扱えないので工夫が必要になる。たぶん先読みもできない。
本家: https://github.com/pyparsing/pyparsing
参考: http://masato.github.io/2014/07/01/python27-etl-pyparsing-syntactic-analysis/

parse (1.19.0) 2021/01

String.format()と逆の働きをするパターンマッチングライブラリ。文字列に {} や {:d} のようなプレースホルダを設けてパターンとする。一般に構文解析というと構文を文脈自由文法で表現できるが、これで表現できる文法は、おそらくそれより弱い、正規表現＋αであると思われる。当然、再帰的な文法なども定義できない。DSL のようなものを処理したいということでなければ、これで十分なケースも多いと思う。
参考: http://coreblog.org/ats/python-parse/

PLY (Python Lex-Yacc) (3.11) 2018/02

有名なCの字句/構文解析ツールであるLex/YaccのPython版。ということは、同じような文法定義構文が使えるものと思われる。解析には基本的には最大1文字の先読みを行う LALR(1) を用いたボトムアップ構文解析が用いられる。LALR を使うので左再帰文法も扱える。
本家: http://www.dabeaz.com/ply/
参考: http://blog.livedoor.jp/shf0811/archives/7346881.html

古いもの/もうないもの

Yapps (2.2.0) 2014/06

Extended LL(1)パーサ。どうやらlookaheadがない模様なので、複雑な言語のparsingには向いていないとのこと。 参考: https://github.com/mk-fg/yapps

jupyLR (0.3) 2012/06

Generalized LRパーサ。幅優先探索により構文が曖昧な場合に複数の構文木を出力できる。これにより、LRパーサで扱えないreduce/reduce衝突なども扱える。 本家: http://bl0b.github.io/jupyLR/

plex

Flexライクな字句解析ツール。2.0.0devで開発が止まっている模様: https://pythonhosted.org/plex/

SimpleParse

2011年から更新なし: http://simpleparse.sourceforge.net/

SPARK

更新状況不明。他のライブラリと名前が紛らわしい: http://pages.cpsc.ucalgary.ca/~aycock/spark/

PyLR

2000年より前にあった有名なライブラリのようだが、今はない。

FlexModule, BisonModule

これらも今はないようだ。これはCのFlexやBisonのラッパーだったようだ。

re.Scanner (ビルトイン)

正規表現による字句解析クラスだったが、Python3.4からはなくなったようだ。

---

まとめ: どれが使いやすいか (2021/02 修正)

まずは文法の複雑さ、特に左再帰が使えるか否かで決めるとよい。パターンマッチングでいい、つまり、文脈自由文法ほどの表現力がいらないなら parse で十分。左再帰がいらないなら pyparsing は使い勝手がよさそうだ。

左再帰文法を使いたいなら ANTLR, Lark, PLY あたりから選ぶことになる。この場合、先読みが1文字でいいなら PLY や Lark の LALR(1) パーサでいいと思うが、すでに lex/yacc 用の構文定義ファイルがある、とかでない限り、わざわざ PLY を使うメリットはそれほどないかも。複雑な文法を書きたい場合は LL(*) 構文解析を用いる ANTLR が最有力。Lark のチャート・パーサがどのくらいパワフルかは調べていないが、別のツールを起動しなくてよいのは便利だろうと思われる。

なお、当初の目的であった、定理証明支援系である Coq の文法も ANTLR では難なく解析してくれた。

(2022/11 追記)
Pure Python な Lark は便利ではあるが、パフォーマンスの点においては ANTLR に劣る面がある。先日、Oracle の SQL 方言である PL/SQL の文法を解析するために Lark を使ってみた。PL/SQL は文法ファイルが1万行のオーダーになる大規模な文法であった。Lark では文法の読み込みが実用的な時間で終了しなかった。それなら生成した parser を書き出しておけばよいかと思ったのだが、生成したのが Earley パーサである場合、その書き出しに対応していないことがわかった。

1. expr ::= expr "+" term みたいなルールをもつ文法。左再帰を持たない文法に書き換えることは理論的には可能である。しかし、書き換えると右再帰文法になってしまうので演算子の結合方法が逆になってしまうという問題がある。また、Coqのような巨大な文法ではやりたくないし人為的なミスが入るのも嫌である。 ↩