Scala Combinators JavaTokennParsers 预期为 '||' 但找到 '>'

Question

当我运行这个测试时:

import com.dvMENTALmadness.parsers.{BinaryOp, ExprType, Number, SimpleEquationParser}
import org.scalatest.FlatSpec

class SimpleEquationParserTest extends FlatSpec {
  "(1+2) > (3+4)" should " == false" in {
    val result = SimpleEquationParser("(1+2) > (3+4)")
    println(result)
    assert( result == Right(BinaryOp(">",BinaryOp("+",Number(1.0),Number(2.0),ExprType.Num),BinaryOp("+",Number(3.0),Number(4.0),ExprType.Num),ExprType.Bool)) )
  }
}

我得到:

Left("`||' expected but `>' found") did not equal Right(BinaryOp(>,BinaryOp(+,Number(1.0),Number(2.0),Num),BinaryOp(+,Number(3.0),Number(4.0),Num),Bool))

如果我将表达式更改为 ((1+2) > (3+4)) 它可以工作，但我需要能够支持可选的括号。有什么建议么？以下是类定义和日志跟踪:

package com.dvMENTALmadness.parsers

import com.dvMENTALmadness.parsers.ExprType.ExprType
import scala.util.parsing.combinator.{JavaTokenParsers, PackratParsers}

sealed trait Expr
sealed trait Var extends Expr {
  def key: String
}
object ExprType extends Enumeration {
  type ExprType = Value
  val Var, Num, Text, Bool = Value
}

case class Text(value: String) extends Expr
case class Number(value: Double) extends Expr
case class Bool(value: Boolean) extends Expr
case class NumericVar(key: String) extends Var
case class TextVar(key: String) extends Var
case class BoolVar(key: String) extends Var
case class AnyVar(key: String) extends Var
case class UnaryOp(operator: String, arg: Expr, expType: ExprType) extends Expr
case class BinaryOp(operator: String, left : Expr, right: Expr, expType: ExprType)  extends Expr

trait ExprParser extends JavaTokenParsers with PackratParsers {

  def foldExpr(etype: ExprType)(pat: Expr ~ List[String ~ Expr]) : Expr = pat match {
    case left ~ xs => xs.foldLeft(left)((left, acc) => acc match {
      case op ~ right => BinaryOp(op, left, right, etype)
    })
  }

  // see: http://jim-mcbeath.blogspot.com/2011/07/debugging-scala-parser-combinators.html
  implicit def toLogged(name: String) = new {
    def !!![T](p:Parser[T]) = log(p)(name) // for debugging
    //def !!![T](p:Parser[T]) = p         // for production
  }
}

trait BoolParser extends ExprParser {

  // Operator precedence: http://www.tutorialspoint.com/scala/scala_operators.htm
  def expr = "expr" !!! bool_expr | num_expr | text_expr
  def bool_expr = "bool_expr" !!! or | bool_term
  def num_expr = "num_expr" !!! num_equality | num_term
  def text_expr = "text_expr" !!! text_equality

  // operations
  def or = "or" !!! and ~ rep("||" ~ and) ^^ foldExpr(ExprType.Bool)
  def and = "and" !!! equality ~ rep("&&" ~ equality) ^^ foldExpr(ExprType.Bool)

  def equality = "equality" !!! bool_equality | num_equality | text_equality
  def bool_equality = "bool_equality" !!! bool_term ~ rep("==" ~ bool_term | "!=" ~ bool_term) ^^ foldExpr(ExprType.Bool)
  def num_equality = "num_equality" !!! relational ~ rep("==" ~ relational | "!=" ~ relational) ^^ foldExpr(ExprType.Num)
  def text_equality = "text_equality" !!! concat ~ rep("==" ~ concat | "!=" ~ concat) ^^ foldExpr(ExprType.Text)

  def relational = "relational" !!! additive ~ rep(">=" ~ additive | "<=" ~ additive | ">" ~ additive | "<" ~ additive) ^^ foldExpr(ExprType.Num)
  def additive = "additive" !!! multiplicative ~ rep("+" ~ multiplicative | "-" ~ multiplicative) ^^ foldExpr(ExprType.Num)
  def multiplicative = "multiplicative" !!! num_term ~ rep("*" ~ num_term | "/" ~ num_term | "%" ~ num_term) ^^ foldExpr(ExprType.Num)
  def concat = "concat" !!! text ~ rep("+" ~ text) ^^ foldExpr(ExprType.Text)

  def operators = "*" | "/" | "%" | "+" | "-" | "&&" | "||"

  // terms
  def term = "term" !!! bool_term | num_term
  def bool_term = "bool_term" !!! bool | bool_parens | not
  def num_term = "num_term" !!!  num | num_parens | neg

  def not:PackratParser[Expr] = "not" !!! "!" ~> bool_term ^^ (x => UnaryOp("!", x, ExprType.Bool))
  def neg:PackratParser[Expr] = "neg" !!! "-" ~> num_term ^^ (x => UnaryOp("-", x, ExprType.Num))

  def parens:PackratParser[Expr] = "parens" !!! "(" ~> expr <~ ")"
  def bool_parens:PackratParser[Expr] = "bool_parens" !!! "(" ~> bool_expr <~ ")"
  def num_parens:PackratParser[Expr] = "num_parens" !!! "(" ~> num_expr <~ ")"
  def text_parens:PackratParser[Expr] = "text_parens" !!! "(" ~> text_expr <~ ")"

  //values
  def bool: PackratParser[Expr] = "bool" !!!
    "true" ^^^ (Bool(true)) |
    "false" ^^^ (Bool(false)) |
    var_factor

  def num: PackratParser[Expr] = "num" !!!
    floatingPointNumber ^^ (x => Number(x.toDouble)) |
    wholeNumber ^^ (x => Number(x.toDouble)) |
    var_factor

  def text: PackratParser[Expr] = "text" !!!
    stringLiteral ^^ (x => Text(stripQuote(x))) |
    var_factor

  def var_factor: Parser[Expr] = "var_factor" !!!
    id <~ ".asNumber" ^^ (x => NumericVar(x)) |
    id <~ ".asText" ^^ (x => TextVar(x)) |
    id <~ ".asBool" ^^ (x => BoolVar(x)) |
    id ^^ (x => AnyVar(x))

  def id: PackratParser[String] = "id" !!! opt("{") ~> ident <~ opt("}")

  private def stripQuote(s: String) = {
    s.substring(1, s.length - 1)
  }
}

object SimpleEquationParser  extends BoolParser {
  def apply(input: String) : Either[String,Expr] = {

    parseAll("root" !!! expr, input) match {
      case Success(r, _) => Right(r)
      case Failure(msg, _) => Left(msg)
      case Error(msg, _) => Left(msg)
    }
  }
}

日志跟踪:

trying root at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying expr at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying bool_expr at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying or at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying and at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying equality at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying bool_equality at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying bool_term at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying bool at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
bool --> [1.1] failure: `true' expected but `(' found

(1+2) > (3+4)
^
trying var_factor at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
id --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
var_factor --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
id --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
id --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
id --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
bool_term --> [1.1] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `(' found

(1+2) > (3+4)
^
trying bool_parens at scala.util.parsing.combinator.PackratParsers$PackratReader@30b7c004
trying bool_expr at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying or at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying and at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying equality at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying bool_equality at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying bool_term at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying bool at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
bool --> [1.2] failure: `true' expected but `1' found

(1+2) > (3+4)
 ^
trying var_factor at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
id --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
var_factor --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
id --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
id --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
trying id at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
id --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
bool_term --> [1.2] failure: string matching regex `\p{javaJavaIdentifierStart}\p{javaJavaIdentifierPart}*' expected but `1' found

(1+2) > (3+4)
 ^
trying bool_parens at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
bool_parens --> [1.2] failure: `(' expected but `1' found

(1+2) > (3+4)
 ^
trying not at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
not --> [1.2] failure: `!' expected but `1' found

(1+2) > (3+4)
 ^
bool_equality --> [1.2] failure: `!' expected but `1' found

(1+2) > (3+4)
 ^
equality --> [1.2] failure: `!' expected but `1' found

(1+2) > (3+4)
 ^
trying num_equality at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying relational at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying additive at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying multiplicative at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying num_term at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
trying num at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@59d016c9
num --> [1.3] parsed: 1
num_term --> [1.3] parsed: Number(1.0)
multiplicative --> [1.3] parsed: (Number(1.0)~List())
trying multiplicative at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@36c88a32
trying num_term at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@36c88a32
trying num at scala.util.parsing.combinator.PackratParsers$PackratReader$$anon$3@36c88a32
num --> [1.5] parsed: 2
num_term --> [1.5] parsed: Number(2.0)
multiplicative --> [1.5] parsed: (Number(2.0)~List())
additive --> [1.5] parsed: (Number(1.0)~List((+~Number(2.0))))
relational --> [1.5] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
num_equality --> [1.5] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
and --> [1.5] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
or --> [1.5] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
bool_expr --> [1.5] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
bool_parens --> [1.6] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
bool_equality --> [1.6] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
equality --> [1.6] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
and --> [1.6] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
or --> [1.6] parsed: (BinaryOp(+,Number(1.0),Number(2.0),Num)~List())
bool_expr --> [1.6] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
expr --> [1.6] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
root --> [1.6] parsed: BinaryOp(+,Number(1.0),Number(2.0),Num)
Left(`||' expected but `>' found)

Answer 1

@Kolmar 是正确的，输入需要使用 num_expr 进行解析。下面的解决方案是我想出的，但感觉不如我想要的那么可靠。问题归结为优先级，但我希望有一种方法可以让解析器在 bool 分支失败后继续检查。相反，我交换了 equality 解析器的顺序以在 bool_equality 之前检查 num_equality:

def equality = "equality" !!! num_equality | bool_equality | text_equality

但是因为 true 和 false 关键字定义在 boolean 分支中，在数值之后求值，所以它们被解析为类型 AnyVar而不是 Bool。为了解决这个问题，我添加了一个 reserved 解析器并将 var_factor 更改为以下内容:

def var_factor: Parser[Expr] = "var_factor" !!!
  id <~ ".asNumber" ^^ (x => NumericVar(x)) |
  id <~ ".asText" ^^ (x => TextVar(x)) |
  id <~ ".asBool" ^^ (x => BoolVar(x)) |
  not(reserved) ~> id ^^ (x => AnyVar(x))

def id: PackratParser[String] = "id" !!! opt("{") ~> ident <~ opt("}")
def reserved: Parser[String] = """\b(true|false)\b""".r

我目前有大约 70 个测试都通过了。我仍然乐于接受有关更强大的解决方案(不那么脆弱)的建议，但这似乎目前运行良好。