"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.