目次


魅力的なPython: Sparkモジュールを使った構文解析

この有用なツールを理解する

Comments

本稿は、「魅力的なPython」でSimpleParseを紹介した以前の記事の続編で、構文解析のいくつかの基本的な考え方を紹介するとともに、Sparkモジュールについて説明したいと思います。構文解析フレームワークは、全体像を把握するのにかなりの研究を要する豊かなテーマです。この2本の記事は、読者にとっても私自身にとっても、手頃な出発点となるものです。

私のプログラミング人生において、テキスト文書中に存在する部品や構造を識別したいことが、しばしばありました。ログ・ファイル、構成ファイル、区切り形式のデータ (delimited data)、あるいはもっと自由な形式の(といっても、ある程度の構造を備えた)レポート・フォーマットといった文書です。これらの文書は、その中で許される独自の「小言語(little language)」を備えています。私の場合、こうした内輪の構文解析作業をプログラミングするときは、手製のステート・マシンや正規表現、前後関係に基づく (context-driven) 文字列のテストを寄せ集めたような方法を使用するのを常としてきました。これらのプログラムは、おおざっぱに言えば、いつでも「テキストを少し読み込んでは、何か得られるかどうかを判定し、さらにテキストを読み込み、同じことを繰り返す」というパターンでした。

パーサーは、文書内の部品や構造の記述から、文書の構成を識別するための簡潔・明瞭な宣言 規則を抽出します。形式的パーサー (formal parsers) は、たいてい、言語が記述する「文法」の記述に、拡張バッカス・ナウア記法 (Extended Backus-Naur Form:EBNF) の一種を使用します。基本的に、EBNF文法では、文書中に検出された部品 に名前が付けられます。また、しばしば、小さな部品を組み合わせて大きな部品が構成されます。小さな部品が大きな部品に出現する頻度と順番は、演算子で指定されます。例として、リスト1に、SimpleParseの記事で紹介したEBNF文法typographify.defを示します (記法は、他のツールと少し異なります)。

リスト1. 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   := [!@#$%^&()+=|\{}:;<>,.?/"]

Spark入門

Sparkパーサーには、各種のEBNF文法と共通する面もありますが、構文解析 / 処理のプロセスを、従来のEBNF文法で許されているものよりも小さなコンポーネントに分解するという点が特徴です。Sparkの長所は、解析の各段階で操作 (operations) を細かく制御できるとともに、カスタム・コードをプロセスの中に挿入できる点にあります。SimpleParseの記事を読まれた方は、われわれのプロセスが、おおざっぱにいって、1) 文法 (およびソース文書) から全体のタグリストを生成し、2) そのタグリストを、カスタム・プログラムで指定したアクションに対するデータとして使用する、というものであったことを思い出されることと思います。

標準的なEBNFベースのツールと比べたときの Sparkの欠点は、冗長であり、直接的な出現数量子(quantifier、すなわち、存在していること(1つ以上)を示す "+"、あるかもしれない(0個以上)という"*"、0個か一つかを示す"?") を欠いているということです。限量子は、Sparkのトークナイザーの正規表現の中では使用でき、構文解析の式の文法では再帰によってシミュレートすることができますが、Sparkの文法表現で数量指定を行うことができれば、よかったと思います。言及に値するもう1つの欠点は、SimpleParseが基礎部分に使用しているCベースのmxTextToolsエンジンに比較して、Sparkの速度が遅くなっているという点です。

Sparkの作者John Aycockは、Compiling Little Languages in Python (参考文献参照) の中で、コンパイラーを4つのステージに分けています。この記事で紹介する例では、その中の最初の2つ半のステージしか使用しません。紙面での制約があるということと、前回紹介した比較的単純な「テキスト・マークアップ」と同じ問題に焦点を絞りたいからです。Sparkは、私が取り上げている「構文解析と処理」に使用できるだけでなく、全サイクルのコード・コンパイラ / インタプリター用としても使用することができます。以下が、Aycockのいう4つのステージです (要約した形で示します)。

  • スキャン、すなわち字句解析 (lexical analysis)。入力ストリームをトークンのリストに分解します。
  • 構文解析 (parsing、syntax analysis)。文法に照らして、トークンのリストが有効な構文となっているかどうかを確認します。
  • 意味解析 (semantic analysis)。抽象構文木 (abstract syntax tree: AST) を1回以上走査 (traverse) して、情報を収集し、入力プログラムが意味をなす かどうかをチェックします。
  • コード生成 (code generation)。このフェーズでは、もう一度ASTを走査し、直接プログラムをインタープリットするか、Cまたはアセンブリーのコードを出力します。

Sparkは、ステージごとに、それぞれの手順を実行するための1個以上の抽象クラスと、これらのクラスを特殊化させる(specialize) ための、かなり特殊なプロトコルを用意しています。ほとんどの継承のパターンのように、単に固有のメソッドを再定義したり追加する代わりに、Sparkの具体的なクラスは、2つの特徴を備えています(これは、各ステージおよびいろいろな親に共通する一般的なパターンです)。まず、具体的なクラスで行われる作業の多くは、メソッドのdocstringsに指定されるという点です。2つ目の特殊なプロトコルは、パターンを記述するメソッドの各集合には、それぞれの役割を示す別々の名前が与えられるというものです。一方、親クラスには、起動すべきインスタンスの機能を探すための内省的(introspective) メソッドが用意されています。これは、例を眺めていくと、わかってくることと思います。

テキスト・マークアップの認識

ここで示す例は、私がすでに他のいろいろな方法で解決してきた問題です。私は、smart ASCIIと呼んでいるフォーマットを、いろいろな目的で使用しています。このフォーマットは、電子メールやニュースグループの通信用として開発された取り決め (conventions) と多くの点で似ています。私は、このフォーマットを、目的に合わせてHTMLやXMLやLaTeXなどの他のフォーマットに自動的に変換して使用します。以下で行うのも、そういうことです。私の意図していることをざっと知ってもらうために、以下に短いサンプルを示しておきます。後で、これを使用します。

リスト2. Smart ASCIIのサンプル・テキスト (p.txt)
Text with *bold*, and -itals phrase-, and [module]--this
should be a good 'practice run'.

このフォーマットには、サンプルに示したもの以外にも、もう少し取り決めがありますが、それほどたくさんあるわけではありません (マークアップと句読点 (punctuation) の間には、微妙な関係がいくつか存在 しますが)。

トークンの生成

このSparkによるsmart ASCIIパーサーが、まず最初に行うべきことは、入力テキストを適当な部品に分解することです。このトークン化のレベルでは、まだ、トークンがどのように構成されているのかには関心がなく、どんなトークンが使われているのかに関心があります。後で、トークンのシーケンスを組み合わせて構文解析木にします。

上のtypographify.defに示した文法は、Sparkの字句解析器 (lexer) / スキャナーを設計する際の手引きになっています。注意すべきことは、スキャナー・ステージでは、「基本要素」である名前しか使用できないという点です。すなわち、他の登録されているパターンを含む複合パターンは、構文解析ステージまで処理が持ち越されるということです。それ以外は、昔の文法をコピーしてくることができます。

リスト3. 縮約版Sparkスクリプトwordscanner.py
class WordScanner(GenericScanner):
"Tokenize words, punctuation and markup"
def tokenize(self, input):
self.rv = []
GenericScanner.tokenize(self, input)
return self.rv
def t_whitespace(self, s):
r" [ \t\r\n]+ "
self.rv.append(Token('whitespace', ' '))
def t_alphanums(self, s):
r" [a-zA-Z0-9]+ "
print "{word}",
self.rv.append(Token('alphanums', s))
def t_safepunct(self, s): ...
def t_bracket(self, s): ...
def t_asterisk(self, s): ...
def t_underscore(self, s): ...
def t_apostrophe(self, s): ...
def t_dash(self, s): ...
class WordPlusScanner(WordScanner):
"Enhance word/markup tokenization"
def t_contraction(self, s):
r" (?<=[a-zA-Z])'(am|clock|d|ll|m|re|s|t|ve) "
self.rv.append(Token('contraction', s))
def t_mdash(self, s):
r' -- '
self.rv.append(Token('mdash', s))
def t_wordpunct(self, s): ...

ここでは、面白い技 (trick) が使われています。WordScannerは、それ自身で完璧な仕事をしてくれるスキャナー・クラスですが、Sparkのスキャナー・クラスは、継承によって、さらに特殊化させることができます。子の正規表現パターンは親よりも先にマッチされ、子のメソッド/ 正規表現 (regexes) は、必要なら、親をオーバーライドすることもできます。したがって、WordPlusScannerで設定された特殊化は、WordScannerでの設定より前に照合されます(場合によっては、その際に、何バイトかが先に横取りされることもあります)。パターンdocstringsには、任意の正規表現を指定することができます(たとえば、メソッド.t_contraction() は、パターンに「前方参照位置指定子(lookbehind assertion)」を含んでいます)。

残念ながら、スキャナーの継承ロジックは、Python 2.2によって少し損なわれています。Python 2.2では、定義されたパターンは、継承チェーンの中のどこで定義されているかにかかわらず、すべて、アルファベット順 (名前順) でマッチされます。この問題を解決するには、Sparkの関数_namelist() の中の1行を変更してやります。

リスト4. spark.pyの反射関数 (reflective function) の修正版
def _namelist(instance):
namelist, namedict, classlist = [], {}, [instance.__class__]
for c in classlist:
for b in c.__bases__:
classlist.append(b)
# for name in dir(c):   # dir() behavior changed in 2.2
for name in c.__dict__.keys():  # <-- USE THIS
if not namedict.has_key(name):
namelist.append(name)
namedict[name] = 1
return namelist

私が、この問題のことをSparkの作者John Aycockに伝えたところ、将来のバージョンで修正するとのことでした。それまでは、みなさん自身で、コードを変更してください。

今度は、上で示したサンプルsmart ASCIIに対してWordPlusScannerがどんな働きをするのかを見ていくことにします。作成されるリストは、実際は、Tokenインスタンスのリストなのですが、.__repr__ メソッドが含まれており、以下のようにインスタンスをきれいに表示するようになっています。

リスト5. WordPlusScannerによるsmart ASCIIのトークン化
>>> from wordscanner import WordPlusScanner
>>> tokens = WordPlusScanner().tokenize(open('p.txt').read())
>>> filter(lambda s: s<>'whitespace', tokens)
[Text, with, *, bold, *, ,, and, -, itals, phrase, -, ,, and, [,
module, ], --, this, should, be, a, good, ', practice, run, ', .]

.t_alphanums() のようなメソッドは、プレフィックスをt_とすることで、Sparkの内部検索 (introspection) で認識されるわけですが、通常のメソッドでもあることを付記しておきたいと思います。メソッドに追加されたコードは、対応するトークンが検出されるつど、実行されることになります。メソッド.t_alphanums() には、そのごく簡単な例として、print 文を入れてあります。

抽象構文木の生成

トークンの検出にも、面白いところはありますが、肝心の仕事は、トークンのリストに文法を適用する部分です。構文解析ステージでは、トークンのリストを基に、任意の木構造を作成します。これは、式の文法を指定することに他なりません。

Sparkには、AST(抽象構文木)を作成する方法がいろいろと用意されています。「手作業」で行う場合は、GenericParser クラスを特殊化します。この場合、具体的な子パーサーに、p_foobar(self, args) という形式の名前を備えたメソッドを数多く用意する必要があります。これらのメソッドのdocstringには、名前に対する1個以上のパターンの割り付けを含みます。それぞれのメソッドには、任意のコードを指定することができます。文法の式がマッチするたびに、そのコードが実行されます。

Sparkには、ASTを「自動的に」生成するための方法も用意されています。このスタイルは、GenericASTBuilder クラスから継承されます。文法の式は、すべて、1個のトップ・レベルのメソッドにリストされ、.terminal() メソッドおよび.nonterminal() メソッドを特殊化することで、生成時に部分木を操作する (あるいは、必要に応じて、それとは別の任意のアクションを実行する) ことができます。得られるのは、やはりASTですが、親クラスがほとんどの仕事をやってくれます。今回の例の文法クラスは、以下のようなものとなります。

リスト6. 縮約版Sparkスクリプトmarkupbuilder.py
class MarkupBuilder(GenericASTBuilder):
"Write out HTML markup based on matched markup"
def p_para(self, args):
'''
para   ::= plain
para   ::= markup
para   ::= para plain
para   ::= para emph
para   ::= para strong
para   ::= para module
para   ::= para code
para   ::= para title
plain  ::= whitespace
plain  ::= alphanums
plain  ::= contraction
plain  ::= safepunct
plain  ::= mdash
plain  ::= wordpunct
plain  ::= plain plain
emph   ::= dash plain dash
strong ::= asterisk plain asterisk
module ::= bracket plain bracket
code   ::= apostrophe plain apostrophe
title  ::= underscore plain underscore
'''
def nonterminal(self, type_, args):
#  Flatten AST a bit by not making nodes if only one child.
if len(args)==1:  return args[0]
if type_=='para': return nonterminal(self, type_, args)
if type_=='plain':
args[0].attr = foldtree(args[0])+foldtree(args[1])
args[0].type = type_
return nonterminal(self, type_, args[:1])
phrase_node = AST(type_)
phrase_node.attr = foldtree(args[1])
return phrase_node

この.p_para() には、docstringに文法規則の集合のみを含めるようにします (コードは含めません)。私は、.nonterminal() メソッドを特殊化して、ASTを少し平らなものにすることにしました。部分木plainのファミリーからなるplainノードは、部分木群を1個の長い文字列に圧縮しています。同様に、マークアップの部分木(すなわち、emph、strong、module、code、title) は、適当な型の1個のノードに折り畳み、1個の複合文字列で構成するようにします。

Sparkの文法に欠落しているものがあることについては、すでに触れたとおりです。数量子がないのでした。以下のような規則を設けることで、

plain ::= plain plain

plain型の対 (つい)の部分木の集合にすることができます。ただ、以下のような、もっとEBNFスタイルに沿った文法式がSparkで許されればよいのにと思います。

plain ::= plain+

そうすれば、もっと簡単に、いくらでも多くのplain を含むn個の部分木群 (n-arysubtrees) を生成できるのではないかと思います。その場合、木は、.nonterminal() で操作しなくても、もっとずっと平坦なものとして生成されるようになるでしょう。

木の操作

Sparkモジュールは、ASTを扱うためのクラスをいろいろと用意しています。これらのクラスは、私の用途からすれば、必要以上に重い機能になっています。必要なら、スキャナーと構文解析のところで紹介したのと同様の継承プロトコルを用いて木をわたる方法が、GenericASTTraversalおよびGenericASTMatcherとして用意されています。

ただ、再帰的な関数を使って木をわたる方法も、そんなに難しい話ではありません。記事のアーカイブ・ファイルprettyprint.py (参考文献参照) に、そのような例をいくつか示したおきました。その1つの例がshowtree() です。この関数は、以下のような約束ごとにしたがって、ASTを表示するというものです。

  • 各行が、降下の深さを示す
  • 子だけからなるノード (中身のないもの) には、先頭に何個かのダッシュが付く
  • ノードの型は、二重山形カッコで囲む

上の例で生成されたASTを見てみることにします。

リスト7. WordPlusScannerによるsmart ASCIIのトークン化
>>> from wordscanner import tokensFromFname
>>> from markupbuilder import treeFromTokens
>>> from prettyprint import showtree
>>> showtree(treeFromTokens(tokensFromFname('p.txt')))
0  <<para>>
1 - <<para>>
2 -- <<para>>
3 --- <<para>>
4 ---- <<para>>
5 ----- <<para>>
6 ------ <<para>>
7 ------- <<para>>
8 -------- <<plain>>
9           <<plain>>  Text with
8          <<strong>> bold
7 ------- <<plain>>
8          <<plain>> , and
6        <<emph>> itals phrase
5 ----- <<plain>>
6        <<plain>> , and
4      <<module>> module
3 --- <<plain>>
4      <<plain>> --this should be a good
2    <<code>> practice run
1 - <<plain>>
2    <<plain>> .

木の構造がわかると理解しやすくなりますが、われわれが目的としている修正マークアップについては、どうなのでしょうか。幸い、数行の記述で、木を走査し、生成することができます。

リスト8. ASTからのマークアップの出力 (prettyprint.py)
def emitHTML(node):
from typo_html import codes
if hasattr(node, 'attr'):
beg, end = codes[node.type]
sys.stdout.write(beg+node.attr+end)
else: map(emitHTML, node._kids)

typo_html.pyは、SimpleParseの回のときと同じファイルです。これは、begintag/endtagの対 (つい) に名前を対応付けるための辞書を記述しているだけのファイルです。もちろん、HTML以外のマークアップにも同じ方法が利用できます。関心のある方のために、今回の例に対するtypo_html.pyの生成結果を以下に示しておきます。

リスト9. プロセス全体のHTML出力
Text with <strong>bold</strong>, and <em>itals phrase</em>,
and <em><code>module</code></em>--this should be a good
<code>practice run</code>.

まとめ

かなりの数のPythonプログラマーが、私にSparkを薦めてきました。Sparkが採用している特殊な約束ごとは、慣れるまでに少し時間がかかりますし、ドキュメントも、もう少し明快な書き方ができるのではないかと思われる箇所がいくつかあるのですが、Sparkのパワーは、本当にものすごいものです。Sparkが実現しているプログラミングのスタイルに従うことで、エンド・プログラマーは、スキャン / 構文解析のプロセス (通常、エンド・ユーザーには「ブラック・ボックス」として示される部分) の随所にコード・ブロックを挿入することができます。

いろいろな長所を備えているSparkですが、欠点は、その速度にあると思います。Sparkは、私が経験した中で、インタプリター言語の速度的な弱点が大きな問題となった初めてのPythonプログラムです。Sparkが遅い のは確かなのですが、それも、あと1秒速ければよいのにという遅さではなく、長い昼飯から帰ってきたときに終わっていてほしいという遅さです。私の経験では、トークナイザーは非常に速く、構文解析は、かなり小さなテスト・ケースでも難渋します。公平を期して記しておくと、John Aycockが私に語ったところによれば、Sparkが採用しているEarleyという構文解析アルゴリズムは、単純なLRアルゴリズムよりも、はるかに一般的であり、遅いのは、大部分がそのためである、とのことでした。私の経験上、私が効率の悪い文法を設計している可能性もありますが、もしそうなら、ほとんどのユーザーが同じような経験をすることになるのではないでしょうか。


ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=231401
ArticleTitle=魅力的なPython: Sparkモジュールを使った構文解析
publish-date=08012002