Rui:ParsingExpressionGrammar

Rui:ParsingExpressionGrammar

(2006/12/13 20:22:55 PST): Ruiからページを分離しました。

Parsing Expression Grammar

(2006/11/16 21:44:07 PST): HaskellのParsecのようなコンビネータパーザを作っています。コンビネータパーザは、再帰下降パーザを高階関数を使って組み立てていくパーザで、書きやすく読みやすいです。文脈自由文法とは異なりパーズ結果は1つに決まり、無限の先読みができるので強力です。

例を1つ示します。CSVパーザなのですが、だいたいBNFと同じように読めるのではないでしょうか。CSVのフォーマットとして、ここでは、(1)レコードはカンマで区切られたフィールドの並び、(2)カンマの周囲の空白は無視、(3)フィールドはクオートでくくられているかクオートを含まない文字列、(4)クオートされた文字列中にクオートを含むには2つ並べる、という規則を採用しました。一般的なCSVと同じ規則です。 

(use peg)

(let* ((spaces ($many ($one-of #[ \t])))
       (comma ($seq spaces ($char #\,) spaces))
       (dquote ($char #\"))
       (double-dquote ($do (($string "\"\"")) ($return #\")))
       (quoted-body ($many ($or double-dquote ($one-of #[^\"]))))
       (quoted ($between dquote quoted-body dquote))
       (unquoted ($many-till anychar ($or comma newline)))
       (field ($or quoted unquoted))
       (record ($sep-by ($->rope field) comma)))
  #?=(parse-string record "a,b,c")
  #?=(parse-string record "\"a\" , b  , c")
  #?=(parse-string record "\"a  \"\" \n\" , b  , c"))

実行結果。正しくパーズできています。確認してみてください。 

#?="/tmp/foo":12:(parse-string record "a,b,c")
#?-    ("a" "b" "c")
#?="/tmp/foo":13:(parse-string record "\"a\" , b  , c")
#?-    ("a" "b" "c")
#?="/tmp/foo":14:(parse-string record "\"a  \"\" \n\" , b  , c")
#?-    ("a  \" \n" "b" "c")

パーザはとてもシンプルで、動くプログラムというよりは、単なる定義のように見えます。「spacesは#[ \t]の繰り返しである。commaはspaces、#\,、spacesという並びである。……」これが動作するのは面白いですね。

入力の抽象化

PEGは無制限の先読みを許すので、1文字しか先読みできない文字列ポートをそのまま入力として使うことはできません。それに、パーズ対象を文字列に制限するより、任意のトークン列を許したほうが便利なので、文字列を前提にしたくありません。そこで、SRFI-80のストリームと同様のものを入力として受け付けることにしました。ストリームは、現在の文字(あるいはトークン)と、次の位置のストリームの2値を返します。副作用を持たないので、無制限の先読みをしても問題ありません。

バックトラックの制御

無制限の先読みをすると、パーズの時間が最悪の場合、入力に対して指数的に必要になります。たいていの文法はトークンをひとつ先読みするだけでほとんどの場合パーズしていけるので、性能の悪いパーザをうっかり書いてしまわない配慮が必要です。ここでは、(1)選択肢のどれかが成功するとそれ以上バックトラックをしない、(2)明示的にほかの選択肢をカットする方法を提供する、ことにしました。ブランチをカットできるのは、Perl 6のrulesに似ています。

検討事項がいくつかあります。

命名規則

このモジュールはコンビネータと基本的なパーザの名前をたくさんエクスポートします。コンビネータの名前はorやdoのような既存の構文と同名なので、$というプリフィックスをつけることにしました。基本的なパーザにはプリフィックスをつけないのがよさそうですが、digitやeofといった識別子をエクスポートすることになるので迷っています。なお、Gaucheのモジュールではモジュール名を先頭につけた名前をエクスポートしている例が多く、それに従うとpeg-という名前をつけることになりますが、パーザコンビネータがエクスポートする識別子は多用するので、あまりにpeg-が並びすぎて冗長になるためその規則はやめました。

文字列に特化したスキャナ

簡単なパーザをプロファイリングしたところ、Schemeレベルで1文字ずつ処理するのが重いようです。文字列のスキャニングに特化したストリームを作成して、文字ではなくトークンを返してもらい、トークン単位でパーズするとパフォーマンスが良くなるのではないでしょうか。スキャナは正規表現を使えばいいと思います。正規表現のマッチはネイティブコード(正規表現のVM)で実行されるので速いはずです。

怠惰な文字列構築

中間文字列を何度も構築すると、同じデータが何回もコピーされてしまうので、中間文字列の生成を避けて最後に一気に文字列を作成したほうが効率的です。text.treeモジュールを使えばいいのですが、意味値を作るときにパーズ途中の文字列が必要になることがあるので、途中で文字列を作成する必要も出てきます。2パスで処理して、最初のパスでは意味値のコンストラクタにテキストツリーを渡してオブジェクトを作成し、パーズ完了後にオブジェクトをアップデートして文字列で置き換えることは可能でしょうけど、あまり現実的ではないように思います。中庸の選択肢として、(1)リスト以外のコンストラクタに文字列を渡すときは明示的に文字列化してもらい、(2)リストだけはパーズ完了後にトラバースしてテキストツリーを文字列化する、というのがよいかなと思います。(追記: <rope>というオブジェクトで中間的なテキストツリーをあらわすことにしました。)

エラーの通知

Parsecと同じく「一番遠く」のエラーを通知するのがよいでしょう。できればスタックトレースを含んだエラーを表示したいです。たとえばCSVのクオートされたフィールドの途中にEOFがある場合にこういうエラーメッセージを出せれば理想的です: 「field -> record -> unquoted-body: Expecting #[^"] or "\"\"", but got EOF」

参考文献

WikipediaのParsing Expression Grammarの記事
短くよくまとまっている
http://en.wikipedia.org/wiki/Parsing_expression_grammar

Parsec, a fast combinator parser
Haskellによるコンビネータパーザ
http://www.cs.uu.nl/people/daan/download/parsec/parsec.html

Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
元論文?
http://pdos.csail.mit.edu/papers/parsing:popl04.pdf

Monadic parser combinators (PDF)
Monadの前提知識を必要としない(といっている)コンビネータパーザの説明。ただしHaskellをちょっとは知っていないとコードが読めない
http://www.cs.nott.ac.uk/~gmh/bib.html#monparsing

JParsec
Javaによるparsecの実装
http://jparsec.codehaus.org/

perl6: Synopsys 5: Regexes and Rules
バックトラックの制御というアイデアが参考になる
http://dev.perl.org/perl6/doc/design/syn/S05.html

最強のパーザー、Parser Combinator (はてなダイアリーの記事)
参考になる
http://d.hatena.ne.jp/tanakh/20040730

comp.compilersの興味深いスレッド
http://groups.google.com/group/comp.compilers/browse_frm/thread/a9918c3676924037/e00b8135ece00e70

A Primitive Recursive-Descent Parser with Backtracking
Java 1.5のパーザをPEGで手書きで書いた論文。PEGとは何かを理解するのによい。コンビネータパーザではない。2つ先のパーズ結果を保存しておくだけでほぼ入力にリニアなパーズ時間になったというのが興味深い。すべての結果を保存しておくpackrat parsingが機能過剰であると示唆している。
http://www2.informatik.hu-berlin.de/~hs/Aktivitaeten/2006_CSP/CSP06_28.pdf

Practical Packrat Parsing
Rats!の最適化、パフォーマンスなど
http://cs.nyu.edu/rgrimm/papers/tr2004-854.pdf

The Packrat Parsing and Parsing Expression Grammars Page
参考文献へのリンクなど
http://pdos.csail.mit.edu/~baford/packrat/

Better Extensibility through Modular Syntax
Javaで書かれたPEGパーザジェネレータRats!の説明。最適化などの話もあり
http://www.cs.nyu.edu/rgrimm/papers/pldi06.pdf

開発記録

性能目標 (2006/11/25 07:45:58 PST)

PEGの性能目標を、正規表現と同程度ということにしました。当初考えていた性能よりずっと上で野心的ですが、本質的に難しいところはなく達成可能なはずです。これくらいの性能が出せればパフォーマンスを気にすることなくいろんなところで使えるので、正規表現では手に余る場面でその代替として非常に役立ってくれるでしょう。

メモリ上に連続したバイト列(あるいは文字列)とそれ以外とで処理を分けて、前者は性能向上のためCで書かれたVMで処理するのがよいでしょう。後者は今と同じようにSchemeレベルで処理します。開発ステップは次のようになるかな。期間はぜんぜん読めませんが3ヶ月くらいでできたら上出来です。

  1. パーザを手続きで表現するのをやめて、中間表現で表すよう変更。コンパイルのフェーズを導入する。コンパイラが出力するのは手続き。
  2. コンパイラがVM命令のリストを出力するよう変更。VMはSchemeで書く。
  3. VMをCで実装する。
  4. 最適化フェーズと、最適化されたコードのためのVM命令を追加する。

PEGによる拡張可能な文法 (2006/11/23 18:19:07 PST)

Better Extensibility through Modular Syntaxで、Jeannieという興味深い拡張C言語が紹介されている。CからJavaオブジェクトのメソッドを呼ぶのは次のように書かなければならず面倒だった。 

jclass cls = (*env)->GetObjectClass(env, obj);
jmethodId mid = (*env)->GetMethodId(env, cls, "method", "signature");
jobject result = (*env)->CallObjectMethod(env, cls, mid, ...);

しかしこれをJeannieでは次のように書ける。 

jobject result = ‘obj.method(...);

バックティック演算子は後続の式をCからJavaに切り替える演算子で、つまりJeannieはCとJavaの両方の文法をつなぎ合わせてできている。2つの文法を合成するのは竹と木を接ぐようなものだが、PEGではそこらへんが簡単ということらしい。Lexerレスで、優先順位があるという2点がそれを簡単にするのだと思う。

これはCのような直接構文木を得られないシンタックスの言語でLispのような強力なマクロを実現する道ではないだろうか。たとえばユーザに文法を拡張するなんらかの方法を定義して、「x < y < z」という式を「(x < y && y < z)」に展開することができるはず。「x < y < z」が正しいCの式であるのにかかわらず、ユーザがそれを上書きするできるのがポイント。このアイデアを突き詰めていけば有意義な成果が得られるかも。

高速化手法の検討 (2006/11/21 19:24:29 PST)

数倍速くするには、パーザを手続きではなく中間表現で表現してコンビネータで組み立てて、最後にコンパイルするのがよいかも。

利点:

欠点:

パーザを手続きで表現することに意外にも利点は少ないようです。手軽な一方、Cによる実装の力を借りたり最適化フェーズを導入して本格的に最適化しようとすると欠点が目立ってきます。正規表現とのハイブリッドにするくらいなら、PEGを正規表現エンジンのようにCで実装するほうがよさそうです。

中間報告 (2006/11/21 08:34:45 PST)

Gauche本体の文字列操作を多少効率化したうえで、正規表現を使って複数の文字列を1かたまりで処理してみると、3倍弱遅い程度まで改善しました。がんばればもうちょっといけそうですが、同程度かそれ以上まで速くするには一段飛躍が必要なようです。

(2006/11/19 07:55:56 PST): パーザ中間報告。

きちんと動作していますが、CSVパーザでtext.csvと比べて4倍遅いです。ここから最適化していかないといけません。そのためにはベンチマークを何個も作るべきでしょうね。

なお、テストには3000行強の郵便番号CSVデータを使いました。来週は開発時間がそうとれそうにないので、ハックしたいかたのためにアーカイブを置いておきます。コメントなどはこのWikiまたはLingrで。

同梱のJSONモジュールはPEGモジュールを使ったサンプルという位置づけです。最終的にはrfc.jsonとして完成させる予定。

peg-20061120.tar.gz 

$ gosh -I. benchmark.scm
;(time (parse-string csv-parser data))
; real   4.286
; user   4.050
; sys    0.230
;(time (port->list reader (open-input-string data)))
; real   0.957
; user   0.850
; sys    0.100

本体への統合 (2008/05/20 04:26:20 PDT)

Shiro(2008/05/20 04:26:20 PDT): 気がついたら1年半も経ってしまっていましたが、 peg-20061120を元にチューニングしていたら結構いけそうな感じになってきたので、 現在Gauche本体へ統合作業中です。

今のとここんな感じ： 

[shiro@scherzo peg]$ ../../src/gosh -ftest -I. ./benchmark.scm 
;(time (parse-string csv-parser data))  ; 現在のバージョン
; real   2.499
; user   2.430
; sys    0.050
;(time (parse-string csv-parser data))  ; peg-20061120
; real   5.443
; user   5.240
; sys    0.030
;(time (port->list reader (open-input-string data))) ; フル手書きパーザ
; real   1.088
; user   1.030
; sys    0.010

もう少しいけそうな感じ。手書きの2倍になったら、利便性と天秤にかけても かなり使いどころがあるように思います。

もう少しいけた。 

;(time (parse-string csv-parser data)) ; 現在のバージョン
; real   1.963
; user   1.900
; sys    0.030
;(time (parse-string csv-parser data)) ; peg-20061120
; real   5.339
; user   5.100
; sys    0.040
;(time (port->list reader (open-input-string data))) ; フル手書きパーザ
; real   1.107
; user   1.020
; sys    0.010

まだ少しいけそう。

2008/05/21 20:36:49 PDT: ここまできた。 

[shiro@scherzo peg]$ ../../src/gosh -ftest -I. benchmark.scm 
;(time (parse-string csv-parser data)) ; 現在のバージョン
; real   1.222
; user   1.170
; sys    0.030
;(time (parse-string csv-parser data)) ; peg-20061120
; real   5.327
; user   5.060
; sys    0.040
;(time (port->list reader (open-input-string data))) ; text.csv
; real   1.117
; user   1.030
; sys    0.000

2箇所ほどスピードクリティカルな部分(入力ストリームの読み込み部分と、 ropeからstringにするところ)をCで書き直したので、pure Schemeで書いている text.csvとの比較は完全にフェアとは言えないかもしれないけれど、 ユーザからは見えないところだからいいかなと。

とりあえずコミット

Shiro(2008/05/26 00:58:43 PDT): ひとまずコミット。現在の性能は: 

;(time (parse-string csv-parser data)) ; 現在のバージョン
; real   0.962
; user   0.930
; sys    0.020
;(time (parse-string csv-parser data)) ; peg-20061120
; real   5.827
; user   5.720
; sys    0.060
;(time (port->list reader (open-input-string data))) ; text.csv
; real   1.229
; user   1.200
; sys    0.000

あるぇ〜、peg-20061120とtext.csvが遅くなってるのはなぜだろう。 何も変えてないと思うんだけど。まあとにかく、Schemeで手書きしたtext.csv よりも速くなったということで、PEGを使わない理由はなくなった。

csvのパージングでは$one-ofが作るパーザが一番時間食ってるので、 こういうプリミティブをCに置き換えちゃえばもっと速くなるだろうけど、 そのへんはこれから色々なパーザを書いて性能を計測しつつ考えることにする。

なお、オリジナルのコードに比べて色々なところが変わっているので注意。

チューニングの指針だけれど、とにかくinner loopでのアロケーションを避ける というのが大きいかな。

気になること(これから検討すること)

Topics
Sponsored Links
Search
Recent Changes
More ...
Last modified : 2012/06/04 05:50:49 UTC
WiLiKi 0.8.3 running on Gauche 0.9.15-p2