[dundee] Parser howto... possibly including bisons so watch out!

[Colin Brough]

> Hey, I was just wandering whether anyone had any experience making 
> parsers. I am currently trying to make a PS2 game (using the PS2 Linux 
> Devkit) and want to start creating config files for various things 
> (maybe XML, maybe custom layout, yet to be decided) and have tried 
> looking into writing my own parser function. I can't seem to find 
> anything anywhere in the form of a guide or tutorial to give me 
> directions. Everywhere I look says Bison.
> I have tried looking for Bison tutorials and come up with very little too.
> Does anyone have any experience with Bison or even have any knowledge on 
> the writing of parsers?

Bison is a (now superior) clone of yacc, and one of the first pieces
of GNU software Stallman ever released. But you will still find a
better set of tutorials googling for yacc than bison (yacc = Yet
Another Compiler Compiler).

You will also find mention of lex to work alongside yacc/bison, and
its probably worth understanding the connection between the two.

Best place to find good reading on this stuff is in an introduction to
compilers course text book - the standard text in my day was the
Dragon book by Aho, Sethi and Ullman:

	http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886

A quick look reveals a new edition (2007) by Aho, Lam, Sethi and
Ullman - at typical text book price of £50!! Yikes... This will
provide the theoretical underpinnings to grammars - see, for a
starter, http://en.wikipedia.org/wiki/LALR_parser.

The grammar is the set of rules that tell you what is a syntactically
valid config file and what is not. Given the grammar (the input file
to yacc/bison) and something to convert the raw text of the config
file into tokens (lex can do this, though for simple cases its as easy
to code it by hand), bison will produce C code that will read your
config files. You then embed stuff (C code) into the yacc/bison input
file that will "do stuff" when a particular construct is
recognised. So at the point in the grammar where something like an
assignment of a variable with a value ( "StartLevel = 3", or whatever)
is recognised you add code that sets the corresponding variable with
the value on the right hand side...

http://epaperpress.com/lexandyacc/ looks like a reasonable
introduction.

Its been nearly 20 years since I did this stuff in anger, so you'll
forgive me for having forgotten the details. The last grammar I wrote
was for my honours project in 1989/90, and I'm *still* very upset that
at some point along the way I lost the tarball with all the source and
documentation for that!

HTH

Cheers

Colin

----------------------------------------------------------------------
Colin Brough                             Colin.Brough at blueyonder.co.uk