top page > computer > haskell > web_lecture > for_programmer > parser_basic.html
更新日:
文責: 重城良国

パーサ: 基本的な関数

用意

モジュールData.Char、Data.Maybeを使う。ファイルの先頭に

import Data.Maybe
import Data.Char

を書く。

パーサの型はどうなるだろうか。字句解析はせずに直接構文解析してしまう。引き数はStringだ。返り値は何かは決まらないので

String -> a

が考えられる。パーサ同士を結合して新たなパーサを作るために「パースした残りの文字列」が必要だ。

String -> (a, String)

パース候補は複数あるので結果はリストだ。

String -> [(a, String)]

名前をつけておく。

type Parse a = String -> [(a, String)]

いつも成功

文字を消費せずにいつも成功し指定した値を返す関数を作る。

succeed :: a -> Parse a
succeed v i = [(v, i)]

第1引数で指定した値vが返り文字列はそのまま次のパーサに渡す。パースの結果はひとつなので単一要素のリストとなる。

% ghci parse.hs
*Main> succeed 123 "hello"
[(123,"hello")]

1文字読み込む

条件を満たす1文字を読み込むパーサを作る関数だ。

check :: (Char -> Bool) -> Parse Char
check p (c : cs) | p c = [(c, cs)]
check _ _ = []

文字列が空または先頭の文字が条件を満たさなければパースは失敗だ。

*Main> :reload
*Main> check isDigit "123"
[('1', "23")]
*Main> check isDigit "abc"
[]

指定した1文字を読み込む関数も作る。

char :: Char -> Parse Char
char = check . (==)

*Main> :reload
*Main> char 'a' "abc"
[('a', "bs")]
*Main> char 'a' "bcd"
[]

または

ふたつのパーサの結果を複数の選択肢とするパーサを作る関数だ。

alt :: Parse a -> Parse a -> Parse a
(p1 `alt` p2) i = p1 i ++ p2 i

*Main> :reload
*Main> (char 'a' `alt` check isDigit) "123"
[('1', "23")]
*Main> (char 'a' `alt` check isDigit) "abc"
[('a', "bc")]

加工

パーサが返した値を加工する。パーサは「すべての可能性」をリストとして返すことに注意する。

build :: Parse a -> (a -> b) -> Parse b
build p f i = [ (f x, r) | (x, r) <- p i ]

Parse型の値pは文字列を取ってタプルのリストを返す関数である。関数pに文字列iを与えるとタプル(結果, 残りの文字列)のリストが返る。内包表記の|の右側ではリストのそれぞれの要素であるタプルのそれぞれの要素で変数x, rを束縛している。|の左側で値xに関数fを適用し値rとのタプルにまとめ直している。この操作はリストの要素すべてに対して行われる。

ここでp iの結果が[(1, "23"), (12, "3"), (123, "")]だった場合を考えよう。文字列"123"をパースした結果として「結果が1で残りが"23"」「結果が12で残りが"3"」「結果が123で文字列すべて消費」の3通りの可能性があるということだ。この場合に「結果を2倍する」ことを考える。

[ (x * 2, r) | (x, r) <- [(1, "23"), (12, "3"), (123, "")] ]

まずは(1, "23")が(x, r)でマッチされxは1にrは"23"となる。そのとき結果の値は(2, "23")となる。同様にxが12、rが"3"となったときには結果は(24, "3")となり、xが123、rが""のときには結果は(246, "")となる。それぞれの結果はリストにまとめられるので[(2, "23"), (24, "3"), (246, "")]が全体の結果となる。これを関数mapで書き直すと

map (\(x, r) -> (x * 2, r)) [(1, "23"), (12, "3"), (123, "")]

となる。

*Main> [ (x * 2, r) | (x, r) <- [(1, "23"), (12, "3"), (123, "")]
[(2,"23"),(24,"3"),(246,"")]
*Main> map (\(x, r) -> (x * 2, r)) [(1, "23"), (12, "3"), (123, "")]
[(2,"23"),(24,"3"),(246,"")]

試してみる

*Main> :reload
*Main> (check isDigit `build` (read . (: ""))) "123" :: [(Integer, String)]
[(1, "23")]

つなげる

ふたつのパーサをつなげる。

(>*>) :: Parse a -> Parse b -> Parse (a, b)
(p1 >*> p2) i = [ ((x, y), r') | (x, r) <- p1 i, (y, r') <- p2 r ]

*Main> :reload
*Main> (char 'a' >*> check isDigit) "a123"
[(('a','1'),"23")]

前後どちらかの返り値をそれぞれ無視する関数も作る。

(>*) :: Parse a -> Parse b -> Parse a
p1 >* p2 = (p1 >*> p2) `build` fst

(*>) :: Parse a -> Parse b -> Parse b
p1 *> p2 = (p1 >*> p2) `build` snd

*Main> :reload
*Main> (char 'a' >* check isDigit) "a123"
[('a', "23")]
*Main> (char 'a' *> check isDigit) "a123"
[('1', "23")]

文字列の終わり

文字列の終わりを調べる。

eof :: Parse ()
eof "" = [((), "")]
eof _ = []

*Main> :reload
*Main> (char 'a' >* eof) "a123"
[]
*Main> (char 'a' >* eof) "a"
[('a',"")]

まとめ

パーサを扱う基本的な関数を定義した。

「パーサ: はじめに」へもどる 「リストのパーサ」へ

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