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

Question

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

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), то есть приводят к АСТ формы FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...).

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

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

Answer 1

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

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

Теперь вы можете легко сделать правильную ассоциативность на term + expr | term для правого ассоциативного, потому что, когда последний термин найден, вы находитесь под + рекурсией. Аналогично, вы делаете левую ассоциативность expr + term | term. Левые ассоциативные причины оставляют рекурсию, и вы никогда не на последнем месте. Даже packrat не спасает от него. Я не понимаю, как вы получаете свои результаты. Шахта

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

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

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

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

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

---

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

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)