A regular grammar of natural numbers could be
<number> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| 0<number> | 1<number> | 2<number>
| 3<number> | 4<number> | 5<number>
| 6<number> | 7<number> | 8<number>
| 9<number>
A context-free grammar of simple arithmetic expressions could be
<E> ::= <E> + <T> | <E> – <T> | <T>
<T> ::= <T> * <F> | <T> / <F> | <F>
<F> ::= ( <E> ) | <number>
The Chmosky hierarchy shows every regular set is a context-free language.
Why Using Regular Grammars
- Regular grammars are simple.
- Efficient lexical analyzers can be constructed from regular grammars.
- Modular design is achieved.
When to Use Regular Grammars and Context-Free Grammars
- Regular grammars are for the structure of lexical constructs such as identifiers, constants, keywords, and so forth.
For example, a regular grammar for the language {
an | n is an integer ≥ 0} is
<A> ::= a <A> | ε
- Context-free grammars are for the nested structures such as balanced parentheses, matching begin-end's, if-then-else's, and so forth.
For example, a context-free grammar for the strings of all balanced parentheses such as the string “
(()(()))()” is
<A> ::= ( <A> ) <A> | ε