CODEWITHSUNDEEP
compiler-constructionprogramming-languagesbnfebnf
nujabes
nujabes

Reputation: 891

I'm struggling to the translation from EBNF to BNF

I'm learning about compilers and concepts of programming languages. How can I translate it?

Problem : 

   <S> → (+ | -)[<C>]{<A>}

At first, I translated like this: 

<S> -> epsilon
     | +<S>
     | -<S>
     | <C><S>
     | <A><S>

However, it has a problem that it can reproduce C!

Upvotes: 1

Views: 261

Answers (2)

comingstorm
comingstorm

Reputation: 26087

Your EBNF original is not recursive in <S>, but your trial BNF is. If you want the BNF to generate the same language, you shouldn't do that. Also, your EBNF can't generate epsilon, so you shouldn't add that to your <S>-production, either.

As the other answer says, you need to introduce additional non-terminals:

<S> -> <plusminus> <optionalC> <repeatedA>
<plusminus> -> + | -
<optionalC> -> <C> | epsilon
<repeatedA> -> <A> <repeatedA> | epsilon

This is a straightforward translation of the EBNF elements in your original grammar. Even if you have additional requirements (such as epsilon-elimination), you should start with this kind of step.

Note that the <S> rule is not recursive. Also, although epsilon is used for some additional nonterminals, it is not part of the <S> or <plusminus> rules, so that, as in the EBNF original, <S> cannot produce it.

Upvotes: 0

sepp2k
sepp2k

Reputation: 370082

Your BNF version can not only produce multiple <C>s, but also multiple +s and -s (or zero, which would also be different from the original grammar).

To fix these issues, you'll need to introduce additional non-terminals. Specifically you could have one that matches just {<A>} and one that matches [<C>]. Your definition of <S> could then be:

<S> -> + <OptionalC> <RepeatedA>
     | - <OptionalC> <RepeatedA>

Upvotes: 2

Related Questions