Slide 2.4: Context-free grammars vs regular grammars

Slide 2.3: The Chomsky hierarchy (cont.)
Slide 2.5: Context-free grammars
Home

Context-Free Grammars vs Regular Grammars

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 {aⁿ | n is an integer ≥ 0}
```
   <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> | ε
```