Productions: || A → xB |
|| A → x |
|| A,B ∈ N |
|| x ∈ T
Only one nonterminal can appear in any derived string,
and it must appear at the right end.
Equivalent to a deterministic finite automaton (simple program).
- Parser never has to back up or do search.
- Linear parsing time.
- Used for simplest items (identifiers, numbers, word forms).
- Any finite language is regular.
- Any language that can be recognized using
finite memory is regular.