Содержание

СОДЕРЖАНИЕ 2

1. ВВЕДЕНИЕ 3

1.1. ГЛОССАРИЙ 3

1.2. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 3

1.3. СУЩЕСТВУЮЩИЕ РЕШЕНИЯ И ИХ НЕДОСТАТКИ 3

1.4. НЕФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 3

2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 4

3. СПЕЦИФИКАЦИЯ ДАННЫХ 4

3.1. СПОСОБ ЗАДАНИЯ ОБРАЗЦА 4

3.1.1. Константы 4

3.1.2. Переменные 4

3.1.3. Генерируемые параметры 4

3.2. ОБЩАЯ СТРУКТУРА ЯЗЫКА ФОРМАЛЬНОГО ОПИСАНИЯ 4

3.3. ОПИСАНИЕ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ 4

3.4. ОПИСАНИЕ ОШИБОЧНЫХ ПРЕОБРАЗОВАНИЙ 4

3.5. ОПИСАНИЕ ПРЕОБРАЗОВАНИЙ 4

3.5.1. from 4

3.5.2. to 5

3.5.3. difficulty 5

3.5.4. inversion 5

3.6. ОПИСАНИЕ РАЗДЕЛА ОПИСАНИЯ ГЕНЕРИРУЕМЫХ ПАРАМЕТРОВ 5

3.7. ОПИСАНИЕ ЗНАЧЕНИЯ ГЕНЕРИРУЕМОГО ПАРАМЕТРА 5

3.7.1. type 5

3.7.2. min 5

3.7.3. max 5

3.7.4. values 5

3.7.5. constraints 5

3.7.6. body 5

3.7.7. param 6

3.7.8. Примечание 6

3.8. ПРИМЕРЫ 6

3.8.1. Пример 1 – описание образца 6

3.8.2. Пример 2 – описание эквивалентных преобразований 6

3.8.3. Пример 3 – описание генерируемых параметров 6

4. ПРОЕКТ 7

4.1. GENEX 7

4.2. GENEX::SCANNER 7

4.3. GENEX::PARSER 8

4.4. GENEX::NODE 8

4.5. GENEX::PARAMETERS 9

4.6. GENEX::EXPRESSION 10

5. АЛГОРИТМЫ 10

5.1. ГЕНЕРАЦИЯ ВЫРАЖЕНИЙ 10

5.1.1. Генерация эквивалентных выражений 10

5.1.2. Генерация ошибочных выражений 10

5.2. ГЕНЕРАЦИЯ ГЕНЕРИРУЕМЫХ ПАРАМЕТРОВ 10

6. ЛЕММА О ПЕРЕСТАНОВКЕ АРГУМЕНТОВ МУЛЬТИАРНОЙ ОПЕРАЦИИ 10

7. РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ 11

7.1. ОБЪЕМ КОДА 11

7.2. ТЕСТИРОВАНИЕ 11

7.2.1. Модульное тестирование 11

7.2.2. Тестирование работоспособности 11

7.2.2.1. Алгебра логики 11

7.2.2.1.1. Образец 11

7.2.2.1.2. Эквивалентные преобразования 11

7.2.2.1.3. Ошибочные преобразования 11

7.2.2.1.4. Результат работы программы 11

7.2.2.2. Кубическое уравнение с одним корнем 12

7.2.2.2.1. Образец 12

7.2.2.2.2. Правила генерации параметров 12

7.2.2.2.3. Результаты работы программы 12

ЗАКЛЮЧЕНИЕ 13

СПИСОК ЛИТЕРАТУРЫ 14

1. Введение

1.1. Глоссарий

Образец – исходное выражение, над которым будут производиться эквивалентные преобразования

Эквивалентное преобразование – такое преобразование, применив которое к любому выражению, мы получим другое выражение, эквивалентное данному

Ошибочное преобразование – такое преобразование, применив которое к любому вы-ражению, мы получим другое выражение, не эквивалентное данному

Описание параметров – часть входных данных, описывающие правила генерации па-раметров

Генерируемый параметр – заданная в образце по определённым правилам переменная, которая в последствие принимает случайное значение в заданном в описание диапазоне и удовлетворяющее всем ограничениям, заданным в описании

Прототип пользовательской функции – заданная по определённым правилам перемен-ная, является особым видом генерируемых параметров. Принимает значение заданной в раз-деле описания пользовательской функции от других генерируемых параметров.

Сложность преобразования – наперёд заданная пользователем неотрицательная цело-численная константа, определяющая относительную сложность применения данного преоб-разования к любому выражению

Сложность выражения – сумма сложностей всех преобразований, сделанных над об-разцом, для получения данного выражения

Код дерева – последовательность байт, являющаяся хеш кодом данного дерева

Нормализованное дерево – такое дерево, в котором у каждой коммутативной операции аргументы расположены по возрастанию кода

Коммутативное дерево – такое дерево, в котором все бинарные операции, которые возможно, заменены эквивалентными коммутативными

Мультиарная операция – особое представление ряда одинаковых бинарных операций

1.2. Описание предметной области

В настоящее время для проверки знаний в учебных заведениях используются тесты и контрольные работы из учебников и задачников.

Производство задачников является нецелесообразной и дорогостоящей деятельностью.

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

1.3. Существующие решения и их недостатки

Было рассмотрено несколько тестирующих систем, которые можно разделить на сле-дующие классы:

• Тестовая система с определённым фиксированным банком заданий;

• Тестовая система с автоматической генерацией заданий узкого профиля, где алго-ритм генерации жестко вшит в систему;

1.4. Неформальная постановка задачи

Необходимо разработать и реализовать библиотеку удовлетворяющую следующим требованиям:

• формальное описание входных данных, а именно:

o образца;

o эквивалентных преобразований;

o ошибочных преобразований;

o прототипов пользовательских функций;

• проверка синтаксиса в заданных пользователем описаниях;

Список литературы

[1] “Разбор выражений” http://algolist.manual.ru/syntax/index.php

[2] Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, 2005

[3] Ахо А., Сети Р., Ульман Дж., Компиляторы, 2008

[4] Шварц Р., Фой Б., Феникс Т., Изучаем глубже PERL, 2008

[5] Уолл Л., Кристиансен Т., Орвант Д., Программирование на PERL, 2007

[6] “Регулярные выражения в PERL”

Примечаний нет.