1

I have a homework problem which I could use some help on. I need to convert the following EBNF statement to BNF

<S> -> <A>{b<A>}
<A> -> a[b]<A>

This is what I have come up with so far;

<S> -> <A> | <A><S> | b<A>
<A> -> a<A> | ab<A>

It doesn't feel right, mainly because it's a WAG. The example in my book (Concepts of Programming Languages, Sebesta) is not helping me at all. So if anyone has any insight, it would be greatly appreciated. Thanks!

Brian McKenna
  • 45,528
  • 6
  • 61
  • 60
dgilbert101
  • 46
  • 1
  • 2
  • 7

2 Answers2

1

Your conversion of the <S> is not completely correct:

<S> -> <A> | <A><S> | b<A>

Because it is possible to recursively choose <A> without having b which is not defined by the original EBNF rule (You can only recursive <A> with b preceding it).

Solutions could be:

(* S is a sequence of A optionally followed by a sequence of b and S together. *)

<S> -> <A>
       | <A> b <S>;

(* A is composed of 'a', followed by an optional 'b', followed by another A. *)

<A> -> a <A>
       | a b <A>;

This is why I like EBNF instead. It is much easier to understand and write! :-)

Ultimately you ask yourself what is required. Write it down. Now consider the optional components and use various combinations of them with the required components (in the right order of course). Then reduce what you can (be careful not to make a mistake).

ndrwnaguib
  • 5,623
  • 3
  • 28
  • 51
1

The first grammar seems buggy, or at least needlessly messy. But take a look here for a mechanical way to convert EBNF to BNF:

http://lampwww.epfl.ch/teaching/archive/compilation-ssc/2000/part4/parsing/node3.html

Abel
  • 56,041
  • 24
  • 146
  • 247
Andre Artus
  • 1,850
  • 15
  • 21