Problem about associativity

[xxchan]

I think the following grammar will produce a right-leaning syntax tree.

EXPR  = START, END
START = GROUP | LIT
END   = "-", EXPR | NOTHING

e.g., in your example in Main, 1-1-1-1 is parsed into Success (Sub (Lit 1) (Sub (Lit 1) (Sub (Lit 1) (Lit 1)))), but it should be Success (Sub (Sub (Sub (Lit 1) (Lit 1)) (Lit 1)) (Lit 1))

[glebec]

I think you mean left vs. right associativity (where the implied parens go) rather than precedence (which operator binds more tightly). Ouch, that is a good point; when I was writing this I wasn't as consciously aware of R/L associativity in parsing. I'll have to take a look later and think about how this interacts with the overall technique to factor out left recursion, and whether I want to change my example and/or address how to enforce left vs right bias.

[xxchan]

What I learned is to turn recursion into repetition:

original grammar:
A -> Aα | β

the trick you use:
A -> βA'
A' -> (αA')?

turn recursion into repetition:
A -> βα*

The result now becomes a list, and we can foldLeft or foldRight the list.

This is just chainl1/chainr1.

[glebec]

Ah that's helpful, thanks. Busy at the moment but will look at updating this repo in the future.