EBNF

[Hans Aberg]

Waite, Goos, "Compiler Construction", Appendix A, p. 383, gives some  
EBNF to BNF translation rules. I rewrite in local notation, suitable  
for implementation in Bison:
  1.  a(b)c := axc, x: b.
  2.  a[b]c := ac | a(b)c.
  3.  au+ c := axc, x: u | xu.
  4.  au* c := a[u+]c.
  5.  a || t := a(ta)*.
where a, b, c are arbitrary RHS rules, x a unique non-terminal, u a  
single or parenthesized grammar symbol, and t a terminal.

Let's adapt this further for the Bison language grammar:

First rewrite these rules further, making the implicit (hidden) non- 
terminals explicit, letting e stand for the empty production:
  2'.  a[b]c := axc, x: e | b.
  3'.  au+ c := axc, x: u | xu.
  4'.  au* c := axc, x: e | xu.
  5'.  a || t c := axc, x: e | xta.

Then attach the extra actions, denoted by A, B:
  1. a(b)Ac := axc, x: bA.
  2. a[b]ABc := axc, x: eA | bB.
  3. au+ ABc := axc, x: uA | xuB.
  4. au* ABc := axc, x: eA | xuB.
  5. a || t AB := axc, x: eA | xtaB.

In the Bison language grammar, A, B will have the form {...}, and the  
e will be omitted. The $k values used in the actions A, B, can be  
inferred from these translation rules.

Waite, Goos [loc. cit.], sec. 5.1.4, p. 109 ff., gives an EBNF  
grammar for EBNF notation. If I translate it into a Bison like  
grammar (expanded into BNF) with the extra actions needed attached,  
using the abbreviations:
  E   expression
  PL  primary-list
  P   primary
  U   unit
  A   atom
  N   non-terminal
  T   terminal
  AC  action
  O   empty
I get something like:
  E:  PL | E "||" T AC AC.
  PL: P | PL "|" P.
  P:  O | U | U "+" AC AC | U "*" AC AC | "[" E "]" AC AC.
  U:  A | "(" E ")" AC.
  A:  N | T | AC.
  O:  .
Modulo that I do not see exactly how the empty production O should be  
integrated into this grammar, as well as the Bison optional mid-rule  
actions, and typos. But this should be enough to display the EBNF  
precedences.

  Hans Aberg