Re: Parsers, grammars and BNF

Chris F Clark <cfc@shell01.TheWorld.com>
Sun, 15 Nov 2009 23:39:25 -0500

          From comp.compilers

Related articles
Parsers, grammars and BNF maniac_ie@yahoo.com (maniac) (2009-11-12)
Re: Parsers, grammars and BNF herron.philip@googlemail.com (Philip Herron) (2009-11-13)
Re: Parsers, grammars and BNF gah@ugcs.caltech.edu (glen herrmannsfeldt) (2009-11-16)
Re: Parsers, grammars and BNF cfc@shell01.TheWorld.com (Chris F Clark) (2009-11-15)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Sun, 15 Nov 2009 23:39:25 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 09-11-040
Keywords: parse, design
Posted-Date: 17 Nov 2009 00:59:13 EST

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: christopher.f.clark@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
------------------------------------------------------------------------------



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.