プログラミングHaskell 8.10 練習問題

1.

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

  def neg: Parser[Int] = for {
    _ <- symbol("-")
    n <- nat
  } yield -n

  def int: Parser[Int] = neg +++ nat

2.

def comment: Parser[Unit] = for {
    _ <- symbol("--")
    _ <- many(sat(_ != '\n'))
    _ <- char('\n')
  } yield ()

3, 4は構文木を書きづらいから省略

5.

うーむ、たとえば「5」って数字を解析するとき、 - expr '+' expr | termの解析で、exprで解析して、natまでたどり着く => '+'がない => termの解析 ..... - term('+' expr | ε)の解析だと、termで解析して、natまでたどり着く => '+'がない => ε(おわり) って感じで、二度目の解析がなくなる、って感じなのかなあ・・・・

6-1.

注釈に書いてあるけど、右結合なのでこのままだと間違いになっちゃう!

// 1 - 2 - 3 - 4 = 1 - 2 - (3 - 4) = 1 - (2 - (-1)) = 1 - 3 = -2
  def exprBad: Parser[Int] = for {
    t <- term
    e <- (for {
      op <- symbol("+") +++ symbol("-")
      ee <- exprBad
    } yield op match {
      case "+" => t + ee
      case "-" => t - ee
    }) +++ succeed(t)

  } yield e

なので、いったんListにして、foldLeftを使って左結合にする。

  // 1 - 2 - 3 - 4 => 1 List(2, 3, 4) => (1 - 2) List(3, 4) => ((-1) - 3) List(4) => (-4) - 4 = -8 
  def expr: Parser[Int] = for {
    t <- term
    e <- (for {
      _ <- symbol("+")
      ee <- expr
    } yield t + ee) +++ many(for {
      _ <- symbol("-")
      ee <- term
    } yield ee).map(_.foldLeft(t)(_ - _)) +++ succeed(t)
  } yield e

6-2

こちらも同様にfoldLeftで左結合。

def term: Parser[Int] = for {
    f <- factor
    e <- (for {
      _ <- symbol("*")
      ee <- term
    } yield f * ee) +++ many(for {
      _ <- symbol("/")
      ee <- factor
    } yield ee).map(_.foldLeft(f)(_ / _)) +++ succeed(f)
  } yield e

7

BNFはこうなるはず。

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

powはこうかける。ちなみに、termにも修正を入れる必要あり。

def pow: Parser[Int] = for {
   f <- factor
    e <- (for {
      _ <- symbol("^")
      ee <- term
    } yield scala.math.pow(f, ee).toInt) +++ succeed(f)
  } yield e
  println("sample35: " + eval("100 * 2 ^ (2 + 1) ^ 2"))
sample35: 51200

すげえ。

8-a.

左結合の減算だと、BNF

espr ::= expr - nat
nat ::= '0' | '1' | '2' | ...

8-b, 8-c

おかしいけど。無限ループしちゃうし てかこれが問題点?

def wrongSub: Parser[Int] = for {
    e <- wrongSub
    _ <- symbol("-")
    n <- nat
    } yield e - n

8-d

6-1で書いたやつ。。。

プログラミングHaskell 8.10 練習問題

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

  def neg: Parser[Int] = for {
    _ <- symbol("-")
    n <- nat
  } yield -n

  def int: Parser[Int] = neg +++ nat
def comment: Parser[Unit] = for {
    _ <- symbol("--")
    _ <- many(sat(_ != '\n'))
    _ <- char('\n')
  } yield ()

3, 4は構文木を書きづらいから省略

  1. うーむ、たとえば「5」って数字を解析するとき、
  2. expr '+' expr | termの解析で、exprで解析して、natまでたどり着く => '+'がない => termの解析 .....
  3. term('+' expr | ε)の解析だと、termで解析して、natまでたどり着く => '+'がない => ε(おわり) って感じで、二度目の解析がなくなる、って感じなのかなあ・・・・

6-1. 注釈に書いてあるけど、右結合なのでこのままだと間違いになっちゃう!

// 1 - 2 - 3 - 4 = 1 - 2 - (3 - 4) = 1 - (2 - (-1)) = 1 - 3 = -2
  def exprBad: Parser[Int] = for {
    t <- term
    e <- (for {
      op <- symbol("+") +++ symbol("-")
      ee <- exprBad
    } yield op match {
      case "+" => t + ee
      case "-" => t - ee
    }) +++ succeed(t)

  } yield e

なので、いったんListにして、foldLeftを使って左結合にする。

  // 1 - 2 - 3 - 4 => 1 List(2, 3, 4) => (1 - 2) List(3, 4) => ((-1) - 3) List(4) => (-4) - 4 = -8 
  def expr: Parser[Int] = for {
    t <- term
    e <- (for {
      _ <- symbol("+")
      ee <- expr
    } yield t + ee) +++ many(for {
      _ <- symbol("-")
      ee <- term
    } yield ee).map(_.foldLeft(t)(_ - _)) +++ succeed(t)
  } yield e

6-2 こちらも同様にfoldLeftで左結合。

def term: Parser[Int] = for {
    f <- factor
    e <- (for {
      _ <- symbol("*")
      ee <- term
    } yield f * ee) +++ many(for {
      _ <- symbol("/")
      ee <- factor
    } yield ee).map(_.foldLeft(f)(_ / _)) +++ succeed(f)
  } yield e

7 BNFはこうなるはず。

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

powはこうかける。ちなみに、termにも修正を入れる必要あり。

def pow: Parser[Int] = for {
   f <- factor
    e <- (for {
      _ <- symbol("^")
      ee <- term
    } yield scala.math.pow(f, ee).toInt) +++ succeed(f)
  } yield e
  println("sample35: " + eval("100 * 2 ^ (2 + 1) ^ 2"))
sample35: 51200

すげえ。

8-a. 左結合の減算だと、BNF

espr ::= expr - nat
nat ::= '0' | '1' | '2' | ...

8-b, 8-c おかしいけど。無限ループしちゃうし てかこれが問題点?

def wrongSub: Parser[Int] = for {
    e <- wrongSub
    _ <- symbol("-")
    n <- nat
    } yield e - n

8-d 6-1で書いたやつ。。。

プログラミングHaskell 8.8 数式

自然数と加算演算子、乗算演算子、および括弧からなる数式を考える。 加算演算子と乗算子は右結合とし、乗算演算子は加算演算子よりも高い結合順序を持つとする。 「2 + 3 + 4」 は「2 + (3 + 4)」 「2 * 3 + 4」は 「(2 * 3) + 4」 を意味する。

BNFで表していきたい。

expr ::= expr '+' expr | expr '*' expr | '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...

これでは、 +*の結合順位についての条件が含まれないので、 以下のように結合順位ごとに規則を用意して書く。

expr ::= expr '+' expr | term
term ::= term '*' term | factor
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...

さらに、右結合であることを表現するために、以下のように規則を変更する。 これで曖昧さはなくなる。

expr ::= term '+' expr | term
term ::= factor '*' term | factor

簡略化すると、

expr ::= term('+' expr | ε)
term ::= factor('*' term  | ε)
factor ::= '(' expr ')' | nat
nat ::= '0' | '1' | '2' | ...

これを書いていく。 Haskellでは、

expr :: Parser Int
expr = do t <- term
         do symbol "+"
            e <- expr
            return (t + e)
         +++ return t

と書けるようだけど、 Scalaだと以下のようになるのかな・・?

def expr: Parser[Int] = for {
    t <- term
    e <- (for {
      _ <- symbol("+")
      ee <- expr
    } yield t + ee) +++ succeed(t)
  } yield e

同様に、termとfactorについても式を書く。

def term: Parser[Int] = for {
    f <- factor
    e <- (for {
      _ <- symbol("*")
      ee <- term
    } yield f * ee) +++ succeed(f)
  } yield e

  def factor: Parser[Int] = +++(for {
    _ <- symbol("(")
    e <- expr
    _ <- symbol(")")
  } yield e)(nat)

なんとこれだけでできる!!

eval関数も加えて実行。ソースコードはあとで全部まとめて。

  println("sample23: " + eval("2 * 3 + 4"))
  println("sample24: " + eval("2 * (3 + 4)"))
  println("sample25: " + eval("2 * (3+4)"))
  println("sample26: " + eval("4"))
  println("sample27: " + eval("2*3-4"))
sample23: 10
sample24: 14
sample25: 14
sample26: 4
Exception in thread "main" java.lang.Exception: unused expression: -4
....

完成した!シンプル!! なんとなく、ちょっとだけパーサーについて理解が深まった気がした。。。

別話だけど、ParserOpsのimplicit conversionをExpressionオブジェクトの中かから使いたかったけど、最初うまく使えなかった。 ExpressionオブジェクトでParsersオブジェクトの中にあるimplicit conversion使いたかったら、ParsersオブジェクトをExpressionオブジェクトよりも上に書かなきゃいけないと。ふむ

プログラミングHaskell 8.7 空白の扱い

実用的なパーサーは、入力文字列中の「トークン」の前後に任意の空白を許す。...(中略)...あるトークンのパーサーを適用する際、前後の空白を無視する部品を定義する。

  def token[A](p: Parser[A]): Parser[A] = for {
    _ <- space
    v <- p
    _ <- space
  } yield v

tokenを利用すると、前後の空白を無視するパーサーを定義するのが簡単になる。

  def identifire: Parser[String] = token(ident) // 前後の空白を無視する識別子のパーサー
  def natural: Parser[Int] = token(nat) // 前後の空白を無視する自然数パーサー
  def symbol(xs: String): Parser[String] = token(string(xs)) // 前後の空白を無視する特定の文字列パーサー

自然数のリストを解析するパーサー。

def naturalList: Parser[List[Int]] = for {
    _ <- symbol("[")
    n <- natural
    ns <- many(for {
      _ <- symbol(",")
      nn <- natural
    } yield nn)
    _ <- symbol("]")
  } yield (n :: ns)

実行。

  println("sample21: " + parse(naturalList)(" [1, 2, 3] "))
  println("sample22: " + parse(naturalList)("[1, 2,]"))
sample21: List((List(1, 2, 3),))
sample22: List()

ほう!!

プログラミング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))

今日のところまで。