Nonterminals

Nonterminals are symbols used in formal grammars to denote syntactic categories that can be replaced by groups of other symbols according to production rules. They are distinguished from terminals, which are the actual symbols of the language (such as words or tokens). In a grammar G = (V, Σ, R, S), V is the set of nonterminals, Σ is the set of terminals, R is the set of productions, and S is the designated start symbol. A production has the form A → α, where A is a nonterminal and α is a string over the combined alphabet (V ∪ Σ), which may include terminals, nonterminals, or even the empty string ε.

Nonterminals serve to encode the hierarchical structure of a language. For example, a simple context-free grammar might include productions like S → NP VP, NP → Det N, VP → V NP, Det → "the" | "a", N → "cat" | "dog", and V → "sees" | "pets". Here S, NP, VP, Det, N, and V are nonterminals, while "the", "a", "cat", "dog" and similar strings are terminals. Through successive applications of productions, nonterminals are rewritten to derive strings consisting solely of terminals.

Derivations can be represented as parse trees, where each internal node is labeled by a nonterminal and its children spell out the production used. Nonterminals may be nullable (they can derive the empty string) and grammars may include unit productions (A → B), which are often eliminated in grammar normalization. In the Chomsky hierarchy, nonterminals are central to context-free grammars, widely used in programming language design and compiler construction to capture the recursive, hierarchical nature of syntax. Nonterminals are conventionally denoted by uppercase symbols.