CODEWITHSUNDEEP
bisonbnf
RAM
RAM

Reputation: 65

How to convert advanced EBNF construction (using braces) to BNF (to be used with Bison)

I am learning Flex/Bison by my own, and I am doing some experiments with VHDL93. I have problems with some grammatical "productions" (as called in the standard) which uses curly braces.

I understand the meaning and how to convert this example given in the standard:

term ::= factor { multiplying_operator factor }
term ::= factor | term multiplying_operator factor

But what about:

choices ::= choice { | choice }

And I do not figure how to convert this

block_configuration ::=
     for block_specification
          { use_clause }
          { configuration_item }
     end for ;

I read a lot of questions in stackoverflow and searched for some EBNF tutorial but I didn't see anything about this kind of construction.

Finally, I understand that this kind of construction:

configuration_declarative_part ::=
     { configuration_declarative_item }

Is translated as:

configuration_declarative_part ::= |
     configuration_declarative_part configuration_declarative_item

Is it ok?

Thanks in advance for any help.

Upvotes: 0

Views: 191

Answers (2)

RAM
RAM

Reputation: 65

Let me see if I understand:

choices ::= choice { | choice }

n1 ::= %empty | choice
n2 ::= %empty | n2 n1

choices ::= choice n2
        ::= choice ( %empty | n2 n1 )
        ::= choice | choice n2 n1
        ::= choice | choices n1
        ::= choice | choices ( %empty | choice )
        ::= choice | choices | choices choice

But choices ::= choices is trivial, so:

choices ::= choice | choices choice

configuration_declarative_part ::= { configuration_declarative_item }

n1 ::= configuration_declarative_item
n2 ::= %empty | n2 n1

configuration_declarative_part ::= n2
                               ::= %empty | n2 n1
                               ::= %empty | configuration_declarative_part n1
                               ::= %empty | configuration_declarative_part configuration_declarative_item

block_configuration ::= for block_specification { use_clause } { configuration_item } end for ;

n1 ::= use_clause
n2 ::= %empty | n2 n1

n3 ::= configuration_item
n4 ::= %empty | n4 n3

block_configuration ::= for block_specification n2 n4 end for ;
                    ::= for block_specification (%empty | n2 n1) (%empty | n4 n3) end for ;
                    ::= for block_specification end for ; |
                        for block_specification n2 n1 end for ; |
                        for block_specification n4 n3 end for ; |
                        for block_specification n2 n1 n4 n3 end for ;

What now? Or is better to do:

block_configuration ::= for block_specification n2 n4 end for ;

With:

n2 ::= %empty | n2 use_clause
n4 ::= %empty | n4 configuration_item

It seems a good rule :-D Thanks

UPDATE: I arrived to the conclusion that is better (more clear) to add a new rule (based in http://lampwww.epfl.ch/teaching/archive/compilation-ssc/2000/part4/parsing/node3.html) than replace and have more complex rules.

Upvotes: 0

Chris Dodd
Chris Dodd

Reputation: 126140

The general case is that each {...} will create two new rules (call them n1 and n2) and be replaced by the second one:

n1:  ...whatever was in the braces...
n2: /* empty */ | n2 n1 ;

so for choices ::= choice { | choice }, the becomes:

n1 ::= /*empty*/ | choice
n2 ::= /*empty*/ | n2 n1
choices ::= choice n2

you then refactor it to remove ambiguity and simplify it if you wish. The above reduces to the equivalent:

choices ::= choice | choices choice

Upvotes: 2

Related Questions