Ассоциативность операторов с использованием парсеров Scala

Стандартная реализация комбинаторов парсеров в Scala (черта Parsers) не поддерживает леворекурсивные грамматики. Однако вы можете использовать PackratParsers если вам нужна левая рекурсия. Тем не менее, если ваша грамматика представляет собой простой анализатор арифметических выражений, вам определенно не нужна левая рекурсия.

Изменить

Есть способы использовать правую рекурсию и при этом сохранить левую ассоциативность, и если вы заинтересованы в этом, просто найдите арифметические выражения и парсеры рекурсивного спуска. И, конечно же, как я уже сказал, вы можете использовать PackratParsers, которые разрешают левую рекурсию.

Но самый простой способ справиться с ассоциативностью без использования PackratParsers — это не использовать рекурсию. Просто используйте один из операторов повторения, чтобы получить List, а затем foldLeft или foldRight по мере необходимости. Простой пример:

trait Tree
case class Node(op: String, left: Tree, right: Tree) extends Tree
case class Leaf(value: Int) extends Tree

import scala.util.parsing.combinator.RegexParsers

object P extends RegexParsers {
  def expr = term ~ (("+" | "-") ~ term).* ^^ mkTree
  def term = "\\d+".r ^^ (_.toInt)
  def mkTree(input: Int ~ List[String ~ Int]): Tree = input match {
    case first ~ rest => ((Leaf(first): Tree) /: rest)(combine)
  }
  def combine(acc: Tree, next: String ~ Int) = next match {
    case op ~ y => Node(op, acc, Leaf(y))
  }
}

Вы можете найти другие, более полные примеры на репозиторий scala-dist.

Я интерпретирую ваш вопрос следующим образом:

Если вы пишете такие правила, как def expression = number ~ "-" ~ expression, а затем оцениваете каждый узел синтаксического дерева, то вы обнаружите, что в 3 - 5 - 4 сначала вычисляется 5 - 4, что дает в результате 1, а затем вычисляется 3 - 1, что дает в результате 2.

С другой стороны, если вы пишете такие правила, как def expression = expression ~ "-" ~ number, эти правила являются леворекурсивными и переполняют стек.

Есть три решения этой проблемы:

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

2. Определите правило как def expression = repsep(number, "-"), а затем при оценке вычислений перебирайте проанализированные числа (которые будут отображаться в плоском списке) в любом направлении, обеспечивающем вам необходимую ассоциативность. Вы не можете использовать это, если появится более одного вида оператора, так как оператор будет отброшен.

3. Определите правило как def expression = number ~ ( "-" ~ number) *. У вас будет начальный номер плюс набор пар оператор-номер в плоском списке для обработки в любом нужном вам направлении (хотя слева направо, вероятно, здесь проще).

4. Используйте PackratParsers, как предложил Даниэль Собрал. Это, вероятно, ваш лучший и самый простой выбор.