|
In computer science and linguistics, a formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. The two main categories of formal grammar are that of generative grammars, which are sets of rules for how strings in a language can be generated, and that of analytic grammars, which are sets of rules for how a string can be analyzed to determine whether it is a member of the language. In short, an analytic grammar describes how to recognize when strings are members in the set, whereas a generative grammar describes how to write only those strings in the set. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
Linguistics is the scientific study of language, which can be theoretical or applied. ...
In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. ...
In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
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. If there are multiple different ways of generating a single string, then the grammar is said to be ambiguous. In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i. ...
For example, assume the alphabet consists of a and b, the start symbol is S and we have the following rules:
- 1.
- 2.
then we start with S, and can choose a rule to apply to it. If we choose rule 1, we replace S with aSb and obtain the string aSb. If we choose rule 1 again, we replace S with aSb and obtain the string aaSbb. This process is repeated until we only have symbols from the alphabet (i.e., a and b). 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 definition In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s,[1][2] a grammar G consists of the following components: Avram Noam Chomsky (Hebrew :××‘×¨× × ×•×¢× ×—×•×ž×¡×§×™ Yiddish: ××‘×¨× × ×•×¢× ×›×מסקי) , Ph. ...
This does not cite any references or sources. ...
-
- where * is the Kleene star operator and denotes 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 — that is, that it contains no symbols at all — an epsilon (ε) is typically written in its place to avoid ambiguity.
- A distinguished symbol that is the start symbol.
Usually such a formal grammar G is simply summarized as the quad-tuple (N,Σ,P,S). A nonterminal symbol is that symbol which has the capability of being further defined in terms of terminals and/or non-terminals. ...
A terminal symbol, in BNF jargon, is a symbol that represents a constant value. ...
In mathematics, two sets are said to be disjoint if they have no element in common. ...
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...
The language of a formal grammar G = (N,Σ,P,S), denoted as , is defined as all those strings over Σ that can be generated by starting with the start symbol S and then applying the production rules in P until no more nonterminal symbols are present.
Example For these examples, formal languages are specified using set-builder notation. In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by indicating the properties that its members must satisfy. ...
Consider the grammar G where , , S is the start symbol, and P consists of the following production rules:
- 1.
- 2.
- 3.
- 4.
Some examples of the derivation of strings in are: - (Note on notation: reads "L generates R by means of production i" and the generated part is each time indicated in bold.)
This grammar defines the language where an 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 hierarchy -
When 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 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.[3] 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. The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ...
Avram Noam Chomsky (Hebrew :××‘×¨× × ×•×¢× ×—×•×ž×¡×§×™ Yiddish: ××‘×¨× × ×•×¢× ×›×מסקי) , Ph. ...
Year 1956 (MCMLVI) was a leap year starting on Sunday (link will display full calendar) of the Gregorian calendar. ...
The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ...
In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ...
In computer science a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and...
The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...
A regular language is a formal language (i. ...
An artistic representation of a Turing Machine . ...
An example of parsing a mathematical expression. ...
Fig. ...
An LL parser is a top-down parser for a subset of the context-free grammars. ...
In computer science, an LR parser is a parser for context-free grammars that reads input from Left to right and produces a Rightmost derivation. ...
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. In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a nonterminal symbol and w is a string consisting of terminals and/or non-terminals. ...
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 (at least 1 a followed by the same number of b's) is context-free, as it can be defined by the grammar G2 with , , S the start symbol, and the following production rules: In the theory of formal languages, a pumping lemma states that any language of a given class can be pumped and still belong to that class. ...
- 1.
- 2.
A context-free language can be recognized in O(n3) 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 O(n3) time whether the string is a member of the language, where n is the length of the string.[4] Further, some important subsets of the context-free languages can be recognized in linear time using other algorithms. Big O notation is often used to describe how the size of the input data affects an algorithms running time. ...
The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. ...
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: It may be nothing, 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.) In computer science a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and...
Syntactic sugar is a term coined by Peter J. Landin for additions to the syntax of a computer language that do not affect its functionality but make it sweeter for humans to use. ...
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 G3 with , , S the start symbol, and the following production rules:
- 1.
- 2.
- 3.
- 4.
- 5.
- 6. (In this case 'S' can not be appear on right hand side in any production.)
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. Fig. ...
In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. ...
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. Some forms of grammars developed include: An example of parsing a mathematical expression. ...
- Tree-adjoining grammars increase the expressiveness of conventional generative grammars by allowing rewrite rules to operate on parse trees instead of just strings.[5]
- Affix grammars[6] and attribute grammars[7][8] allow rewrite rules to be augmented with semantic attributes and operations, useful both for increasing grammar expressiveness and for constructing practical language translation tools.
Tree-adjoining grammar (TAG) is a grammar formalism defined by Aravind Joshi which is often used in computational linguistics and natural language processing. ...
A parse tree or concrete syntax tree is a tree that represents the syntactic structure of a string according to some formal grammar. ...
This article is in need of attention from an expert on the subject. ...
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 example of parsing a mathematical expression. ...
Flowcharts are often used to represent algorithms. ...
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 [9] directly implements unrestricted analytic grammars. Substitution rules are used to transform an input to produce outputs and behaviour. The system can also produce 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 parsers.[10]
- Link grammars: a form of analytic grammar designed for linguistics, which derives syntactic structure by examining the positional relationships between pairs of words.[11][12]
- Parsing expression grammars (PEGs): a more recent generalization of TDPL designed around the practical expressiveness needs of programming language and compiler writers.[13]
Top-Down Parsing Language (TDPL) is a type of analytic formal grammar developed by Alexander Birman in the early 1970s in order to study formally the behavior of a common class of practical top-down parsers that support a limited form of backtracking. ...
The 1970s decade refers to the years from 1970 to 1979, also called The Seventies. ...
This article or section does not cite its references or sources. ...
Link grammar (LG) is a theory of syntax by Davy Temperley and Daniel Sleator which builds relations between pairs of words, rather than constructing constituents in a tree-like hierarchy. ...
Linguistics is the scientific study of language, which can be theoretical or applied. ...
It has been suggested that packrat parser be merged into this article or section. ...
A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...
A diagram of the operation of a typical multi-language, multi-target compiler. ...
References - ^ a b Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
- ^ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.
- ^ Grune, Dick & Jacobs, Ceriel H., Parsing Techniques—A Practical Guide, Ellis Horwood, England, 1990.
- ^ Earley, Jay, "An Efficient Context-Free Parsing Algorithm," Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
- ^ Joshi, Aravind K., et al., "Tree Adjunct Grammars," Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.
- ^ Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
- ^ Knuth, Donald E., "Semantics of Context-Free Languages," Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.
- ^ Knuth, Donald E., "Semantics of Context-Free Languages (correction)," Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.
- ^ http://languagemachine.sourceforge.net
- ^ Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
- ^ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
- ^ Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993. (Revised version of above report.)
- ^ Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.
See also In computer science, an abstract syntax tree (AST) is a finite, labeled, directed tree, where the internal nodes are labeled by operators, and the leaf nodes represent the operands of the node operators. ...
An adaptive grammar is a formal grammar that explicitly provides mechanisms within the formalism to allow its own production rules to be manipulated. ...
In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i. ...
The Backus–Naur form (also known as BNF, the Backus–Naur formalism, Backus normal form, or Panini–Backus Form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. ...
A parse tree is a grammatical structure represented as a tree data structure. ...
See L-system for information on Lindenmayer systems. ...
Lojban (IPA , official full name Lojban: a realization of Loglan) is a syntactically unambiguous, predicate logic-based constructed language which was created by the Logical Language Group in 1987 as a realization of Loglan, with the intent to make the language more complete, usable, and freely available. ...
External links - Yearly Formal Grammar conference
|
Feeds |
Contact