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

1

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

Чтобы уточнить, если у меня есть правило, как:     def subtract: Parser [Int] = num ~ & quot; - & quot; ~ add {x = & gt; x._1._1 - x._2} затем оценка 7 - 4 - 3 получается 6 вместо 0.

На самом деле я реализовал это так: я создаю бинарное дерево, в котором операторы являются неконечными узлами, а конечные узлы являются числами. То, как я оцениваю дерево, это левый дочерний (оператор) правый дочерний. При построении дерева для 7 - 4 - 5 я бы хотел, чтобы оно выглядело следующим образом:

-
-   5
7   4   NULL   NULL

где - корень, его дети - и 5, а вторые - дети 7 и 4.

Тем не менее, единственное дерево, которое я могу легко построить, это

-
7   -
NULL   NULL   4   5

который отличается, а не то, что я хочу.

В принципе, простое заключение в скобки - 7 - (4 - 5), тогда как я хочу (7 - 4) - 5.

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

У меня сложилось впечатление, что я могу сделать парсер LL только с парсерами scala. Если вы знаете другой способ, пожалуйста, скажите мне!

btw, оформить заказ-Скала расстояние для дальнейших примеров - я просто редактирую свой ответ с этой ссылкой. Daniel C. Sobral
Пожалуйста, уточните, что вы подразумеваете под "ассоциативность операторов обратная". Daniel C. Sobral

Ваш Ответ

2   ответа
1

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

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

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

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

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

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

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

Спасибо Дэниелу, объявив их ленивым Вэ nnythm
@ Daniel: я не знаю, честно ли невозможно создать комбинаторы LL (k) parserc или это просто не реализовано. Если вы знаете, что это невозможно, не стесняйтесь удалять «(в настоящее время)», но имейте в виду, что я внес некоторые другие изменения, которые также прояснили ваш ответ, поэтому не удаляйте их, если они также не соответствуют действительности. Ken Bloom
@ nnythm Вы, вероятно, не объявляете парсеры packrat какlazy val, ноdef. Ты используешьdef с традиционными парсерными комбинаторами,lazy val с партерами пакетов. На самом деле,def позволяет без проблем пересылать ссылки и рекурсии, чтоlazy val делать тоже по низкой цене в производительности. В грамматике без прямых ссылок или рекурсии вы можете объявить все какval. Daniel C. Sobral
@ Daniel: После небольшого исследования Википедии, я думаю, что везде, где мы упоминали парсеры LL, мы действительно хотели сказать парсеры LR? Ken Bloom
Я строю дерево, прежде чем делать какую-либо оценку. Могу ли я просто преобразовать правоассоциативное дерево в левоассоциативное дерево? Я не мог найти какую-либо литературу об этом в Интернете, хотя, похоже, у меня в голове все работает. PackratParsers также дает мне переполнение стека в моей левой рекурсии, поэтому я думаю, что я собираюсь перейти к преобразованию дерева, если оно правильное. nnythm
7

Parsers trait) не поддерживает леворекурсивные грамматики. Вы можете, однако, использовать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 оцениваются слева направо и являются рекурсивными слева, следовательно, это LL, если не LL (k). nnythm
@ nnythm: На самом деле ты прав. По умолчанию библиотеки разбора Scala - это парсеры с рекурсивным спуском и, следовательно, LL (k), хотя я не знаю, что такое k для комбинаторов синтаксического анализа Scala. LL (k) грамматики не могут обрабатывать левую рекурсию. Это парсер LR, который может обрабатывать левую рекурсию, а комбинаторы парсера Scala не парсеры LR. Ken Bloom
правильно, я имел в виду, что они генерируют самый левый вывод, а не то, что они остаются рекурсивными. nnythm
Вот парсер разуimport scala.util.parsing.combinator._ object SO JavaTokenParsers with PackratParsers { lazy val left: Parser[String] = left ~ ("+" ~> ident) ^^ {case a1 ~ a2 => s"Sum($a1,$a2)"} | ident ; println(parseAll(left, "a+b+c+d"))}. Почему это переполнение стека несмотря наlazy val? Valentin Tihomirov

Похожие вопросы