人気ブログランキング | 話題のタグを見る

パーサジェネレータ peg.rb の使い方

パーサジェネレータ peg.rb を使って、パーサを記述するときのプログラムの構成は、

require 'peg.rb'

(文法を定義する部分)

(定義したパーサを利用するプログラム本体)

のようになる。

1.文法の定義の仕方

peg.rb を使って文法の定義をする場合は次の例のように、クラス Peg のオブジェクトを作った後、関数を発生させるインスタンスメソッド(関数ジェネレータ)を使ってパース用の関数を定義していく、関数ジェネレータの引数は、parser.mkseq( ’関数名’、’パターン’、[ 'アクション' ] ) のように文字列リテラルを使用する。

記述例

require 'peg.rb'

parser = Peg.new

parser.mkseq('expression', 'term and add_terms')
parser.mkstar('add_terms', 'ad_term')
parser.mkseq('ad_term', 'add and term')

....

関数ジェネレータによる文法の定義は、PEGの文法をそのまま逐語的に定義していくだけである。上の定義は、それぞれ、

expression <- term add_terms
add_terms <- ad_term*
ad_term <- add term

を逐語的に定義に利用しているだけだ。上の文法は普通はPEGでは

expression <- term (add term)*

のように演算子 * を使って一行で済ませるところだが、パーサジェネレータプログラムの制限で3行に分解して定義しなくてはならない。また、PEGの演算子ごとに関数ジェネレータは違うものを使わなければならない。

A <- e1 e2 のような sequence の場合、mkseq 関数ジェネレータを使って

parser.mkseq('A', 'e1 and e2')

のように定義する。sequence を定義する場合は e1 と e2 の間に and を補う必要がある。

A <- e1 / e2 のような、prioritized choice の場合、mkslash 関数ジェネレータを使って、

parser.mkslash('A', 'e1', 'e2')

と定義する、パターンの e1 と e2 は別々の引数として渡す。

終端文字のパターンを検出する関数を記述する場合は、mkterm 関数ジェネレータを使う。

A <- [1-9][0-9]* spasing のような場合、

parser.mkterm('A', '/\A[1-9][0-9]*\s*/')

のようにする。正規表現も’...'のように引用符でくくって文字列リテラルとして渡す。正規表現の先頭には必ず、文字列の先頭を意味する \A アンカーを記述する必要がある。

mkterm 関数ジェネレータと、mkseq 関数ジェネレータは第3引数としてアクションプログラムを文字列リテラルとして渡すことができる。たとえば

mkseq('ad_term', 'add and term', 'push(pop + pop)')

のようにする。

まだ、PEG自体がそれほど普及していないので分かりづらいかもしれないが上の関数ジェネレータの使い方は、PEGの表記を逐語的にプログラムに落とし込む以外のことはやっていない。Wikipedia などにPEGの演算子の説明があるが、数も少ないのですぐに使いこなせるようになると思う。

mkemp 関数ジェネレータは空の文字列にマッチする関数を発生させる。

parser.mkemp('empty')

のように使う。peg.rb には、PEG の ?演算子(0または1回の繰り返し) は定義していないので A <- e1 e2? は、

mkseq('A', 'e1 and e2_option')
mkslash('e2_option', 'e2', 'empty')

のように定義する。また、+ 演算子(e の一回以上の繰り返し)、たとえば A <- e1 e2+ は、

mkseq('A', 'e1 and e2 and e2_star')
mkstar('e2_star', 'e2')

のように定義する。

PEGで文法を定義するとき注意しないといけないのは、PEG では、CFG のような再帰的定義は同一行内ではできない。関数内で無限の関数呼び出しが起きてスタックエラーになるからだ。下のような CFG の再帰的定義、

expr ::= expr + term

のようなものは、

expr <- term ('+' term)*

のように、*演算子で代用する。peg.rb では

parser.mkseq('expr', 'term and add_term_star')
parser.mkstar('add_term_star', 'add_term')
parser.mkseq('add_term', 'add and term')

とプログラムする。ただし、非終端記号の再帰的定義が不可能なわけではなく、

expr <- term ('+' term)*
term <- factor ('*' factor)*
factor <- number / '(' expr ')'

のように、行が変われば再帰的定義は可能だ。

2.Peg オブジェクトのインスタンス変数

Peg オブジェクトのインスタンス変数は、@line, @match, @stack の3つだ。@line には解析をする文字列を代入する。

parser.line = '(1 + 2) + 3 * 4'

@match には、mkterm 関数ジェネレータや、mkseq 関数ジェネレータで定義された関数のパターンがマッチしたときに、マッチした文字列が代入される。

@stack は汎用のスタックだが、インスタンスメソッド push(value) でデータをスタックに積み、pop メソッドで取り出すことができる。

3.定義したパーサの使い方

上の手順で定義したパーサは Peg オブジェクトを操作することで使うことができる。まず、構文解析をしたい文字列を @line に代入し、非終端記号に相当するインスタンスメソッドを呼び出すと、マッチすれば true を返し、マッチしていなければ、false を返す。アクションを定義していれば、マッチするたびにプログラムが実行されるので、前回の arithmatic.rb のように入力文字列に応じた処理を行うことができる。

利用例

parser.line = '(1 + 2) + 3 * 4'
parser.factor
p parser.match #=> '(1 + 2)'
p parser.line #=> '+ 3 * 4'


4.peg.rb の目的

peg.rb を開発した理由は、パーサジェネレータの処理の中身の見える小さなプログラムが欲しかったからだ。中身が分かっていれば、なにをやっているのかが分かっているので安心だし、自由にカスタマイズできる。たとえば + 演算子や、? 演算子を処理する関数ジェネレータを追加したりできる。また、サイズが小さければ、コピペで使用できるので、peg.rb がないのでプログラムが動かないなどのトラブルも避けることができる。

peg.rb ができたことで、ブログのこのシリーズをはじめた最初の目的、「間に合わせで使うミニ言語用のパーサを作る」という目的は達成されたように思う。irb の完全な解読は挫折してしまったが、ほかのひとの作ったプログラムのソースを読むことが、プログラミングのスキルを上げる上でどんなに有効かは体感することができた。

プログラミングネタの記事は一応これでおしまい。プログラムをやりだすと、面白くて、寝ても覚めてもプログラムという状態になりやすいので用心しなければならない。プログラマでない人がどうやってプログラミングを活用することができるかというテーマで面白いアイディアが湧いてきたら、また、プログラミングねたに挑戦してみたい。

peg.rb のライセンスは Ruby ライセンスとする。
by tnomura9 | 2008-05-02 05:28 | Ruby | Comments(0)
<< peg.rb バク修正 世界一簡単なパーサジェネレータ >>