Search code examples
parsingsyntaxbnf

Can you modify this BNF grammar to always contain an odd number of dogs?

Can you modify this BNF grammar to always contain an odd number of dogs?

<pets> ::= <pets> <pet> | <pet>
<pet>  ::= dog | cat

Examples of 'pets':

    dog cat
    cat dog
    dog dog dog
    dog dog cat cat dog
    dog cat dog dog

Not examples of 'pets':

cat
dog cat dog
cat cat
Solution

  • You want to conceptually have a state machine. You are in one of two states: you have seen an odd number of dogs, or you have seen an even number of dogs.

    Try:

    // 0 or more cats
<cats> ::= cat <cats> | ""
// 1 dog possibly surrounded by cats
<one_dog> ::= <cats> dog <cats>

<even_dogs> ::= <one_dog> <one_dog> <even_dogs> | <cats>
<odd_dogs> ::= <even_dogs> <one_dog>

    It could use some cleaning up, but it should work. The key thing to note that < cats > and will match against nothing. The only thing that production that must have a token is < one_dog >.