Editing Context-free grammar (section)

== Subclasses ==
There are a number of important subclasses of the context-free grammars:
* [[LR parser|LR(''k'')]] grammars (also known as [[deterministic context-free grammar]]s) allow [[parsing]] (string recognition) with [[deterministic pushdown automaton|deterministic pushdown automata]] (PDA), but they can only describe [[deterministic context-free language]]s.
* [[SLR grammar|Simple LR]], [[LALR parser|look-ahead LR]] grammars are subclasses that allow further simplification of parsing. SLR and LALR are recognized using the same PDA as LR, but with simpler tables, in most cases.
* [[LL parser|LL(''k'') and LL(''*'')]] grammars allow parsing by direct construction of a leftmost derivation as described above, and describe even fewer languages.
* [[Simple grammar]]s 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 grammar]]s have the property that the terminal symbols are divided into left and right bracket pairs that always match up in rules.
* [[Linear grammar]]s have no rules with more than one nonterminal on the right-hand side.
* [[Regular grammar]]s are a subclass of the linear grammars and describe the [[regular language|regular]] languages, i.e. they correspond to [[finite automaton|finite automata]] and [[regular expression]]s.

LR parsing extends LL parsing to support a larger range of grammars; in turn, [[GLR parser|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 grammar]]s, it is as efficient as can be expected.  Although GLR parsing was developed in the 1980s, many new language definitions and [[parser generator]]s continue to be based on LL, LALR or LR parsing up to the present day.