Parsers, grammars and BNF

[maniac]

Hey everyone,

I want to write a BNF for a particular language.

Can anyone recommend a good resource/guide for generating a BNF for a
language?

I'm just wondering is there a formula to follow before I start
examining every possible statement!

Cheers

Tom

[Philip Herron]

Hey Tom,

2009/11/12 maniac <mani...@yahoo.com>:

I wouldn't worry about any particular 'formula', the way i figured out
how to do it was just writing YACC, and reading the dragon book helped
me a lot as well as there was an o'reilley book Lex and Yacc i have it
here somewhere it was probably the most useful out of any it shows you
how to think about the problem easily and well + its very short you
only need to care about the first ~100 pages the rest is one big SQL
implementation which just gets very specific.

Although i prefer having a hand-written parser since you can Taylor it
to be more specific to your implementation, Lex and Yacc are really
helpful when your still prototyping your language, gives you less to
worry about when building it.

--Phil

[glen herrmannsfeldt]

Philip Herron <herron...@googlemail.com> wrote:

> I wouldn't worry about any particular 'formula', the way i figured out
> how to do it was just writing YACC, and reading the dragon book helped
> me a lot as well as there was an o'reilley book Lex and Yacc i have it
> here somewhere it was probably the most useful out of any it shows you
> how to think about the problem easily and well + its very short you
> only need to care about the first ~100 pages the rest is one big SQL
> implementation which just gets very specific.

Many years ago (1977) I worked on a macro-processor called STEP.
Well, someone had written it, declared it finished, and then left.
I got to test it out, try some simple and not so simple problems,
and make some improvements.

As far as I know, the manual still exists but the program itself
does not. It was written in IBM Fortran IV, or maybe standard
Fortran 66. Unlike most macro-processors which recognize patterns
in text without any context, this one pretty much allowed one to
specify the exact syntax (through the SYNTAX macro) that would
be matched, and then generate the appropriate code which would then
be passed back up the parse tree.

One that I did with it was to write a parser for IBM Fortran IV,
or as close as I could get to it. (One complication is that record
boundaries are ignored on input.) It was very easy to write the
macros directly from the BNF in the IBM Fortran syntax checker
manual. (The Fortran reference manuals don't have the BNF.)

I don't know that it ever got wide distribution, but I do wonder
if anyone might still have a copy around somewhere. Otherwise,
unlike lex/yacc, but like most macro-processors, this one
was completely interpreted.

> Although i prefer having a hand-written parser since you can Taylor it
> to be more specific to your implementation, Lex and Yacc are really
> helpful when your still prototyping your language, gives you less to
> worry about when building it.

-- glen

[Chris F Clark]

It depends on what sort of advice you are looking for on writing BNF.
If you wariting plain BNF (not EBNF--i.e. no regexes), there are some
basic structures that are used and not many variations to worry about.

For example, if you want an optional A (sometime written A-opt or in
EBMF A?), you write a rule like:

A-opt: A | /* empty */;

The only real question s one faces are:

1) to use right or left recursion for lists (A* or A+)
A-list: A A-list | A ;
vs.
A-list: A-list A | A ;

2) how much to flatten (inline) rules ( A? B? )
A-opt-then-B-opt: A-opt B-opt ;
vs:
A-opt-then-B-opt: A B | A | B | /* empty */ ;

3) to write precedence rules explicitly or use "hacks"
This example is too complex to put here.

If you use EBNF there are some more choices, e.g. when to use
operatoes versus rule formulas.

We have a tutorial for Yacc++ that gives canned examples for a lot of
constructs and an appropriate EBNF choice for them, mostly different
styles of lists (eg. with and without terminators) However, if you are
doing plain BNF it may not be much help.

BTW, I believe there is a tool outther somewhere that if you write
A-opt (A?), A-list (A+), and A-opt-list (A*) will expand them as
above.

Hope this helps,
-Chris

******************************************************************************
Chris Clark email: christoph...@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------