Как реализовать монадический анализ? - PullRequest
Новая
       10

Как реализовать монадический анализ?

3 голосов
/ 09 июня 2019

Я застрял в понимании того, как работает Монада.

1 Ответ

1 голос
/ 10 июня 2019

Обычно, когда мы говорим "монадический синтаксический анализ", мы имеем в виду сделать Parser монадой.Мы пишем 

class Parser[+A] { ... }

A Parser[A] принимает входные данные и возвращает проанализированный A, или может произойти сбой, или, возможно, останется какой-то ввод.Давайте сделаем это по-настоящему простым: Parser[A] принимает List[Char], а Option союзник возвращает A, а оставшиеся List[Char]. 

case class Parser[+A](parse: List[Char] => Option[(A, List[Char])]) {
  def accepts(l: List[Char]): Boolean
    = parse(l).map(_._2.isEmpty).getOrElse(false)
  // do not bother with the List('#') stuff
}

Вы создаете Parserиспользуя комбинаторы.a.flatMap(b) - это синтаксический анализатор, который соответствует a, за которым следуют b

// case class Parser[+A](...) {
  def flatMap[B](f: A => Parser[B]): Parser[B] = Parser { input =>
    parse(input).flatMap { case (x, midput) => f(x).parse(midput) }
  }
// }

и Parser.unit(x) возвращает x без использования какого-либо ввода, поэтому Monad важно.Вы также должны иметь map, который изменяет возвращаемое значение без изменения того, что соответствует.Вам также нужен комбинатор для чередования.Я оставлю их для реализации. 

object Parser {
    def unit[T](x: T): Parser[T] = ???
}
// case class Parser[+A](...) {
    def map[B](f: A => B): Parser[B] = ???

    // left-biased greedy: if this parser succeeds (produces Some) then
    // that parser is never tried (i.e. no backtracking)
    // replacing Option with Seq is the easiest way to get backtracking
    // but we don't need it to define S
    def orElse[B](that: Parser[B]): Parser[Either[A, B]] = ???
// }

Вы также хотите, чтобы некоторые базовые Parser s строили из них более сложные.Parser.char(x) соответствует одному символу x и не возвращает ничего полезного. 

// object Parser {
  def char(c: Char): Parser[Unit] = Parser {
    case x :: rest if c == x => Some(((), rest))
    case _ => None
  }
// }

Тогда вы можете определить S довольно естественным образом.Вы даже можете заставить синтаксический анализатор возвращать Int для того, сколько a с / сколько b с было сопоставлено: 

lazy val S: Parser[Int]
  = (for { _ <- Parser.char('a')
           i <- S
           _ <- Parser.char('b')
         } yield (i + 1)).orElse(Parser.unit(0)).map(_.merge)
// i.e
lazy val S: Parser[Int]
  = Parser.char('a').flatMap { _ =>
      S.flatMap { i =>
        Parser.char('b').map { _ =>
          i + 1
        }
      }
    }.orElse(Parser.unit(0)).map(_.merge)

S.accepts("".toList) // true
S.accepts("aaabbb".toList) // true
S.accepts("aaa".toList) // false
S.accepts("bbbaaa".toList) // false

Вам не нужно перемещать List[Char] вопределение S, потому что написанные нами комбинаторы делают это за вас, оставляя позади только логику самой грамматики.

...