EBNF to BNF Conversion [duplicate]

This question already has answers here: Converting EBNF to BNF (2 answers) Closed 8 years ago.

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!

---

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

---

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).