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

你想在概念上拥有一个状态机。您处于以下两种状态之一：您看到了奇数条狗，或者您看到了偶数条狗。

尝试：

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