Jump to content

Production (computer science)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Jarble (talk | contribs) at 21:20, 16 May 2015 (disambiguating a link). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions is the main component in the specification of a formal grammar (specifically a generative grammar). The other components are a finite set of nonterminal symbols, a finite set (known as an alphabet) of terminal symbols that is disjoint from and a distinguished symbol that is the start symbol.

In an unrestricted grammar, a production is of the form where and are arbitrary strings of terminals and nonterminals however may not be the empty string. If is the empty string, this is denoted by the symbol , or (rather than leave the right-hand side blank). So productions are of the form:

where is the Kleene star operator, and denotes set union.

The other types of formal grammar in the Chomsky hierarchy impose additional restrictions on what constitutes a production. Notably in a context-free grammar, the left-hand side of a production must be a single nonterminal symbol. So productions are of the form:

Grammar generation

To generate a string in the language, one begins with a string consisting of only a single start symbol, and then successively applies the rules (any number of times, in any order) to rewrite this string. This stops when we obtain a string containing only terminals. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating this single string, then the grammar is said to be ambiguous.

For example, assume the alphabet consists of and , with the start symbol , and we have the following rules:

1.
2.

then we start with , and can choose a rule to apply to it. If we choose rule 1, we replace with and obtain the string . If we choose rule 1 again, we replace with and obtain the string . This process is repeated until we only have symbols from the alphabet (i.e., and ). If we now choose rule 2, we replace with and obtain the string , and are done. We can write this series of choices more briefly, using symbols: . The language of the grammar is the set of all the strings that can be generated using this process: .

See also