Tuesday, January 13, 2009

Backus-Naur Form

Backus-Naur form, is a way to describe grammar for programming languages, communication protocols, instruction set and to represent part of natural language too. It express free context grammar.
A BNF consist of a set of derivation rules, made of symbols. Every Symbol is expressed as a rule like:
<symbol> ::= expression
an expression could be another symbol or a choice of symbols separated by a vertical bar. On the right side a symbol could be a terminal symbol or a non-terminal symbol. A terminal symbol is a symbol which never appears on the left side. When you find a non-terminal symbol on the right side you have to exchange it with its expression, at the end of the chain you are going to find a terminal symbol you can use :).
Starting from the first definition to the terminals symbol definition you could "write" everything could be expressed by that BNF.

See also:
BNF on wiki
PHP source [you can find the EBNF in the source]

In the next post im going to tell you how i write an xsd (XML Scheme) about XML syntax in order to transform it into graph by a XSLT.

At the begin, the acronym BNF meant Backus Normal Form, but later decided to use Naur instead of Normal in honour of Peter Naur a member of the Algol committee.
The most "popular" variant of BNF is absolutely EBNF (Extended Backus Naur Form which introduce optional repeatable (group) of symbols.

Some examples in order to understand how BNF works.

In italian language, the structure of an affermative sentence in simple present sounds (also) like:
Subject + verbs + subject
We define subject as: Article + noun
In english sounds the same, so a sentence in that way could be: "The child eats candies".
Well, let's try to derive a BNF that express that simple rule

<Affermative Sentence> ::= <Subject> <Verbs> <Subject>
<Verbs> ::= 'all the simple present verb these are all terminal symbols!'
<Subect> ::= <Article> <Nouns>
<Article> ::= The | A | An
<Nouns> ::= 'all the nouns, these are all terminal symbols!'

If you start from the root <Affermative Sentence> and substitute element's with it's definition, in the end you should get an affermative simple present sentence. Of course, we should extend the definition in order to explain when to use "The" instead of "A" or "An", but this BNF is just to let you understand how it works.
Here you can find EBNF definition on wiki, it's a very good entry, so check it out!

An other more complex example:
Now we are going to discover the power of BNF syntax. We want to write rules for a string which built a SQL insert query. A query for a link table:
Table 1 -> link table <- Table 2 (N:N)
This will be the form:
List of comma separated ids ended by ';'; every list are follow by an id and ':'. The ids before ':' comes from table 1, the comma separated id from table 2
Strings like:
And so on.

<Query Block> ::= <Table id> <Table Separator> [<Single Table List>] <Closer Table List> | <Query Block>
<Single Table List> ::= <Table id> <Separator> | <Single Table List>
<Closer Table List> ::= <Table id> <Closer>
<Table id> ::= <Digit> | <Table id>
<Digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0'
<Table Separator> ::= ':'
<Separator> ::= ','
<Closer> ::= ';'

sentence inside square brakets mean the sentence is optional!
In the next day im going to post another example.
Have a nice Day!