Formal grammar

A formal grammar is a set of symbols and the production rules for rewriting some of them into every possible string of a formal language over an alphabet. A grammar does not describe the meaning of the strings—only their form.

In applied mathematics, formal language theory is the discipline that studies formal grammars and languages. Its applications are found in theoretical computer science, theoretical linguistics, formal semantics, mathematical logic, and other areas.

A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also be used as the basis for a parser—a function in computing that determines whether a given string belongs to the language or is grammatically incorrect. To describe such parsers, formal language theory uses separate formalisms, known as automata theory. One result of automata theory is that it is not possible to design a recognizer for certain formal languages.

Many languages have the meanings of their strings structured according to their syntax—a practice known as compositional semantics. In these cases, the first step to describing the meaning of a string 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).

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.