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

1. Задание

Написать программу для автоматического приведения заданной контекстно-свободной грамматики (КС-грамматики) к нормальной форме Хомского (БНФ).
Вход программы: терминальный и нетерминальный алфавиты грамматики, целевой символ, правила грамматики, 2 числа – диапазон длин для генерации цепочек.
Выход: построенная грамматика в БНФ (все 4 элемента), результат генерации цепочек по обеим грамматикам.
Подробно:
Язык задан КС-грамматикой, причём для приведения к БНФ она должна находиться в каноническом виде (раздел лекций 3.2.2). Приводить её к этому виду не требуется, достаточно только проверить корректность задания – действительно ли исходная грамматика находится в каноническом виде – и при отрицательном результате выдать соответствующее сообщение. Причём в этом сообщении должны быть конкретно указаны причины, почему именно грамматика не имеет канонического вида (например: «в грамматике присутствуют цепные правила: А→С», или «в грамматике присутствует недостижимый символ: В»). Для того чтобы в исходной грамматике можно было использовать пустое правило, необходимо либо предусмотреть поле ввода для символа, которым обозначается пустая цепочка, либо дать пояснения пользователю, как именно ему следует задавать пустое правило.
Программа должна:
1. проверить заданную КС-грамматику – находится ли она в каноническом виде и при отрицательном результате выдать сообщение;
2. привести заданную КС-грамматику к нормальной форме Хомского (раздел 3.3.1);
3. проверить построенную грамматику (БНФ) на эквивалентность исходной.
Для проверки построенной грамматики в БНФ на эквивалентность исходной по обеим грамматикам следует сгенерировать множества всех цепочек в заданном пользователем диапазоне длин и проверить эти множества на идентичность. При обнаружении несовпадения должна выдаваться диагностика различий – где именно несовпадения и в чём они состоят. Для удобства сравнения множества цепочек необходимо упорядочить, цепочки перенумеровать, для генерации цепочек по каждой грамматике сделать отдельную кнопку. Следует предусмотреть возможность многократного изменения диапазона длин цепочек и повторной их генерации для новых значений длины.
Приведение КС-грамматики к нормальной форме Хомского следует осуществлять согласно алгоритму, изложенному в лекционном материале (раздел 3.3.1).
2. Описание алгоритма решения задачи

Сначала множество нетерминальных символов новой грамматики строится на основе множества нетерминальных символов исходной грамматики: VN'=VN.
Затем алгоритм работает с правилами P исходной грамматики и в зависимости от их вида строит множество правил P' и пополняет множество нетерминальных символов VN'.
1. Правила вида A→a, A→BC, S→λ, где A, B, C∈VN, a∈VT, переносятся во множество P' без изменений.
2. Если встречается правило вида (A→aB)∈P, где A, B∈VN, a∈VT, то во множество правил P' добавляются правила A→<AaB>B и <AaB>→a, а новый символ <AaB> добавляется во множество нетерминальных символов VN'.
3. Если встречается правило вида (A→Ba)∈P, выполняется аналогичное действие: во множество правил P' добавляются правила A→B<ABa> и <ABa>→a, а новый символ <ABa> добавляется во множество нетерминальных символов VN'.
4. Если встречается правило вида (A→ab)∈P, где A∈VN, a, b∈VT, то во множество правил P' добавляются правила A→<Aa><Ab> и <Aa>→a, <Ab>→b, а новые символы <Aa>, <Ab> добавляются во множество нетерминальных символов VN'.
5. Если встречается правило вида (A→X1X2...Xk)∈P, где k>2, A∈VN, ∀i Xi∈VT∪VN, то во множество правил P' добавляются правила
A→X1'<X2'...Xk'>,
<X2'...Xk'>→X2'<X3'...Xk'>,
...
<Xk–1'Xk'>→Xk–1'Xk',
где все новые нетерминальные символы <...> добавляются во множество нетерминальных символов VN'. Что касается символов Xi', то их вид зависит от того, чем являлся исходный символ Xi. Если для некоторого i Xi∈VN, то Xi'≡Xi∈VN'; если Xi∈VT, то Xi' – новый нетерминальный символ, т.е. Xi'∈VN' и в P' нужно добавить правило Xi'→Xi.

Оценка: Отлично
Дата оценки: 15.05.2022

Помогу с вашим онлайн тестом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com
E-mail: ego178@mail.ru