startsymbool

Startsymbool is a term used in formal grammar and rewriting systems to denote the initial symbol from which all strings of the language are derived. It is typically a nonterminal symbol, distinct from the terminal symbols that appear in the generated strings. The start symbol is the root of every derivation and of the parse tree for any sentence belonging to the language.

In a context-free grammar G = (V, Σ, R, S), S is the start symbol. From S, production rules are applied to replace nonterminals with sequences of nonterminals and terminals until a string of terminals is obtained. For example, in a simple arithmetic grammar, the start symbol E may have productions such as E → E + T | T.

Most grammars use a single start symbol, but some grammars permit multiple designated starts. In parsing, it is common to define an augmented grammar by introducing a new start symbol S' and a rule S' → S. This creates a unique starting point required by certain parsing algorithms (for example LR parsers) and simplifies the construction of parsing tables.

If the start symbol can derive the empty string, the language includes the empty string. Otherwise, the empty string is not in the language.

The startsymbool is a conventional, language-agnostic notion and does not prescribe any particular syntax; its exact symbol is arbitrary, though S is the common default. See also grammar, nonterminal, production rule, Chomsky hierarchy, parsing.