使用Scala解析器的运算符关联性 [英] Operator associativity using Scala Parsers

问题描述

所以我一直在尝试用Scala的解析器编写一个计算器，这很有趣，除了我发现运算符的关联性是向后的，并且当我尝试使我的语法左递归时，即使它是完全明确的，出现堆栈溢出.

So I've been trying to write a calculator with Scala's parser, and it's been fun, except that I found that operator associativity is backwards, and that when I try to make my grammar left-recursive, even though it's completely unambiguous, I get a stack overflow.

为了澄清，如果我有一条规则，例如: def减:Parser [Int] = num〜-"〜加{x => x._1._1-x._2} 然后计算7-4-3得出的结果是6而不是0.

To clarify, if I have a rule like: def subtract: Parser[Int] = num ~ "-" ~ add { x => x._1._1 - x._2 } then evaluating 7 - 4 - 3 comes out to be 6 instead of 0.

我实际实现此方法的方式是，我正在构成一棵二叉树，其中运算符是非叶节点，叶节点是数字.我评估树的方式是左子(运算符)右子.在为7-4-5构建树时，我希望它看起来像是:

The way I have actually implemented this is that I am composing a binary tree where operators are non-leaf nodes, and leaf nodes are numbers. The way I evaluate the tree is left child (operator) right child. When constructing the tree for 7 - 4 - 5, what I would like for it to look like is:

-
-   5
7   4   NULL   NULL

其中-是根，其子代是-和5，第二个-子代是7和4.

where - is the root, its children are - and 5, and the second -'s children are 7 and 4.

但是，我唯一可以轻松构造的树是

However, the only tree I can construct easily is

-
7   -
NULL   NULL   4   5

这是不同的，不是我想要的.

which is different, and not what I want.

基本上，简单的括号是7-(4-5)，而我想要的是(7-4)-5.

Basically, the easy parenthesization is 7 - (4 - 5) whereas I want (7 - 4) - 5.

我该如何破解?我觉得我应该能够以正确的运算符优先级编写计算器.我应该先对所有内容进行令牌化，然后再撤消令牌吗?我可以拿走所有孩子，让他们成为合适孩子父母的合适孩子，然后让其父母成为前孩子的左孩子，这样就可以倒掉我的树了吗?乍看之下似乎不错，但我并没有真正深入地考虑过.我觉得我一定有某种失踪的情况.

How can I hack this? I feel like I should be able to write a calculator with correct operator precedence regardless. Should I tokenize everything first and then reverse my tokens? Is it ok for me to just flip my tree by taking all left children of right children and making them the right child of the right child's parent and making the parent the left child of the ex-right child? It seems good at a first approximation, but I haven't really thought about it too deeply. I feel like there must just be some case that I'm missing.

我的印象是，我只能使用scala解析器进行LL解析器.如果您知道另一种方法，请告诉我！

My impression is that I can only make an LL parser with the scala parsers. If you know another way, please tell me!

推荐答案

Scala解析器组合器的标准实现(Parsers特性)不支持左递归语法.但是，您可以使用

Scala's standard implementation of parser combinators (the Parsers trait) do not support left-recursive grammars. You can, however, use PackratParsers if you need left recursion. That said, if your grammar is a simple arithmetic expression parser, you most definitely do not need left recursion.

修改

有多种方法可以使用右递归并仍然保持左关联性，如果您热衷于此，只需查找算术表达式和递归下降解析器即可.而且，当然，正如我说的那样，您可以使用PackratParsers ，它允许左递归.

There are ways to use right recursion and still keep left associativity, and if you are keen on that, just look up arithmetic expressions and recursive descent parsers. And, of course, as, I said, you can use PackratParsers, which allow left recursion.

但是不使用PackratParsers来处理关联性的最简单方法是避免使用递归.只需使用重复运算符之一来获取List，然后根据需要获取foldLeft或foldRight.简单的例子:

But the easiest way to handle associativity without using PackratParsers is to avoid using recursion. Just use one of the repetition operators to get a List, and then foldLeft or foldRight as required. Simple example:

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 存储库.

这篇关于使用Scala解析器的运算符关联性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！