プログラミング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で書いたやつ。。。