How to change code using Scala Parser Combinators to take operator precedence into account?

Question

Consider this part of the grammar:

  def expression = SimpleExpression ~ opt(relation ~ SimpleExpression)
  def relation = "=" | "#" | "<=" | "<" | ">=" | ">" | "IN" | "IS"
  def SimpleExpression = opt("+" | "-") ~ rep1sep (term, AddOperator)
  def AddOperator = "+" | "-" | "OR"
  def term = factor ~ rep(MulOperator ~ factor)
  def MulOperator = "*" | "/" | "DIV" | "MOD" | "&"
  def factor: Parser[Any] = number | "(" ~ expression ~ ")" | "~" ~ factor

Is it necessary to rewrite parts of it to create new rules, or is there just a method (like | vs. ||| for first vs. longest rule matching) I'm currently missing which does the necessary thing?

Answer 1

Operator precedence is a natural result of the way rules are written. For example, in this grammar a SimpleExpression is composed of addition, subtraction and logical-or of term, and a term is composed of multiplication, division, modulus and logical-and of factor.

So if you have this:

1 + 2 * 3

You'll get the following back (roughly speaking, for clarity):

List(1, (2 ~ List(* ~ 3)))

And if you have this:

1 * 2 + 3

You'll get this back (roughly speaking):

List((1 ~ List(* ~ 2)), 3)

You lose the addition operators because of rep1sep -- separators are discarded.