Re: Extended BNF?

[Akim Demaille]

Le 26 juin 09 à 00:20, Paul Hilfinger a écrit :

> Has anyone considered adding extended BNF to Bison?  I refer to things
> like
>
> A.      p : a? ;
> B.      p : a ( b | c ) d ;
> C.      p : a ( ',' a )*
> D.      p : a+
>
> and so forth.

Hi Paul,

Yes, this has been considered several times, but each time tricky  
questions, and other patches that need to be completed, made this  
dream continuously postponed.

>  There are numerous questions to answer, mostly involving
> semantic actions and including:

Yes, exactly.  The grammar side of the question is quite  
straightforward, but the actions are very unclear.

> 1. How do we specify the semantic types of such constructs?
> 2. How do we refer to, e.g., the values of b and c from example B in  
> actions?
>   Presumably this would only be legal inside the parentheses.

Named references have been introduced in Bison, they should help  
here.  You would use $b and $c, or whatever name you attached to the  
symbols:

        p[res]: a[x] (b[y] | c[y]) d[z];

> 3. Assuming we translate * and + into equivalent non-extended
>   productions, how do we specify left vs. right-recursive lists?

Yep :)

> 4. How do we specify list constructors for * and +?
> 5. How do we supply a value for the empty case in A?
> 6. How do we supply a value for the ( ... ) construct in B?

I have no clear answer for these questions, I just have the same  
questions :).  But I have some pointers that might provide valuable  
ideas.

The SDF/SGLR folks (http://strategoxt.org/Sdf/WebHome) have an  
approach that I like when desugaring EBNF into BNF.  Constructs like "a 
+" or "a?" behave like nonterminal identifiers, and you may well  
define "a?" as you wish.  But if "a?" is left undefined in the  
grammar, *then* the tool adds a default

        a -> a?
          -> a?

(they write somewhat backwards, apparently because of signatures in  
many-sorted algebras. http://homepages.cwi.nl/~daybuild/daily-books/syntax/2-sdf/sdf.html#section.symbols)

They also support a nice construct: {x y}* means zero-or-more x's  
separated by y's, and {x y}+ stands for one-or-more.


Menhir (http://cristal.inria.fr/~fpottier/menhir/) supports user- 
defined "macros" (parameterized rules) to specify additional grammar  
meta-constructs and how to desugar them.  I never really looked at it,  
but Menhir is certainly a clearer source of inspiration for Bison than  
SDF since the former is user-action based, while the later is directly  
building the parse-tree (which magically "resolves" all your  
questions :).

They also support "inlined" rules, which provides good opportunities  
for factoring.  For instance, in a grammar of mine, I have (like most  
people do):

exp:
  exp "+" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "-" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "*" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "**" exp            { $$ = ast_call(@$, $1, $2, $3); }
| exp "/" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "%" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "^" exp           { $$ = ast_call(@$, $1, $2, $3); }
| exp "<<" exp            { $$ = ast_call(@$, $1, $2, $3); }
| exp "bitand" exp        { $$ = ast_call(@$, $1, $2, $3); }
| exp "bitor" exp         { $$ = ast_call(@$, $1, $2, $3); }
| exp ">>" exp            { $$ = ast_call(@$, $1, $2, $3); }
;

They can define a simple "exp: exp op exp" rule, and declare inlined- 
rule to define op, and let associativity/prececence do its job.


HTH.