Одна из главных причин, лежащих в основе появления языков программирования высокого уровня, — это вычислительные задачи, которые требуют больших объёмов рутинных и однообразных вычислений. Поэтому к языкам программирования всегда предъявлялись и предъявляются до сих пор требования максимального приближения формы записи вычислений к естественному языку математики. В связи с этим одной из первых областей системного программирования стало исследование способов анализа выражений.
Каждый язык программирования описывается с помощью строго определенного набора правил, определяющих структуру правильной программы.
Интересует магистерская работа на заказ ? Переходите по ссылке на Work5.
Наиболее удобным формализмом для описания синтаксических конструкций языка программирования являются контекстно-свободные грамматики, например, широко распространена нормальная форма Бэкуса-Наура. Она представляет собой формальную систему описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории.
Формальной грамматикой называется способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Отсюда возникает такой термин как синтаксический анализ или по-другому парсинг — процесс сопоставления линейной последовательности лексем (слов) языка с его формальной грамматикой. Результатом парсинга обычно является дерево разбора, которое также называют синтаксическим деревом. Синтаксический анализ выполняет программа или часть программы, которая называется синтаксическим анализатором или парсером.
При парсинге исходный текст преобразуется в структуру данных, обычно в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Синтаксическая структура предложения, полученная в ходе парсинга, может быть представлена либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторой комбинации первого и второго способов представления.
В области исследования анализа предложений были получены многочисленные результаты, однако наибольшее распространение получил метод парсинга с помощью обратной польской записи, которую предложил польский математик Я. Лукашевич.
Грамматики одинаково помогают решать задачи как программистов, использующих язык, так и создателей компиляторов для данного языка:
• Грамматика предоставляет точную и достаточно легкую для понимания синтаксическую спецификацию языка программирования.
• Для некоторых классов грамматик мы можем автоматически сконструировать эффективный анализатор, который определяет, является ли исходная программа синтаксически правильной.
• Аккуратно созданная грамматика может придать языку программирования такую структуру, которая будет полезна и при трансляции исходной программы в правильный объектный код, и при определении ошибок.
• Компиляторы, разработанные на базе грамматик, могут быть достаточно легко расширены (это особенно полезно для добавления новых конструкций, появившихся как результат развития языка)
Однако грамматики используются не только в языках программирования, но и в каждом из языков, на котором говорят люди (например, использование различных знаков препинания), в математических выражениях применяются знаки арифметических, логических операций. Примеров грамматики можно приводить бесконечное множество, однако в данной курсовой работе остановимся на грамматике языков программирования и грамматике математики.
C помощью контекстно-свободных грамматик определяется контекстно-свободная составляющая языка программирования, то есть только то, каким образом записывается та или иная конструкция языка. Другая важная часть определения синтаксической правильности программы - правильность использования типов в программе - не может быть определена с помощью контекстно-свободных грамматик. Поэтому если программа выводима в грамматике, это еще не означает, что она полностью синтаксически правильна.
Целью работы является изучение алгоритма обратной польской нотации.
Для выполнения работы нужно решить следующие задачи:
1. Рассмотреть обратную польскую запись выражения и машину стеков – алгоритм вычисления значения выражения, основанный на данной нотации;
2. Написать программу на языке высокого уровня C#, удовлетворяющую поставленным задачам с требуемыми входными и выходными данными;
3. В ходе реализации использовать структура стека.
Предметом курсовой работы является изучение алгоритма.
Объектом – алгоритм обратной польской нотации.
Курсовая работа состоит из введения, основной части, заключения и программы. В основной части работы содержится три главы: в первой главе приводится краткая теория по синтаксическим анализаторам; во второй главе приводится подробный разбор алгоритм обратной польской нотации и пример вычисления; в третьей главе составлено краткое руководство программиста и результаты работы программы.
25 страниц
65% уникальность
2022 год
34 просмотров
