Курсовая работа по дисциплине: Теория языков программирования и методы трансляции. Вариант №7.

1. ПОСТАНОВКА ЗАДАЧИ

Написать программу для автоматического приведения заданной контекстно-свободной грамматики (КС-грамматики) к нормальной форме Хомского (БНФ).

Вход программы: терминальный и нетерминальный алфавиты грамматики, целевой символ, правила грамматики, 2 числа - диапазон длин для генерации цепочек.

Выход: построенная грамматика в БНФ (все 4 элемента), результат генерации цепочек по обеим грамматикам.

Подробно:

Язык задан КС-грамматикой, причём для приведения к БНФ она должна находиться в каноническом виде (раздел лекций 3.2.2). Приводить её к этому виду не требуется, достаточно только проверить корректность задания - действительно ли исходная грамматика находится в каноническом виде - и при отрицательном результате выдать соответствующее сообщение. Причём в этом сообщении должны быть конкретно указаны причины, почему именно грамматика не имеет канонического вида (например: <в грамматике присутствуют цепные правила: А>С>, или <в грамматике присутствует недостижимый символ: В>). Для того чтобы в исходной грамматике можно было использовать пустое правило, необходимо либо предусмотреть поле ввода для символа, которым обозначается пустая цепочка, либо дать пояснения пользователю, как именно ему следует задавать пустое правило.

Программа должна:

1.проверить заданную КС-грамматику - находится ли она в каноническом виде и при отрицательном результате выдать сообщение;

2.привести заданную КС-грамматику к нормальной форме Хомского (раздел 3.3.1);

3.проверить построенную грамматику (БНФ) на эквивалентность исходной.

Для проверки построенной грамматики в БНФ на эквивалентность исходной по обеим грамматикам следует сгенерировать множества всех цепочек в заданном пользователем диапазоне длин и проверить эти множества на идентичность. Генерация цепочек осуществляется в соответствии с лабораторной работой №1.

При обнаружении несовпадения должна выдаваться диагностика различий - где именно несовпадения и в чём они состоят. Для удобства сравнения множества цепочек необходимо упорядочить, цепочки перенумеровать, для генерации цепочек по каждой грамматике сделать отдельную кнопку. Следует предусмотреть возможность многократного изменения диапазона длин цепочек и повторной их генерации для новых значений длины.
Приведение КС-грамматики к нормальной форме Хомского следует осуществлять согласно алгоритму, изложенному в лекционном материале (раздел 3.3.1).

Уважаемый слушатель, дистанционного обучения,
Оценена Ваша работа по предмету: Теория языков программирования и методы трансляции
Вид работы: Курсовая работа
Оценка: Отлично
Дата оценки: 11.09.2016
Рецензия:Уважаемый С*