このBNF文法は、常に奇数の犬を含むように変更できますか？

Question

このBNF文法は、常に奇数の犬を含むように変更できますか？ 「ペットのの

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

例：

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

ない 'ペット' の例：

cat 
dog cat dog 
cat cat 

Answer 1

あなたは概念的ステートマシンを持っていると思います。あなたは2つの状態のうちの1つに入っています：奇数の犬を見たか、あなたは犬を偶数回見ました。

試してみてください。

// 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> 

それはいくつかのクリーニングを使用することができ、それが動作するはずです。そのことを覚えておくべき重要なことは< cat>で、これは何にもマッチしません。トークンを持たなければならないプロダクションは< one_dog>です。