 | レベル: 初級 David Mertz (mertz@gnosis.cx), Analyzer, Gnosis Software, Inc.
2002年 1月 01日 Python用に数多くの構文解析ツールが作成されています。このコラムでは、Python上に構築された高水準の構文解析言語について解説します。SimpleParseは、文法を非常に分かりやすい形で表現できるEBNF形式の構文規則をmxTextToolsに付加します。
ほとんどのプログラマーがそうだと思いますが、ログ・ファイルやコンフィギュレーション・ファイル、(タブやカンマによる) 区切り形式のデータ、あるいはもっと自由な形式の (といっても、ある程度の構造を備えた) レポート・フォーマットなどのテキスト文書に含まれる部品や構造を判定したいことがよくあります。これらの文書はいずれも、それ自体に独自の「小言語 (little language) 」を備えています。
筆者の場合、こうした内輪の構文解析作業をプログラミングするときは、手製のステート・マシンや正規表現、前後関係に基づく文字列のテストを寄せ集めたような方法を使用するのを常としてきました。このようなプログラムのパターンは、おおざっぱに言えば、テキストを少し読み込んでは、何かを取り出せるかを判定し、さらにテキストを読み込み、同じことを繰り返すというものでした。
多様な形式を扱うパーサーは、文書内の部品や構造の記述から、文書の構成を判定するための簡潔・明瞭な宣言規則を抽出します。ここでとくに興味深い点は、宣言的である (declarative) という点です。筆者がこれまで特定のケース毎に個別に作成してきたパーサーは、いずれも命令型 (imperative) でした。何文字か読み込んでは、ある程度の判断を下し、いくつか変数を蓄積し、不要なものを除去し、これを繰り返すというものでした。このコラムで関数型プログラミングを取り上げた際にご説明したように、プログラムで処理手順を記述するスタイルのものは、比較的エラーを起こしやすく、保守が難しいものとなります。
正式なパーサーは、たいてい言語の「文法」の記述に、拡張バッカス・ナウア記法 (Extended Backus-Naur Form: EBNF) の一種を使用しています。このコラムで紹介するツールも、一般に使用されているコンパイラー開発ツールYACC (および、その亜種) と同様、EBNFを使用します。基本的に、EBNF文法では、文書中に検出された部品 (parts)に名前が付けられます。また、しばしば、小さな部品を組み合わせて大きな部品が構成されます。小さな部品が大きな部品に出現する頻度と順番は、演算子で指定されます。たいていは、正規表現に使われるものと同じ記号が使われます。パーサーの用語では、文法で名前が与えられる部品のことを「生成規則 (production) 」といいます。
おそらく読者も、このことだとは知らなかったとしても、EBNFの記述が実際に使われているのを見たことがあるのではないでしょうか。たとえば、おなじみのPython言語リファレンスでも、Pythonにおける浮動小数点数を以下のように定義しています。
浮動小数点数のEBNFスタイルの記述
floatnumber: pointfloat | exponentfloat
pointfloat: [intpart] fraction | intpart "."
exponentfloat: (nonzerodigit digit* | pointfloat) exponent
intpart: nonzerodigit digit* | "0"
fraction: "." digit+
exponent: ("e"|"E") ["+"|"-"] digit+ |
あるいは、XMLのDTD要素がEBNFスタイルで定義されているのを見かけたこともあるのではないでしょうか。たとえば、developerWorksのチュートリアルの<body> は、以下のように定義されています。
developerWorksのDTDに使用されているEBNFスタイルの記述
<!ELEMENT body ((example-column | image-column)?, text-column) > |
記法は、少しずつ違いますが、量化 (quantification) 、選言 (alternation) 、順序付け (sequencing) といった一般的な概念は、EBNFスタイルのすべての文法に存在します。
SimpleParseによるタグ・リストの作成
SimpleParse は、おもしろいツールです。このモジュールを使うためには、その前提ジュールとして、Cで「タグ付けエンジン (tagging engine) 」を実現しているmxTextTools が必要です。mxTextTools (後で説明する参考文献を参照) は、強力なツールではあるのですが、少し使い難い面があります。SimpleParse をmxTextTools の上にレイヤーとしてかぶせてやると、作業が非常に簡単になります。
SimpleParse の使い方は、いたって簡単です。それは、mxTextTools の複雑な部分をほとんど考慮する必要がなくなるからです。最初にやるべきことは、処理したい言語を記述するEBNFスタイルの文法を作成することです。次に、mxTextTools を呼び出して、この文法を文書に適用したときに得られるすべての生成規則を列挙したタグ・リストを作成します。最後に、mxTextTools から返されたタグ・リストを利用して仕上げをします。
この記事でわれわれが構文解析の対象とする「言語」は、「smart ASCII」を使ってボールド体とか、モジュール名とか、書名などを指定している、マークアップ・コードの集合です。これは、まさしく、それまでmxTextTools を使って判定していた言語であり、さらにそれ以前の初期の記事では、正規表現やステート・マシンを使って判定していた言語です。この言語は、通常のプログラミング言語よりも、はるかに単純ですが、例題にできる程度の複雑さは備えています。
ここで、少し補足しておく必要があるでしょう。mxTextTools で得られる「タグ・リスト」というのは、どんなものなのかということです。これは、基本的には、ソース・テキストの生成規則が検出された箇所に、その文字オフセットを示していくという入れ子型構造 (nested structure) です。mxTextTools は、ソース・テキストをすばやく走査しますが、ソース・テキストそのものには何も手を加えません (少なくともSimpleParse の文法を使っているかぎり) 。以下が、縮約されたタグ・リストの例です。
SimpleParseの文法から生成されたタグ・リスト
(1,
[('plain',
0,
15,
[('word', 0, 4, [('alphanums', 0, 4, [])]),
('whitespace', 4, 5, []),
('word', 5, 10, [('alphanums', 5, 10, [])]),
('whitespace', 10, 11, []),
('word', 11, 14, [('alphanums', 11, 14, [])]),
('whitespace', 14, 15, [])]),
('markup',
15,
27,
...
289) |
途中の省略した部分 (...) は、さらにたくさんのマッチがあることを示しています。ここに示した部分からは、以下のことがわかります。ルートの生成規則 ("para") に成功し、それがオフセット289 (ソース・テキストの長さ) で終わったということ。子の生成規則 "plain" がオフセット0～15でマッチしたということ。この子の "plain" も、それ自身、さらに小さな生成規則で構成されています。生成規則 "plain" の次に、生成規則 "markup" がオフセット15～27でマッチしています。詳細は省略してありますが、この1個目の "markup" もいろいろなコンポーネントで構成され、それ以下のソースには、さらに生成規則が続きます。
smart ASCIIを表現するEBNFスタイルの文法
上では、SimpleParse +mxTextTools によって得られるタグ・リストを眺めたわけですが、今度は、このタグ・リストを生成するのに使用された文法に目を向ける必要があります。この文法の部分が、実際の作業が発生する部分です。EBNFの文法は、目を通せば、ほとんど自明だと思います (ただし、文法の設計には少し頭を使ったりテストを行う必要がありますが) 。
typographify.def
para := (plain / markup)+
plain := (word / whitespace / punctuation)+
whitespace := [ ＼t＼r＼n]+
alphanums := [a-zA-Z0-9]+
word := alphanums, (wordpunct, alphanums)*, contraction?
wordpunct := [-_]
contraction := "'", ('am'/'clock'/'d'/'ll'/'m'/'re'/'s'/'t'/'ve')
markup := emph / strong / module / code / title
emph := '-', plain, '-'
strong := '*', plain, '*'
module := '[', plain, ']'
code := "'", plain, "'"
title := '_', plain, '_'
punctuation := (safepunct / mdash)
mdash := '--'
safepunct := [!@#$%^&()+=|＼{}:;<>,.?/"] |
この文法は、「smart ASCII」言語を言葉で記述しようした場合と、ほとんど同じようになります。簡単明瞭です。それぞれの節 (paragraph) は、通常のテキストとマークアップを付したテキストで構成されます。通常の単なるテキストは、単語、空白および句読点からなります。マークアップを付したテキストは、普通の強調や特別な強調が指定されていたり、モジュール名だったりします。特別な強調にするときには、テキストをアスタリスクで囲みます。他も同様です。「単語」の定義とか、短縮形の終わり方など、いくつか考慮すべき問題はありますが、EBNFの構文がソース・テキストを記述する上での妨げになることはありません。
これに対して、正規表現を使えば、同じような規則を、もっと簡潔に記述することができます。smart ASCIIマークアップ・プログラムの最初のバージョンは、そうしていました。しかし、このような簡素な記述を行うのは、はるかに難しい作業であり、それに後で手を加えるのは、さらに難しいことです。以下のコードは、ほぼ (上と) 同じ規則を表現したものです(まったく同じではありませんが) 。
smart ASCIIのマークアップをPythonのregexsで表したもの
# [module] names
re_mods =r"""([＼(＼s'/">]|^)＼[(.*?)＼]([<＼s＼.＼),:;'"?!/-])"""
# *strongly emphasize* words
re_strong =r"""([＼(＼s'/"]|^)＼*(.*?)＼*([＼s＼.＼),:;'"?!/-])"""
# -emphasize- words
re_emph =r"""([＼(＼s'/"]|^)-(.*?)-([＼s＼.＼),:;'"?!/])"""
# _Book Title_ citations
re_title =r"""([＼(＼s'/"]|^)_(.*?)_([＼s＼.＼),:;'"?!/-])"""
# 'Function()' names
re_funcs =r"""([＼(＼s/"]|^)'(.*?)'([＼s＼.＼),:;"?!/-])"""
|
既存の言語に、幾分新しい要素が加わった変形を発見したり考案した場合には、こうした正規表現を扱うよりもEBNF文法を扱うほうが、ずっと簡単です。それにmxTextToolsは通常、パターン操作を高速に行ってくれるようになっています。
タグ・リストの作成と使い方
このサンプル・プログラムでは、実際の文法を別個のファイルとしました。たいていは、別個のファイルにしたほうが利用しやすいでしょう。通常、文法の変更は、アプリケーションのロジックを変更することとは別個の作業となるからで、ファイル構成もそれを反映しています。一方、文法の取り扱いは、文字列としてSimpleParse 関数に渡すことだけですから、原則として、メイン・アプリケーションに文法を含める形にすればよいでしょう (あるいは、何らかの方法で動的に文法を作成するという方法もありえます) 。
次に、タグ付けアプリケーションを見てみることにしましょう。以下が、その全体です (簡潔なので)。
typographify.py
import os
from sysimport stdin, stdout, stderr
from simpleparseimport generator
from mx.TextToolsimport TextTools
input = stdin.read()
decl = open('typographify.def').read()
from typo_htmlimport codes
parser = generator.buildParser(decl).parserbyname('para')
taglist = TextTools.tag(input, parser)
for tag, beg, end, partsin taglist[1]:
if tag =='plain':
stdout.write(input[beg:end])
elif tag =='markup':
markup = parts[0]
mtag, mbeg, mend = markup[:3]
start, stop = codes.get(mtag, ('<!-- unknown -->','<!-- / -->'))
stdout.write(start + input[mbeg+1:mend-1] + stop)
stderr.write('parsed %s chars of %s＼n' % (taglist[-1], len(input)))
|
処理内容は、以下のとおりです。まず文法を読み込み、文法からmxTextTools用パーサーを作成します。次に、入力ソースをタグ・テーブル (すなわち作成したパーサー) にかけ、タグ・リストを作成します。最後に、タグ・リストをループして処理し、マークアップの付された新しいテキストを出力します。ループでは、もちろん、生成規則を検出するつど、処理したいことを行うことができます。
smart ASCII用の文法の場合、ソース中のテキストは、すべて、"plain" 生成規則か "markup" 生成規則のいずれかに該当することになるでしょう。したがって、タグ・リストを1レベルだけループすれば充分です ("title" など、個々のマークアップの生成規則について1レベル下を調べる場合を除き) 。しかし、たいていのプログラミング言語がそうであるように、もっと自由な形式の文法の場合、タグ・リストを再帰的にレベルを下げていき、すべてのレベルで生成規則の名前を探すといったことも簡単に行うことができます。たとえば、マークアップ・コードの入れ子を許す文法の場合、たぶん、この再帰スタイルを使用することになるでしょう。文法の手直のやり方を考えてみるのも楽しいかもしれません (ヒント: 生成規則同士は、相互に再帰的にすることができることを忘れないでください) 。
出力されるマークアップ・コードは、本質的な理由ではなく、整理の都合上、これもまた別のファイルに格納されます。ここでは、switch 文として辞書を使用するというちょっとした仕掛けを使用しています (ただし、この例では、otherwise のケースは狭すぎますが) 。これは、たとえば、HTMLとかDocBookとかLaTeXなど、将来、いろいろな「出力フォーマット」のファイルを作成することもあるだろうという考えからです。今回の例で使用したマークアップ・ファイルは、以下のようなものです。
typo_html.py
codes = ＼
{'emph' : ('<em>','</em>'),
'strong' : ('<strong>','</strong>'),
'module' : ('<em><code>','</code></em>'),
'code' : ('<code>','</code>'),
'title' : ('<cite>','</cite>'),
} |
これを、他の出力フォーマットに拡張するのは容易です。
結論
SimpleParse は、Cで作成したmxTextTools モジュールが難解ながらも備えているパワーと速度を活かしながら、簡潔で非常に判読しやすいEBNFスタイルのラッパーを提供しています。EBNF文法も、ただ見聞きしただけであるにしろ、すでに多くのプログラマーによく知られています。どんなものが理解しやすいのかについては何も検証することなどできませんが (各人の直観によって異なるので) 、ソースの長さについては計量的に評価を述べることはできます。以前に手作業で作成したmxTypographify モジュールのサイズは、以下のとおりです。
wc mxTypographify.py
199 776 7041 mxTypographify.py |
この199行のうち、かなりの行はコメントです。また、199行の中の18行は、時間の比較を行うために、マークアップ関数を正規表現版として含めたものです。このプログラムの処理内容は、本質的には、上に示したtypographify.py が行っていることとまったく同じです。一方、今回のSimpleParse プログラムは、サポート・ファイルも含めて、以下のサイズとなりました。
wc typo*.def typo*.py
19 79 645 typographify.def
20 79 721 typographify.py
6 25 205 typo_html.py
45 183 1571 total
|
結局、約1/4の行数になったことになります。このバージョンのコメントは、ずっと少なくなっていますが、それは、概して、EBNF文法がそれ自体でかなりの部分説明になっているからです。LOC (コードの行数) について過度に強調するつもりはありませんが、コードの長さをできるだけ小さくするとか、できるだけ大きくするといったことに興ずることもできるでしょう。ただ、一般的なことを言えば、プログラマーの作業研究についての数少ない経験的結果の1つに、プログラマー1人月あたりのkLOCは、言語やライブラリーによらず、一定値にかなり近いものであるということがあります。もちろん、正規表現版は、SimpleParse 版の1/3の長さですが、その表現密度の高さゆえに、保守が破綻しやすく、また記述も困難なものになると思います。総合的に考えるとSimpleParse が最もすぐれた手法だと思います。
参考文献
著者について | 
| | David Mertz氏は、ニーチェの助けを借りて、これらの著作が、ある昔の言語学者の思想なのだと書きたいのですが、その嘘は自ずと化けの皮がはがれることでしょう。ただ、おそらく彼の (まさしくここで只で宣伝してもらえる) 近刊書Text Processing in Pythonは、いつの日にか、言語学のサイバー版 (cybernetic variant of philology) と間違えられることになるのではないでしょうか。彼のメール・アドレスはmertz@gnosis.cx です。彼の研究活動はhttp://gnosis.cx/publish/ に紹介されています。
これまでのコラム、今後のコラムに関するご意見、ご要望がありましたら、ぜひお知らせください。 |
記事の評価
| |
