engineerklub | Дата: Среда, 24.02.2021, 20:33 | Сообщение # 1 |
Генералиссимус
Группа: Администраторы
Сообщений: 28596
Статус: Offline
| Теория языков программирования и методы трансляции. 9-й вариант
Тип работы: Работа Курсовая Форматы файлов: Microsoft Word, Delphi Сдано в учебном заведении: ДО СИБГУТИ
Описание: Задание
Вариант 9 Написать программу для автоматического построения регулярного выражения (РВ) по словесному описанию языка. Вход программы: алфавит языка, обязательные начальная и конечная подцепочки, кратность длины всех цепочек языка, 2 числа – диапазон длин для генерации цепочек. Выход: построенное регулярное выражение, результат генерации цепочек. Подробно: Язык задан своим алфавитом, обязательной начальной и конечной подцепочками и указанием кратности длины всех цепочек языка. В заданных подцепочках не должно находиться символов, не содержащихся в алфавите. В крайнем случае они (одна или обе) могут быть и пустыми. Особый случай – это пересечение заданных цепочек по одному или нескольким символам, в том числе и полное их совпадение. Кратность длины цепочек задается любым натуральным числом. Кратность, равная единице, равносильна отсутствию ограничений на длину цепочек. Программа должна: 1. по предложенному описанию регулярного языка строить РВ, задающее этот язык, в том виде, как было рассмотрено в теории, раздел 2.1.1; 2. с помощью построенного РВ генерировать все цепочки языка в заданном пользователем диапазоне длин. При генерации цепочек языка по РВ можно использовать любые структуры и алгоритмы, в том числе и прямой перебор. Рассмотрим пример построения регулярного выражения. Задан язык: алфавит {a,b,c}, обязательная начальная цепочка ‘саа’, конечная цепочка ‘aab’, длина цепочек кратна 2. Анализируем задание: язык будет состоять из цепочек чётной длины, начинающихся с цепочки ‘cаа’ и заканчивающихся на ‘aab’, например {сaab, сaaааb, caaасааb, сaabсaab, …}. Для начала определим минимально возможную цепочку этого языка. Это ‘сaab’ – она получается при максимальном пересечении начальной и конечной цепочек, удовлетворяет всем условиям и является при этом самой короткой. Удлинить её можно путём уменьшения области пересечения начальной и конечной цепочек. Следующая по длине цепочка могла бы быть ‘сaаab’ (пересечение по одному символу), но она не удовлетворяет условию чётности длины. А вот ещё следующая цепочка – ‘сaaааb’ – получена простым соединением начальной и конечной цепочек. Это основа нашего РВ. Её можно удлинять, помещая между начальной и конечной цепочками некоторое количество символов алфавита, причём для сохранения чётности длины это количество тоже должно быть чётным. Для генерации любого количества пар символов используется итерация, а выбор одного из нескольких символов записывается в виде суммы. Итоговое регулярное выражение будет иметь вид: саа((а+b+c)(a+b+c))*aab+caaaab. Если в этом же задании изменить кратность длины на единицу, то итоговое РВ изменится таким образом: добавлять можно будет не пары символов, а по одному символу любое количество раз, и пересечения цепочек будут использованы все. Итоговое регулярное выражение будет иметь вид: саа(a+b+c)*aab+caaab +caaaab.
Доп.задание:
Программа чужая. Для получения положительной оценки придется выполнить дополнительное задание. Добавьте генерацию цепочек по введенному пользователем РВ.
Результат доработки:
Для выполнения дополнительного задания на панель программы добавлена редактируемая область для строки РВ. Данная область используется следующим образом. При построении РВ в эту область выводится результат, т.е. построенное РВ. При генерации цепочек из этой области читается строка с РВ. В любой момент времени можно изменить содержимое области с РВ с клавиатуры. В строке с РВ все символы, не совпадающие с символами круглых скобок и символами операций выбора и итерации, считаются символами алфавита языка. При этом символы алфавита языка, введенные в другом поле на панели программы игнорируются. Таким образом, при измененной с клавиатуры строке с РВ, т.е. отличной от той, которая была получена при построении РВ по входным данным, алфавит языка при генерации цепочек может быть другой. Вывод на экран сгенерированных по РВ цепочек оставлен прежним.
СКАЧАТЬ
|
|
| |