[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


From: Hans Aberg
Subject: EBNF
Date: Wed, 8 Mar 2006 21:03:09 +0100

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]