您可以修改此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

您想从概念上讲有一个状态机。您处于两种状态之一：您看到过奇数的狗，或者您看到过偶数的狗。

尝试：

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

它可能需要一些清理，但应该可以。要注意的关键是<cats>和不会匹配任何内容。生产中必须具有令牌的唯一内容是<one_dog>。