Четверг, 28.11.2024, 03:58
Приветствую Вас, Гость
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Теория языков программирования и методы трансляции. 9-й вари
engineerklubДата: Среда, 24.02.2021, 20:33 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 28596
Репутация: 0
Статус: 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.

Доп.задание:

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

Результат доработки:

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

СКАЧАТЬ
 
  • Страница 1 из 1
  • 1
Поиск:

Рейтинг@Mail.ru