CS 3723  Programming Languages
Types of Grammars

This is the third of 3 pages about grammars.

1. Formal Grammars (Introduction)
2. Derivations, Parse Trees, Ambiguity
3. Types of Grammars (this page)

In page 1 above, familiarize yourself with the terms:

• symbols,
• alphabet,
• sentence,
• language,
• context-free Grammars (also called: CFG, Formal Grammar, BNF Grammar, Backus-Naur grammar, or just a grammar.

Context-free grammar (CFG):

• terminal symbols = terminals,
• non-terminal symbols = non-terminals,
• replacement rules = rewriting rules, or productions, or just rules
• derivation = derivation sequence, or replacement sequence

In page 2 above, familiarize yourself with the terms:

• rightmost derivation,
• leftmost derivation,
• parse tree,
• ambiguity, that is ambiguous grammar.

Regular grammars are a special case of the context-free grammars we have emphasized.

Definition of Regular Grammar: A regular grammar is a CF grammar, where each grammar rule has at most one non-terminal on the right hand side, and if present, this non-terminal must be at the right end. There can be any number of non-terminals in the right-hand side, including none at all.

It turns out that regular grammars generate exactly the same languages as are recognized by finite state automata (that is, NFAs, DFAs, or NFAs with ε-moves). This is also exactly the same languages at are described by regular expressions.

For example, consider the regular expression /b(ab)*/. One corresponding regular grammar is:

S ---> bT
T ---> abT | ε

The regular expression /(a|b)*abb/ can be described by the regular grammar:

S ---> aS | bS | abb

The CF grammars describe a much larger collection of languages than the regular languages. A CF grammar is a more powerful tool than a regular grammar, and the definition makes it clear that the regular grammars are a special case of CF grammars. It turns out that there is a class of finite automata that have an additional stack to save items on called PDAs or Push-Down Automata. The languages recognized by PDAs are exactly the same as those described by context-free grammars.

In fact, soon we will study a shift-reduce parser, which is just a finite machine with a stack. A shift-reduce parser can't handle all CF languages. More complicated LR parsers push states as well as symbols onto a stack, and they can handle a larger class of languages, but still not all CF languages.

These grammars allow anything at all on the left side of a rule. For example (here only the lower-case a is terminal):

This grammar describes the language {aⁱ | i is a positive power of 2}, that is all strings a²ⁿ, for n > 0.

One can simulate an arbitrary Turing machine using an unrestricted grammar, which means that one can carry out any computation at all with such a grammar.

Here are some additional examples of unrestricted grammars: Examples1, Examples2, Examples3