Recursive Descent ParserとPackrat Parser

Parsing

Packrat Parsing: Simple, Powerful, Lazy, Linear Timeの論文にある簡単な数式のパーザを手書きして、Recursive Descent ParserとPackrat Parserで速度を比較。

Packrat ParserとRecursive Descent Parserは基本的な構文解析の枠組みは似ている。Recursive Descent Parser、Packrat Parserともに解析中にバックトラックが発生する。Recursive Descent Parserはバックトラックが頻発すると計算量が指数的に増大してしまうが、Packrat Parserは計算結果をメモ化しているため計算量が線形に抑えられる。

Packrat Parsingは、Recursive Descent Parsing + 遅延評価 + メモ化、というのが現在の認識。

論文ではHaskellでコードが書いてあるけど、I love SchemeなのでSchemeで書き直して理解しながらやりました。

ソースコードはこちら: プログラミング:PackratParsing:Sample

文法定義

;; Additive <- Multitive '+' Additive / Multitive
;; Multitive <- Primary '*' Multitive / Primary
;; Primary <- '(' Additive ')' / Decimal
;; Decimal <- '0' / '1' / '2' / ... / '9'

Recursive Descent Parser

gosh> (time (eval-RDP "1+2*(3+4*(5+6))"))
;(time (eval-RDP "1+2*(3+4*(5+6))"))
; real   0.002
; user   0.000
; sys    0.000
(:result 95 ())
gosh> (time (eval-RDP "(((((((((1)))))))))"))
;(time (eval-RDP "(((((((((1)))))))))"))
; real   7.165
; user   7.020
; sys    0.020
(:result 1 ())

(((((((((1)))))))))なんかは、バックトラックが頻発するので、実行時間が指数的に爆発する。

Packrat Parsing

gosh> (time (eval-PP "1+2*(3+4*(5+6))"))
;(time (eval-PP "1+2*(3+4*(5+6))"))
; real   0.001
; user   0.000
; sys    0.000
(:result 95 #<<derivs> 0x8145658>)
gosh> (time (eval-PP "(((((((((1)))))))))"))
;(time (eval-PP "(((((((((1)))))))))"))
; real   0.001
; user   0.000
; sys    0.000
(:result 1 #<<derivs> 0x816b180>)

Packrat Parsingの場合は、一度parseした結果がメモ化されているので、バックトラックが発生するたびに計算し直す必要がないので、実行時間が線形になる。