top page > computer > programming > algorithm > parse > packrat.html
更新日:
文責: 重城良国

パックラット構文解析

パックラット構文解析とは

PEGによって表現された文法を解析する手法。メモ化することによって解析を線形時間で行うことができる。

PEG文法と実行効率

PEG文法は仮想的なコンピュータの動作に対応しているため、そのままの動作で構文解析器が作れるが、素直な実装にすると処理に指数関数時間(O(c^n))が必要になる。しかし、メモ化を利用することで線形時間(O(n))で処理を行うことができる。

パックラット構文解析の仕組み

パックラット構文解析による解析は、ひとつの表を作っていく作業と考えられる。その表は横が位置となり縦が文法規則となる。

構文解析が終わったとき、その表は虫食い状態になっている。つまり、必要なマス目だけうめられるということ。

解析の例

4つのトークン、hello、goodBye、world、yoshikuniから成る列を解析する例を考える。文法は以下のようになっているものとする。

MESSAGE = GREETING NAME
GREETING = hello / goodBye
NAME = world / yoshikuni

このような文法でトークン列[hello, yoshikuni]を解析するとする。解析は以下の表を順にうめていく作業と考えることができる。

規則位置1位置2
MESSAGE(a)(b)
GREETING(c)(d)
NAME(e)(f)

位置はトークンの現れる場所を示す。[hello, yoshikuni]の例では位置1にはhelloがあり、位置2にはyoshikuniがある。それぞれのマスには解析結果が入る。全体の解析結果はMESSAGEという規則を列の先頭に適用した結果なので、(a)に入ることになる。

  1. 求める結果は(a)に入る値ということになる
  2. MESSAGE規則ではGREETINGを位置1に適用する必要がある
  3. よって(c)の値が必要になる
  4. GREETINGはhelloを受け入れるので(c)の値はhelloとなる
  5. GREETINGはトークンを1つ消費したので位置を1つ進める
  6. MESSAGE規則の残りはNAMEを位置2に適用したものである
  7. これは(f)のマスに入る
  8. 位置2にはyoshikuniがありNAMEはこれを受け入れる
  9. よって(f)はyoshikuniとなる

上記の解析終了後に表は以下のようになる。

規則位置1位置2
MESSAGEhello yoshikuni(b)
GREETINGhello(d)
NAME(e)yoshikuni

表の(b), (d), (e)はうめられていないことがポイントである。

解析例をHaskellで表現する

Haskellの遅延性を生かすことで、このアルゴリズムは簡潔に書くことができる。このコードの説明は、また別のページで書いていく予定。

data Token
	= Hello
	| GoodBye
	| World
	| Yoshikuni
data Result v
	= Parsed v Derivs
	| NoParse
data Derivs = Derivs {
	dvMessage :: Result (Token, Token),
	dvGreeting :: Result Token,
	dvName :: Result Token,
	dvToken :: Result Token }
eval :: [Token] -> Maybe (Token, Token)
eval ts = case dvMessage (parse ts) of
	Parsed v rem -> Just v
	_ -> Nothing
parse :: [Token] -> Derivs
parse ts = d where
	d = Derivs message greeting name token
	message = pMessage d
	greeting = pGreeting d
	name = pName d
	token = case ts of
		(t : ts') -> Parsed t (parse ts')
		_ -> NoParse
pMessage :: Derivs -> Result (Token, Token)
pMessage d = case dvGreeting d of
	Parsed g d' -> case dvName d' of
		Parsed n d'' -> Parsed (g, n) d''
		_ -> NoParse
	_ -> NoParse
pGreeting :: Derivs -> Result Token
pGreeting d = case dvToken d of
	Parsed Hello d' -> Parsed Hello d'
	Parsed GoodBye d' -> Parsed GoodBye d'
	_ -> NoParse
pName :: Derivs -> Result Token
pName d = case dvToken d of
	Parsed World d' -> Parsed World d'
	Parsed Yoshikuni d' -> Parsed Yoshikuni d'
	_ -> NoParse

「構文解析」トップへもどる

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics