調査の動機

Coq https://coq.inria.fr/ という定理証明支援系で使われる式のparsingをしたいと思った。

そこでPythonの字句/構文解析ツールについて、いくつかざっと調べてみた。

評価基準

Coqの式の文法はなかなか複雑 (文法定義によると左再帰文法¹であるうえ、先読み (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にあるようだ。