parsing - この 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 つの状態のいずれかにいます。

試す：

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

いくつかのクリーンアップが必要になる可能性がありますが、機能するはずです。注意すべき重要なことは、 < ネコ > と 何に対しても一致しないということです。トークンが必要なプロダクションは < one_dog > だけです。