A formal grammar is a set of rules for forming strings in a formal language. A formal language has an alphabet of characters e.g. {a, b}. A grammar does not describe the meaning of the strings, only their form; meaning is a matter of semantics.
A context-free grammar is one where the left hand side of each production rule consists of a single non-terminal symbol. Not all languages can be generated by context-free grammars.
A regular language is context-free, that is the symbols have rules but no meaning or context. A regular grammar is more restricted than a context free garammar: the left hand side is a single nonterminal symbol while the right-hand side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else. A regular language can be recognised by a finite state machine and can also be defined by a regular expression.
Example:
S -> aSb
S -> ba
These are termed the production rules of the grammar as they define the rules for producing strings within it.
S is defined recursively in that S is embedded in the right side of the first rule. If we take aSb then we can replace the second S with aSb again to give aaSbb. If we replace this new S with the second rule we have aababb. This has no context or meaning.
This language is not regular; this is:
S -> aA
A -> aA
A -> bB
B -> bB
B -> є
Formal languages are used for the precise definition of data formats and the syntax of programming languages.
BNF is a way of expressing the syntax of context-free languages. John Backus introduced the technique in 1959 for ALGOL. Peter Naur simplified it.
A specification in BNF is a set of derivation rules written as:
<symbol> ::= expression
where <symbol> is non-terminal and expression consists of one or more sequences of symbols. Symbols on the left are always non-terminal but non-terminals also appear on the right, with further definitions below. Terminal symbols never appear on the left, only on the right.
<postal address> ::= <name part> <address part> <postcode>
Continue: