Re: Extended BNF?

[Hans Aberg]

On 28 Jun 2009, at 14:26, Akim Demaille wrote:

> > 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.

> > 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.

The problem is where to to put them in order to avoid cluttering in  
the source code.

> > 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.

The form a(b)c translates into two rules axc, x: b. So in B, (...)  
gets a $2 values passed on from the $$ values of b and c. The actions  
might be written as
   p: a ( b {...} | c {...} ) d ;
But this will probably be hard to read when these actions are large.

> 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];

So this idea needs to be augmented with a way to place the actions  
somewhere else.

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

I thought one should only implement the left recursive ones that avoid  
stack buildups. Only if there is a strong need for the other one, that  
would be implemented. Otherwise, it would be easy to implement special  
symbols for that.

> > 4. How do we specify list constructors for * and +?

I suggested to put them directly after the + and + to avoid conflict  
with the implicit actions.

> > 5. How do we supply a value for the empty case in A?

  p : a? {...} {...} {...} ;
Where the two first actions belong to "a?", ahich produces a $1 value  
used to define the $$ of p.

> > 6. How do we supply a value for the ( ... ) construct in B?

See above.

> 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)

That may invite programming errors, if one can treat it as anything.

> 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.

The Waite-Goose translation rules I indicated includes a || t := a(ta)*.

  Hans