Тестирование софта - статьи


         

t предложения, оканчивающегося токеном t,


последовательности нетерминалов и токенов. Если в грамматике G существует вывод S
?X
?? t предложения, оканчивающегося токеном t, то будем считать, что множество Fu содержит пустую последовательность ? ?Fu. Через Ft будем обозначать объединение множеств Fu для токена t:
Иными словами, множество Ft – это множество токенов, каждый из которых допустим для токена t в качестве следующего. В дальнейшем нас главным образом будет интересовать дополнение к множеству Ft в множестве T ?{?}. Будем обозначать это дополнение через
Теорема 1. Последовательность токенов, содержащая подпоследовательность tt', где t'?
t, не является предложением языка, описываемого грамматикой G. Доказательство. Очевидно из построения множества
t. > Для последовательности токенов ? = t1...tn такой, что существует вывод S
???, можно определить множество токенов
такое, что если t'?
, то не существует вывода S
??t'?. Тогда любая последовательность ??t'?, где t'?
, не является предложением языка, описываемого грамматикой G. Итак, мы научились получать последовательности токенов, заведомо не являющиеся предложениями целевого языка. К вопросу о произвольности негативной последовательности токенов мы вернемся в следующем параграфе.

Содержание  Назад  Вперед