# 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:

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. Appreciation to my father who stated to me regarding this website, this weblog
is iin fact remarkable.

2. Un saludo y muchas gracias!

3. Hello, the whole thing is going sound here and ofcourse every one is sharing data, that’s really excellent, keep uup writing.

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

5. Asking questions are actually pleasant thing if you are
not understanding anything fully, except this paragraph offers good understanding even.

6. Hi there everyone, it’s my first pay a visit at this site, and article is in fact fruitful for
me, keep up posting such articles.

7. 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.

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

9. Hey just wanted to give you a brief heads up and
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.

10. As there are numerous stores on tthe internet, you will be
able to browse a nujber of stores at the comfort
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)

11. 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

12. 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

13. 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!

14. Hello my friend! I want to say that this post is amazing, nice written and come with almost all important infos.
I would like to peer extra posts like this .

15. 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!

16. 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!

17. 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.

18. 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.

19. 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!

20. I’m not that much of a online reader to be honest but your sites really nice, keep it up!