Scala PackratParsers (комбинаторы парсеров) и левая ассоциативность

Я использую Scala's PackratParsers (комбинаторы парсеров) с леворекурсивной грамматикой следующего вида

lazy val expr: PackratParser[Expr] = (
    ...
  | expr ~ (":" ~ expr).+ ^^ {
      case expr ~ rest => (expr /: rest)(combineBinary)
    }
  | ...
)

def combineBinary(acc: Expr, next: String ~ Expr) = next match {
  case op ~ expr => FunctionCall(op, acc, expr)
}

Я хотел бы, чтобы бинарный оператор ":" был левоассоциативным, чтобы выражения формы x1:x2:...:xn анализировались как (((x1:x2):x3):...:xn), т.е. приводили к AST формы FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...).

Удивительно, но с грамматикой PackratParsers, определенной выше, результирующий AST по-прежнему является правоассоциативным. Почему так происходит и что можно сделать, чтобы это изменить?

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


scala parser-combinators left-recursion
person Martin Studer    schedule 06.12.2015    source источник
comment
Я имел дело с той же проблемой, но смог решить ее с помощью этого pdf. На странице 21 есть отличный пример для дальнейшего развития.   -  person Nathan Merrill    schedule 07.03.2018

Ответы (1)


arrow_upward
1
arrow_downward

тл; dr Я не знаю, как packrat может спасти вас от двух больших проблем, которые у вас есть. Это спасло меня от stackoverflow, но у меня не было такого вопиющего левого отказа.

Я имею в виду, что ваша рекурсия expr + expr никогда не должна заканчиваться. Я так понимаю, что у вас где-то есть некая база индукции, т.е. expr = expr + expr | term.

Теперь вы можете легко сделать правильную ассоциативность с помощью term + expr | term для правильной ассоциативности, потому что, когда последний термин найден, вы глубоко под + рекурсией. Точно так же вы делаете левую ассоциативность expr + term | term. Левая ассоциативная связь вызывает левую рекурсию, и вы никогда не достигаете конечного термина. От этого не спасает даже пакрат. Я не понимаю, как вы получаете свои результаты. Мой

object EP extends JavaTokenParsers with PackratParsers {
    def expr: Parser[_] = expr ~ ("+" ~> expr) | ident /*^^ {
          case ident ~ rest => (ident /: rest){case (acc, e) => acc + s" + (${e.toString})"}
    } | ident*/
}
List("a", "a + b", "a + b + c+ d") foreach {input => 
    println("left: " +  EP.parseAll(EP.expr, input))
}

стек переполняется. Это спасло меня один раз, но у меня не было такого вопиющего левого отказа. И я не знаю, как это может спасти вас от второй проблемы, которую вы задаете.

В любом случае, вы должны устранить рекурсию, заменив expr + term | term на

def left: Parser[_] = ident ~ appendix 
def appendix = "+" ~> left | ""

Но это, однако, снова правильная рекурсия, потому что мы видим, что ident снова является первым узлом.

Решение: поэтому вы просто используете то, что делают все люди: используйте rep синтаксический анализатор, который предоставляет вам список, итерируемый слева:

def right: Parser[_] = ident ~ ("+" ~> right) ^^ {case head ~ tail => s"Right($head, $tail)"} | ident 
lazy val left: Parser[_] = ident ~ rep("+" ~> ident) ^^ 
    {case head ~ tail => (head /: tail){case (acc, expr) => s"Left($acc, $expr)"}}

println("right => " + parseAll(right, "a + b + c+ d"))
println("left => " + parseAll(left, "a + b + c+ d"))

производит

right => [1.13] parsed: Right(a, Right(b, Right(c, d)))
left => [1.13] parsed: Left(Left(Left(a, b), c), d)
person Valentin Tihomirov    schedule 30.12.2015
comment
Вы должны использовать lazy vals с PackratParsers вместо defs - тогда левая рекурсия сама по себе не проблема - person Martin Studer; 31.12.2015
comment
@MartinStuder Для меня это все еще проблема. object EP extends JavaTokenParsers with PackratParsers { lazy val expr: Parser[_] = expr ~ ("+" ~> expr) | ident } ; println("left: " + EP.parseAll(EP.expr, "a + b + c + d")) переполняет стек и я не вижу где можно заменить место больше дефов на вал. - person Valentin Tihomirov; 31.12.2015