Backus Naur Form (BNF)

Backus Naur Form (or Backus Normal Form or BNF) is a way of specifying data types and language syntax. It has three components:

Backus Naur Form
::= Definition
| or
{….}* 0 or more
{….}+ 1 or more
[….] optional
<….> terminal or non-terminal
  • A set of terminals which require no further definition.
  • A set of non-terminals or syntactic categories that are defined in terms of other terminals and non-terminals.
  • A set of productions or rules, that state how to construct a terminal from non-terminals and terminals.

The left hand side of the definition is the non-terminal, and the right hand side is the production or rule.

For example, the BNF for a list of symbols in Scheme is:

<list-of-symbols> ::= ()
                       | (<symbol> . <list-of-symbols>)

Here ( ) . <symbol> are terminals and <list-of-symbols> is the non-terminal. To explain the Scheme syntax a little () is an empty list, (x . y) is a “dotted pair”, and and a proper list is made by dotting pairs together terminating in an empty list, so (x . (y . (z . ()))) equals the proper list (x y z).

Backus Normal Form is an inductive definition. In an inductive definition you list one or more specific examples, and describe how to construct more complex examples from simpler ones. You can see that the list of symbols example is inductive, since list-of-symbols appears on both sides of the equation.

Another example is the BNF for a binary tree:

<tree> ::= <number>
          | (<symbol> <tree> <tree>)

Here are some binary trees which obey this definition:

tree
I recently saw on Eric Lippert’s blog a rather more thorough discussion of binary trees, including the interesting snippet that the number of binary trees with n nodes is given by the Catalan numbers (2n)!/(n+1)!n!

An final example of BNF is the definition for a nested list of symbols, s-list:

            <s-list> ::= ()
                        | (<symbol-expression> . <s-list>)

<symbol-expression> ::= <symbol> 
                         | <s-list> 

Examples of the types of nested list you can make are:

()
(())
(a)
(a b c d)
((a) (b) (c) (d))
((a b) c (d e (f (g))))

In the past I’ve always been quite annoyed by Back Naur Form, mainly because computer manual writers tend to tell you the BNF for some language syntax rather than giving examples of actual usage. Maybe now I understand BNF a little better I won’t be quite so annoyed. But I still think examples work best for explaining, definitions are only really useful when you understand what your talking about.

22 thoughts on “Backus Naur Form (BNF)

  1. Wow! After all I got a webpage from where I
    be able to truly obtain valuable data concerning my
    study and knowledge.

  2. May I just say what a relief to find somebody who really knows what they’re discussing online.
    You certainly realize how to bring a problem to light and make it important.

    More people need to read this and understand this side of the
    story. I can’t believe you are not more popular given that you definitely have the gift.

  3. It’s remarkable designed for me to have a website, which is useful inn support of my knowledge.
    thanks admin

  4. Hey just wanted to give you a brief heads up and
    let you know a few of the images aren’t loading correctly.
    I’m not sure why but I think its a linking issue. I’ve tried it in two different internet
    browsers and both show the same outcome.

  5. As there are numerous stores on tthe internet, you will be
    able to browse a nujber of stores at the comfort
    of your home before you take your pick.
    You may decide that thhe right thing ffor you is to
    have a piece oof jewellery made so that you can give a
    gift which is unique and unlike anything which someone else has.
    Once your budgett is set why not try throwing around some
    hints to see if there is a certain something that your lady might be interested in this year.

    Feel free to visit my page … Diamond jewellery amerika (luxuriantbeer4338.skyrock.com)

  6. Heya! I just wanted to ask if you ever have any problems with hackers?
    My last blog (wordpress) was hacked and I ended up losing months of hard work due
    to no data backup. Do you have any methods to protect against hackers?

    Feel free to surf to my site Check This Out

  7. Howdy, I am new to running a blog and websites in general and was wondering how you got the “www” included in your web
    address name? I see your domain name, “http://moleseyhill.com/blog/2010/05/05/backus-naur-form/” has the www and my web address looks like, “http://mydomain.com”.
    Do you know the correct way I can alter this?
    I’m using WordPress platform. Regards

  8. Do you mind if I quote a couple of your posts as long as
    I provide credit and sources back to your website? My blog is in
    the very same niche as yours and my users
    would truly benefit from a lot of the information you present here.

    Please let me know if this alright with you. Appreciate it!

  9. Hello there! Do you know if they make any plugins to assist with Search Engine Optimization?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
    If you know of any please share. Many thanks!

  10. Wow that was unusual. I just wrote an extremely long comment but after
    I clicked submit my comment didn’t appear. Grrrr… well I’m
    not writing all that over again. Regardless, just wanted
    to say great blog!

  11. The second line is drawn upward from some point on the right slanting line.
    The good news is that a VPN (virtualprivate network) makes it completely possible to get the Hulu contentand at a reasonable price.
    In today’s airtight indoor spaces, a home probably has a half-dozen or more filters to diagnose and inspect, and even some of them on a year-round basis.

  12. These reports contain the SEO strategies that are implemented during that time
    period. For creating a search engine for associate’s URL a pre-followed but exceptional result is required. 00 runs a game at the 2006 Classic and the manager is expected to once again use his basic pitching and defense approach.

  13. Pretty nice post. I just stumbled upon your weblog and wanted
    to mention that I have truly loved surfing around your weblog posts.
    In any case I will be subscribing in your feed and I hope you write again very soon!

  14. Generally I don’t read article on blogs, however I wish to say that this write-up very pressured me to try and do it! Your writing style has been amazed me. Thank you, very great article.

    Also visit my blog post – voltaire diamonds

Leave a Reply

Your email address will not be published. Required fields are marked *