Where can I get material for learning EBNF?

Question

Extended Backus–Naur Form: EBNF

I'm very new to parsing concepts. Where can I get sufficiently easy to read and follow material for writing a grammar for the boost::spirit library, which uses a grammar similar to EBNF?

Currently I am looking into EBNF from Wikipedia.

Answer 1

The Wikipedia article is accurate. If you have access, definitely read Wirth's original article on EBNF.

The other thing to know is that EBNF was designed to make it easy to hand-write recursive-descent parsers for languages in which each syntactic construct has identifying keywords at the beginning. Curly braces translate to while loops; square brackets (optional stuff) translates to if, and alternatives translate to if-then-else or case statements. If you have the luxury of designing your language this way you can knock out a parser quickly and give good error messages.

The only place this gets a bit tedious is when you have a language in which there are infix operators with many different levels of precedence. For that you want Dave Hanson's paper Compact Recursive-Descent Parsing of Expressions. Maybe the Princeton tech report series has a free version, and you can always look at the code in Hanson's C front end.

Answer 2

BNF itself is simple, but you need to get used to the way compiler writers think. They are not necessarily easy read, but following are lecture notes from UC Berkeley and Stanford.

• Berkeley CS 164: Lecture Notes
• Stanford CS143: Lecture Notes

Answer 3

Here is an ebnf parser in php.

Also, learning a little about how regular expression engines are implemented might help. Try: re2.

Answer 4

Well, I think that Wikipedia is the simplest way for two reasons:

• It states the most relevant points on the article
• It has links for further reading at the bottom of the page

Also I would suggest reading of standart BNF just to get familiar with the idea behind it.

At least I always start with Wikipedia too, and it almost always helps.