Formal grammar

A formal grammar describes which strings from an <a href="/facts/Alphabet_/6KW9qYRW">alphabet</a> of a <a href="/facts/Formal_language/crDTyP8q">formal language</a> are valid according to the language's <a href="/facts/Syntax/6PxSV98p">syntax</a>. A grammar does not describe the <a href="/facts/Semantics/1L4WwLAP">meaning of the strings</a> or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of <a href="/facts/Production_(computer_science)/J7E2FXKs">production rules</a> for such strings in a formal language.
Formal language theory, the discipline that studies formal grammars and languages, is a branch of <a href="/facts/Applied_mathematics/qyqklXXm">applied mathematics</a>. Its applications are found in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, <a href="/facts/Theoretical_linguistics/15wbqaY1">theoretical linguistics</a>, <a href="/facts/Formal_semantics_(logic)/VdAKHszK">formal semantics</a>, <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, and other areas.
A formal grammar is a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> 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 sometimes be used as the basis for a "<a href="/facts/Recognizer/GMusWd0a">recognizer</a>"—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 <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>. One of the interesting results of automata theory is that it is not possible to design a recognizer for certain formal languages. <a href="/facts/Parsing/nRKB01S3">Parsing</a> is the process of recognizing an utterance (a string in natural languages) by breaking it down to a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> 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 <a href="/facts/Compositional_semantics/yP2hR4Le">compositional semantics</a>. 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 <a href="/facts/Parse_tree/FeBEtXcz">parse tree</a> in computer science, and as its <a href="/facts/Deep_structure_and_surface_structure/l00JHPXK">deep structure</a> in <a href="/facts/Generative_grammar/Pm1AMX5U">generative grammar</a>).

Formal grammar open-in-new

Formal grammar