In
formal language theory, a grammar is a finite set of rewriting rules describing the replacement of
strings of symbols with other strings. That is, each rule is given by a pair of strings.
The language generated by a grammar is defined as the set of strings that can be formed by arbitrarily substituting substrings according to the rules, starting from the string consisting of some fixed initial symbol.
Usually, only the strings formed from a designated subset of symbols, the terminal symbols, are counted as part of the generated language; any other symbols that occur in rules are called nonterminals, and strings containing nonterminals are only used as intermediate results. Furthermore, all left hand sides of rules are required to contain at least one nonterminal. These restrictions do not really affect the formalism much.
General grammars are fully expressive (Turing complete) devices to describe languages, and therefore, they are of limited practical value. It is impossible, for instance, to write a program that, given a grammar and a string, tells you whether or not the string can be derived with the grammar.
More restricted forms of grammar exist that, at the expense of some expressive power, do allow systematic parsing of strings; some important ones are given by the Chomsky hierarchy.