A formal grammar (sometimes simply called a grammar) is a set of rules for forming strings in a formal language. These rules that make up the grammar describe how to form strings from the language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings—only their location and the ways that they can be manipulated.
Formal grammars and languages form the formal language theory, which is closely related to automata theory. Its applications are found in theoretical computer science, theoretical linguistics, formal semantics, mathematical logic, and other areas. Noam Chomsky was the first to theorize an organized hierarchy of different grammars.
In its simplest form, a formal grammar is just a set of rules for writing and rewriting strings along with a "start symbol" that initiates the process. 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 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).
Contents |
|
Universite Marne-la-Vallee (Communique de presse)
The introduction of deep pushdown automata is inspired by the standard conversion of a context-free grammar to an equivalent pushdown automaton, M, ...
and more »
