[mrkeen]

I put it off as well, I figured precedence and associativity is something I'd learn later after I figured out how to stop my **ing grammars from looping forever. But it was right there in front of me!

When I looked at someone else's working code, they'd laid it out so that each layer could only call into the same layer or the next layer down:

  parseSum     = ...
  parseProduct = ...
  parseTerm    = ...

which should eliminate the mutual-infinite-recursion case, since the control flow can't ever go upward. And it didn't look like a co-incidence that they'd laid the code out from low-precedence mathematical operators to high-precedence mathematical operators.

The code I ended up using is something like

  parseSum = parseProduct then many('+' then parseProduct) // where 'many' means 0 or more.

But if you don't have 'many' in your grammar syntax, it looks like this would work instead:

  parseSum = parseProduct + parseSum

But the above is wrong for two reasons. Firstly, you need to have a '+', so there's no way to parse an expression that doesn't have a '+' in it. But it also right-associates and you end up with (1+(2+(3+4))) which is probably fine for addition (give or take some C-int-overflow-rules), but breaks division. I think you can fix both by putting the terminal case first, and then left-recursing after that:

  parseSum = parseProduct | parseSum + parseProduct

Then there's only one remaining issue to deal with - what do you do when you actually want to loop? Sums can contain products, and products can contain sums (as long as they're in parens.) Well, parens bind tighter than any other precedence, so they go straight to the bottom:

  parseSum     = ...
  parseProduct = ...
  parseTerm    = ...
  parseParens  = '(' parseSum ')'

So we've broken the no-upward-control-flow rule, but is it an infinite loop? The only case where control flow can go upward is if you consume a '(' first, so I say no.