Можете ли вы изменить эту грамматику BNF, чтобы она всегда содержала нечетное количество собак? - PullRequest
Новая
       17

Можете ли вы изменить эту грамматику BNF, чтобы она всегда содержала нечетное количество собак?

3 голосов
/ 07 января 2011

Можете ли вы изменить эту грамматику 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

1 Ответ

5 голосов
/ 07 января 2011

Вы хотите, чтобы концептуально был конечный автомат.Вы находитесь в одном из двух состояний: вы видели нечетное количество собак, или вы видели четное количество собак.

Попробуйте: 

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

Можно использовать некоторую очистку, но это должно работать.Главное отметить, что <коты> и ничем не будут соответствовать.Единственное, что для производства должен иметь токен, это .

...