Search code examples
bisonebnf

Problems to convert a particular EBNF rule to BNF

I am working with Flex/Bison and VHDL 93. I have a problem with the following rule:

choices ::= choice { | choice }

If I convert it to BNF:

N1 ::= %empty | choice
N2 ::= %empty | N2 N1
choices ::= choice N2
choices ::= choice | choice N2 N1
choices ::= choice | choices N1
choices ::= choice | choices | choices choice

But choices : choices is unuseful so finally

choices ::= choice | choices choice

So, what is the problem? Well, imagine that the rule to convert is:

choices ::= choice { choice }

And I apply the rules to convert to BNF:

N1 ::= choice
N2 ::= %empty | N2 N1
choices ::= choice N2
choices ::= choice | choice N2 N1
choices ::= choice | choices N1
choices ::= choice | choices choice

Which is the same previous result!!! What is happens? Where is the problem? I had problems with this rule more than a year ago, I am working again in this project and my problems with choices is still here :P

Here what the VHDL 93 standard said about choices:

In the second case, "choices" can be replaced by a list of "choice," separated by vertical bars.

I don't know from where the ',' comes from.

Thanks.

Solution

  • The VHDL description is quite clear: you need a list of choice separated by vertical bars. The EBNF is possibly confusing because the vertical bar might be misinterpreted as an EBNF operator. But from the description, it's evident that it is actually a token.

    So, in bison/yacc syntax:

    choices: choice
       | choices '|' choice