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

Question

Я пишу простой компилятор как школьная работа. Я ищу автоматизированный подход для генерации как положительных, так и отрицательных данных тестирования для проверки моего компилятора, учитывая формальную грамматику и другие спецификации. Язык, с которым я имею дело, имеет средний размер с примерно 38 нетерминалами. Для иллюстрации приведем снимок грамматики:

program: const_decl* declaration* ENDMARKER

# statement
stmt: flow_stmt | '{' stmt* '}' | NAME [stmt_trailer] ';' | ';'

stmt_trailer: arglist | ['[' expr ']'] '=' expr

flow_stmt: if_stmt | for_stmt | while_stmt | read_stmt ';' | write_stmt ';' | return_stmt ';'

return_stmt: 'return' ['(' expr ')']

if_stmt: 'if' '(' condition ')' stmt ['else' stmt]

condition: expr ('<'|'<='|'>'|'>='|'!='|'==') expr | expr

for_stmt: ('for' '(' NAME '=' expr ';' condition ';'
    NAME '=' NAME ('+'|'-') NUMBER ')' stmt)

Существуют ли какие-либо инструменты для генерации входного файла с помощью грамматики? Рукописные тесты слишком утомительны или слишком слабы, чтобы обнаружить проблемы. Пример этого языка здесь:

void main() {
  int N;
  int temp;
  int i, j;
  int array_size;

  reset_heap;
  scanf(N);

  for (i = 0; i < N; i = i + 1) {
    scanf(array_size);
    if (array_size > max_heap_size) {
      printf("array_size exceeds max_heap_size");
    } else {
      for (j = 0; j < array_size; j = j + 1) {
        scanf(temp);
        heap[j] = temp;
      }
      heap_sort(array_size);
      print_heap(array_size);
    }
  }
}

Автоматическое создание контролируемых данных тестирования может сэкономить дни. Учитывая простоту языка, должен быть какой-то способ эффективно сделать это. Любой указатель и понимание очень ценится.

Answer 1

Любой указатель и понимание приветствуются.

Это должно иметь подтему How to avoid combinatorial explosion when generating test data.

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

Одна из лучших серий статей, которые я нашел по этому поводу, написана Эриком Липпертом, Каждое двоичное дерево существует , представьте, что BNF преобразован в двоичные операторы, а затем преобразован в AST при чтении дерева. Однако он использует Catalan (каждая ветвь имеет два листа), и когда я писал свое приложение, я предпочел Motzikin (ветвь может иметь один или два листа).

Также он сделал его в C # с LINQ , а я сделал в Прологе, используя DCG .

Генерировать данные на основе BNF или DCG несложно, реальная хитрость заключается в том, чтобы ограничить область расширения и размер расширения и ввести неверные данные.

По области расширения предположим, что вы хотите протестировать вложенные операторы на три уровня глубиной, но при этом иметь корректный код, который компилируется. Очевидно, что вам нужен шаблонный код для его компиляции, тогда вы начинаете изменять глубоко вложенный if, добавляя или удаляя предложение else. Таким образом, необходимо установить ограничения, чтобы стандартный код был постоянным, а часть тестирования - переменной.

По размеру расширения скажем, что вы хотите проверить условные выражения. Вы можете легко рассчитать, что если у вас много операторов и вы хотите проверить их всех в комбинациях, вы скоро столкнетесь с комбинаторным взрывом. Хитрость заключается в том, чтобы убедиться, что вы тестируете достаточно глубоко и достаточно широко, но не в каждой комбинации. Снова помогает судебное использование ограничений.

Итак, смысл всего этого в том, что вы начинаете с инструмента, который принимает BNF и генерирует действительный код. Затем вы модифицируете BNF, чтобы добавить ограничения, и измените генератор, чтобы понять ограничения для генерации примеров кода.

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

После того, как это сработает, вы можете начать наложение на уровни автоматизации.

Если вы пойдете этим путем и решите, что вам придется изучать пролог, сначала посмотрите на Меркурий . Я не делал этого с Меркурием, но если я сделаю это снова, Меркурий будет первым в списке.

Хотя мой действительный код не является общедоступным, это и это ближе всего к нему, что является общедоступным.

По пути мне было весело с ним в Code Golf .

При создании терминалов, таких как зарезервированные слова или значения для типов, вы можете использовать предварительно определенный список с действительными и недействительными данными, например, для if, если язык чувствителен к регистру, я бы включил в список if, If, IF, iF и т. д. Для типов значений, таких как байты без знака, я бы включил -1, 0, 255 и 256.

Когда я тестировал базовые двоичные математические выражения с +, -, * и ^, я сгенерировал весь тест для трех основных чисел -2, -1, 0, 1 и 2. Я подумал, что это будет бесполезно, поскольку у меня уже были сотни тестовых случаев, но, поскольку для генерации всех тестовых примеров потребовалось всего несколько минут и несколько часов для его запуска, к моему удивлению, он обнаружил шаблон, который я не охватывал. Суть в том, что вопреки тому, что большинство людей говорят о необходимости иметь множество тестовых случаев, помните, что это всего лишь время на компьютере, изменив несколько ограничений, как и большое количество тестов.