Scala парсеры Packrat, сообщения об ошибках и прозрачность ссылок - PullRequest
Новая
       12

Scala парсеры Packrat, сообщения об ошибках и прозрачность ссылок

4 голосов
/ 22 февраля 2020

Я пытаюсь разобрать логические выражения в дерево Expr, используя парсеры Packrat Scala из scala-parser-combinators. 

  sealed trait Expr
  case class Term(term: String) extends Expr
  case class And(x: Expr, y: Expr) extends Expr
  case class Or(x: Expr, y: Expr) extends Expr

aaa and bbb          --> And(Term(aaa),Term(bbb))
aaa and bbb or ccc   --> Or(And(Term(aaa),Term(bbb)),Term(ccc))
aaa and (bbb or ccc) --> And(Term(aaa),Or(Term(bbb),Term(ccc)))

Эта грамматика, кажется, работает отлично: 

object Parsing extends RegexParsers with PackratParsers {

  override val skipWhitespace = false

  val validIdentifiers = List("aaa", "bbb", "ccc", "ddd")

  lazy val term: PackratParser[Term] = """\s*""".r ~> """\w+""".r flatMap { identifier =>
    if (validIdentifiers.contains(identifier))
      success(Term(identifier))
    else
      err(s"expected one of: $validIdentifiers")
  }

  lazy val and: PackratParser[And] =
    expr ~ """\s+and\s+""".r ~ (term | parensExpr) ^^ { case e1 ~ _ ~ e2 => And(e1, e2) }

  lazy val or: PackratParser[Or] =
    expr ~ """\s+or\s+""".r ~ (term | parensExpr) ^^ { case e1 ~ _ ~ e2 => Or(e1, e2) }

  lazy val parensExpr: PackratParser[Expr] = """\s*\(""".r ~> expr <~ """\s*\)""".r

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(expr)

  def parseExpr(input: String): ParseResult[Expr] =
    parse(root, new PackratReader(new CharSequenceReader(input)))
}

Но сообщения об ошибках иногда .... плохие. Если синтаксический анализатор найдет неверный идентификатор в левой части and, он правильно скажет нам об этом. 

println(parseExpr("invalidIdentifier and aaa"))


[1.18] error: expected one of: List(aaa, bbb, ccc, ddd)
invalidIdentifier and aaa
                 ^

Но если он найдет неверный идентификатор в справа со стороны and, это даст нам это вводящее в заблуждение сообщение об ошибке. 

println(parseExpr("aaa and invalidIdentifier"))

[1.4] failure: end of input expected
aaa and invalidIdentifier
   ^

Я почти уверен, что это произойдет, потому что expr попробует все 4 варианта: and / or / parensExpr потерпит неудачу, но term удастся, просто набрав Term("aaa").

Затем root phrase включится и проверит, есть ли еще вход для потреблять и терпеть неудачу, потому что есть: «и invalidIdentifier».

Так что я подумал, что я буду pu sh phrase на один уровень ниже. Другими словами, я изменил это: 

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(expr)

На это: 

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(term) ||| phrase(and) ||| phrase(or) ||| phrase(parensExpr)

Теперь все 4 параметра должны потерпеть неудачу, но мы должны увидеть сообщение об ошибке and, потому что and потреблял больше входных данных, чем другие 3 опции

Теперь я получаю более качественные сообщения об ошибках, НО, к моему удивлению, некоторые ранее действительные входные данные теперь недействительны! 

println(parseExpr("aaa or bbb"))

[1.4] failure: string matching regex '\s+and\s+' expected but ' ' found
aaa or bbb
   ^

println(parseExpr("aaa and bbb or ccc"))

[1.12] failure: end of input expected
aaa and bbb or ccc
           ^

Я не понимаю, почему.

На самом деле, даже простое, тривиальное изменение, такое как это: 

  // before
  lazy val root: PackratParser[Expr] =
    phrase(expr)

  // after
  lazy val root: PackratParser[Expr] =
    phrase(term ||| and ||| or ||| parensExpr)

... ломает ранее действительные входные данные.

Как получилось? Разве эти два определения root не должны быть эквивалентными? Разве эти парсеры не являются прозрачными по ссылкам?

Что более важно, как мне go исправить это?

1 Ответ

0 голосов
/ 03 марта 2020

У меня следующие ошибки с точным кодом, который вы опубликовали. Я полагаю, что это ожидаемые сообщения об ошибках? библиотека: 

import $ivy.`org.scala-lang.modules::scala-parser-combinators:1.1.2`

Может быть, проблема с версией библиотеки?

...