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


Позитивные и негативные тесты для синтаксического анализатора - часть 2


последовательности нетерминалов и токенов. Если в грамматике 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.

Итак, мы научились получать последовательности токенов, заведомо не являющиеся предложениями целевого языка. К вопросу о произвольности негативной последовательности токенов мы вернемся в следующем параграфе.


Начало  Назад  Вперед