Grammarsymbols

Grammarsymbols are the symbols used to define grammars in formal language theory. A grammar G is typically described by a quadruple (N, Σ, P, S), where N is a finite set of nonterminal symbols, Σ is a finite set of terminal symbols, P is a set of production rules, and S is the designated start symbol. Grammarsymbols fall into two main classes: terminals and nonterminals. Terminals are the basic symbols that appear in the strings of the language and cannot be replaced during derivations. Nonterminals are symbols that stand for sequences of terminals and/or other nonterminals and are replaced by the productions in P.

Production rules express how nonterminals can be rewritten as sequences of terminals and nonterminals. A rule has the form A -> α, where A ∈ N and α ∈ (N ∪ Σ)*. The start symbol S is the initial nonterminal from which derivations begin. In some notations, production arrows appear as ::= or →. The empty string is written ε, representing a production that yields nothing. The derivation relation (⇒) indicates step-by-step transformations from one string of symbols to another.

Notation systems such as BNF and EBNF provide conventions for writing grammars using grammarsymbols. In BNF, productions are written with angle brackets around nonterminals (for example <expr> ::= ...). In EBNF, meta-characters such as [ ], { }, and ( ) indicate optionality, repetition, and grouping, while | expresses alternatives. Grammarsymbols are central to the design of compilers and evaluators, formal language research, and parsing theory, serving as the basis for generating parse trees and for proving properties about languages. Example: with N = {S}, Σ = {a}, S as start symbol, and P: S -> a S | ε, the language consists of any number of a's.