Parser combinator grammar not yielding correct associativity

Question

I am working on a simple expression parser, however given the following parser combinator declarations below, I can't seem to pass my tests and a right associative tree keeps on popping up.

def EXPR:Parser[E] = FACTOR ~ rep(SUM|MINUS) ^^ {case a~b => (a /: b)((acc,f) => f(acc))}
def SUM:Parser[E => E] = "+" ~ EXPR ^^ {case "+" ~ b => Sum(_, b)}
def MINUS:Parser[E => E] = "-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}

I've been debugging hours for this. I hope someone can help me figure it out it's not coming out right.

"5-4-3" would yield a tree that evaluates to 4 instead of the expected -2.

What is wrong with the grammar above?

Answer 1

It seems using "+" ~ EXPR made the answer incorrect. It should have been FACTOR instead.

Answer 2

"-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}

for 5-4-3, it expands to

Diff(5, 4-3)

which is

Diff(5, Diff(4, 3))

however, what you need is:

Diff(Diff(5, 4), 3))

// for 5 + 4 - 3 it should be

Diff(Sum(5, 4), 3)

you need to involve stack.

Answer 3

I don't work with Scala but do work with F# parser combinators and also needed associativity with infix operators. While I am sure you can do 5-4 or 2+3, the problem comes in with a sequence of two or more such operators of the same precedence and operator, i.e. 5-4-2 or 2+3+5. The problem won't show up with addition as (2+3)+5 = 2+(3+5) but (5-4)-2 <> 5-(4-2) as you know.

See: Monadic Parser Combinators 4.3 Repetition with meaningful separators. Note: The separators are the operators such as "+" and "*" and not whitespace or commas.

See: Functional Parsers Look for the chainl and chainr parsers in section 7. More parser combinators.

For example, an arithmetical expressions, where the operators that separate the subexpressions have to be part of the parse tree. For this case we will develop the functions chainr and chainl. These functions expect that the parser for the separators yields a function (!);

The function f should operate on an element and a list of tuples, each containing an operator and an element. For example, f(e0; [(1; e1); (2; e2); (3; e3)]) should return ((eo 1 e1) 2 e2) 3 e3. You may recognize a version of foldl in this (albeit an uncurried one), where a tuple (; y) from the list and intermediate result x are combined applying x y.

You need a fold function in the semantic parser, i.e. the part that converts the tokens from the syntactic parser into the output of the parser. In your code I believe it is this part.

{case a~b => (a /: b)((acc,f) => f(acc))}

Sorry I can't do better as I don't use Scala.