2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Haskell入門ハンズオン! #3: 当日用資料 2/5

Last updated at Posted at 2018-03-09

Haskell入門ハンズオン! #3: 当日用資料 2/5

はじめに

構文解析器をつくり、それを使って四則演算の式を読み込み、評価する。たとえば、つぎのような式を読み込む

3+(5*4)

そして、この結果を計算して、つぎのように表示する。

23

このように、文字列を決められたルールで解釈することを、構文解析とよぶ。今回は構文解析と、数値への評価を同時にやってしまう。

パーサコンビネータ

まず「パーサコンビネータ」を構成する関数群を定義する。「パーサコンビネータ」とは、構文解析器(パーサ)を組み上げるための道具だ。この道具を対話環境で試しながら作っていく。内容としては、拙書「Haskell - 教養としての関数型プログラミング」第20章の内容(P.298 - 310)を「ほぼ、まるまる」といった感じだ。

モジュールの導入

対話環境で使う関数をファイル内で導入しておく。こういうことは本番コードでは、あまりやらない。ここでは、ハンズオンでの便宜のため、このようなかたちとした。ファイルcalc.hsを、つぎのように作る。

% vim calc.hs
import Data.Maybe (listToMaybe, fromJust)
import Data.Char (isDigit, isSpace, digitToInt)

予約語importを使って、モジュールを導入する。対話環境に読み込んでおこう。

*Main> :load calc.hs

パーサの型

ここで、「パーサ」の型を考える。「文字列を読み込んで値をかえす関数」だと

String -> a

Haskellで標準的な文字列はString型の値だ。String型の値とは、実はChar型の値のリストだ。

*Main> ['x', 'y', 'z']
"xyz"

['x', 'y', 'z']と"xyz"とは、おなじものだ。また、「String -> a」の「a」は型変数だ。型変数は、実際に型が使われるときには、具体的な型(Char, Bool, Doubleなど)に置き換えられる。

ふたつのパーサをつなげることを考える。まえのパーサでパースしきれなかった文字列を、つぎのパーサにわたすことを考えると、パーサは結果の値だけでなく、「残りの文字列」もかえしたほうがいいだろう。すると、パーサの型は、つぎのようになる。

String -> (a, String)

(Foo, Bar)のような構造をタプルとよぶ。ふたつ以上の値をまとめるのに使うことができる。

さらに、パースの結果として、最終的には、ひとつにしぼるとしても、解析の途中では複数の候補が必要になることもある。パーサの型はさらに、つぎのようになる。

String -> [(a, String)]

[Foo]という表記は「Foo型の値のリスト」の型を意味する。この型全体の意味は、つぎのようになる。

文字列を引数としてとり
「パースの結果と残りの文字列」のリストをかえす関数

これから、パーサをあつかう関数をいくつか作る。そのたびに、String -> [(a, String)]を書くのは冗長だ。このようなとき、型に別名(型シノニム)をつけられる。ファイルcalc.hsに、つぎのように追加する。

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

予約語typeを使って、型シノニムParseを定義した。型引数aのところには具体的な型がはいる。

Parse Char ===> String -> [(Char, String)]
Parse Bool ===> String -> [(Bool, String)]
Parse Double ===> String -> [(Double, String)]

パーサコンビネータを構成する関数群

いつも成功するパーサ

「いつも成功して、決められた値をかえすパーサ」を作る関数。

calc.hs
succeed :: a -> Parse a
succeed v inp = [(v, inp)]

いまは「何のためにあるか」は、わからなくていい。対話環境で試してみよう。

*Main> :reload
*Main> (succeed 123) "hello"
[(123,"hello")]

文字列を消費せずに123をかえすパーサに、文字列"hello"をあたえたら、ひとつの「結果の値123と残りの文字列"hello"」に解析された。

条件つきで1文字、読み込むパーサ

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

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

関数checkの定義には、パターンマッチとガードという、ふたつの構文が使われている。第2引数のところの(c : cs)はパターンマッチだ。第2引数の文字列のうち、先頭の文字で変数cを束縛し、残りの文字列で変数csを束縛している。ちなみに、「値で変数を束縛する」は「値を変数に代入する」のように、頭のなかで変換するとわかりやすいかもしれない。

| p cのところがガードだ。これは、p cを評価した結果がTrueのとき、全体が=の左辺の[(c, cs)]に評価されるということだ。これらのパターンマッチとガードの、どちらかを満たさなければ、2行目にうつる。定義の2行目の_(アンダースコア)は、第1引数と第2引数とが、使われないということだ。引数は無視されて、全体はに評価される。これは、1文字目cが条件を満たさなければ、パースは失敗するということだ。対話環境で試してみる。

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

1文字目が数字なら成功し、そうでなければ失敗するパーサを作り、使った。

指定した1文字を読み込むパーサ

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

calc.hs
char :: Char -> Parse Char
char c = check (== c)

(== c)は演算子の部分適用だ。演算子の第1引数のところが空いている。部分適用によって作られた関数に引数をあたえると、その「空いているところ」にはいる。たとえば(== c) 'a'のようにすると、'a' == cとしたのとおなじことになる。つまり、(== c)は引数と値cとを等値比較する関数になる。関数checkに「値cとの等値比較をする関数」をあたえると、指定した1文字cを読み込むパーサになる。対話環境で試してみる。

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

1文字目が指定した文字'a'であるとき、パースは成功し、文字'a'が消費され、文字'a'が結果になる。そうでなければ、パースは失敗する。

ふたつのパーサのうち、どちらか

ふたつのパーサのうちのどちらかで解析するパーサを作る。パーサは「リストをかえす関数」なので、かえされたリストを結合すればいい。

calc.hs
alt :: Parse a -> Parse a -> Parse a
(p1 `alt` p2) inp = p1 inp ++ p2 inp

演算子(++)はリストを結合する。パーサの失敗を空リストとするので、パーサp1が失敗したとき、パーサp2の結果が全体の結果になる。逆も成り立つ。

まえに、演算子は()でかこむと、関数になると説明した。

*Main> 3 + 5
8
*Main> (+) 3 5
8

逆に、2引数関数は``(バッククォート)でかこむと、演算子になる。

*Main> mod 8 3
2
*Main> mod 8 `mod` 3
2

「``(バッククォート)で演算子になる」のは、関数を使うときだけでなく、関数を定義するときにも成り立つ。つまり、関数altの定義は、つぎとおなじことだ。

alt p1 p2 inp = p1 inp ++ p2 inp

「パーサp1とp2とを足し合わせる感じ」を表現したくて、定義にも演算子の構文を使った。対話環境で試してみよう。

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

「文字'a'、または、数字」の1文字をパースするパーサを作り、使った。

パースの結果を加工する

パースした結果の値に関数を適用して、べつの値に変換する関数。

calc.hs
build :: Parse a -> (a -> b) -> Parse b
(p `build` f) inp = [ (f x, r) | (x, r) <- p inp ]

ここで使っているのは、リスト内包表記という構文糖だ。文字列inpに関数pを適用した結果としてリストができる。そのリストの要素すべてに対して、パターン(x, r)を使って、変数x, rを束縛し、式(f x, r)によって新しい値を作っている。対話環境で試してみよう。

*Main> :reload
*Main> (check isDigit `build` digitToInt) "123"
[(1,"23")]

関数digitToIntは数字の1文字を数値に変換する関数だ。check isDigitだけだと、結果は文字'1'になる。それに関数buildを使ってdigitToIntを適用することで、数値の1にしている。

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

ふたつのパーサをつなげる演算子を定義する。

calc.hs
(>@>) :: Parse a -> Parse b -> Parse (a, b)
(p1 >@> p2) inp = [ ((x, y), r') | (x, r) <- p1 inp, (y, r') <- p2 r ]

ここでもリスト内包表記を使っている。パーサp1で解析した結果の残りの文字列rが、パーサp2の引数としてわたされている。パーサp1の複数の結果すべてに対して、パーサp2の複数の結果すべてが計算される。全体の結果として、それぞれのパースの結果の値x, yがタプルとして、まとめられて、それにさらに、パーサp2による解析の残りのr'を追加した。対話環境で試す。

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

文字'a'をパースするパーサと、数字をパースするパーサとをつなげたパーサだ。

つなげたパーサの、かたほうの結果だけを残す

ふたつのパーサをつなげるとき、どちらかのパース結果を捨てたいときがある。たとえば「123,456」のような文字列をパースするとき、,(カンマ)はパースの結果には必要ない。まえの結果と、うしろの結果について、それぞれを残す(他方を捨てる)ような、結合用の関数を定義する。

calc.hs
(>@) :: Parse a -> Parse b -> Parse a
p1 >@ p2 = (p1 >@> p2) `build` fst

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

関数fstとsndは、それぞれ、タプルの第1要素、第2要素を取り出す関数だ。これを関数buildによって、パースの結果に適用している。対話環境で試す。

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

それぞれ、まえの値、うしろの値だけ結果として残る。

文字列のおわりを調べる

文字列のすべてを解析したことを確認するパーサを定義する。

calc.hs
eof :: Parse ()
eof "" = [((), "")]
eof _ = []

型()はユニット型と呼ばれる型であり、値()のみを値とする。情報量は0になる。簡単に言うと、パーサeofにはかえす結果がないということだ。対話環境で試す。

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

解析されていない文字列が残っていれば、パースは失敗する。

まとめ

構文解析に使う基本的な道型を定義した。以下のパーサやパーサをあつかう関数だ。

succeed, check, char, alt, build, (>@>), (>@), (@>)

これらを使って、パーサを組み立てていく。

当日用資料 3/5へ

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?