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

Курсовая работа
цифры 20 (вар 10)

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

Тема: «Программа для автоматического построения регулярной грамматики (леволинейной или праволинейной) по словесному описанию языка»

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

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

СОДЕРЖАНИЕ:

1 Постановка задачи 
2 Алгоритм решения задачи 
3 Описание основных переменных, основных блоков и подпрограмм 
4 Текст программы 
5 Результаты тестирования программы 
6 Распечатка файлов результатов 

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

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

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

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

1 Описание входных данных программы и ее результатов

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

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

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

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

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

СОДЕРЖАНИЕ:

1 Постановка задачи 
1 Описание входных данных программы и ее результатов 
3 Описание основных переменных, основных блоков и подпрограмм 
4 Алгоритм решения задачи 
5 Текст программы 
6 Результаты работы программы 
7 Ответы на контрольные вопросы 

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

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

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

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

1 Описание входных данных программы и ее результатов

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

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

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

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

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

СОДЕРЖАНИЕ:

1 Постановка задачи 
1 Описание входных данных программы и ее результатов 
3 Описание основных переменных, основных блоков и подпрограмм 
4 Алгоритм решения задачи 
5 Текст программы 
6 Результаты работы программы 
7 Ответы на контрольные вопросы 

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

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

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

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

2 Описание входных данных программы и ее результатов

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

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

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

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

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

СОДЕРЖАНИЕ:

1 Постановка задачи 
2 Описание входных данных программы и ее результатов 
3 Описание основных переменных, основных блоков и подпрограмм 
4 Алгоритм решения задачи 
5 Текст программы 
6 Результаты работы программы 
7 Ответы на контрольные вопросы 

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

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

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