Как можно было бы протестировать интерпретатор или компилятор?

Question

Я экспериментировал с созданием интерпретатора для Brainfuck, и хотя я довольно прост в настройке и настройке, часть меня хочет иметь возможность запускать тесты против него. Я не могу понять, сколько тестов нужно написать, чтобы проверить все возможные комбинации команд, чтобы убедиться в правильности реализации.

Очевидно, что с Brainfuck набор инструкций невелик, но я не могу не думать, что по мере добавления новых инструкций ваш тестовый код будет расти в геометрической прогрессии. Во всяком случае, больше, чем ваши типичные тесты.

Теперь я новичок в написании компиляторов и интерпретаторов, так что мои предположения вполне могут быть далеки от базовых.

В принципе, где вы вообще начинаете тестировать что-то подобное?

Answer 1

Тестирование компилятора немного отличается от тестирования некоторых других типов приложений, потому что компилятор может создавать разные версии кода на ассемблере, если они все делают правильно. Однако, если вы просто тестируете интерпретатор, он почти такой же, как и любое другое текстовое приложение. Вот Unix-ориентированное представление:

1. Вы захотите создать набор регрессионных тестов . Каждый тест должен иметь
   • Исходный код, который вы будете интерпретировать, скажем test001.bf
   • Стандартный ввод в программу, которую вы будете интерпретировать, скажем test001.0
   • То, что вы ожидаете от интерпретатора при стандартном выводе, скажем test001.1
   • То, что вы ожидаете от интерпретатора при стандартной ошибке, скажем test001.2 (вы беспокоитесь о стандартной ошибке, потому что хотите проверить сообщения об ошибках вашего интерпретатора)

2. Вам понадобится скрипт "run test", который выполняет что-то вроде следующего

   function fail {
     echo "Unexpected differences on $1:"
     diff $2 $3
     exit 1
   }
   
   for testname
   do
     tmp1=$(tempfile)
     tmp2=$(tempfile)
     brainfuck $testname.bf < $testname.0 > $tmp1 2> $tmp2
     [ cmp -s $testname.1 $tmp1 ] || fail "stdout" $testname.1 $tmp1
     [ cmp -s $testname.2 $tmp2 ] || fail "stderr" $testname.2 $tmp2
   done
   

3. Вам будет полезно иметь скрипт "create test", который выполняет что-то вроде

   brainfuck $testname.bf < $testname.0 > $testname.1 2> $testname.2
   

   Вы запускаете это, только когда полностью уверены, что переводчик работает для этого случая.

4. Вы держите свой набор тестов под контролем исходного кода.

5. Удобно украсить ваш тестовый скрипт, чтобы вы могли пропустить файлы, которые, как ожидается, будут пустыми.

6. Каждый раз, когда что-то меняется, вы перезапускаете все тесты. Вы, вероятно, также запускаете их все ночью по заданию cron.

7. Наконец, вы хотите добавить достаточно тестов, чтобы получить покрытие тестами исходного кода вашего компилятора. Качество инструментов покрытия широко варьируется, но GNU Gcov является адекватным инструментом покрытия.

Удачи с вашим переводчиком! Если вы хотите увидеть любовно созданную, но не очень хорошо документированную инфраструктуру тестирования, посмотрите каталог test2 для Quick C-- компилятора .

Answer 2

Я написал статью о тестировании компилятора, первоначальный вывод которого (слегка смягченный для публикации) был: Морально неправильно изобретать велосипед. Если вы уже не знаете всего о существующих решениях и у вас есть веская причина игнорировать их, вы должны начать с изучения уже существующих инструментов. Самое простое место для начала - Гну-С-Пытка , но имейте в виду, что оно основано на Дежа-Гну, ​​который, скажем так, имеет проблемы. (Мне потребовалось шесть попыток даже заставить сопровождающего включить в список рассылки сообщение о критической ошибке о примере Hello World.)

Я нескромно предлагаю вам взглянуть на следующее как на отправную точку для инструментов для исследования:

1. Программное обеспечение: практика и опыт Апрель 2007 . (Платное ПО, недоступное для широкой публики - бесплатный препринт по адресу http://pobox.com/~flash/Practical_Testing_of_C99.pdf.

2. http://en.wikipedia.org/wiki/Compiler_correctness#Testing (в значительной степени написано мной.)

3. Библиография тестирования компилятора (Пожалуйста, сообщите мне о любых обновлениях, которые я пропустил.)

Answer 3

Я не думаю, что есть что-то «особенное» в тестировании компилятора; в некотором смысле это почти проще, чем тестирование некоторых программ, поскольку у компилятора есть такая базовая сводка высокого уровня - вы передаете исходный код, он возвращает вам (возможно) скомпилированный код и (возможно) набор диагностических сообщений.

Как и любой сложный программный объект, будет много путей к коду, но, поскольку он очень ориентирован на данные (текст, текст и байты), он прост для авторских тестов.

Answer 4

Я думаю, что в случае бред-фука тестирование должно быть выполнено с помощью скриптов брейк-фука. Я бы проверил следующее:

1: все ячейки инициализированы в 0

2: Что происходит, когда вы уменьшаете указатель данных, когда он в данный момент указывает на первую ячейку? Это обернуть? Это указывает на неверную память?

3: Что происходит, когда вы увеличиваете указатель данных, когда он указывает на последнюю ячейку? Это обернуть? Указывает ли это на недопустимую память

4: правильно ли работает выход

5: правильно ли работает вход

6: правильно ли работает [] материал

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

Возможны и другие тесты, но, возможно, именно здесь я и начну. Я написал компилятор BF несколько лет назад, и у него было несколько дополнительных тестов. В частности, я тщательно тестировал материал [], имея много кода внутри блока, так как в ранней версии моего генератора кода были проблемы (на x86 с использованием jxx у меня были проблемы, когда блок генерировал более 128 байтов или около того код, в результате чего неверный x86 asm).

Answer 5

Секрет в том, чтобы:

• Разделите проблемы
• Соблюдайте закон Деметры
• Введите ваши зависимости

Что ж, программное обеспечение, которое сложно протестировать, является признаком того, что разработчик написал его, как будто это 1985 год. Извините, что, используя три принципа, которые я здесь представил, даже BASIC с линейным номером будет тестируемым на модуле (возможно вставьте зависимости в BASIC, потому что вы можете сделать «goto variable».

Answer 6

Вы можете протестировать некоторые уже написанные приложения.