"Ambiguous" left- and right- recursive rules should be an error

[alexwarth]

(See #55 for the backstory.)

Right now it's possible for Ohm programmers to write "ambiguous" left- and right-recursive rules in a grammar, e.g.,

AddExp
  = AddExp "+" AddExp  -- plus
  | AddExp "-" AddExp  -- minus
  | MulExp

This should be a compile-time error.

Why? Because the associativity of the + and - operators (see above) is not obvious, and it easily could have been. For instance, if you want them to associate to the left, then a much better way to write the above rule is:

AddExp
  = AddExp "+" MulExp  -- plus
  | AddExp "-" MulExp  -- minus
  | MulExp

And now the associativity is obvious. (Similarly, if right-associativity is desired, then AddExp should be rewritten to be right-recursive.)

[pdubroy]

I see a few issues with the implementation in #175:

• it only detects a specific structure of left- and right- recursion (although it's probably the most common case in Ohm)
• it doesn't detect some things that don't look like right recursion, but are. E.g., it wouldn't catch the following case:

  G {
    AddExp = AddExp "+" AddExp noop -- rec
           | digit
    noop =
  }
  

A solution for this should probably use the existing mechanism for detecting left recursion, and build on that. Since we do want to detect this statically, we will probably have to live with some limitations.