Context-free Grammar - Subclasses

Subclasses

There are a number of important subclasses of the context-free grammars:

• LR(k) grammars (also known as deterministic context-free grammars) allow parsing (string recognition) with deterministic pushdown automata, but they can only describe deterministic context-free languages.

• Simple LR, Look-Ahead LR grammars are subclasses that allow further simplification of parsing.

• LL(k) and LL(*) grammars allow parsing by direct construction of a leftmost derivation as described above, and describe even fewer languages.

• Simple grammars are a subclass of the LL(1) grammars mostly interesting for its theoretical property that language equality of simple grammars is decidable, while language inclusion is not.

• Bracketed grammars have the property that the terminal symbols are divided into left and right bracket pairs that always match up in rules.

• Linear grammars have no rules with more than one nonterminal in the right hand side.

• Regular grammars are a subclass of the linear grammars and describe the regular languages, i.e. they correspond to finite automata and regular expressions.

LR parsing extends LL parsing to support a larger range of grammars; in turn, generalized LR parsing extends LR parsing to support arbitrary context-free grammars. On LL grammars and LR grammars, it essentially performs LL parsing and LR parsing, respectively, while on nondeterministic grammars, it is as efficient as can be expected. Although GLR parsing was developed in the 1980s, many new language definitions and parser generators continue to be based on LL, LALR or LR parsing up to the present day.