読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

PetitParserでバックトラックが重い場合

Smalltalk

Smalltalk処理系を作ろうと思い、Smalltalkバイトコードコンパイラで止まっていたNirnLeafをどうにか先に進めようと、PetitParserをSqueak Smalltalkで使ってみることにした。

を読んでなんとなくわかったので書いていたけど、無限ループに思える処理が起きた。

expression := ...
statement := assign / expression.
statements := statement, (dot, statement) star, dot optional.

というようなパーサを書いて、statementsにfoo. barをパースさせるまでは良かった。

foo. bar.と最後にドットを追加したところ、Squeakがフリーズしてしまった。alt-.で止めてデバッガを起動しても、コールスタックからは何が原因なのか解析するのが難しい。

まずstatementsのやり方が無限ループになるのかならないのか試してみた。

a   := $a asParser trim.
dot := $. asParser trim.
par := a, (dot, a) star, dot optional.

par parse: 'a. a'.  "=> #($a #(#($. $a)) nil)"
par parse: 'a. a.'. "=> #($a #(#($. $a)) $.)"

というわけで、無限ループにはならずパースできる。

それならバックトラックが大量に起きているのかと思い、いろいろ試行錯誤した挙句、「そういえばPackrat Parsingとか聞いたことあるな、一度パースしたものを記憶しておくということか」と思い当たって、statementを次のように変えた。

statement := (assign / expression) memoized.

そうしたら一瞬でパースできました。めでたしめでたし。

わかったこと

  • PEGパーサで無限ループのようなことが起きたら、バックトラックしない同じ構造のパーサを作り、無限ループかどうか確かめてみる
  • バックトラックで重くなってる場合は、その部分のパーサをメモ化する。(Packrat Parser)
広告を非表示にする