Formal grammar
In [[formal semantics]], [[computer science]] and [[linguistics]], a '''formal grammar''' (also called '''formation rules''') is a precise description of a [[formal language]] – that is, of a [[set]] of [[String (computer science)|strings]] over some [[Alphabet (computer science)|alphabet]].  In other words, a grammar describes which of the possible sequences of symbols (strings) in a language constitute valid words or statements in that language, but it does not describe their [[semantics]] (i.e. what they mean).
The branch of mathematics that is concerned with the properties of formal grammars and languages is called [[formal language theory]].

A grammar is usually regarded as a means to [[generate]] all the valid strings of a language; it can also be used as the basis for a [[recognizer]] that determines for any given string whether it is [[grammatical]] (i.e. belongs to the language).  To describe such recognizers, formal language theory uses separate formalisms, known as [[automata theory|automata]].

A grammar can also be used to [[analyze]] the strings of a language – i.e. to describe their internal structure.  In computer science, this process is known as [[parsing]].  Most languages have very [[compositional semantics]], i.e. the meaning of their utterances is structured according to their [[syntax]]; therefore, the first step to describing the meaning of an utterance in language is to analyze it and look at its analyzed form (known as its [[parse tree]] in computer science, and as its [[deep structure]] in [[generative grammar]]).

== Background ==
=== Formal language ===
{{Main|Formal language}} 

A ''formal language'' is an organized [[set]] of [[symbol]]s the essential feature of which is that it can 
be precisely defined in terms of just the shapes and locations of those symbols. Such a language can be defined, then, without any [[reference]] to any [[meaning (linguistics)|meaning]]s of any of its expressions; it can exist before any [[formal interpretation]] is assigned to it -- that is, before it has any meaning. First order logic is expressed in some formal language. A formal grammar determines which symbols and sets of symbols are [[Formula (mathematical logic)|formula]]s in a formal language.

=== Formal systems ===
{{main|Formal system}}

A ''formal system'' (also called a ''logical calculus'', or a ''logical system'') consists of a formal language together with a [[deductive apparatus]] (also called a ''deductive system''). The deductive apparatus may consist of a set of [[transformation rule]]s (also called ''inference rules'') or a set of [[axiom]]s, or have both. A formal system is used to [[Proof theory|derive]] one expression from one or more other expressions.

=== Formal proofs ===
{{main|Formal proof}}

A ''formal proof'' is a sequence of well-formed formulas of a formal language, the last one of which is a [[theorem]] of a formal system. The theorem is a [[syntactic consequence]] of all the wffs preceding it in the proof. For a wff to qualify as part of a proof, it must be the result of applying a rule of the deductive apparatus of some formal system to the previous wffs in the proof sequence.

=== Formal interpretations ===
{{main|Formal semantics|Formal interpretation}}

An ''interpretation'' of a formal system is the assignment of meanings to the symbols, and truth-values to the sentences of a formal system. The study of formal interpretations is called [[formal semantics]]. ''Giving an interpretation'' is synonymous with ''constructing a [[Structure (mathematical logic)|model]].

== Formal grammars ==
{{main|formal language|generative grammar}}
A grammar mainly consists of a set of rules for transforming strings.  (If it ''only'' consisted of these rules, it would be a [[semi-Thue system]].)  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.  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 ways of generating the same single string, then the grammar is said to be [[ambiguous grammar|ambiguous]].

For example, assume the alphabet consists of <math>a</math> and <math>b</math>, the start symbol is <math>S</math> and we have the following rules:

: 1. <math>S \rightarrow aSb</math>
: 2. <math>S \rightarrow ba</math>

then we start with <math>S</math>, and can choose a rule to apply to it. If we choose rule 1, we obtain the string <math>aSb</math>. If we choose rule 1 again, we replace <math>S</math> with <math>aSb</math> and obtain the string <math>aaSbb</math>. This process can be repeated at will until all occurrences of ''S'' are removed, and only symbols from the alphabet remain (i.e., <math>a</math> and <math>b</math>). For example, if we now choose rule 2, we replace <math>S</math> with <math>ba</math> and obtain the string <math>aababb</math>, and are done. We can write this series of choices more briefly, using symbols: <math>S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb</math>. The language of the grammar is the set of all the strings that can be generated using this process: <math>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.

=== Formal definition ===
In the classic formalization of generative grammars first proposed by [[Noam Chomsky]] in the 1950s,<ref name="Chomsky1956">{{Cite journal 
 | author = Chomsky, Noam
 | title = Three Models for the Description of Language
 | journal = [[IRE Transactions on Information Theory]]
 | volume = 2 
 | issue = 2
 | pages = 113&ndash;123
 | year = 1956
 | doi = 10.1109/TIT.1956.1056813
}}</ref><ref name="Chomsky1957">{{Cite book
 | author = Chomsky, Noam
 | title = Syntactic Structures
 | publisher = [[Mouton]]
 | location = The Hague
 | year = 1957
}}</ref> a grammar ''G'' consists of the following components:
* A finite set <math>N</math> of ''[[nonterminal symbol]]s''.
* A finite set <math>\Sigma</math> of ''[[terminal symbol]]s'' that is [[Disjoint sets|disjoint]] from <math>N</math>.
* A finite set <math>P</math> of ''production rules'', each of the form
:: <math>(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*} </math> 
:where <math>{}^{*}</math> is the [[Kleene star]] operator and <math>\cup</math> denotes [[union (set theory)|set union]]. That is, each production rule maps from one string of symbols to another, where the first string contains at least one nonterminal symbol. In the case that the second string is the [[empty string]] &ndash; that is, that it contains no symbols at all &ndash; in order to avoid confusion, the empty string is often denoted with a special notation, often (<math>\lambda</math>, <math>e</math> or <math>\epsilon</math>.
* A distinguished symbol <math>S \in N</math> that is the ''start symbol''. 
A grammar is formally defined as the ordered quad-tuple <math>(N, \Sigma, P, S)</math>. Such a formal grammar is often called a ''rewriting system'' or a ''phrase structure grammar'' in the literature.<ref>{{cite book|first=Seymour|last=Ginsburg|authorlink=Seymour Ginsburg|title=Algebraic and automata theoretic properties of formal languages|publisher=North-Holland|pages=8-9|date=1975|isbn=0720425069}}</ref><ref>{{cite book|last=Harrison|first=Michael A.|authorlink=Michael A. Harrison|title=Introduction to Formal Language Theory|publisherAddison-Wesley Publishing Company|date=1978|pages=13|isbn=0201029553}}</ref>

The operation of a grammar can be defined in terms of relations on strings:
* Given a grammar <math>G = (N, \Sigma, P, S)</math>, the binary relation <math>\Rightarrow_G</math> (pronounced as  "G derives in one step") on strings in <math>(\Sigma \cup N)^{*}</math> is defined by:
<math>x \Rightarrow_G y \mbox{ iff } \exists u, v, w \in \Sigma^*, X \in N: x = uXv \wedge y = uwv \wedge X \rightarrow w \in P</math>
* the relation <math>{\Rightarrow_G}^*</math> (pronounced as ''G derives in zero or more steps'') is defined as the [[transitive closure]] of <math>(\Sigma \cup N)^{*}</math>
* the ''language'' of <math>G</math>, denoted as <math>\boldsymbol{L}(G)</math>, is defined as all those strings over <math>\Sigma</math> that can be generated by starting with the start symbol <math>S</math> and then applying the production rules in <math>P</math> until no more nonterminal symbols are present; that is, the set <math>\{ w \in \Sigma^* \mid S {\Rightarrow_G}^* w \}</math>.

Note that the grammar <math>G = (N, \Sigma, P, S)</math> is effectively the [[semi-Thue system]] <math>(N \cup \Sigma, P)</math>, 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 <math>S</math> to strings without nonterminal symbols.

=== Example ===
''For these examples, formal languages are specified using [[set-builder notation]].''

Consider the grammar <math>G</math> where <math>N = \left \{S, B\right \}</math>, <math>\Sigma = \left \{a, b, c\right \}</math>, <math>S</math> is the start symbol, and <math>P</math> consists of the following production rules:

: 1. <math>S \rightarrow aBSc</math>
: 2. <math>S \rightarrow abc</math>
: 3. <math>Ba \rightarrow aB</math>
: 4. <math>Bb \rightarrow bb </math>

Some examples of the derivation of strings in <math>\boldsymbol{L}(G)</math> are: 

* <math>\boldsymbol{S} \Rightarrow_2 \boldsymbol{abc}</math>
* <math>\boldsymbol{S} \Rightarrow_1 \boldsymbol{aBSc} \Rightarrow_2 aB\boldsymbol{abc}c \Rightarrow_3 a\boldsymbol{aB}bcc \Rightarrow_4 aa\boldsymbol{bb}cc</math>
* <math>\boldsymbol{S} \Rightarrow_1 \boldsymbol{aBSc} \Rightarrow_1 aB\boldsymbol{aBSc}c \Rightarrow_2 aBaB\boldsymbol{abc}cc \Rightarrow_3 a\boldsymbol{aB}Babccc \Rightarrow_3 aaB\boldsymbol{aB}bccc </math><math> \Rightarrow_3 aa\boldsymbol{aB}Bbccc \Rightarrow_4 aaaB\boldsymbol{bb}ccc \Rightarrow_4 aaa\boldsymbol{bb}bccc</math>

:(Note on notation: <math>L \Rightarrow_i R</math> reads "''L'' generates ''R'' by means of production ''i''" and the generated part is each time indicated in bold.)

This grammar defines the language <math>L = \left \{ a^{n}b^{n}c^{n} | n \ge 1 \right \}</math> where <math>a^{n}</math> denotes a string of ''n'' consecutive <math>a</math>'s. Thus, the language is the set of strings that consist of 1 or more <math>a</math>'s, followed by the same number of <math>b</math>'s, followed by the same number of <math>c</math>'s.

=== The Chomsky hierarchy ===
{{main|Chomsky hierarchy}} <!-- for me THIS article is BETTER, but for wiki structure the whole article is bigger than a section -->
When [[Noam Chomsky]] first formalized generative grammars in 1956,<ref name="Chomsky1956"/> 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 express fewer formal languages. Two important types are ''[[context-free grammar]]s'' (Type 2) and ''[[regular grammar]]s'' (Type 3). The languages that can be described with such a grammar are called ''[[context-free language]]s'' and ''[[regular language]]s'', 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 [[parsing|parser]]s for them can be efficiently implemented.<ref name="Grune&Jacobs1990">Grune, Dick & Jacobs, Ceriel H., ''Parsing Techniques &ndash; A Practical Guide'', Ellis Horwood, England, 1990.</ref> 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 parser]]s and [[LR parser]]s 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 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 <math>\left \{ a^{n}b^{n} | n \ge 1 \right \}</math> (at least 1 <math>a</math> followed by the same number of <math>b</math>'s) is context-free, as it can be defined by the grammar <math>G_2</math> with <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, <math>S</math> the start symbol, and the following production rules:

: 1. <math>S \rightarrow aSb</math>
: 2. <math>S \rightarrow ab</math>

A context-free language can be recognized in <math>O(n^3)</math> time (''see'' [[Big O notation]]) by an algorithm such as [[Earley's algorithm]]. That is, for every context-free language, a machine can be built that takes a string as input and determines in <math>O(n^3)</math> time whether the string is a member of the language, where <math>n</math> is the length of the string.<ref name="Earley1970">Earley, Jay, "An Efficient Context-Free Parsing Algorithm," ''Communications of the ACM'', Vol. 13 No. 2, pp. 94-102, February 1970.</ref> Further, some important subsets of the context-free languages can be recognized in linear time using other algorithms.

==== Regular grammars ====
In [[regular grammar]]s, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted: It 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 [[syntactic sugar|easier to denote]] while still defining the same class of languages.)

The language defined above is not regular, but the language <math>\left \{ a^{n}b^{m} \,| \, m,n \ge 1 \right \}</math> (at least 1 <math>a</math> followed by at least 1 <math>b</math>, where the numbers may be different) is, as it can be defined by the grammar <math>G_3</math> with <math>N=\left \{S, A,B\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, <math>S</math> the start symbol, and the following production rules:

:# <math>S \rightarrow aA</math>
:# <math>A \rightarrow aA</math>
:# <math>A \rightarrow bB</math>
:# <math>B \rightarrow bB</math>
:# <math>B \rightarrow \epsilon</math>

All languages generated by a regular grammar can be recognized in linear time by a [[finite state machine]]. Although, in practice, regular grammars are commonly expressed using [[regular expression]]s, 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 more recently, 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 [[parsing|parse]]. Some forms of grammars developed include:

* [[Tree-adjoining grammar]]s increase the expressiveness of conventional generative grammars by allowing rewrite rules to operate on [[parse tree]]s instead of just strings.<ref name="JoshiEtAl1975">Joshi, Aravind K., ''et al.'', "Tree Adjunct Grammars," ''Journal of Computer Systems Science'', Vol. 10 No. 1, pp. 136-163, 1975.</ref>
* [[Affix grammar]]s<ref name="Koster1971">Koster , Cornelis H. A., "Affix Grammars," in ''ALGOL 68 Implementation'', North Holland Publishing Company, Amsterdam, p. 95-109, 1971.</ref> and [[attribute grammar]]s<ref name="Knuth1968">Knuth, Donald E., "Semantics of Context-Free Languages," ''Mathematical Systems Theory'', Vol. 2 No. 2, pp. 127-145, 1968.</ref><ref name="Knuth1971">Knuth, Donald E., "Semantics of Context-Free Languages (correction)," ''Mathematical Systems Theory'', Vol. 5 No. 1, pp 95-96, 1971.</ref> allow rewrite rules to be augmented with semantic attributes and operations, useful both for increasing grammar expressiveness and for constructing practical language translation tools.

== Analytic grammars ==
Though there is very little 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:

* [[The Language Machine]] <ref name="TheLanguageMachine">[http://languagemachine.sourceforge.net the language machine<!-- Bot generated title -->]</ref> directly implements unrestricted analytic grammars. Substitution rules are used to transform an input to produce outputs and behaviour. The system can also produce [http://languagemachine.sourceforge.net/picturebook.html the lm-diagram] which shows what happens when the rules of an unrestricted analytic grammar are being applied.
* [[Top-down parsing language]] (TDPL): a highly minimalist analytic grammar formalism developed in the early 1970s to study the behavior of [[Top-down parsing|top-down parsers]].<ref name="Birman1970">Birman, Alexander, ''The TMG Recognition Schema'', Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.</ref>
* [[Link grammar]]s: a form of analytic grammar designed for [[linguistics]], which derives syntactic structure by examining the positional relationships between pairs of words.<ref name="Sleater&Temperly1991">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.</ref><ref name="Sleater&Temperly1993">Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," ''Third International Workshop on Parsing Technologies'', 1993. (Revised version of above report.)</ref>
* [[Parsing expression grammar]]s (PEGs): a more recent generalization of TDPL designed around the practical [[expressiveness]] needs of [[programming language]] and [[compiler]] writers.<ref>Ford, Bryan, ''Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking'', Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.</ref>

==References==

<references/>

==See also==
<div style="-moz-column-count:3; column-count:3;">
* [[Abstract syntax tree]]
* [[Adaptive grammar]]
* [[Ambiguous grammar]]
* [[Backus–Naur form|Backus–Naur form (BNF)]]
* [[Concrete syntax tree]]
* [[Extended Backus–Naur form|Extended Backus–Naur form (EBNF)]]
* [[Grammar framework]]
* [[L-system]]
* [[Lojban]]
* [[Post canonical system]]
</div>

==External links==
* [http://www.formalgrammar.tk/ Yearly Formal Grammar conference]

{{logic}}
{{Formal languages and grammars}}

[[Category:Formal languages]]
[[Category:Sentential logic]]

[[bs:Formalna gramatika]]
[[cs:Formální gramatika]]
[[de:Formale Grammatik]]
[[et:Formaalne grammatika]]
[[el:Τυπική γραμματική]]
[[es:Gramática formal]]
[[fr:Grammaire formelle]]
[[gl:Gramática formal]]
[[ko:형식 문법]]
[[hr:Formalna gramatika]]
[[it:Grammatica formale]]
[[hu:Formális nyelvtan]]
[[nl:Formele grammatica]]
[[ja:形式文法]]
[[pl:Gramatyka formalna]]
[[pt:Gramática formal]]
[[ru:Формальная грамматика]]
[[sr:Формална граматика]]
[[fi:Formaali kielioppi]]
[[sv:Formell grammatik]]
[[uk:Формальні граматики]]
[[zh:形式文法]]