2017-10-30

基本的なパーサー

プログラミング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がない。気がする。

2017-10-30

パーサーの型

プログラミング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の結果と、消費されなかった文字列との組である。

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

2017-10-30

パーサーとは (1)

プログラミングHaskellより。

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

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

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

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

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

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

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

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

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

2017-10-29

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

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

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

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

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

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

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

.......

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

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

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

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