1800

Курсовая и Лабораторные работы 1-3 по дисциплине: Теория языков программирования и методы трансляции. Вариант №10*

ID: 237692
Дата закачки: 06 Июля 2023
Продавец: IT-STUDHELP (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: СибГУТИ

Описание:
Курсовая работа
Вариант №10

Постановка задачи

Написать программу для автоматического построения регулярной грамматики (леволинейной или праволинейной) по словесному описанию языка.
Вход программы: алфавит языка, обязательная конечная подцепочка, кратность длины всех цепочек языка, тип грамматики (ЛЛ либо ПЛ), 2 числа – диапазон длин для генерации цепочек.
Выход: построенная грамматика (все 4 элемента), результат генерации цепочек.
Подробно:
Язык задан своим алфавитом, обязательной конечной подцепочкой, которая должна присутствовать во всех цепочках языка, и указанием кратности длины всех цепочек языка. В конечной цепочке не должно находиться символов, не содержащихся в алфавите. В крайнем случае она может быть и пустой. Кратность длины цепочек задаётся любым натуральным числом. Кратность, равная единице, равносильна отсутствию ограничений на длину цепочек.
Программа должна:
1. по предложенному описанию регулярного языка строить регулярную грамматику, генерирующую этот язык, в том виде, как она рассматривалась в теории, раздел 1.3.1;
2. с помощью построенной грамматики генерировать все цепочки языка в заданном пользователем диапазоне длин.
Грамматика должна строиться и праволинейная, и леволинейная. Желаемый тип грамматики выбирается пользователем в меню. Все правила грамматики должны соответствовать выбранному типу! Отдельно следует указывать, какой нетерминальный символ является целевым. Если в грамматике используется пустое правило, то необходимо дать пояснение, каким именно символом обозначается пустая цепочка.
После построения грамматики пользователь может убедиться в её правильности путём генерации всех цепочек языка в том диапазоне длин, который он задаст. Генерацию каждой цепочки языка следует поэтапно отображать на экране в виде цепочки вывода (в соответствии с примерами раздела 1.4.1.). Генерация осуществляется в соответствии с лабораторной работой №1.

=============================================
=============================================

Лабораторная работа 1
Генерация цепочек языка

Постановка задачи:

Пусть язык задан контекстно-свободной грамматикой (теоретический материал разделов 1.1–1.4). Написать программу, которая по заданной грамматике будет генерировать ВСЕ цепочки языка в некотором диапазоне длин. Использовать только левосторонний или правосторонний вывод! Диапазон длин генерируемых цепочек должен задаваться пользователем при запуске программы.
Предусмотреть возможность выбора пользователю – использовать заданную в программе грамматику или вводить свою с клавиатуры.
На вход программы подаётся КС-грамматика (терминальный и нетерминальный алфавиты, целевой символ, правила вывода), задаётся диапазон длин цепочек, указывается тип вывода (левосторонний или правосторонний).
Рекомендуется для ввода исходных данных использовать соответствующую форму. При вводе правил грамматики не рекомендуется предоставлять пользователю излишнюю свободу действий, например, удобнее запретить ввод в левой части правил более чем одного нетерминального символа, чем проверять введённые правила на соответствие контекстно-свободному типу.
На выходе должен быть список построенных цепочек. Все цепочки в списке должны быть различны. При получении одинаковых цепочек (разными способами) их следует сохранять в списке выводимых цепочек только в случае выполнения дополнительного задания.
Проверить программу на примерах из лекционного курса и на заданиях из контрольных вопросов к теоретической части.

Входные данные программы:
1. Терминальный алфавит (запрещается ввод заглавных букв)
2. Нетерминальный алфавит (запрещается ввод любых символов, кроме заглавных букв)
3. Целевой символ (выбирается из нетерминального алфавита)
4. Правила вывода (формат правила A->aB|cC)
5. Минимальная длина цепочки (ограничена снизу значением 0, сверху максимальной длиной цепочки)
6. Максимальная длина цепочки (ограничена снизу минимальной длиной цепочки, сверху значением 5)
7. Тип вывода (выбор левого или правого осуществляется с помощью соответствующей радиокнопки)

------------------------------------------------------------------------------

Ответы на контрольные вопросы:

1. Как поведёт себя программа, если при вводе правил грамматики сделать ошибку – ввести правила грамматики, не соответствующей КС-типу, или не использовать какие-то символы исходных алфавитов, или поместить в левой части правил терминальный символ?
2. Используется ли при генерации цепочек рекурсия? Если да, то как ограничена её глубина?
3. Какой язык порождается грамматикой G({0},{S,A},{SAAA, AAAA |0}, S)? Правильно ли Ваша программа работает на этом примере?
4. Разрешает ли Ваша программа использовать в исходной грамматике пустые правила? Если нет – доработайте программу.

=============================================

Лабораторная работа 2
Моделирование работы ДКА

Постановка задачи

Пусть регулярный язык задаётся конечным автоматом – ДКА (теоретический материал разделов 1.5, 2.2). Написать программу, которая будет проверять по заданному автомату вводимую цепочку и делать вывод о том, принадлежит ли она рассматриваемому регулярному языку. В случае отрицательного ответа необходимо давать пояснение, по какой причине цепочка не принадлежит языку – например, «в цепочке присутствуют посторонние символы», «после прочтения цепочки автомат не пришёл в конечное состояние» и т.п. Исходный автомат вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры.
На вход программы подаётся ДКА (множество состояний, алфавит языка, начальное состояние, множество заключительных состояний, функция переходов в виде таблицы) и проверяемая цепочка символов (может вводиться многократно, т.е. возможно проверить любое количество цепочек). При этом в проверяемую цепочку могут входить и символы, не принадлежащие алфавиту языка; цепочка может быть и пустой.
Программа должна предоставлять пользователю возможность изменять начальное и конечные состояния с сохранением введённой функции переходов для заданного автомата.
Выход – отображение на экране процесса проверки цепочки в виде последовательной смены конфигураций и вывод результата – сообщения, принадлежит ли цепочка языку.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно:
1) Предоставить пользователю возможность не только вводить данные с клавиатуры, но и загружать автомат из файла (выбор – в соответствующем пункте меню или нажатием кнопки в исходном окне программы). При этом следует накладывать определённые ограничения на формат файла и производить соответствующие проверки во избежание загрузки некорректных данных.
2) Также по желанию пользователя результаты помимо вывода на экран сохранять в файле. Выбор – аналогично загрузке данных.

Входные данные программы:
1. Множество состояний
2. Алфавит языка алфавита
3. Начальное состояние (выбирается из множества состояний)
4. Множество финальных состояний (выбирается из множества состояний, при этом должно быть выбрано хотя бы одно состояние)
5. Функция переходов (формат перехода q1 0 q2)
6. Слово, проверяемое на соответствие языку автомата

------------------------------------------------------------------------------

Ответы на контрольные вопросы:

1. Как поведёт себя программа, если при вводе таблицы переходов ДКА сделать (случайно или преднамеренно) ошибку – например, ввести несуществующее состояние?
2. Все ли ячейки таблицы переходов исходного ДКА обязательно должны быть заполнены или можно использовать неполностью определённый ДКА?
3. В каком случае ДКА распознаёт пустую цепочку как цепочку языка?

=============================================

Лабораторная работа 3
Перевод с помощью МП-преобразователя

Постановка задачи

Пусть дан преобразователь с магазинной памятью; написать программу, которая будет выполнять перевод цепочек с одного языка на другой с помощью заданного преобразователя (теоретический материал раздела 4.2). При невозможности выполнить перевод (цепочка не принадлежит исходному языку) необходимо выводить на экран соответствующее сообщение.
Исходный преобразователь вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры, выполняя его до тех пор, пока не возникнет желание закончить работу. Процесс перевода цепочки в виде последовательной смены конфигураций отображать на экране.
На вход программы подаётся ДМП-преобразователь (множество состояний, алфавиты входного и выходного языков, алфавит магазина, начальное состояние, начальное содержимое стека, множество заключительных состояний, функция переходов в виде списка правил) и проверяемая цепочка символов (аналогично лаб. раб. №2).
Рекомендуется за основу взять программу лабораторной работы №2, дополнив исходные данные алфавитом стека, начальным содержимым стека и выходным алфавитом, функцию переходов – в соответствии с определением преобразователя, а конфигурации – содержимым памяти и выходными цепочками.
Выход: отображение на экране процесса перевода цепочки в виде последовательной смены конфигураций преобразователя, результат перевода – полученная цепочка.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно:
Предоставить пользователю возможность не только вводить данные с клавиатуры, но и загружать преобразователь из файла (аналогично лабораторной работе №2).

Входные данные программы:
1. Множество состояний
2. Алфавит языка алфавита
3. Алфавит стека
4. Начальное состояние (выбирается из множества состояний)
5. Начальный символ стека (выбирается из алфавита стека)
6. Множество финальных состояний (выбирается из множества состояний, при этом должно быть выбрано хотя бы одно состояние)
7. Функция переходов (формат перехода q1 0 q2)
8. Слово, проверяемое на соответствие языку автомата

------------------------------------------------------------------------------

Ответы на контрольные вопросы:

1. Как поведёт себя преобразователь, если поданная на его вход цепочка не может быть распознана (не принадлежит к заданному языку)?
2. Как соотносятся алфавиты исходного языка и того, на который выполняется перевод (должны совпадать, различаться…)? Поясните ответ.
3. Как поведёт себя Ваша программа при некорректном вводе? Например, функция переходов задана не в том формате, определена не для того количества параметров, использует алфавит, отличный от заданных…

=============================================

Комментарии:
Проверил(а): Бах Ольга Анатольевна
Оценка: Зачет
Дата оценки: 07.07.2023г.

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

Размер файла: 1,4 Мбайт
Фаил: (.rar)
-------------------
Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные!
Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку.
Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот.
-------------------

Скачать

Добавить в корзину

Занесено в корзину

        Коментариев: 0

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

Курсовая и Лабораторные работы 1-3 по дисциплине: Теория языков программирования и методы трансляции. Вариант №10
Теория языков программирования и методы трансляции. Лабораторные работы 1-5. Все варианты. Курсовая работа. Вариант 10. Экзаменационная работа. Билет 25.
Ещё искать по базе с такими же ключевыми словами.