Вопрос по 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. Если вы знаете другой способ, пожалуйста, скажите мне!

Error: User Rate Limit Exceededscala-distError: User Rate Limit Exceeded Daniel C. Sobral
Error: User Rate Limit Exceeded Daniel C. Sobral

Ваш Ответ

2   ответа
1

def expression = number ~ "-" ~ expression3 - 5 - 45 - 43 - 1

def expression = expression ~ "-" ~ number

Post-process the abstract syntax tree to convert it from a right-associative tree to a left-associative tree. If you're using actions on the grammar rules to do the computation immediately, this won't work for you.

Define the rule as def expression = repsep(number, "-") and then when evaluating the computation, loop over the parsed numbers (which will appear in a flat list) in whichever direction provides you the associativity you need. You can't use this if more than one kind of operator will appear, since the operator will be thrown away.

Define the rule as def expression = number ~ ( "-" ~ number) *. You'll have an initial number, plus a set of operator-number pairs in a flat list, to process in any direction you want (though left-to-right is probably easier here).

Use PackratParsers as Daniel Sobral suggested. This is probably your best and simplest choice.

Error: User Rate Limit Exceededlazy valError: User Rate Limit ExceededdefError: User Rate Limit ExceededdefError: User Rate Limit Exceededlazy valError: User Rate Limit ExceededdefError: User Rate Limit Exceededlazy valError: User Rate Limit Exceededval.
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded nnythm
Error: User Rate Limit Exceeded nnythm
Error: User Rate Limit Exceeded
7

ParsersPackratParsers

Edit

you can use PackratParsers

PackratParsersListfoldLeftfoldRight

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded nnythm
Error: User Rate Limit Exceeded nnythm
Error: User Rate Limit Exceededimport 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"))}Error: User Rate Limit Exceededlazy val?

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