Критерии полноты тестирования
Мы рассматриваем известные алгоритмы синтаксического анализа (LL-анализ и LR-анализ, построенные на основе стека - см. []) в качестве алгоритмов, моделирующих поведение парсера.
Критерий полноты набора позитивных тестов для тестирования LL-анализатора:
(PLL) Покрытие всех пар вида
(нетерминал A, допустимый следующий токен t),
где пара (A, t) считается покрытой тогда и только тогда, когда в тестовом наборе существует предложение языка, обрабатывая которое LL-анализатор придет в ситуацию, когда на вершине стека будет находиться символ A, а текущим входным символом будет токен t.
Критерий полноты набора позитивных тестов для тестирования LR-анализатора:
(PLR) Покрытие всех пар вида
(символ s состояния конечного автомата,
помеченный символом X переход из состояния s),
где пара (s, X) считается покрытой тогда и только тогда, когда в тестовом наборе существует предложение языка, обрабатывая которое LR-анализатор придет в ситуацию, когда на вершине стека будет находиться символ s, а началом текущего входного потока будет последовательность токенов, отвечающая символу X.
Критерий полноты набора негативных тестов для тестирования LL-анализатора:
(NLLR) Покрытие всех пар
(нетерминал A; «некорректный» токен t'),
где пара (A, t') считается покрытой тогда и только тогда, когда среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая что LL-анализатор, обрабатывая эту последовательность, придет в ситуацию, когда после обработки как минимум R «правильных» токенов, на вершине стека будет находиться символ A, а текущим входным символом будет «некорректный» токен t'.
Критерий полноты набора негативных тестов для тестирования LR-анализатора:
(NLRR) Покрытие всех пар
(символ s состояния конечного автомата; «некорректный» токен t'),
где пара (s, t') считается покрытой тогда и только тогда, когда среди тестов имеется последовательность токенов, не принадлежащая целевому языку, такая, что LR-анализатор, обрабатывая эту последовательность, придет в ситуацию, когда после обработки как минимум R «правильных» токенов, на вершине стека будет находиться символ s, а текущим входным символом будет «некорректный» токен t'.
Существует семейство алгоритмов генерации тестов, удовлетворяющих этим критериям. Их подробное описание можно найти в работе [].
Следует особо отметить следующее важное свойство предложенных в этой работе алгоритмов генерации негативных тестов: алгоритмы гарантированно строят тесты, не принадлежащие целевому формальному языку. Это свойство позволяет отказаться при построении оракула от использования каких бы то ни было эталонных синтаксических анализаторов.
Разработан инструмент SynTesK [], в котором реализованы алгоритмы, удовлетворяющие критериям PLL и NLL1, а также критерию NLR1 для некоторого специального вида грамматик [].
Инструмент SynTesK успешно применялся для тестирования компиляторов реальных языков программирования, в т.ч. C и Java []. Практические результаты этого применения показали эффективность реализованных в SynTesK алгоритмов.
