このサイトではopenpearで公開されているPEGパーサコンビネータのドキュメントを記述しています。
なるべく分かりやすい記述を心がけていますが、意味の分からない所などがあったら開発者に質問しましょう。
本ライブラリについて
特徴
- PHPで記述されており、パーサの構築にはPHPそのものを記述する
- PEGで定義されている演算子は、PEGクラスメソッドとして実装されている
- PEGで定義されている演算子の他に、実際にパーサを書く際に便利なヘルパーメソッドを用意している
- 文字列だけではなく、配列もパーサに与えることができる
- PEG_IContextを実装することで任意のデータ構造をパーサに与えることができる
実装
- 再帰下降型のパーサである
- 左再帰には対応していないし、対応する予定も無い
- 通常のパーサはメモ化されないので、メモ化する場合はPEG::memo()メソッドを利用する
基本的な使い方
- パーサの構築
- コンテキストの構築
- パーサにコンテキストを与える
パーサの構築
パーサは通常PEGクラスメソッドから生成される。
ユーザは解釈したい文法にあわせて任意のパーサを構築する。
<?php
$parser = PEG::seq('a', 'b');
コンテキストの構築
PEG::contextメソッドを使うことで通常利用するコンテキストは生成される。
コンテキストは、パーサが解釈する対象や、対象の現在の位置の状態等を持つ。
<?php
$context = PEG::context('abc');
パーサにコンテキストを与える
パーサにコンテキストを与えるにはparseメソッドを呼び出す。
この返り値がパーサが返す結果である。パーサは失敗を返す事もある。
<?php $result = $parser->parse($context);
examples
簡易的なS式パーサ
シンボルとリストを解釈できる簡易的なS式パーサ。パーサを構築するのに8行程度。
<?php
include_once 'PEG.php';
// パーサの構築
$space = PEG::many(PEG::char("\r\n \t"));
$symbol = PEG::join(PEG::many1(PEG::char("()\r\n\t ", true)));
$paren = PEG::third('(', $space, PEG::many(PEG::ref($atom)), ')');
$atom = PEG::memo(PEG::first(PEG::choice($paren, $symbol), $space));
$sexpr = PEG::second($space, $atom);
// コンテキストの構築
$context = PEG::context('(a (b (c ())))');
// コンテキストをパーサにかける
$result = $sexpr->parse($context);
// 結果
var_export($result);
/*
array (
0 => 'a',
1 =>
array (
0 => 'b',
1 =>
array (
0 => 'c',
1 =>
array (
),
),
),
)
*/
四則演算の数式を逆ポーランド記法に変換する
演算子や括弧で優先順位のつく四則演算の数式を解釈して逆ポーランド記法に変換するパーサ。
<?php
include_once 'PEG.php';
// フックに使う関数の定義
$fn = function($result) {
list($first, $rest) = $result;
return !$rest
? array($first)
: array_merge(array($first), call_user_func_array('array_merge', $rest));
};
$listof = function($item, $glue) use($fn) {
return PEG::hook($fn, PEG::seq($item, PEG::many($glue, $item)));
};
$torpn = function(Array $expr) use(&$torpn) {
$first = array_shift($expr);
$ret = is_array($first) ? $torpn($first) : $first ;
foreach (array_chunk($expr, 2) as $buf) {
list($op, $right) = $buf;
$ret .= (is_array($right) ? " {$torpn($right)}" : " {$right}") . " {$op}";
}
return $ret;
};
// パーサの構築
$space = PEG::many(PEG::char("\r\n \t"));
$zero = PEG::seq(PEG::char('0'));
$notzero = PEG::seq(PEG::char('123456789'), PEG::many(PEG::digit()));
$strnum = PEG::join(PEG::choice($notzero, $zero));
$num = PEG::hook('intval', PEG::first($strnum, $space));
$paren = PEG::second(PEG::seq('(', $space), PEG::ref($exp1), PEG::seq(')', $space));
$atom = PEG::choice($num, $paren);
$op = function($str) use($space) { return PEG::first(PEG::char($str), $space); };
$exp3 = PEG::memo($listof($atom, $op('/')));
$exp2 = PEG::memo($listof($exp3, $op('*')));
$exp1 = PEG::memo($listof($exp2, $op('+-')));
$exp = PEG::second($space, PEG::hook($torpn, $exp1), PEG::eos());
// 試してみる
var_dump($exp->parse(PEG::context('1 + 2 * 3'))); // => 1 2 3 * +
var_dump($exp->parse(PEG::context('(1 + 2) * 3'))); // => 1 2 + 3 *
var_dump($exp->parse(PEG::context('1 + 2 * 3 / 4'))); // => 1 2 3 4 / * +
var_dump($exp->parse(PEG::context('1 + 2 * 3 * 4'))); // => 1 2 3 * 4 * +
