top page > computer > haskell > packages > papillon > steps_to > first.html
更新日:
文責: 重城良国

papillonに到るまで: 最初の例

(工事中 20%)

まずは非常に単純な例を作成してみよう。この例ではパックラット構文解析の良さはわからないが、どのような処理をするかを知るための単純な例である。

まずは単純な再帰下降構文解析器を示す。そして、それをどう変化させれば、メモ化が実現できるかを示そう。以下の文法を例として使うことにする。Haskellのコードに合わせて、大文字、小文字の使いかたは慣用的な使いかたとは逆にしてある。

message = greeting name
greeting = Hello / GoodBye
name = World / Yoshikuni

単純な再帰下降構文解析器

helloRecurse.hs

data Token = Hello | GoodBye | World | Yoshikuni deriving Show
pMessage :: [Token] -> Maybe ((Token, Token), [Token])
pMessage ts = case pGreeting ts of
	Just (g, ts') -> case pName ts' of
		Just (n, ts'') -> Just ((g, n), ts'')
		_ -> Nothing
	_ -> Nothing
pGreeting :: [Token] -> Maybe (Token, [Token])
pGreeting (Hello : ts) = Just (Hello, ts)
pGreeting (GoodBye : ts) = Just (GoodBye, ts)
pGreeting _ = Nothing
pName :: [Token] -> Maybe (Token, [Token])
pName (World : ts) = Just (World, ts)
pName (Yoshiukni : ts) = Just (Yoshikuni, ts)
pName _ = Nothing

Maybeモナドを利用する

helloMonad.hs

とくに深い意味はないがMaybeモナドを利用するとよりすっきりと書ける。

pMessage ts = do
	(g, ts') <- pGreeting ts
	(n, ts'') <- pName ts'
	return ((g, n), ts'')

メモ化する

「遅延型を利用したメモ化」参照。

helloMemo.hs

data Derivs = Derivs {
	message :: Maybe ((Token, Token), Derivs),
	greeting :: Maybe (Token, Derivs),
	name :: Maybe (Token, Derivs),
	token :: Maybe (Token, Derivs) }
parse :: [Token] -> Derivs
parse ts = d
	where
	d = Derivs m g n t
	m = pMessage d
	g = pGreeting d
	n = pName d
	t = case ts of
		(t : ts') -> Just (t, parse ts')
		_ -> Nothing
pMessage :: Derivs -> Maybe ((Token, Token), Derivs)
pMessage d = do
	(g, d') <- greeting d
	(n, d'') <- name d'
	return ((g, n), d'')
pGreeting :: Maybe (Token, Derivs)
pGreeting d = do
	(t, d') <- token d
	case t of
		Hello -> return (t, d')
		GoodBye -> return (t, d')
		_ -> fail "not parsed"
pName :: Derivs -> Maybe (Token, Derivs)
pName d = do
	(t, d') <- token d
	case t of
		World -> return (t, d')
		Yoshikuni -> return (t, d')
		_ -> fail "not parsed"

(作成中)

「papillonに到るまで」トップへもどる

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