A grammar is used to describe how the vocabulary (tokens) of the language can be correctly used, i.e., how valid sentences can be formed from tokens. This relates broadly to linguistics in general. There are several types of grammars: unstructured, context-sensitive, context-free, regular, etc.
A grammar is {left, right}-recursive if and only if there exists a non-terminal symbol that can derive to a sentential form with itself as the {leftmost, rightmost} symbol. In other words, the non-terminal symbol should be on the {leftmost, rightmost}. The most common form is direct self-recursive, when the definition can be satisfied with only one substitution.
Ambiguity
A grammar is said to be ambiguous if there exists more than one parse tree for a given sentence. If there exists more than one leftmost/rightmost derivation, or if the leftmost and rightmost derivations give us different parse trees.
In compiler design we favour unambiguous grammars.
There’s no algorithmic way to detect and remove ambiguity (i.e., it is NP-complete), but there are some heuristics and rules we can use to disambiguate. We find that reducing ambiguity generally tends to involve reducing .
Some ways we can get rid of the ambiguity:
- Get rid of one of the recursions. For example, we could induce left-recursion only, assuming associativity can be defined from left to right.