A formalism for describing languages. This works for regular and fancier languages.
Rules:
- Lines with an arrow (→) are Derivations
- Terminals: A concrete character that may appear in the input
- Non-terminals: An abstract symbol. Must be defined by 1+ rules.
- Alternation: The bar (|) means OR
- Repetition: * means 1+
EBNF creates productions which you use to create ASTs.
Ambiguity
Multiple of the same terminal in the same sub-NFA is an indication of ambiguity. Note that subtraction and division and left associative which is left recursive. Things that are left recursive cannot be LL(1). What we do, is refactor to write a weakly equivalent grammar in EBNF using repetition that does not constrain the associativity.