

Formal grammarBecome a member of TranslationDirectory.com at just $8 per month (paid per year) 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 strings over some 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. 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).
Formal grammarsA grammar mainly consists of a set of rules for transforming strings. (If it only consisted of these rules, it would be a semiThue 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. For example, assume the alphabet consists of a and b, the start symbol is S and we have the following 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 choose rule 1 again, we replace S with aSb and obtain the string aaSbb. This process can be repeated at will until all occurrences of S are removed, and only symbols from the alphabet remain (i.e., a and b). For example, if we now choose rule 2, we replace S with ba and obtain the string aababb, 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: . Formal definitionIn the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s,^{[1]}^{[2]} a grammar G consists of the following components:
A grammar is formally defined as the ordered quadtuple (N,Σ,P,S). Such a formal grammar is often called a rewriting system or a phrase structure grammar in the literature.^{[3]}^{[4]} The operation of a grammar can be defined in terms of relations on strings:
Note that the grammar G = (N,Σ,P,S) is effectively the semiThue system , 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 S to strings without nonterminal symbols. ExampleFor these examples, formal languages are specified using setbuilder notation. Consider the grammar G where , , S is the start symbol, and P consists of the following production rules:
Some examples of the derivation of strings in are:  
This grammar defines the language where a^{n} denotes a string of n consecutive a's. Thus, the language is the set of strings that consist of 1 or more a's, followed by the same number of b's, followed by the same number of c's. The Chomsky hierarchyWhen Noam Chomsky first formalized generative grammars in 1956,^{[1]} 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 contextfree grammars (Type 2) and regular grammars (Type 3). The languages that can be described with such a grammar are called contextfree 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.^{[5]} For example, all regular languages can be recognized by a finite state machine, and for useful subsets of contextfree grammars there are wellknown algorithms to generate efficient LL parsers and LR parsers to recognize the corresponding languages those grammars generate. Contextfree grammarsA contextfree grammar is a grammar in which the lefthand side of each production rule consists of only a single nonterminal symbol. This restriction is nontrivial; not all languages can be generated by contextfree grammars. Those that can are called contextfree languages. The language defined above is not a contextfree language, and this can be strictly proven using the pumping lemma for contextfree languages, but for example the language (at least 1 a followed by the same number of b's) is contextfree, as it can be defined by the grammar G_{2} with , , S the start symbol, and the following production rules:
A contextfree language can be recognized in O(n^{3}) time (see Big O notation) by an algorithm such as Earley's algorithm. That is, for every contextfree language, a machine can be built that takes a string as input and determines in O(n^{3}) time whether the string is a member of the language, where n is the length of the string.^{[6]} Further, some important subsets of the contextfree languages can be recognized in linear time using other algorithms. Regular grammarsIn regular grammars, the left hand side is again only a single nonterminal symbol, but now the righthand 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 defined above is not regular, but the language (at least 1 a followed by at least 1 b, where the numbers may be different) is, as it can be defined by the grammar G_{3} with , , S the start symbol, and the following production rules: 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 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 grammarsMany 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. Some forms of grammars developed include:
Analytic grammarsThough 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 wellformed. 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:
See alsoReferences
External links
Published  October 2008 Information from Wikipedia
is available under the terms of the GNU Free Documentation
License
Email this article to your colleague! Need more translation jobs? Click here! Translation agencies are welcome to register here  Free! Freelance translators are welcome to register here  Free! Please see some ads as well as other content from TranslationDirectory.com: 


Legal Disclaimer Site Map 