2019-10-06 追記
左再帰は扱えないけど，最近はPEGパーサも結構流行っています．
Pythonだと https://github.com/erikrose/parsimonious とか https://github.com/KuramitsuLab/pegpy があります．
調査の動機
Coq https://coq.inria.fr/ という定理証明支援系で使われる式のparsingをしたいと思った。
そこでPythonの字句/構文解析ツールについて、いくつかざっと調べてみた。
評価基準
Coqの式の文法はなかなか複雑 (文法定義によると左再帰文法1であるうえ、先読み (lookahead) が必要) である。
そこで以下を選択の際のポイントとした。他の文法を扱いたい場合は、当然これとは異なった判断基準となる。
- 左再帰文法を扱いたいか
- 先読みが必要な複雑な文法であるか
- 文法をDSLで記述するか、パーサコンビネータとして定義するか
以下調査結果である。
新しいもの
pyparsing (2.2.0) 2017/03
構文解析ライブラリ。パーサコンビネータをベースとしたアプローチで、OneOfやOptional、Groupといったクラスを組み合わせて構文解析ルールを作成する仕組み。プログラミング言語の文法設計で面倒な「ネストしたコメント」の定義が非常に簡単。言語クラスの指定などは非常に容易であるが、左再帰文法をそのままでは扱えないので工夫が必要になる。
Pyparsingの使い方: http://masato.github.io/2014/07/01/python27-etl-pyparsing-syntactic-analysis/
PLY (Python Lex-Yacc) (3.11) 2018/02
有名なCの字句/構文解析ツールであるLex/YaccのPython版。ということは同じような文法定義構文が使えるものと思われる。解析には基本的にはLALR(1)構文解析が用いられる。
本家: http://www.dabeaz.com/ply/
参考: http://blog.livedoor.jp/shf0811/archives/7346881.html
parse (1.6.6; 2014/11)
String.format()と逆の働きをするパターンマッチングライブラリ。
参考: http://coreblog.org/ats/python-parse/
古いもの/もうないもの
- 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からはなくなったようだ。
まとめると、
- 単純なパターンマッチングで十分ならparse
- 左再帰文法をコーディングしたい/ルールを独立した文書として記述したい、かつ複雑な先読みがいらないならPLY
- ルールをコーディングで定義したいならpyparsing
がよいと思われる。
結局ANTLRの一強か
なお、PLYは1トークンしか先読みしてくれない。複雑な文法を書きたい場合は LL(*) 構文解析を用いる ANTLR (Javaツール) のほぼ一択である。例えば、定理証明支援系であるCoqの文法もANTLRでは難なくparseしてくれる。ANTLRのv4にはPython2/3用のparserを生成する機能が備わっている。また、ANTLRのPythonラッパもPyPIにあるようだ。
-
expr ::= expr "+" termみたいなルールをもつ文法。左再帰を持たない文法に書き換えることは理論的には可能だがCoqのような巨大な文法ではやりたくないし人為的なミスが入るのもいや。 ↩
