bug-bison
[Top][All Lists]
Advanced

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

## EBNF

 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]
• EBNF, Hans Aberg <=