Scala 解析器组合器，解析器由于优先级而失败

Question

我正在尝试为编程语言 Icon 编写一个解释器。此过程中的步骤之一是为 Icon 编写一个解析器，我是通过以下方式完成的：

import java.io.FileReader
import scala.util.parsing.combinator.syntactical._
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.PackratParsers
import scala.util.parsing.combinator.JavaTokenParsers

abstract class expr
case class CstInt(val value : Int) extends expr
case class FromTo(val from : expr, val to : expr) extends expr
case class Write(val value : expr) extends expr
case class And(val e1 : expr, val e2 : expr) extends expr
case class Or(val e1 : expr, val e2 : expr) extends expr

object ExprParser extends JavaTokenParsers with PackratParsers{

lazy val exp : PackratParser[expr] = andexp | exp2

lazy val exp2 : PackratParser[expr] = fromTo | exp3

lazy val exp3 :PackratParser[expr] = orexp | exp4 

lazy val exp4 : PackratParser[expr] = integer | exp5

lazy val exp5 : PackratParser[expr] = write 

lazy val integer : PackratParser[expr] = wholeNumber ^^ { s => CstInt(s.toInt)}

lazy val  write : PackratParser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}

lazy val fromTo : PackratParser[FromTo] = ("(" ~> integer) ~ ("to" ~> integer <~ ")") ^^ { case from ~ to => FromTo(from, to)}

lazy val andexp : PackratParser[And] = exp ~ ("&" ~> exp) ^^ { case e1 ~ e2 => And(e1, e2)}

lazy val orexp : PackratParser[Or] = exp ~ ("|" ~> exp) ^^ { case e1 ~ e2 => Or(e1, e2)}

def parseInput(input: String) : expr =
    parseAll (exp, input) match {
        case Success(tree, _) => tree
        case e: NoSuccess => throw new IllegalArgumentException(e.toString())
    }

}

object Interpret {
def main(args : Array[String]) : Unit = {
    println(ExprParser.parseInput(args(0)))
    }
}

但是，当我尝试解析以下表达式时遇到了一些问题：

write((1 to 4) | 4)

我收到此错误：

java.lang.IllegalArgumentException: [9.17] failure: `)' expected but ` ' found

而解析

write((1 to 4) & 4)

工作得很好。如果我将 orexp 解析器移动到 fromto 解析器上方的 exp 组，第一个表达式可以正常工作。然而，这并不符合 Icon 给出的规则，也没有解决根本问题。

有人有解决方案的想法吗？根据 Scala 文档，混合 Packrat 解析器和常规解析器应该没问题。

Answer 1

好的，我已阅读论文在 Scala 中的 Packrat 解析器上，我担心这个语法不能按原样工作。问题是 fromTo 作为 write 内的 exp ，然后 write 本身失败（并且没有其他替代方案，外部 exp 失败）。它永远不会回过头来说“好吧，让我们看看是否还有另一个同样有效的 exp”。

但是，查看此文本，我没有看到< code>fromTo 将括号作为其语法的一部分。如果简单地重写以从该级别删除那些括号，它将起作用：

object ExprParser extends JavaTokenParsers with PackratParsers{
  lazy val exp : PackratParser[expr] = andexp | exp2
  lazy val exp2 : PackratParser[expr] = fromTo | exp3
  lazy val exp3 :PackratParser[expr] = orexp | exp4 
  lazy val exp4 : PackratParser[expr] = integer | exp5
  lazy val exp5 : PackratParser[expr] = write | exp6
  lazy val exp6 : PackratParser[expr] = "(" ~> exp <~ ")"
  lazy val integer : PackratParser[expr] = wholeNumber ^^ { s => CstInt(s.toInt)}
  lazy val  write : PackratParser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}
  lazy val fromTo : PackratParser[FromTo] = integer ~ ("to" ~> integer) ^^ { case from ~ to => FromTo(from, to)}
  lazy val andexp : PackratParser[And] = exp ~ ("&" ~> exp) ^^ { case e1 ~ e2 => And(e1, e2)}
  lazy val orexp : PackratParser[Or] = exp3 ~ ("|" ~> exp) ^^ { case e1 ~ e2 => Or(e1, e2)}
}

Answer 2

我不是这方面的专家，但为了解决您的问题，我首先将您的表达式分组为一行，如下所示：

lazy val exp : PackratParser[expr] = (andexp | orexp | fromTo | integer | write)

然后我更改了您的顺序 - fromTo 列在 orexp 之前。

现在似乎工作正常。

安德烈斯