Formal grammar

In computer science a formal grammar is an abstract structure that describes a formal language precisely, i.e., a set of rules that mathematically delineates a (usually infinite) set of finite-length strings over a (usually finite) alphabet. Formal grammars are so named by analogy to grammar in human languages.

Related Topics:
Computer science - Abstract structure - Formal language - Infinite - Set - Strings - Finite - Alphabet - Grammar

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Formal grammars fall into two main categories: generative and analytic.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• A generative grammar, the most well-known kind, is a set of rules by which all possible strings in the language to be described can be generated by successively rewriting strings starting from a designated start symbol. A generative grammar in effect formalizes an algorithm that generates strings in the language.
• An analytic grammar, in contrast, is a set of rules that assume an arbitrary string to be given as input, and which successively reduce or analyze that input string yielding a final boolean, "yes/no" result indicating whether or not the input string is a member of the language described by the grammar. An analytic grammar in effect formally describes a parser for a language.

In short, an analytic grammar describes how to read a language, whereas a generative grammar describes how to write it.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Formal grammar: Generative grammars ►