4

我正在尝试为编程语言 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 解析器和常规解析器应该没问题。

4

2 回答 2

2

Ok, I have read the paper on packrat parsers in Scala, and I'm afraid this grammar won't work as is. The problem being that fromTo as exp inside write, and then write itself fails (and, having no other alternatives, the outer exp fails). It never goes back and say "well, let's see if there's another exp that is also valid".

However, looking at this text, I don't see fromTo having parenthesis as part of its grammar. If it were simply rewritten to remove those parenthesis from that level, it would work:

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)}
}
于 2011-06-16T22:49:29.860 回答
0

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

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

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

现在似乎工作正常。

安德烈斯

于 2011-06-18T17:13:43.813 回答