Re: Q: list template?

[Hans Aberg]

At 12:37 +0100 2002/11/12, Akim Demaille wrote:
>Hans> Some WWW page at Berkeley, but I do not recall where. I thnik it
>Hans> said some students had made extensions to EBNF (Extended BNF),
>Hans> not only the BNF that Bison uses.
>
>Can't find anything like this.

It was a long time ago (year+) I looked at it, but I think that I might
have gone to their main website (which should be <http://www.berkeley.edu>
or something) and made a search for "Bison" or "Yacc".

>  I'd be interested to understand how
>they can solve these issues.

The implementation is not difficult as such: Just follow the EBNF to BNF
rewrite rules as indicated say in Waite & Goos, "Compiler Construction",
Appendix A, p. 383.

It lists the following constructions (translations using Bison notation):
  (a) := x, where x: a           -- Parenthesis
  a? := | a                      -- Optional.
  [a] := | a                     -- Optional, alternative notation.
  a+ := x, where x: a | x a      -- One or more.
  a* := x, where x:   | x a      -- Zero or more.
  a || t := a(ta)*               -- An a followed by zero or more ta.

If one wants to implement it in say Bison, one will have to figure out to
insert some extra actions. Bison already has the technique as such in it,
namely when implementing rule midactions, which is done by introducing an
anonymous empty variable with an action.

Yesterday, I had a brief look at how it might work:

For example, a? requires that $$ can be initialized when there is no "a".
So either one can require (in the .y grammar, the RHS of the rules)
  ... a? {a_empty} ...
or one can assume (like under C++), that $$ can always be initialized when
empty, in which case the {a_empty} part can be dropped.

For a+ and a*, one needs the initialization value of the first occurring
"a" plus how to move one step, i.e., "x a". So I figure one might require
  ... a+ {a_first} {a_next} ...
  ... a* {a_first} {a_next} ...
where a_first should define the first $$, in the case of a+, one may refer
to the value of "a" as $1, and a_next should define $$ in terms of $1, the
sequences of a's before, and $2, that latest "a". For example, one might
define a non-zero sequence delimited under C++
  as: '{' a+ { $$ = new std::list(1, $1); } { $$ = $1.push_back($2); }
      '}' { $$ = $1; }

  Hans Aberg