Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / КУРСОВАЯ РАБОТА, АВТОМАТИЗАЦИЯ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

Автоматы с магазинной памятью. Автоматизированный практикум

cool_lady 300 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 25 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 01.04.2021
Пояснительная записка курсового проекта 27 с., 3 рис., 3 таб., 4 источников, 3 листинга, 2 приложения. ФОРМАЛЬНЫЕ ЯЗЫКИ, ПРЕОБРАЗОВАНИЯ ГРАММАТИК, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ, ТРАНСЛЯТОР, СТЕК, ПРЕОБРАЗОВАНИЕ ВХОДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, БУФЕР ВВОДА/ВЫВОДА. В данном курсовом проекте: «Автоматы с магазинной памятью. Автоматизированный практикум» Была разработана программа, реализующая анализ и обработку вводимых входных последовательностей и недостижимых символов. Программа написана на языке высокого уровня программирования C# в среде разработки Visual Studio 2019 Community и содержит полное описание своей работы и принципов построения архитектуры в виде комментариев в коде программы.
Введение

В последнее время круг задач, решаемых с помощью ЭВМ, значительно расширился, а сложность задач возросла. В этой ситуации все чаще используются языки высокого уровня, а также специализированные языки. Кроме того, всем известен тот факт, что ЭВМ понимает программы, состоящие только из внутренних команд процессора. В связи с этим возникает задача перевода программы с языка высокого уровня на язык, понятный процессору ЭВМ (трансляция). Разрабатывается один из вариантов программы, выполняющей такой перевод, – транслятор. Цель курсовой работы - закрепить основы и углубить знания в области теории автоматов и формальных языков. Формальные грамматики как математический аппарат появились именно по необходимости представления синтаксиса в трансляторах и автоматизации синтаксического анализа. В отличии от лексики и семантики, которые можно реализовать, используя содержательные средства, синтаксический анализатор почти невозможно сделать, руководствуясь здравым смыслом. Здесь необходимо иметь промежуточный уровень между синтаксисом языка и программируемой системой, таким уровнем являются формальные грамматики. В настоящее время существует множество разнообразных языков программирования. Их практическое использование невозможно без соответствующей системы программирования, основу которой составляет транслятор или компилятор. И новые языки продолжают появляются, поэтому изучение этой дисциплины важно для тех, кто так или иначе занимается программированием.
Содержание

Нормативные ссылки 5 Введение 6 1 Необходимость использования автоматов с магазинной памятью 7 2 Организация автомата с магазинной памятью 9 3 Распознаватель скобочных выражений 11 4 Распознавание вложенности скобок и q-грамматика 14 5 Описание алгоритма программы 16 6 Тестирование приложения 18 Заключение 20 Список используемой литературы 21 Приложение А – Листинг классов программы 22 Приложение Б. Скриншот проверки на плагиат 27
Список литературы

1. Ключко В.И., Власенко А.В., Кушнир Н.В., Кушнир А.В. Теория языков программирования и методы трансляции: учеб. пособие / Кубан. гос. технол. ун-т.- Краснодар: Изд. ФГБОУ ВПО «КубГТУ», 2019.- 148 с. 2. Теория языков программирования и методы трансляции: метод. указания по выполнению курсовой работы для студентов всех форм обучения по направлениям: 230100.62 Информатика и вычислительная техника / Сост.: В.И. Ключко, А.В. Власенко, Н.В. Кушнир; Кубан. гос. технол. ун-т. Каф. информационных систем и программирования. – Краснодар: Изд. КубГТУ, 2018. – 27 с. 3. Теория языков программирования и методы трансляции: метод. указания по выполнению лабораторных работ для студентов всех форм обучения и МИППС направления 230100.62 Информатика и вычислительная техника / Сост.: . Ключко В.И., Власенко А.В., Кушнир Н.В., Кушнир А.В; Кубан. гос. технол. ун-т. Каф. информационных систем и программирования. – Краснодар: Изд. КубГТУ, 2019. – 43 с.
Отрывок из работы

1 Необходимость использования автоматов с магазинной памятью Синтаксический разбор осуществляется с применением более сложных грамматик, обеспечивающих иерархическое определение одних правил через другие. Поэтому, для построения распознавателей, мощности конечных автоматов, используемых при лексическом анализе, уже не хватает. Необходим более мощный и универсальный автомат, поддерживающий построение дерева разбора и выстраивающий его как сверху вниз, так и снизу вверх. Из предыдущих тем известно, что конечный автомат можно расширить дополнительной рабочей памятью, чтобы обеспечить распознавание цепочек, порождаемых практически любыми грамматиками. Организация и поведение такого автомата определяется классом грамматик. Как определено в классификации Хомского, контекстно-свободным грамматикам можно поставить в соответствие автомат с магазинной памятью (АМП). То, что даже простые цепочки проблематично распознать с использованием конечного автомата, можно проиллюстрировать решением следующей элементарной задачи: необходимо построить распознаватель правильной вложенности круглых скобок. Такая вложенность скобок часто встречается в различных языках программирования при построении арифметических выражений. Для решения данной задачи необходимо: Определять равенство скобок, то есть количество открывающихся и закрывающихся скобок должно быть равным; Следить за правильностью их вложения, то есть, чтобы любой закрывающейся скобке предшествовала соответствующая открывающаяся. Невозможность использования конечного автомата подтверждается и тем, что грамматику, порождающую рассматриваемые цепочки, нельзя свести к праволинейной (тому виду, который, по классификации Хомского, эквивалентен конечному автомату). Ее также нельзя представить только итеративными диаграммами Вирта, непосредственно соответствующими конечному автомату. Это определяется наличием в грамматике правил с рекурсией в середине. А такая рекурсия не может быть сведена к итерации. Грамматика G7.1 Может быть определена следующим образом: G7.1 = ({A, S}, { (, ) }, P, S) , Где P определяется как: 1. S (A ) A 2. A S 3. A Одним из путей решения задачи является добавление счетчика скобок, который, при просмотре цепочки увеличивается на 1, если встретится открывающаяся скобка. Закрывающаяся скобка уменьшает значения счетчика на единицу. Начальное состояние счетчика (перед просмотром цепочки) равно 0. По завершении просмотра цепочки значение счетчика должно быть равным 0. При этом, в ходе просмотра цепочки счетчик не может принимать отрицательные значения. Подход обеспечивает решение поставленной задачи. Однако, наличие счетчика уже определяет автомат с дополнительно рабочей памятью, которому также необходимо наличие арифметического устройства. Поэтому, использование стека вряд ли будет сложнее. Кроме того, в реальной ситуации могут быть более сложные зависимости. Например, может быть несколько видов скобок со своими правилами вложенности и их взаимным расположением. Значит, необходим универсальный подход, обеспечивающий преодоление различных ситуаций. Таким универсальным подходом и является использование автомата с магазинной памятью. 2 Организация автомата с магазинной памятью АМП в качестве рабочей памяти использует стек, называемый также магазином. Данная память поддерживает только ограниченные операции доступа, в то же время достаточные для решения сложных задач, включая и задачи распознавания цепочек. Автомат с магазинной памятью определяется следующими пятью объектами: Конечным множеством входных символов, включающим концевой маркер (). Конечным множеством магазинных символов, включающим маркер дна (). Конечным множеством состояний, включающим начальное состояние. Устройством управления (УУ), которое каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход. Переход, в отличие от выхода, заключается в выполнении операций над магазином, состоянием и входом. Операции, запрашивающие входной символ после концевого маркера или выталкивания из магазина после маркера дна, а также операция вталкивания маркера дна, исключаются. Начальным содержимым магазина, содержащим маркер дна и, возможно пустую, цепочку магазинных символов. Автомат с магазинной памятью называется распознавателем, если у него 2 выхода: "Допустить" и "Отвергнуть". Существуют следующие операции автомата: Динамическое поведение АМП описывается через его операциями над входной цепочкой и стеком, а также переходами из одного состояния в другое. К операциям над стеком относятся: "Вытолкнуть" - выталкивает из стека верхний символ (будем также использовать сокращенное обозначение ""). "Втолкнуть А" - вталкивает в стек магазинный символ А (будем также использовать сокращенное обозначение "А"). "Заменить XYZ" - используется для сокращения записи, когда необходимо вытолкнуть верхний символ и вместо него втолкнуть несколько других (конкретно в данном случае, где мы имеем X, Y, Z). Запись эквивалентна: XYZ (сокращенно обозначим: XYZ). Переход АМП из одного состояния в другое указывается явно операцией "Состояние t", где t - новое состояние автомата (будем сокращать текст данной операции до "[t]"). Сдвиг входной головки на один символ вправо относительно входной ленты задается операцией "Сдвиг" (сократим до ""). После ее выполнения текущим символом становится следующий символ на входной ленте. Другой операцией над входной головкой является "Держать", которая не изменяет положение входной головки до следующего шага (можно просто не писать, если нет сдвига). Переход или шаг автомата - это выполнение операций над стеком и входной головкой, а также изменение состояния. При этом необязательно, чтобы за один шаг происходили все изменения. Возможно: или входная головка останется на месте, или не произойдет операции над стеком, или не изменится состояние. 3 Распознаватель скобочных выражений Рассмотрим одну из возможных реализация АМП, для задачи проверки корректности вложенности круглых скобок. Кратко опишем общий принцип работы автомата. Если входная головка читает "(", то в магазин заталкивается символ А. Если входная головка читает ")", то из магазина выталкивается содержащийся там символ. Цепочка отвергается, если: На входе остаются правые скобки, а магазин пуст. Входная цепочка прочитана до конца, а в магазине остаются символы А, соответствующие левым скобкам, для которых не нашлось пары Определим данный АМП следующим образом: Множество входных символов: { (, ), }. Множество магазинных символов: { A, } Множество состояний: t, где t является также и начальным состоянием автомата, раз оно единственное. Переходы: (, A, S А, S, (, , S А, S, ), A, S , S, ), , S Отвергнуть , A, S Отвергнуть , , S Допустить В начальном состоянии магазин содержит только маркер дна (). Из представленного описания видно, что поведение автомата имитирует ранее рассмотренный метод распознавания с использованием счетчика. Только вместо счетчика используются "палочки". Эти палочки могут записываться в стек и стираться из него, отражая разность между прочитанными открывающимися и закрывающимися скобками. Работу данного АМП можно рассмотреть на примере распознавания нескольких цепочек. Пусть, первая цепочка будет иметь следующий вид: ( ( ) ( ) ). Тогда осуществляемые автоматом переходы можно представить в виде следующей последовательности текущих состояний его устройств (таблица 1) Номер шага Содержимое стека Состояние автомата Остаток входной цепочки Номер применяемого правила 1 [t] ( ( ) ( ) ) 2 2 A [t] ( ) ( ) ) 1 3 A A [t] ) ( ) ) 3 4 A [t] ( ) ) 1 5 A A [t] ) ) 3 6 A [t] ) 3 7 [t] Допустить Таблица 1. Последовательности текущих состояний устройств В приведенном примере цепочка оказалась распознанной. Следующий пример раскрывает поведение автомата при распознавании цепочки, содержащей большее число правых круглых скобок чем левых: ( ) ) ) Таблица переходов и состояний в этом случае будет выглядеть следующим образом (таблица 2): Номер шага Содержимое стека Состояние автомата Остаток входной цепочки Номер применяемого правила 1 [t] ( ) ) ) 2 2 A [t] ) ) ) 3 3 [t] ) ) Отвергнуть Таблица 2. Таблица переходов и состояний Такая таблица является типичной формой представления одного внутреннего состояния для любого АМП. Если у автомата имеется несколько внутренних состояний, то для каждого из них строится такая таблица переходов. В большинстве реальных случаев АМП имеют только одно состояние. Методы, используемые при нисходящем разборе, достаточно универсальны и разнообразны. Применение восходящего разбора позволяет использовать более мощные KC(1) грамматики, в том числе и грамматики с левой рекурсией, которые при нисходящем разборе использовать невозможно. Возникают проблемы преобразования таких грамматик в грамматики с правой рекурсией, ориентированные на нисходящий разбор. Такое преобразование не всегда очевидно. Однако, применение диаграмм Вирта для представления синтаксиса языков программирования позволяет легко заменить все левые рекурсии на итерации и использовать полученные правила для нисходящего разбора. Поэтому, при практической разработке трансляторов, не имеет особого смысла использовать восходящий разбор.
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Курсовая работа, Автоматизация технологических процессов, 28 страниц
340 руб.
Курсовая работа, Автоматизация технологических процессов, 23 страницы
300 руб.
Курсовая работа, Автоматизация технологических процессов, 29 страниц
350 руб.
Курсовая работа, Автоматизация технологических процессов, 44 страницы
450 руб.
Курсовая работа, Автоматизация технологических процессов, 39 страниц
340 руб.
Курсовая работа, Автоматизация технологических процессов, 33 страницы
350 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg