Meta-Syntax

Over the few years that I've been learning to write software, I find myself often struggling to think in terms of metadata. More accurately, meta-metadata. So it's no surprise that I have found myself struggling to understand Backus-Narf Form (BNF) syntax. I finally decided to sit down and take a closer look at it and I found it surprisingly easier to understand than I initially thought. Read on to see my findings.


What, you might think, is BNF? Backus-Narf Form is a syntax to describe a syntax. It was created in the mid 50's as a way to describe a programming language. In those days, they were still working with things like assembly. So you can see the advantage of being able to define a language, before having to write it.

Where do you encounter BNF? I see it on the web all the time, particularly in the form of documentation on T-SQL statements. Let's say one day I need to select the first three results from a table. I forgot how and turn to Google. I may be initially relieve to find a page at Microsoft. However, after seeing the example SQL, I would often find my self disappointed because it would look something like this:

<SELECT statement> ::=  
    [WITH <common_table_expression> [,...n]]
    <query_expression> 
    [ ORDER BY { order_by_expression | column_position [ ASC | DESC ] } 
  [ ,...n ] ] 
    [ <FOR Clause>] 
    [ OPTION ( <query_hint> [ ,...n ] ) ] 
<query_expression> ::= 
    { <query_specification> | ( <query_expression> ) } 
    [  { UNION [ ALL ] | EXCEPT | INTERSECT }
        <query_specification> | ( <query_expression> ) [...n ] ] 
<query_specification> ::= 
SELECT [ ALL | DISTINCT ] 
    [TOP ( expression ) [PERCENT] [ WITH TIES ] ] 
    < select_list > 
    [ INTO new_table ] 
    [ FROM { <table_source> } [ ,...n ] ] 
    [ WHERE <search_condition> ] 
    [ <GROUP BY> ] 
    [ HAVING < search_condition > ] 

Ok, this looks pretty intimidating. All I want is some data from my table. I don't remember it being nearly this complicated. Couldn't they have just given me example code?

Now that all the whining is out of the way. Let's break it down into simple easy to under stand snippets of the syntax.

1. Order, the first thing to make sure you note, is the order of things matter. The SELECT above really does come before the WITH.
2. Choice |, that bar indicates that there is a choice between two items e.g. 1 | 2 you can have one or two, not both.
3. Option [ ], anything in closed between those two brackets is optional.
4. Category < >, think of this like a label for something you defined e.g. <select statement> ::= everything here can be called a select statement.
5. Repetition { }, zero or more times. ::= { digit } This as you can see goes to infinity.Ok, getting a little fancy at the end, using the syntax to help describe it's self. Now let's take chunks of the above SQL statement and break it down to see what kind of information we can wring out of it.

<SELECT statement> ::=  
    [...] 

Ok this part looks less intimidating, its just them saying, "Hey, we're formally declaring a SELECT SQL statement here."

<SELECT statement> ::=  
    [WITH <common_table_expression> [,...n]]
    <query_expression> 
     

Hmm, I've never used WITH, but because of our new found understanding. We now know that there is a WITH statement that can be used and is considered in the class of SELECT statements. The [,...n] is tricky, turns out it's Microsoft's way of saying, the following code can be repeated.

<SELECT statement> ::=  
<query_specification> ::= 
SELECT [ ALL | DISTINCT ] 
    [TOP ( expression ) [PERCENT] [ WITH TIES ] ] 
    < select_list > 
    [ INTO new_table ] 
    [ FROM { <table_source> } [ ,...n ] ] 
    [ WHERE <search_condition> ] 
    [ <GROUP BY> ] 
    [ HAVING < search_condition > ] 

I decided to just go for the meat of it, SELECT. We see we can use either ALL or DISTINCT, it looks like at the same time with TOP.

TOP suddenly looks more interesting as I see that I can now specify PERCENT if I want to grab a portion of the table instead of an exact number like three. Now I see WITH TIES, this means that if I select the top 10% out of 100 and two rows match in the order by. Then I could end up with eleven or more.

I could keep going on, but this post took longer than I expected to write. I think you're getting the hang of it. It'll take some practice to get used to before you can comfortably read it. At least now when you get, or see, this you won't feel helpless. :)

References:

• Microsoft. (2012). SELECT (Transact-SQL). Available from: http://msdn.microsoft.com/en-us/library/ms189499. [Accessed: 4/5/2012].
• Microsoft. (2012). TOP (Transact-SQL). Available from: http://msdn.microsoft.com/en-us/library/ms189463.aspx. [Accessed: 4/5/2012].
• Microsoft. (2012). Transact-SQL Syntax Conventions (Transact-SQL). Available from: http://msdn.microsoft.com/en-us/library/ms177563.aspx. [Accessed: 4/5/2012].
• Th. Estier. (2012). About BNF. Available from: http://cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html. [Accessed: 4/5/2012].