Scala парсер комбинаторы, ошибка на конце строки - PullRequest
Новая
       21

Scala парсер комбинаторы, ошибка на конце строки

2 голосов
/ 28 апреля 2011

Я пытаюсь создать интерпретатор для языка программирования Icon в Scala. Сейчас я работаю над настройкой парсера для него.

Код, который я написал до сих пор: 

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())
    }
}

Теперь моя проблема в том, что когда я запускаю этот код на этом входе:

написать (от 1 до 5) и написать (от 3 до 5)

Я получаю следующий вывод: 

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)

Я добавил распечатки, чтобы увидеть, соответствует ли они даже оператору &.

Код отлично работает на других странных вводах, таких как:

записать ((если & терпеть неудачу, то 3 или 5) в (от 3 до 5))

Так что, похоже, проблема связана именно с анализатором andexp.

Любая помощь будет принята с благодарностью, поскольку я совершенно новичок в Scala и комбинаторах синтаксического анализа, и мне кажется, что найти хорошую документацию довольно сложно.

Ответы [ 3 ]

1 голос
/ 28 апреля 2011

Может ли это быть из-за цикла в def exp = ... | exp?

0 голосов
/ 28 апреля 2011

Итак, как упоминалось в моем комментарии к ответу Бена Джексона, проблема заключалась в том, что мне нужно было сделать exp a PackratParser, рабочий код здесь: 

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())
    }
}

С моим предыдущим кодомКажется, я допускаю левую рекурсию, которая не может быть обработана обычным парсером.Если кто-то может объяснить, почему fromTo работал, а exp не был PackratParser, а andexp - нет, мне все равно было бы интересно узнать, почему это так.

0 голосов
/ 28 апреля 2011

Обратите внимание, что синтаксические анализаторы пакета имеют ограничения в отношении левой рекурсии.И смешивание packrat с non-packrat по взаимному рекурсивному правилу - это странно.Я понятия не имею, как это будет работать (или нет), и я бы просто не узнал.

...