Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

構文解析ライブラリ。パーサコンビネータをベースとしたアプローチで、OneOfOptionalGroupといったクラスを組み合わせて構文解析ルールを作成する仕組み。プログラミング言語の文法設計で面倒な「ネストしたコメント」の定義が非常に簡単。言語クラスの指定などは非常に容易であるが、左再帰文法をそのままでは扱えないので工夫が必要になる。
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にあるようだ。


  1. expr ::= expr "+" term みたいなルールをもつ文法。左再帰を持たない文法に書き換えることは理論的には可能だがCoqのような巨大な文法ではやりたくないし人為的なミスが入るのもいや。 

shinsa82
日本IBM 東京基礎研究所 リサーチ・スタッフ・メンバー。形式検証、ロジック、定理証明とかソフトウェア工学が専門です。ブロックチェーンの研究をやったり AI フレームワークの設計・実装を手伝ったり、まあ社会人なので色々しています。 ※執筆した記事の内容は私個人の見解です。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away