Comments / Profile of igorkarp / Habr

User

igorkarp May 12 2013 at 18:10

Посмотрел я на приведенный JS код, на то как все в одну кучу смешано, как ошибки во входной строке не обрабатываются, как выражения не оптимизируются. И, в основном с целью с parser combinators поиграться, переписал на Scala. Мухи получились отдельно, котлеты отдельно, потом еще оптимизацию прикрутил.

2-ая задача (Scala)

import scala.util.parsing.combinator._
import scala.util.parsing.input.CharSequenceReader

sealed abstract trait Expr {
  def allStrings: List[String]
  def isLiteral = false
  def isEmpty = false
}
case class Literal(s: String) extends Expr {
  override def allStrings: List[String] = List(s)
  override def isLiteral = true
}
case object Empty extends Expr {
  override def allStrings: List[String] = Nil
  override def isEmpty = true
}
case class Multi(es: List[Expr]) extends Expr {
  override def allStrings: List[String] = es.flatMap(_.allStrings)
}
case class Concat(es: List[Expr]) extends Expr {
  override def allStrings: List[String] = allStrings(List(""), es)

  private def allStrings(prefixes: List[String], es: List[Expr]): List[String] = es match {
    case Nil => prefixes
    case h :: t => allStrings(for (p <- prefixes; s <- h.allStrings) yield p + s, t)
  }
}

trait ExprParsers extends RegexParsers {
  override val skipWhitespace = false

  def literal: Parser[Literal] = """[^{|}]+""".r ^^ { Literal(_) }
  def multi: Parser[Multi] = "{" ~> repsep(cexpr, "|") <~ "}" ^^ { l => Multi(l.distinct) }
  def concat: Parser[Concat] = (mexpr +) ^^ { Concat(_) }
  def cexpr: Parser[Expr] = concat
  def mexpr: Parser[Expr] = literal | multi
}

trait ExprOptParsers extends ExprParsers {
  override def cexpr: Parser[Expr] = super.cexpr ^^ { _ match {
    case Concat(List(x)) => x
    case Concat(l) if l.forall(_.isLiteral) => Literal(l.map(_ match {case Literal(t) => t}).mkString)
    case Concat(l) if l.exists(_.isEmpty) => Empty
    case x => x
  }}
  override def mexpr: Parser[Expr] = super.mexpr ^^ { _ match {
    case Multi(Nil) => Empty
    case Multi(List(x)) => x
    case Multi(l) if l.exists(_.isEmpty) => Empty
    case x => x
  }}
}

object Parser extends ExprOptParsers {
  private lazy val main: Parser[Expr] = phrase(cexpr)
  private def parse(s: String): Expr = main(new CharSequenceReader(s)) match {
    case Success(e, _) => e
    case NoSuccess(m, n) => throw new IllegalArgumentException("Parsing error at " + n.pos + "\n" +
        n.pos.longString + ": " + m)
  }

  def printAll(s: String): Unit = {
    val p = parse(s)
    println(p.allStrings.mkString("\n"))
    println(p)
  }

  def shouldFail(s: String): Unit = {
    try {
      val p = parse(s)
    } catch {
      case e: IllegalArgumentException => println(e.getMessage)
    }
  }

  def main(args: Array[String]): Unit = {
    shouldFail("{")
    shouldFail("}")
    shouldFail("")
    printAll("тест")
    printAll("тест {тест}")
    printAll("{тест} {тест}")
    printAll("{тест {тест}}")
    printAll("{}")
    printAll("{{{{{{{{{{тест {тест}}}}}}}}}}}")
    printAll("{A | B | C} тест")
    printAll("{A | B} {A | B}")
    printAll("{A |A | B} {A | B| B}")
    printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро|мгновенно} случайным образом|менялось каждый раз}.")
    printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро{}|мгновенно} случайным образом|менялось каждый раз}.")
  }
}