Formal grammar
|
|
In computer science a formal grammar is an abstract structure that describes a formal language precisely, i.e., a set of rules that mathematically delineates a (usually infinite) set of finite-length strings over a (usually finite) alphabet. Formal grammars are so named by analogy to grammar in human languages.
Formal grammars fall into two main categories: generative and analytic.
- A generative grammar, the most well-known kind, is a set of rules by which all possible strings in the language to be described can be generated by successively rewriting strings starting from a designated start symbol. A generative grammar in effect formalizes an algorithm that generates strings in the language.
- An analytic grammar, in contrast, is a set of rules that assume an arbitrary string to be given as input, and which successively reduce or analyze that input string yield a final boolean, "yes/no" result indicating whether or not the input string is a member of the language described by the grammar. An analytic grammar in effect formally describes a parser for a language.
In short, an analytic grammar describes how to read a language, whereas a generative grammar describes how to write it.
| Contents |
Generative grammars
A generative grammar consists of a set of rules for transforming strings. 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, and if there are multiple different ways of generating a single string, then the grammar is said to be 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 \longrightarrow aSb<math>
- 2. <math>S \longrightarrow ba<math>
then we start with "<math>S<math>", and can choose a rule to apply to it. If we choose rule 1, we replace '<math>S<math>' with '<math>aSb<math>' and obtain "<math>aSb<math>". If we choose rule 1 again, we replace '<math>S<math>' with '<math>aSb<math>' and obtain "<math>aaSbb<math>". This process is repeated until we only have symbols from the alphabet (i.e., '<math>a<math>' and '<math>b<math>'). Finishing off our example, if we now choose rule 2, we replace '<math>S<math>' with '<math>ba<math>' and obtain "<math>aababb<math>", and are done. We can write this series of choices more briefly, using symbols: <math>S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow 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, a grammar G consists of the following components:
- A finite set <math>N<math> of nonterminal symbols.
- A finite set <math>\Sigma<math> of terminal symbols that is disjoint from <math>N<math>.
- A finite set <math>P<math> of production rules where a rule is of the form
- string in <math>(\Sigma \cup N)^{*} \longrightarrow<math> string in <math>(\Sigma \cup N)^{*} <math>
- (where <math>{}^{*}<math> is the Kleene star and <math>\cup<math> is union) with the restriction that the left-hand side of a rule (i.e., the part to the left of the <math>\longrightarrow<math>) must contain at least one nonterminal symbol.
- A symbol <math>S<math> in <math>N<math> that is indicated as the start symbol.
Usually such a formal grammar <math>G<math> is simply summarized as <math>(N, \Sigma, P, S)<math>.
The language of a formal grammar <math>G = (N, \Sigma, P, S)<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.
Example
Consider, for example, the grammar <math>G<math> with <math>N = \left \{S, B\right \}<math>, <math>\Sigma = \left \{a, b, c\right \}<math>, <math>P<math> consisting of the following production rules
- 1. <math>S \longrightarrow aBSc<math>
- 2. <math>S \longrightarrow abc<math>
- 3. <math>Ba \longrightarrow aB<math>
- 4. <math>Bb \longrightarrow bb <math>
and the nonterminal symbol <math>S<math> as the start symbol. Some examples of the derivation of strings in <math>\boldsymbol{L}(G)<math> are:
- <math>\boldsymbol{S} \longrightarrow (2) abc<math>
- <math>\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (2) a\boldsymbol{Ba}bcc \longrightarrow (3) aa\boldsymbol{Bb}cc \longrightarrow (4) aabbcc<math>
- <math>\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (1) aBaB\boldsymbol{S}cc \longrightarrow (2) a\boldsymbol{Ba}Babccc \longrightarrow (3) aaB\boldsymbol{Ba}bccc\longrightarrow (3) aa\boldsymbol{Ba}Bbccc <math><math> \longrightarrow (3) aaaB\boldsymbol{Bb}ccc \longrightarrow (4) aaa\boldsymbol{Bb}bccc \longrightarrow (4) aaabbbccc<math>
(where the used production rules are indicated in brackets and the replaced part is each time indicated in bold).
It is clear that this grammar defines the language <math>\left \{ a^{n}b^{n}c^{n} | n > 0 \right \}<math> where <math>a^{n}<math> denotes a string of n <math>a<math>'s.
Generative formal grammars are identical to Lindenmayer systems (L-systems), except that L-systems are not affected by a distinction between terminals and nonterminals, L-systems have restrictions on the order in which the rules are applied, and L-systems can run forever, generating an infinite sequence of strings. Typically, each string is associated with a set of points in space, and the "output" of the L-system is defined to be the limit of those sets.
The Chomsky Hierarchy
When Noam Chomsky first formalized generative grammars in the 1950s, he classified them into four 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 grammars and regular grammars. 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, 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, for context-free grammars there are well-known algorithms to generate efficient LL parsers and LR parsers.
Context-free grammars
In context-free grammars, the left hand side of a production rule may only be formed by a single non-terminal symbol. The language defined above is not a context-free language, but for example the language <math>{ a^{n}b^{n} | n > 0 }<math> is, as it can be defined by the grammar <math>G2<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 \longrightarrow aSb<math>
- 2. <math>S \longrightarrow ab<math>
Regular grammars
In regular grammars, the left hand side is again only a single non-terminal symbol, but now the right-hand side is also restricted: It may be nothing, or a single terminal symbol, or a single terminal symbol followed by a non-terminal symbol, but nothing else. (Sometimes a broader definition is used: one can allow longer strings of terminals or single non-terminals without anything else 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 > 0 \right \}<math> is, as it can be defined by the grammar <math>G3<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:
- 1. <math>S \longrightarrow aA<math>
- 2. <math>A \longrightarrow aA<math>
- 3. <math>A \longrightarrow bB<math>
- 4. <math>B \longrightarrow bB<math>
- 5. <math>B \longrightarrow \epsilon<math>
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 parse. Of course these two goals tend to be at odds: the more expressive a grammar formalism is, the harder it is to analyze or parse using automated tools. Some forms of grammars more recently developed include:
- Tree-adjoining grammars increase the expressiveness of conventional generative grammars by allowing rewrite rules to operate on parse trees instead of just strings.
- Affix Grammars and attribute grammars allow rewrite rules to be augmented with semantic attributes and operations, useful both for increasing grammar expressiveness and for constructing practical language translation tools.
A yearly conference is devoted to formal grammars: [1] (http://www.formalgrammar.tk)
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. 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 of a parser for the language. Examples of analytic grammar formalisms include the following:
- Top-down parsing language (TDPL): a highly minimalist analytic grammar formalism developed in the early 1970s to study the behavior of top-down parsers.
- Parsing expression grammars (PEGs): a more recent generalization of TDPL designed around the practical expressiveness needs of programming language and compiler writers.
- Link grammars: a form of analytic grammar designed for linguistics, which derives syntactic structure by examining the positional relationships between pairs of words.
See also
Template:Formal languages and grammarsfr:Grammaire formelle de:Formale Grammatik pl:Gramatyka formalna zh-cn:形式文法