开发者

Scala parser combinators, failure on end of line

I am trying to build an interpreter for the Icon programming language, in Scala. Right now I am working on setting up a parser for it.

The code I have written so far is:

package interpreter
import scala.util.parsing.combinator.syntactical._
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.PackratParsers
import scala.util.parsing.combinator.JavaTokenParsers

object ExprParser extends JavaTokenParsers with PackratParsers{

def exp : Parser[expr] =
    andexp |
    fail |
    ifexp |
    fromTo |
    write |
    string |
    arithm |
    "(" ~> exp <~ ")" |
    exp

def integer : Parser[CstInt] = wholeNumber ^^ { s => { //println("matching int");
new CstInt(s.toInt)}}
def string : Parser[CstStr] = stringLiteral ^^ { s => { //println("matching string");
new CstStr(s)}}


def fail : Parser[Fail] = "&fail" ^^ { e => Fail()}

def  write : Parser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}

def ifexp : Parser[If] = ("if" ~> exp) ~ ("then" ~> exp) ~ ("else" ~> exp) ^^ { case cond ~ suc ~ fail => If(cond, suc, fail)}


// Arithmetic
def arithm : Parser[expr] =
    term ~ ("+" ~> arithm) ^^ { case l ~ r => Prim("+", l, r)} |
    term ~ ("-" ~> arithm) ^^{ case l ~ r => Prim("-", l, r)} |
    term

def term : Parser[expr] =
    factor ~ ("*" ~> term) ^^ { case l ~ r => Prim("*", l, r)} |
    factor ~ ("/" ~> term) ^^ { case l ~ r => Prim("/", l, r)} |
    factor

def factor : Parser[expr] =
    integer |
    "-" ~> arithm |
    "(" ~> arithm <~ ")"


//PackratParser to allow left recursive grammars
lazy val fromTo : PackratParser[FromTo] = exp ~ ("to" ~> exp) ^^ { case from ~ to => FromTo(from, to)}

lazy val andexp : PackratParser[And] = exp ~ ("&" 开发者_运维问答~> exp) ^^ { case e1 ~ e2 =>{ println("matching and" + e1); println(" arg2: " + e2); And(e1, e2)}}

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

Now, my problem is that when I run this code on this input:

write(1 to 5) & write(3 to 5)

I get the following output:

matching andWrite(FromTo(CstInt(1),CstInt(5)))
arg2: Write(FromTo(CstInt(3),CstInt(5)))
matching andWrite(FromTo(CstInt(1),CstInt(5)))
arg2: Write(FromTo(CstInt(3),CstInt(5)))
java.lang.IllegalArgumentException: [1.30] failure: `&' expected but `' found

write(1 to 5) & write(3 to 5)
                             ^
at interpreter.ExprParser$.parseInput(parser.scala:62)
at interpreter.Main$.main(main.scala:9)
at interpreter.Main.main(main.scala)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at sbt.Run.run0(Run.scala:60)
at sbt.Run.execute$1(Run.scala:47)
at sbt.Run$$anonfun$run$2.apply(Run.scala:50)
at sbt.Run$$anonfun$run$2.apply(Run.scala:50)
at sbt.TrapExit$.executeMain$1(TrapExit.scala:33)
at sbt.TrapExit$$anon$1.run(TrapExit.scala:42)

I added the printouts as a way of seeing whether it even matched the & operator.

The code runs fine on other weird inputs like:

write((if &fail then 3 else 5) to (3 to 5))

So it seems to be a problem specifically related to the andexp parser.

Any help would be much appreciated, as I am completely new to Scala and the parser combinators, and it is somewhat hard to find good documentation I think.


Could this be due to the cycle in def exp = ... | exp?


Note that packrat parsers have limitations with regard to left recursion. And mixing packrat with non-packrat on a mutal recursive rule is way strange. I have no idea how that would work (or not), and I'd just avoid finding out.


So, as mentioned in my comment on Ben Jacksons answer, the problem was that I needed to make exp a PackratParser, the working code is here:

package interpreter
import scala.util.parsing.combinator.syntactical._
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.PackratParsers
import scala.util.parsing.combinator.JavaTokenParsers

object ExprParser extends JavaTokenParsers with PackratParsers{

lazy val exp : PackratParser[expr] =
    andexp |
    fail |
    ifexp |
    fromTo |
    write |
    string |
    arithm |
    "(" ~> exp <~ ")" 

def integer : Parser[CstInt] = wholeNumber ^^ { s => { //println("matching int");
new CstInt(s.toInt)}}
def string : Parser[CstStr] = stringLiteral ^^ { s => { //println("matching string");
new CstStr(s)}}


def fail : Parser[Fail] = "&fail" ^^ { e => Fail()}

def  write : Parser[Write] =  "write" ~> "(" ~> exp <~ ")" ^^ {  e => Write(e)}

def ifexp : Parser[If] = ("if" ~> exp) ~ ("then" ~> exp) ~ ("else" ~> exp) ^^ { case cond ~ suc ~ fail => If(cond, suc, fail)}


// Arithmetic
def arithm : Parser[expr] =
    term ~ ("+" ~> arithm) ^^ { case l ~ r => Prim("+", l, r)} |
    term ~ ("-" ~> arithm) ^^{ case l ~ r => Prim("-", l, r)} |
    term

def term : Parser[expr] =
    factor ~ ("*" ~> term) ^^ { case l ~ r => Prim("*", l, r)} |
    factor ~ ("/" ~> term) ^^ { case l ~ r => Prim("/", l, r)} |
    factor

def factor : Parser[expr] =
    integer |
    "-" ~> arithm |
    "(" ~> arithm <~ ")"


//PackratParser to allow left recursive grammars
lazy val fromTo : PackratParser[FromTo] = exp ~ ("to" ~> exp) ^^ { case from ~ to => FromTo(from, to)}

lazy val andexp : PackratParser[And] = exp ~ ("&" ~> exp) ^^ { case e1 ~ e2 =>{ println("matching and" + e1); println(" arg2: " + e2); And(e1, e2)}}

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

With my previous code I seem to have been allowing for left recursion, which cannot be handled by the normal parser. If anyone can clarify why fromTo was working without exp being a PackratParser, while andexp was not, I would still be interested to hear why that is so.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜