関数型パーサー

8.1 パーサー

パーサーとは、文字列をとり、文字列の文法構造を表現する曖昧さのない構文木を返すプログラムである。

8.2 パーサーの型

詳しいことについては省略。とりあえず、ここではパーサーの型を以下のように定める。

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

文字列を受け取ると、それをパースした型aの結果と、消費されなかった文字列のペアのリストを返す、という型になっている。返り値のリストが空であることが失敗を表す。

8.3 基本的なパーサー

他のパーサーを構築するのに利用する基本的なパーサーを三つ定義する。

return
解析が必ず成功し、入力文字列は消費せずに、与えられた引数を結果としてそのまま返す。

return :: a -> Parser a

return v = \inp -> [(v, inp)]
failure
解析が必ず失敗する。

failure :: Parser a

failure = \inp -> []
item
入力文字列が空ならば解析が失敗し、そうでなければ最初の文字を消費し結果として返す。

item :: Parser Char

item = \inp -> case inp of

[] -> []

x : xs -> [(x, xs)]

パーサーの実現方法を抽象化して、文字列へのパーサーの適用は以下の関数で表すことにする。

parse	:: Parser a -> String -> [(a, String)]
parse p inp	= p inp

例はこんな感じである。

>	parse (return 1) "abc"
	[(1, "abc")]
>	parse failure "abc"
	[]
>	parse item "abc"
	[('a', "bc")]

8.4 連結

複数のパーサーを組み合わせるための連結演算子 >= (「そして」)を定義する。

(>=)	:: Parse a -> (a -> Parser b) -> Parser b
p >= f	= \inp ->	case parse p inp of
		[] -> []
		[(v, out)] -> parse (f v) out

この連結演算子を用いると、「文字を三つ消費し、二番目を捨てて、一番目と三番目を組にして返すパーサーp」は以下のように定義できる。

p :: Parser (Char, Char)
p = item >= \x ->
item >= const
item >= \y ->
return (x, y)

例はこんな感じである。

>	parse p "abcdef"
	[(('a', 'c'), "def")]
>	parse p "ab"
	[]

8.5 選択

連結の他に、選択演算子 +++ (「または」)を定義する。
選択演算子は、一番目のパーサーを文字列に適用し、もし失敗したら、代わりに二番目のパーサーを適用する。

(+++)	:: Parse a -> Parser a -> Parser a
p +++ q	= \inp ->	case parse p inp of
		[] -> parse q inp
		[(v, out)] -> [(v, out)]

例はこんな感じである。

>	parse (failure +++ return 'd') "abc"
	[('d', "abc")]
>	parse (item +++ return 'd') "abc"
	[('a', "abc")]

8.6 パーサーの部品

三つの基本的なパーサー(return, failure, item)と連結/選択演算子を共に使うと、有益なパーサーの部品をたくさん作成できる。

sat
入力文字の一文字目が、述語pを満たしているのならそれを消費し、そうでないのなら失敗するパーサーsatは、itemを用いて以下のように定義できる。

sat :: (Char -> Bool) -> Parser Char

sat p = item >= \x ->

if p x then return x else failure
Data.Charパッケージにて定義される述語を組み合わせると、一文字だけを消費する様々なパーサーを定義できる。

・ digit :: Parser Char

digit = sat isDigit

・ lower :: Parser Char

lower = sat isLower

・ upper :: Parser Char

upper = sat isUpper

・ alphanum :: Parser Char

alphanum = sat isAlphaNum

・ char :: Char -> Parser Char

char x = sat (==x)

例はこんな感じである。

> parse digit "123"

[('1', "23")]

> parse (char 'a') "abc"

[('a', "abc")]
パーサーcharを使って、パーサーstring xsを定義できる。パーサーstring xsは、入力文字列が文字列xsに合致すれば成功し、それ自身を結果として返す。

string :: String -> Parser String

string [] = return []

string (x : xs) = char x >= \x ->

string xs >= \xs ->

return (x : xs)

例はこんな感じである。

> parse (string "abc") "abcdef"

[("abc", "def")]

> parse (string "abc") "ab1234"

[]
パーサーmany pとmany1 pは、パーサーpを失敗するまでできるだけ多く適用し、その結果をリストにして返す。

many :: Parser a -> Parser [a]

many p = many1 p +++ return []

many1 :: Parser a -> Parser [a]

many1 p = p >= \v ->

many p >= \vs ->

return (v : vs)

例はこんな感じである。

> parse (many digit) "123abc"

[("123", "abc")]

> parse (many digit) "ab1234"

[("", "ab1234")]

> parse (many1 digit) "ab1234"

[]
このmanyを用いて、「小文字で始まり、0個以上のアルファベット文字か数字が続く」という規則の識別子(変数名)のパーサーを定義できる。

ident :: Parser String

ident = lower >= \x ->

many alphanum >= \xs ->

return (x : vs)

他、「数字文字が一つ以上繰り返される」自然数のパーサーや、空白のパーサーも定義できる。
nat :: Parser Int

space :: Parser ()

8.7 空白の扱い

パーサーはトークンの前後に任意の空白を許す。例えば、"1+2" と "1 + 2"は同じように解析される。これを実現するため、あるトークンのパーサーを適用する際、前後の空白を無視する部品を定義する。

token	::	Parser a -> Parser a
token	=	space	>=	const
		p	>=	\v ->
		space	>=	const
		return v

「数字文字が一つ以上繰り返される」自然数のパーサーnatに適用すると、空白が無視される。

>	parse (token nat) " 123 "
	[(123, "")]

8.8 数式

8.9 この章の参考文献

8.10 練習問題

パーサーintを定義せよ。

int :: Parser Int

int = natural +++

( symbol "-" >= const

natural >= \n ->

return (-n) )
コメントを解析するパーサーcommentを定義せよ。

comment :: Parser ()

comment = symbol "--" >= const

many (sat (/= '\n')) >= const

char '\n' >= const

return ()
「2+3+4」の構文木をふたつ書け。
省略
「2+3」「2*3*4」「(2+3)+4」の構文木を書け。
省略
簡略化により、パーサーの性能が向上するのはなぜか。
簡略化することにより、共通部分のパースを何度もしなくて済む。
減算演算子、除算演算子にも対応せよ。
構文規則の設定。
- 加算演算子 : 右結合, 3 (結合力)
- 減算演算子 : 左結合, 3
- 乗算演算子 : 右結合, 4
- 割算演算子 : 左結合, 4
expr := term '+' expr | expr '-' term | term
term := factor '*' term | term '/' factor | factor
factor := '(' expr ')' | nat
nat := '0' | '1' | '2' | ...

累乗演算子を扱えるようにせよ。

構文規則

expr	:=	term '+' expr \| expr '-' term \| term
term	:=	power '*' term \| term '/' power \| power
power	:=	factor '^' power \| factor
factor	:=	'(' expr ')' \| nat
nat	:=	'0' \| '1' \| '2' \| ...

練習問題8と同じような感じで、左結合を実現した。

くりっく(´・ω・`) σ▼

自然数と左結合の減算演算子を使った数式について考える問題。
- 構文規則
  expr := expr '-' factor | factor
  factor := '(' expr ')' | nat
  nat := '0' | '1' | '2' | ...
- expr' :: Parser Int
  
  expr' :: Parser Int
  
  expr' = ( expr' >= \e
  
  symbol "-" >= const
  
  factor >= \n ->
  
  return (e - n) ) ++ factor
  
  factor' :: Parser Int
  
  factor' = natural +++
  
  ( symbol "(" >= const
  
  expr' >= \e ->
  
  symbol ")" >= const
  
  return e )
- 問題点
- 解決策を示せ(manyとfoldlを使え)
  
  expr'' :: Parser Int
  
  = factor'' >= \n ->
  
  ( many ( symbol "-" >= const factor'' )) >= ns
  
  return (foldl (-) n ns)
  
  factor'' :: Parser Int
  
  factor'' = natural +++
  
  ( symbol "(" >= const
  
  expr'' >= \e ->
  
  symbol ")" >= const
  
  return e )

>	parse digit "123"
	[('1', "23")]
>	parse (char 'a') "abc"
	[('a', "abc")]

>	parse (string "abc") "abcdef"
	[("abc", "def")]
>	parse (string "abc") "ab1234"
	[]

>	parse (many digit) "123abc"
	[("123", "abc")]
>	parse (many digit) "ab1234"
	[("", "ab1234")]
>	parse (many1 digit) "ab1234"
	[]

expr	:=	expr '-' factor \| factor
factor	:=	'(' expr ')' \| nat
nat	:=	'0' \| '1' \| '2' \| ...

・	digit	:: Parser Char
	digit	= sat isDigit

・	lower	:: Parser Char
	lower	= sat isLower

・	upper	:: Parser Char
	upper	= sat isUpper

・	alphanum	:: Parser Char
	alphanum	= sat isAlphaNum