Parser Combinator
Graham Hutton 氏の『プログラミング Haskell』 第8章 関数型パーサーを Groovy で書く。
Page Redirection にコードがあるがテキストとは少し違う。
Parser で扱う補助的な関数を定義する
- Closure を Parser として扱うので Parser 自体は定義しない
- Just は単にタプルのファクトリメソッドで Haskell の Maybe の実装ではない*1
- Groovy では Haskell と違い String と List
は別物なので同じ様に扱うための関数を定義する*2
class Parsers { // Parser<A> = { String -> Maybe<A, String> } // parse = { Parser<A>, String -> A } static def parse(Closure p, inp) { p.call(inp) } // Maybe<A, String> static def Just = { v, inp -> [v, inp] } static def Nothing = null // (v, out) = { Maybe<A, String> -> [A, String] } static def valueOf = { it == Nothing ? [] : it } // cons = { Character, String -> String } // cons = { Character, List<Character> -> String } // cons = { A, List<A> -> List<A> } static def cons(x, xs) { x instanceof Character ? "$x${xs as char[]}" : [x, *xs] } // { String -> char } // { List<A> -> A } static def head(String xs) { xs.charAt(0) } static def head(List xs) { xs.head() } // { String -> String } // { List<A> -> List<A> } static def tail(String xs) { xs.substring(1) } static def tail(List xs) { xs.tail() } // Error // pred ? value : error (msg) のように記述するため void ではない static def error(String msg) { assert false, msg } } import static Parsers.*
タプル
タプルはリストで代用するが 1.8 からタプルは簡単に定義できるみたいだ。
import groovy.transform.* @ToString @EqualsAndHashCode @TupleConstructor class Pair<A, B> { A _1 B _2 def getAt(int i) { "get_${i+1}"() } } static def Just = { v, inp -> new Pair(v, inp) }
Parser のための演算子を定義する
use でなく mixin を使用するのはスクリプトのトップレベルに記述するため。*3
>>>
- Haskell では >>=
- Parser と次の Parser を返す関数を直列に連結する
- 関数は最初の Parser の生成した値を参照できる
>>
- Haskell でも >>
- Parser と次の Parser を直列に連結する
- テキストにはでてこない
|
- テキストでは +++
- Parser と Parser を並列に連結する
- 演算子の優先順位は >>> より低い
class ParserOps { static def bind(Closure p, Closure f) { { inp -> def m = parse(p, inp) def (v, out) = valueOf(m) m == Nothing ? Nothing : parse(f(v), out) } } // (>>>) = { Parser<A>, { A -> Parser<B> } -> Parser<B> } static def rightShiftUnsigned(Closure p, Closure f) { bind(p, f) } // (>>) = { Parser<A>, Parser<B> -> Parser<B> } static def rightShift(Closure p, Closure q) { bind(p, { q }) } // (|) = { Parser<A>, Parser<A> -> Parser<A> } static def or(Closure p, Closure q) { { inp -> parse(p, inp) ?: parse(q, inp) } } } Closure.mixin(ParserOps)
準備が整ったので、テキストにしたがって記述していく。
再帰が書きやすいように定義はすべて変数ではなくスクリプトのプロパティにする。
基本的なパーサ
- return_ は引数を返す Parser を生成する
- failure は必ず失敗する Parser である
- item は入力があれば 1文字削り取って返す Parser である
- 他の Parser はこの 3つを ParserOps で定義した演算子で組合せて定義する
// { A -> Parser<A> } return_ = { v -> { inp -> Just (v, inp) } } // Parser<Character> failure = { inp -> Nothing } item = { inp -> !inp ? Nothing : Just (head (inp), tail (inp)) } assert parse (return_(1), "abc") == Just (1, "abc") assert parse (failure, "abc") == Nothing assert parse (item, "") == Nothing assert parse (item, "abc") == Just ('a', "bc")
連結
テキストでは bind ではなく do 式で記述されている。*4
// Parser<Tuple<Character, Character>> p = item >>> { x -> item >>> { item >>> { y -> return_([x,y]) } } } assert parse (p, "abcdef") == Just (['a', 'c'], "def") assert parse (p, "ab") == Nothing
選択
assert parse (item | return_('d'), "abc") == Just('a', "bc") assert parse (failure | return_('d'), "abc") == Just('d', "abc") assert parse (failure | failure, "abc") == Nothing
パーサーの部品
// { { Character -> Boolean } -> Parser<Character> } sat = { p -> item >>> { x -> p(x) ? return_(x) : failure } } // Parser<Character> digit = sat (Character.&isDigit) lower = sat (Character.&isLowerCase) upper = sat (Character.&isUpperCase) letter = sat ({ it ==~ /[a-zA-Z]/ }) alphanum = sat ({ it ==~ /[a-zA-Z0-9]/ }) char_ = { x -> sat { it == x } } assert parse (digit, "123") == Just ('1', "23") assert parse (digit, "abc") == Nothing assert parse (char_('a'), "abc") == Just ('a', "bc") assert parse (char_('a'), "123") == Nothing // { String -> Parser<String> } string = { s -> !s ? return_(s) : // return_("") char_ (head (s)) >>> { string (tail (s)) >>> { return_(s) } } } assert parse (string("abc"), "abcdef") == Just ("abc", "def") assert parse (string("abc"), "ab1234") == Nothing // { Parser<A> -> Parser<List<A>> } many = { p -> many1(p) | return_([]) } many1 = { p -> p >>> { v -> many(p) >>> { vs -> return_(cons (v,vs)) } } } assert parse (many (digit), "123abc") == Just ("123", "abc") assert parse (many (digit), "abcdef") == Just ([], "abcdef") // [] -> "" assert parse (many1 (digit), "abcdef") == Nothing // Parser<String> ident = lower >>> { x -> many (alphanum) >>> { xs -> return_(cons (x, xs)) } } nat = many1 (digit) >>> { xs -> return_(xs.toInteger()) } space = many (sat (Character.&isWhitespace)) >>> { return_(null) } assert parse (ident, "abc def") == Just ("abc", " def") assert parse (nat, "123 abc") == Just (123, " abc") assert parse (space, " abc") == Just (null, "abc")
空白の扱い
// { Parser<String> -> Parser<String> } token = { p -> space >>> { p >>> { v -> space >>> { return_(v) } } } } // Parser<String> identifier = token (ident) natural = token (nat) symbol = { xs -> token (string (xs)) } assert parse (token (natural), "123 ") == Just (123,"") // Parser<List<Integer>> p = symbol("[") >>> { natural >>> { n -> many (symbol(",") >>> { natural }) >>> { ns -> symbol("]") >>> { return_(cons (n, ns)) } } } } assert parse(p, " [1, 2, 3] ") == Just ([1,2,3],"") assert parse(p, "[1, 2,]") == Nothing
数式
// fact = ( expr ) | natural // term = fact { * term } // expr = term { + expr } // Parser<Integer> factor = symbol("(") >>> { expr >>> { e -> symbol(")") >>> { return_(e) } } } | natural term = factor >>> { f -> symbol("*") >>> { term >>> { t -> return_(f * t) } } | return_(f) } expr = term >>> { t -> symbol("+") >>> { expr >>> { e -> return_(t + e) } } | return_(t) } // { String -> Integer } eval = { xs -> def m = parse (expr, xs) def (n, out) = valueOf(m) m == Nothing ? error ("invalid input") : out ? error ("unused input " + out) : n } assert eval ("2*3+4") == 10 assert eval ("2*(3+4)") == 14 assert eval ("2 * (3 + 4)") == 14
ここから練習問題の内容
left-factorising
数式の expr は次のようにも書ける。
2*(3+4) を実行すると 3+4 が 2回表示される。
// expr = term + expr | term expr = term >>> { t -> symbol("+") >>> { expr >>> { e -> println "$t + $e" return_(t + e) } } } | term
これは term だけで一致してしまうために起こる。
// term を展開する
term = fact * term
= fact * fact
= fact * (expr)
= fact * (term + expr)
= natural * (natural + natural)
- term に一致するので term + expr は失敗する
- 再度、term が呼び出され今度は成功する
さらに、term = fact * term | fact と定義すると 2 * 2 で計 4 回呼び出されることになる。
同じ Parser から始まる処理が or で並列になっている場合に括り出すことが left-factorising。
memoize
left-factorising を行えば呼び出し回数は減るが、複数回呼び出されても処理を行わなければ同じはず。
Groovy 1.8 から Closure は標準でメモ化できる。Parser は副作用がない関数なのでメモ化してしまえば 1 回しか呼び出されなくなる。
expr = expr.memoize()
左結合
数式の演算を - で行うと右結合になっているため計算結果が正しくない。
expr = (term - (term - (term - ...)))
左結合にするには expr で再帰せずに many を用いて演算をまとめて行う。
expr = term >>> { t -> many (symbol("-") >> term) >>> { es -> return_(es.inject(t) { acc, v -> acc - v }) } | return_(t) }
Groovy では逆に演算が単純にメソッド呼び出しに置き換えられるので左結合になる。
2 ** 1 ** 0 // 1 : Groovy => 2.power(1).power(0) 2 ** 1 ** 0 // 2 : Ruby
