Курсовая с практикой на тему Разработать структуру данных алгоритм и программу для реализации восходящего синтаксического распознавателя.

Содержание:

ВВЕДЕНИЕ 3
РАЗДЕЛ 1. АНАЛИТИЧЕСКИЙ РАЗДЕЛ 6
1.1 Грамматики предшествования. Задача синтаксического анализа 6
1.2 Понятие восходящего синтаксического анализа 8
1.3 Постановка задачи 11
РАЗДЕЛ 2. ОБЗОР ЯЗЫКА ПРОГРАММИРОВАНИЯ 14
РАЗДЕЛ 3. РЕАЛИЗАЦИЯ ПРОЕКТА 16
3.1 Основные моменты реализации 16
3.2 Подбор тестов и результаты тестирования 18
ЗАКЛЮЧЕНИЕ 20
СПИСОК ЛИТЕРАТУРЫ 21
ПРИЛОЖЕНИЕ 23
Приложение А. Листинг кода 23

Введение:

Основным назначением искусственных языков является передача информации компьютерам и управляющим устройствам. Искусственные языки значительно проще естественных языков, поскольку в них отсутствуют неоднозначности и синонимы, упрощенные синтаксис и семантика, а также существенно снижена контекстная зависимость. Текст представляет собой задачу, которая должна выполняться компьютером. Текст такой задачи, как правило, создается человеком, поэтому язык написания текста строится таким образом, чтобы он был понятный и удобный людям, его используют. Язык, ориентированная на человека, как правило, не совпадает с видом команд, выполняемых компьютером. Чтобы выполнить преобразование текста входном языке в последовательность команд, понятных компьютеру, используют специальные программы, которые называются языковыми процессорами.
Основное требование к речевого процессора заключается в том, что он должен точно передать содержание текста, написанного входной языке. Основой каждого языка есть алфавит. Искусственный язык содержит в себе правила образования простейших выражений языка (лексем) и правила построения сложных выражений с более простых. Эти две группы правил называются соответственно лексической и синтаксической системами языка. Правила, по которым выражениям языка сопоставляется содержание, образуют семантическую систему языка.
Для описания лексики, синтаксиса и семантики используются различные средства. Так, описание лексем языка может быть выполнен, например, с помощью грамматик, регулярных выражений или конечных автоматов, описание синтаксиса языка — с применением контекстно-свободных грамматик с определенными ограничениями или магазинных автоматов, а описание ее семантики — с помощью атрибутных грамматик.
Теория формальных грамматик и языков является основным разделом математической лингвистики специфической математической дисциплины, ориентированной на изучение структуры природных и искусственных языков. Эта теория возникла в 50-х годах в работах американского лингвиста Ноама Хемском, который выходил исключительно из потребностей лингвистики, традиционно понимается как наука о построении естественного языка. Однако, вскоре стало ясно, что методы его теории могут быть применены и к искусственным специализированных языков, в том числе, алгоритмических. По характеру математического аппарата, применяемого теория формальных грамматик и языков близка к теории автоматов.
Под грамматикой понимают некоторую систему правил, задает множество цепочек символов языка. Эти цепочки могут интерпретироваться как языковые объекты различных уровней: как словоформы, словосочетания или предложения. Словоформа (или просто слово) — (последовательность) цепь морфем. Морфема — наименьшая грамматически значима часть слова (словоформы).
Актуальность исследований в данном направлении не угасает последние несколько десятков лет. Новый виток этих исследований связан с развитием искусственного интеллекта и различных интеллектуальных сервисов. Естественно данная конкретная работа не претендует на научную новизну, и преследует исключительно учебные цели.
Целью работы является рассмотрение частного случая распознавания и анализа на примере жестко формализованных математических выражений.
Объект исследования – грамматики предшествования и алгоритмы их анализа
Предмет исследования – применение алгоритма анализа для распознавания математического выражение поданного на вход алгоритма в виде строки.
Практическая часть работы предполагает реализацию программы, которая может распознавать и вычислять математические выражения содержащие операции, константы, скобки и некоторые (ограниченный набор) математические функции.

Заключение:

В объеме курсовой работы проведены исследования в области современных языков программирования высокого уровня и их применение для решения прикладных задач.
В качестве прикладной задачи рассматривается задача разбора математического выражения.
Структура работы включает введение, основную часть и выводы.
В первом разделе проведено исследование теории грамматик и алгоритм восходящего синтаксического анализа, который положен в основу программной реализации практической части. Также в первом разделе приводится постановка задачи и ее анализ. Второй раздел работы посвящен краткой характеристике языка, используемого для реализации программной части.
В последнем разделе приводится описание отдельных решений по реализации, а также подбор тестов и примеры выполнения тестового набора программой. Листинг (приложение 1) содержит детально комментированный программный код, что позволяет легко понять ход и особенности реализации алгоритма.
В качестве практической реализации разработан калькулятор строчных математических выражений, основанный на классическом подходе преобразования строчного выражения в постфиксную форму. Реализация имеет ряд ограничений, но соответствует поставленной задаче. Разработанная программа прошла тестирования, выявленные, в ходе тестирования, ошибки откорректированы.
 

Фрагмент текста работы:

РАЗДЕЛ 1. АНАЛИТИЧЕСКИЙ РАЗДЕЛ
1.1 Грамматики предшествования. Задача синтаксического анализа
С появление программируемых машин возникла необходимость анализа или разбора последовательностей команд передаваемых на обработку. Исследования в этой области породили отдельные направления математики, такие как теория формальных языков, теория синтаксического анализа. Непосредственное отношение к теме имеет и теория автоматов.
Цели и направления данных дисциплин заключаются в построении алгоритмов и подходов к формализации языка, приведении его к некоторым, поддающимся математическому описанию и формализации, конструкциям.
Одним из ключевых понятий данных направления являются грамматики. Рассмотрим основные понятия, связанные с грамматиками и дальнейшим построением алгоритма.
Грамматики предшествования
Пусть G = (Σ, Γ, P, S) КС-грамматика, X, Y ∈ Σ ∪ Γ. Определим отношения простого предшествования =•, <• и •>:
X .= Y , если XY входит в основу некоторой r-формы;
X <• Y , если основа некоторой r-формы начинается с символа Y , перед которым стоит символ X;
X •> Y , если основа некоторой r-формы заканчивается символом X, после которого стоит символ Y (Y ∈ Σ ?)[4].

Рисунок 1.1 – Графическая интерпретация отношений
Среди грамматик предшествования выделяют грамматики простого предшествования.
Грамматика называется обратимой, если любые два различных правила вывода имеют различные правые части.
КС-грамматика G = (Σ, Γ, P, S) называется грамматикой простого предшествования (ПП-грамматикой), если она без циклов, обратима и для любой упорядоченной пары символов из Σ ∪ Γ выполняется не более одного отношения простого предшествования.