- A grammar is a defined structure of a language (a grammar is a language of languages) which shapes a language
- A grammar defines and shapes a language describing the syntax
- A programming language is defined and shaped by a context free grammar
The Chomsky hierarchy introduces us to this concept with more detail:
- Type-2 grammars are context free. (Non-deterministic pushdown automaton)
- Type 3 grammars are regular. (Finite state automaton).
We have an alphabet of a language. We have terminal and non-terminal characters. We have constraints (production rules).
A context-free grammar G is defined by the 4-tuple:[5]
G = ( V , Σ , R , S ) {\displaystyle G=(V,\Sigma ,R,S)} G=(V,\Sigma ,R,S) where
V is a finite set; each element v ∈ V {\displaystyle v\in V} v\in V is called a nonterminal character or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by G.
Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
R is a finite relation from V to ( V ∪ Σ ) ∗ {\displaystyle (V\cup \Sigma )^{}} (V\cup \Sigma )^{}, where the asterisk represents the Kleene star operation. The members of R are called the (rewrite) rules or productions of the grammar. (also commonly symbolized by a P)
S is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of V.
LISP EXAMPLE
expression = atom | list
atom = number | symbol
number = [+-]?['0'-'9']+
symbol = ['A'-'Z''a'-'z'].*
list = '(', expression*, ')'
The Tau meta language can use any grammar. This means it can use any syntax it wants, such as C, C++, Python, Java, or the Controlled Natural Language (controlled English). A syntax for a programming language is merely a set of rules defining the combination of symbols to be considered in a correctly structured document. Words, phrases, alphabets, all can be customized by anyone using Tau. Context free grammars may be enough for "almost all" natural language parsing.