Почему комбинатор парсера не отступает?

Учитывать

import util.parsing.combinator._
object TreeParser extends JavaTokenParsers {

    lazy val expr: Parser[String] = decimalNumber | sum
                                                  //> expr: => TreeParser.Parser[String]
    lazy val sum: Parser[String] = expr ~ "+" ~ expr ^^ {case a ~ plus ~ b => s"($a)+($b)"}
                                                  //> sum: => TreeParser.Parser[String]
    println(parseAll(expr, "1 + 1"))                       //> TreeParser.ParseResult[String] = [1.3] failure: string matching regex 
                                              //| `\z' expected but `+' found
}

Та же история с fastparse

import fastparse.all._
val expr: P[Any] = P("1" | sum)
val sum: P[Any] = expr ~ "+" ~ expr
val top = expr ~ End
println(top.parse("1+1")) // Failure(End:1:2 ..."+1")

Парсеры прекрасно понимают, что использование первого литерала — плохая идея, но не пытайтесь вернуться к производству суммы. Почему?

Я понимаю, что парсер берет первую ветку, которая может успешно съесть часть входной строки, и завершает работу. Здесь «1» выражения соответствует первому входному символу, и синтаксический анализ завершается. Чтобы получить больше, нам нужно сделать сумму первой альтернативой. Впрочем, глупо

lazy val expr: Parser[String] = sum | "1"

заканчивается переполнением стека. Поэтому авторы библиотеки подходят к ней с другой стороны

val sum: P[Any] = P( num ~ ("+".! ~/ num).rep )
val top: P[Any]   = P( sum ~ End )

Здесь мы начинаем sum с терминала, что хорошо, но этот синтаксис более многословен, и, кроме того, он создает терминал, за которым следует список, что хорошо для оператора редукции, такого как sum, но его трудно сопоставить с рядом. бинарных операторов.

Что, если ваш язык определяет выражение, допускающее бинарный оператор? Вы хотите сопоставить каждое вхождение expr op expr и сопоставить его с соответствующим узлом дерева.

expr ~ "op" ~ expr ^^ {case a ~ _ ~ b => BinOp(a,b)"} 

Как ты это делаешь? Короче говоря, мне нужен жадный парсер, который потребляет всю строку. Это то, что я подразумеваю под «жадным», а не жадным алгоритмом, который прыгает в первый вагон и заканчивается в тупике.