Parsing - parsing taking too much

Question
1

A sample grammar for polynomials:

> LINEARSUM == 
>    LINEARSUM + LINEARSUM 
> |  LINEARSUM – LINEARSUM 
> |  NUMBER * LINEARSUM 
> |  - LINEARSUM 
> |  ( LINEARSUM ) 
> |  VALUE

I have implemented this grammar using the parser combinators library (specifically PackratParsers) and it is insensitive to whitespace.

However, I have a problem in that the parsing does as much as possible. So when I do this MyParser.parse("-x + y"), firstly it says x + y is a linearsum, and then it sees it is preceded by a -. My code then negates the “x + y” in the ^^ section to give -x -y.

My question is should I be thinking about i) a new grammar ii) changing ordering (although I have tried this and the same problem reoccurs) iii) using different parsing methods in order to solve this?

2

Quite likely it’s i), at least as a first step - you may want to split your grammar into multiple productions in order to establish operator applicability and precedence. A web search for “arithmetic expression grammar” should yield some inspiration.

3

But I am right in thinking it should not be giving up on the first choice since -x +y does satisfy LINEARSUM + LINEARSUM where -x is one and y is another, separated by a +? It seems to give up on option one and goes onto option four.

4

My guess would be that the parser probes non-left-recursive alternatives first. If it were always probing alternatives strictly in order, it’d never get past the first left-recursive alternative and get stuck in an infinite loop.