Formal grammar

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for strings in a formal language.
Formal language theory, the discipline that studies formal grammars and languages, is a branch of applied mathematics. Its applications are found in theoretical computer science, theoretical linguistics, formal semantics, mathematical logic, and other areas.
A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a "recognizer"—a function in computing that determines whether a given string belongs to the language or is grammatically incorrect. To describe such recognizers, formal language theory uses separate formalisms, known as automata theory. One of the interesting results of automata theory is that it is not possible to design a recognizer for certain formal languages.
Parsing is the process of recognizing an utterance (a string in natural languages) by breaking it down to a set of symbols and analyzing each one against the grammar of the language. Most languages have the meanings of their utterances structured according to their syntax—a practice known as compositional semantics. As a result, the first step to describing the meaning of an utterance in language is to break it down part by part and look at its analyzed form (known as its parse tree in computer science, and as its deep structure in generative grammar).
History.
's treatise "Astadyayi" gives formal production rules and definitions to describe the formal grammar of Sanskrit. There are different uses of "form" and "formalism", which have changed over time, depending on the fields the relevant author was in contact with. A historical overview of the concept is given in 
Introductory example.
A grammar mainly consists of a set of "production rules", rewriting rules for transforming strings. Each rule specifies a replacement of a particular string (its "left-hand side") with another (its "right-hand side"). A rule can be applied to each string that contains its left-hand side and produces a string in which an occurrence of that left-hand side has been replaced with its right-hand side.
Unlike a semi-Thue system, which is wholly defined by these rules, a grammar further distinguishes between two kinds of symbols: "nonterminal" and "terminal" symbols; each left-hand side must contain at least one nonterminal symbol. It also distinguishes a special nonterminal symbol, called the "start symbol".
The language generated by the grammar is defined to be the set of all strings without any nonterminal symbols that can be generated from the string consisting of a single start symbol by (possibly repeated) application of its rules in whatever way possible.
If there are essentially different ways of generating the same single string, the grammar is said to be ambiguous.
In the following examples, the terminal symbols are "a" and "b", and the start symbol is "S".
Example 1.
Suppose we have the following production rules:
then we start with "S", and can choose a rule to apply to it. If we choose rule 1, we obtain the string "aSb". If we then choose rule 1 again, we replace "S" with "aSb" and obtain the string "aaSbb". If we now choose rule 2, we replace "S" with "ba" and obtain the string "", and are done. We can write this series of choices more briefly, using symbols: formula_3.
The language of the grammar is the infinite set formula_4, where formula_5 is formula_6 repeated formula_7 times (and formula_8 in particular represents the number of times production rule 1 has been applied). This grammar is context-free (only single nonterminals appear as left-hand sides) and unambiguous.
Examples 2 and 3.
Suppose the rules are these instead:
This grammar is not context-free due to rule 3 and it is ambiguous due to the multiple ways in which rule 2 can be used to generate sequences of formula_12s.
However, the language it generates is simply the set of all nonempty strings consisting of formula_6s and/or formula_14s.
This is easy to see: to generate a formula_14 from an formula_12, use rule 2 twice to generate formula_17, then rule 1 twice and rule 3 once to produce formula_14. This means we can generated arbitrary nonempty sequences of formula_12s and then replace each of them with formula_6 or formula_14 as we please.
That same language can alternatively be generated by a context-free, nonambiguous grammar; for instance, the regular grammar with rules
Formal definition.
The syntax of grammars.
In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s, a grammar "G" consists of the following components:
A grammar is formally defined as the tuple formula_33. Such a formal grammar is often called a rewriting system or a phrase structure grammar in the literature.
Some mathematical constructs regarding formal grammars.
The operation of a grammar can be defined in terms of relations on strings:
Note that the grammar formula_34 is effectively the semi-Thue system formula_49, rewriting strings in exactly the same way; the only difference is in that we distinguish specific "nonterminal" symbols, which must be rewritten in rewrite rules, and are only interested in rewritings from the designated start symbol formula_12 to strings without nonterminal symbols.
Example.
"For these examples, formal languages are specified using set-builder notation."
Consider the grammar formula_44 where formula_52, formula_53, formula_12 is the start symbol, and formula_55 consists of the following production rules:
This grammar defines the language formula_60 where formula_61 denotes a string of "n" consecutive formula_6's. Thus, the language is the set of strings that consist of 1 or more formula_6's, followed by the same number of formula_14's, followed by the same number of formula_65's.
Some examples of the derivation of strings in formula_66 are: 
The Chomsky hierarchy.
When Noam Chomsky first formalized generative grammars in 1956, he classified them into types now known as the Chomsky hierarchy. The difference between these types is that they have increasingly strict production rules and can therefore express fewer formal languages. Two important types are "context-free grammars" (Type 2) and "regular grammars" (Type 3). The languages that can be described with such a grammar are called "context-free languages" and "regular languages", respectively. Although much less powerful than unrestricted grammars (Type 0), which can in fact express any language that can be accepted by a Turing machine, these two restricted types of grammars are most often used because parsers for them can be efficiently implemented. For example, all regular languages can be recognized by a finite-state machine, and for useful subsets of context-free grammars there are well-known algorithms to generate efficient LL parsers and LR parsers to recognize the corresponding languages those grammars generate.
Context-free grammars.
A "context-free grammar" is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called "context-free languages".
The language formula_60 defined above is not a context-free language, and this can be strictly proven using the pumping lemma for context-free languages, but for example the language formula_69 (at least 1 formula_6 followed by the same number of formula_14's) is context-free, as it can be defined by the grammar formula_72 with formula_73, formula_74, formula_12 the start symbol, and the following production rules:
A context-free language can be recognized in formula_78 time ("see" Big O notation) by an algorithm such as Earley's recogniser. That is, for every context-free language, a machine can be built that takes a string as input and determines in formula_78 time whether the string is a member of the language, where formula_8 is the length of the string. Deterministic context-free languages is a subset of context-free languages that can be recognized in linear time. There exist various algorithms that target either this set of languages or some subset of it.
Regular grammars.
In regular grammars, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted. The right side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else. (Sometimes a broader definition is used: one can allow longer strings of terminals or single nonterminals without anything else, making languages easier to denote while still defining the same class of languages.)
The language formula_69 defined above is not regular, but the language formula_82 (at least 1 formula_6 followed by at least 1 formula_14, where the numbers may be different) is, as it can be defined by the grammar formula_85 with formula_86, formula_74, formula_12 the start symbol, and the following production rules:
All languages generated by a regular grammar can be recognized in formula_94 time by a finite-state machine. Although, in practice, regular grammars are commonly expressed using regular expressions, some forms of regular expression used in practice do not strictly generate the regular languages and do not show linear recognitional performance due to those deviations.
Other forms of generative grammars.
Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. Some forms of grammars developed include:
Recursive grammars.
A recursive grammar is a grammar that contains production rules that are recursive. For example, a grammar for a context-free language is left-recursive if there exists a non-terminal symbol "A" that can be put through the production rules to produce a string with "A" as the leftmost symbol. An example of recursive grammar is a clause within a sentence separated by two commas. All types of grammars in the Okoye hierarchy can be recursive.
Analytic grammars.
Though there is a tremendous body of literature on parsing algorithms, most of these algorithms assume that the language to be parsed is initially "described" by means of a "generative" formal grammar, and that the goal is to transform this generative grammar into a working parser. Strictly speaking, a generative grammar does not in any way correspond to the algorithm used to parse a language, and various algorithms have different restrictions on the form of production rules that are considered well-formed.
An alternative approach is to formalize the language in terms of an analytic grammar in the first place, which more directly corresponds to the structure and semantics of a parser for the language. Examples of analytic grammar formalisms include the following: