parsing - 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

好的，我已经阅读了 paper在 Scala 中的 Packrat 解析器上，我担心这个语法不会按原样工作。问题在于 fromTo如 exp内write ，然后 write本身失败(并且没有其他选择，外部 exp 失败)。它永远不会返回并说“好吧，让我们看看是否还有另一个 exp 也是有效的”。

然而，看着this text ，我没看到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)}
}