プログラミングHaskell 8.6 パーサーの部品

述語pを満足する一文字用のパーサー sat p を定義する。

def sat(p: Char => Boolean): Parser[Char] = {
    item.flatMap(x => p(x) match {
      case true => succeed(x)
      case false => failure
    })
  }

これを使えば、数字・アルファベットとかのパーサーも。

  def digit: Parser[Char] = sat(_.isDigit)
  def lower: Parser[Char] = sat(_.isLower)
  def upper: Parser[Char] = sat(_.isUpper)
  def letter: Parser[Char] = sat(_.isLetter)
  def alphanum: Parser[Char] = sat(_.isLetterOrDigit)
  def char(x: Char): Parser[Char] = sat(_ == x)

実行。

  println("sample9: " + parse(digit)("123"))
  println("sample10: " + parse(digit)("abc"))
  println("sample11: " + parse(char('a'))("abc"))
  println("sample12: " + parse(char('a'))("123"))
sample9: List((1,23))
sample10: List()
sample11: List((a,bc))
sample12: List()

パーサーcharを使って string xsを定義。

 def string(s: String): Parser[String] = s.toList match {
    case Nil => succeed("")
    case x :: xs => for {
      _ <- char(x)
      _ <- string(xs.mkString)
    } yield (x :: xs).mkString
  }

実行。

  println("sample13: " + parse(string("abc"))("abcdef"))
  println("sample14: " + parse(string("abc"))("ab1234"))
sample13: List((abc,def))
sample14: List()

次の二つのパーサー many pmany1 p は、パーサーpを失敗するまでできるだけ多く適用し、適用が成功した結果をリストにして返す。

相互再帰になってる。自分で発想できなそう・・・・

  def many1[A](p: Parser[A]): Parser[List[A]] = for {
    v <- p
    vs <- many(p)
  } yield (v :: vs)
  def many[A](p: Parser[A]): Parser[List[A]] = many1(p) +++ succeed(Nil)

実行。

  println("sample15: " + parse(many(digit))("123abc"))
  println("sample16: " + parse(many(digit))("abcdef"))
  println("sample17: " + parse(many1(digit))("abcdef"))
sample15: List((List(1, 2, 3),abc))
sample16: List((List(),abcdef))
sample17: List()

パーサー manymany1を使うと、「識別子(変数名)」のパーサーを定義できる。識別子は、小文字で始まり、0個以上のアルファベット文字か数字文字が続く。数字文字が一つ以上繰り返される「自然数」のパーサーや、空白文字やタブ文字、あるいは改行文字が一つ以上繰り返される「空白」のパーサーも定義できる。

本文では readって関数が使われてるけど、これはキャストする関数っぽい。この(本文の)場合だと、型推論からIntってことがわかるからキャスト先は省略されてるのかな。。Scalaではxsは List[Char]だから、 mkStringでStringにして、 toIntでキャスト。

  def ident: Parser[String] = for {
    x <- lower
    xs <- many(alphanum)
  } yield (x :: xs).mkString

  def nat: Parser[Int] = for {
    xs <- many1(digit)
  } yield xs.mkString.toInt

  def space: Parser[Unit] = for {
    _ <- many(sat(_.isSpaceChar))
  } yield(())

実行。

  println("sample18: " + parse(ident)("abc def"))
  println("sample19: " + parse(nat)("123 abc"))
  println("sample20: " + parse(space)(" abc"))
sample18: List((abc, def))
sample19: List((123, abc))
sample20: List(((),abc))

だんだんわかってきた!きがする!!!many, many1すごい。

プログラミングHaskell 8.5 選択

だいぶ間があいたけど、引き続き。

パーサーを結合させるもう一つの自然な方法は、一番目のパーサーを入力文字列に適用し、もし失敗したら、代わりに二番目のパーサーを適用することである。

+++(「または」と読む)を定義する。

def +++[A](p: Parser[A])(q: Parser[A]): Parser[A] = (inp: String) =>
    parse(p)(inp) match {
      case List() => parse(q)(inp)
      case List((v, out)) => List((v, out))
    }

実行。

object Main extends App {
  ...
  println("sample7: "  + parse(+++(item)(succeed('d')))("abc"))
  println("sample8: "  + parse(+++(failure)(succeed('d')))("abc"))
}
sample7: List((a,bc))
sample8: List((d,abc))

プログラミングHaskell 8.4 連結

ひきつづきプログラミングHaskellScalaで書き換えつつ読んでいきます。

おそらく、二つのパーサーを組み合わせる最も単純な方法は、一方の後に他方を適用することだろう。一番目のパーサーの返す出力文字列が、二番目のパーサーの入力文字列となる。 連結演算子>>=(そして)を用いて、結果を処理する形でパーサーを連結させる方が経験上便利だ。

これは、flatMapのシグネチャだ!

//  def >>=[A, B]: Parser[A] => Parser[B] => Parser[(A, B)]
def >>=[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B] = (inp: String) =>
  parse(p)(inp) match {
    case List() => List()
    case List((v, out)) => parse(f(v))(out)
  }

とここから、本の中ではdo記法を使っていくわけなのですが、ここまでの状態でfor文を書くと、以下のようになりますが、

// 動かない
def p = for {
    x <- item
    _ <- item
    y <- item
  } yield (x, y)
Error:(50, 10) value flatMap is not a member of Parsers.Parser[Char]
    x <- item

Parser型にflatMapやmapを定義していないためにコンパイルできません。ここではParserはtypeで宣言しただけであって、それにflatMapをもたせる....?よくわからないけど、FPinScalaで見たことのある方法で可能そう....!(後ほど書いてあります)。

ここではfor式を展開したバージョンを書いて、本についていきます。

// ずるいけど、mapを書きます
def map[A, B](p: Parser[A])(f: A => B): Parser[B] = (inp: String) =>
    parse(p)(inp) match {
      case Seq() => Seq()
      case Seq((v, out)) => Seq((f(v), out))
    }

def p: Parser[(Char, Char)] =
  >>=(item)((c: Char) =>
    >>=(item)((_: Char) =>
      map(item)((ccc: Char) => (c, ccc))
    )
  )

以下のコードで実行します。

object Main extends App {
  ....
  println("sample5: " + parse(p)("abcdef"))
}
sample5: List(((a,c),def))

確かに答えが得られています。何が起こっているんだ・・・・当てられる文字列の情報(今回の実行であれば"abcdef")がpというメソッドでは一切でてこないのに、うまくいっている...?いつ消費されて、いつ返されているんだ。。。Stateモナドと呼ばれる類のやつなんだろうけど、不思議すぎる〜〜〜どうなってるか、を考えずに、flatMap(>>=)では、次に渡されているんだと無心で思って次に進んでいきたいと思います。


ちなみに、Scalaで上のやつをfor式で書けるようにするには以下のようにします。ParserはParserOpsへ自動的(暗黙的に)変換され、ParserOpsが持っているメソッドを使うことができます。定義はParsersオブジェクトに配置して、それらの定義をParserOpsから呼び出します。(説明あってるカナ)

object Parsers { self =>
  type Parser[T] = (String) => Seq[(T, String)]
  ....
  // 上で書いた map とか >>= 書く
  ....
  implicit def parserOps[T](p: Parser[T]) = ParserOps(p)
  case class ParserOps[T](p: Parser[T]) {
    def flatMap[S](f: T => Parser[S]): Parser[S] =
      self.>>=(p)(f)
    def map[S](f: T => S): Parser[S] =
      self.map(p)(f)
  }
  
  def pp: Parser[(Char, Char)] = for {
    x <- item
    _ <- item
    y <- item
  } yield(x, y)
}

以下のコードで実行。

object Main extends App {
  ....
  println("sample6: " + parse(pp)("abcdef"))
}
sample6: List(((a,c),def))

今日のところまで。

基本的なパーサー

プログラミングHaskellより。

ここで、他のパーサーを構築するのに利用する基本的なパーサー三つを定義しよう。

ちょっと本の表記から変えます。

  • return予約語なので、メソッド名をreturn -> succeedにします。

  • String => List[Char]への変換は明示的に行う(Stringにunapplyメソッドがないからパターンマッチが行われてなさそう)*1

// def succeed[T]: T => Parser[T]
// def failure[T]: Parser[T]
// def item: Parser[Char]

def succeed[T](t: T) = (inp: String) => Seq((t, inp))
def failure[T] = (inp: String) => Seq()
def item = (inp: String) => inp.toList match {
  case List() => Seq()
  case x :: xs => Seq((x, xs.toString))
}

こんな感じだろうか.....

パーサーは関数なので、通常の関数適用を使って、パーサーを文字列へ適用できる。 しかし、パーサーの実現方法を抽象化して、独自の適用関数を定義するほうが望ましい

わからない!どうしてそっちのが望ましいんだろう。。

//  def parse[T]: Parser[T] => String => Seq[(T, String)]
def parse[T](p: Parser[T])(inp: String): Seq[(T, String)] = p(inp)

どう振る舞うのかの例を示す。

以下のように書いたScalaプログラムを動かしてみます。

object Main extends App {
  import Parsers._
  println("sample1: " + parse(succeed(1))("abc"))
  println("sample2: " + parse(failure)("abc"))
  println("sample3: " + parse(item)(""))
  println("sample4: " + parse(item)("abc"))
}

object Parsers {
  type Parser[T] = (String) => Seq[(T, String)]

  def succeed[T](t: T) = (inp: String) => Seq((t, inp))
  def failure[T] = (inp: String) => Seq()
  def item = (inp: String) => inp.toList match {
    case List() => Seq()
    case x :: xs => Seq((x, xs.mkString))
  }
  def parse[T](p: Parser[T])(inp: String): Seq[(T, String)] = p(inp)
}

結果。

sample1: List((1,abc))
sample2: List()
sample3: List()
sample4: List((a,bc))

早速心が折れてしまいそうだけどw、少しずつ続けよう。

*1:"hoge".foreach(println)が可能なのは、Predef内でscala.collection.immutable.StringOpsに暗黙的に変換されており、StringOpsがいろいろ持っているため。ここにもunapplyがない。気がする。

パーサーの型

プログラミングHaskellより。 でもScalaで書いてみます。

適切な構文木の型Treeが与えられたとすると、パーサーはString -> Treeを持つ関数として表現できる。

type Parser = String => Tree

しかし、一般的にはパーサーがすべての文字列を使い切るとは限らない。 このため、消費しなかった文字列を返すように、パーサーの型を拡張する。

type Parser = String => (Tree, String)

同様に、構文の解析は常に成功するとは限らない。 失敗を扱えるように、パーサーの型をさらに拡張して、結果のリストを返すようにする。

Maybeを使えるって書いてあるけど、本のとおり、Seqでいきます。

type Parser = String => Seq[(Tree, String)]

最後に、パーサーが異なれば、異なる構文木を返すだろう。たとえば、数値パーサーは整数を返すだろう。そこで、返り値の型がTreeに限定されているのを抽象化し、型Parserの型変数にすると便利だ。

Scala的にはジェネリクス(って呼ばないのかな?)を使ってみます。

type Parser[T] = (String) => Seq[(T, String)]

リストの要素は、型Tの結果と、消費されなかった文字列との組である。

しょうじき、ここらへんで、どんな感じで返ってくるってこと????というのが想像が追いつきません。が次に進んでみます。

パーサーとは (1)

プログラミングHaskellより。

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

曖昧さをなくすってのが大事なんだろう。

たとえば、文字列 "2 * 3 + 4"が与えられたとき、数式のパーサーは以下のような形の構文木を生成するだろう。

    +
   / \
  *   4
 / \ 
2  3

この構文木の構造から、演算子+とは二つの引数をとり、+よりもの結合順位の方が高いことが明らかである。

この構文木をどうやって型(クラス)で表現するかも大事そう。

ほとんどの実用的なプログラムは、入力をあらかじめ処理するためにパーサーを使うので、パーサーはコンピュータの重要な分野だ。たとえば、電卓プログラムは数式を評価する前に構文を解析し、HugsHaskellのプログラムを実行する前に構文を解析し、また、Webブラウザはハイパーテキスト文書を表示する前に構文を解析する。

すごいすごい、解析しまくりだ。

入力の構造を明確にしておけば、以降の処理が格段に簡単になる。

たしかに!現実世界から、プログラミングの世界に移すにはすべてパーサーが必要そう!

パーサーを書けるようになりたい

パーサーを書けるようになりたい、と思いました。 JSONとかxmlとかcsvとか。

以下のようなことをフワ〜っと思っていました。

  • 社会人になって2年半、もうプログラミング歴も同じだけ経ったから(やばい)、なにか動くものを作りたい。
    • 全く新しいものを作るってのはまだ僕には無理そう。思いつかないし、腰も思い・・・車輪の再発明になるけど、いつも使えるようなツールを作ろう。
  • インフラよりも、アプリケーションロジックを重視したい。
    • ちょっと難しそうなやつをできるようになりたい。
  • 関数型プログラミングに通じるものがいい。

そういえば、JSON, xml,...とか整形ツールってよく使うな〜、

日常の開発でもJSONパーサー使うな〜、

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方 を読んでいたら、コンパイラにもパーサーって使われてんだな〜、

.......

あれ、パーサーってちょうどよさそう!と思いました。

  • パーサーを書くには関数型プログラミングのメリットが十分に活かせる(らしい)
  • FPinScala でJSONパーサーの章を読んで、全くわからないw ので、僕にはレベル高い。

ってことで、 なんとかして年内には、いちばん単純な 文字列=>JSONオブジェクト に解釈できるJSONパーサーが書けるように努力してみよう! ってことでブログを書くことにしました。

できるかな...(^_^;A