2
Институт информационных технологий
Кафедра Математического и программного обеспечения ЭВМ
направление подготовки (специальности)
Информационные системы и технологии
КУРСОВАЯ РАБОТА
по дисциплине Теория автоматов и формальных языков
на тему Конструирование модели лексического и синтаксического анализа
Выполнил студент группы
1ИСб-00-21оп
Фурсов Георгий Алексеевич
Руководитель
Ганичева Оксана Георгиевна
Череповец, 2020
Оглавление
Введение
1. Описание и анализ предметной области
1.1 Описание предметной области
1.2 Анализ предметной области
2. Конструирование модели лексического анализа
2.1 Лексический анализ
2.2 Построение конечного автомата
2.3 Построение регулярной грамматики по конечному автомату
3. Построение лексического анализатора
3.1 Определение лексического анализатора
3.2 Моделирование работы лексического анализатора
3.3 Логическое проектирование
3.4 Физическое проектирование
4. Конструирование модели синтаксического анализа
4.1 Связь между КС-грамматиками и синтаксическим анализом
4.2 Построение КС-грамматики
4.3 Построение дерева разбора
Заключение
Список литературы
Приложения
Введение
Лексический анализ -- процесс аналитического разбора входной последовательности символов на распознанные группы -- лексемы, с целью получения на выходе идентифицированных последовательностей. Лексический анализ используется в компиляторах и интерпретаторах исходного кода языков программирования, и в различных синтаксических анализаторах.
Как правило, лексический анализ производится с точки зрения определённого формального языка или набора языков. Язык, а точнее его грамматика, задаёт определённый набор лексем, которые могут встретиться на входе процесса.
Цель лексического анализа обычно состоит в том, чтобы подготовить входную последовательность для другой программы, например, для синтаксического анализатора, и избавить его от определения лексических подробностей в контекстно-свободной грамматике.
Синтаксический анализ -- это процесс сопоставления линейной последовательности лексем (слов) естественного или формального языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом.
В ходе синтаксического анализа исходный текст преобразуется в структуру данных, обычно -- в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Простейший способ реагирования на некорректную входную цепочку лексем -- завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.
1. Описание и анализ предметной области
1.1 Описание предметной области
Лексический анализ представляет собой первую фазу компиляции. Его основная задача состоит в чтении новых символов и выдачи последовательности лексем, используемых синтаксическим анализатором в своей работе. Лексической единицей языка является лексема.
Лексема -- это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка. Ярчайшим примером лексем в повседневной жизни служат слова русского языка.
В языках программирования лексемами являются ключевые слова, идентификаторы, константы и операторы (знаки операций, пунктуации и сравнения). Состав лексем, как правило, определяется синтаксисом языка.
Лексемы представляют собой набор, последовательность символов кода, которая соответствует шаблону. Шаблон - правило, описывающее набор лексем, которые могут представлять определенную лексему в исходной программе.
Лексический анализатор (сканер) или лексем -- это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. Выходная информация лексема далее передаётся на обработку компилятором, в частности, для синтаксического анализа. На самом деле лексический анализатор не обязательно должен быть в составе компилятора - все его функции может выполнить и синтаксический анализатор. [4]
Лексический анализ включают в состав практически всех компиляторов по следующим причинам:
• применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации;
• для выделения в тексте и разбора лексем применяется простая и эффективная техника анализа, в то время как на этапе синтаксического анализа конструкций исходного языка используются достаточно сложные алгоритмы разбора;
• при конструкции компилятора, когда лексический анализ реализован отдельно от синтаксического, для перехода от одной версии языка программирования к другой достаточно только перестроить относительно простой лексический анализатор
Лексический анализатор, так как является частью, во многом зависим от компилятора -функции, состав и типы лексем выбираются разработчиками компилятора и могут меняться с его версией. Также лексем может выполнять некоторые второстепенные задачи - удаление из кода программы комментариев, лишних (не имеющих смысла) пробелов, а также символов табуляции и новых строк. Еще одной второстепенной задачей является согласование сообщений об ошибках компиляции и текста исходной программы. Например, лексический анализатор может подсчитывать количество считанных строк и указать строку, вызвавшую ошибку. В некоторых компиляторах лексический анализатор создает копию текста исходной программы с указанием ошибок.
Таким образом, можно выделить следующие функции лексического анализатора:
• исключение из текста исходной программы комментариев;
• исключение из текста исходной программы незначащих пробелов, символов табуляции и перевода строки;
• выделение лексем следующих классов: идентификаторы; строковые, символьные и числовые константы; ключевые (служебные) слова, операторы (знаки операций и сравнения, разделители).
В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором последовательно. Но для многих языков программирования на этапе лексического анализа может быть недостаточно информации для однозначного определения типа и границ очередной лексемы.
Поэтому в большинстве компиляторов лексический и синтаксический анализаторы - это взаимосвязанные части. Возможны два метода организации взаимосвязи лексического анализа и синтаксического разбора:
• последовательный;
• параллельный.
При последовательном варианте лексический анализатор просматривает весь текст исходной программы от начала до конца один раз и преобразует его в структурированный набор данных. Этот набор данных называют также таблицей лексем. В таблице лексем ключевые слова языка, идентификаторы и константы, как правило, заменятся на специально оговоренные коды, им соответствующие (конкретная кодировка определяется разработчиком при реализации компилятора). Таблица лексем строится полностью вся сразу, и больше к ней компилятор не возвращается. Всю дальнейшую обработку выполняют следующие фазы компиляции.
При параллельном варианте лексический анализ исходного текста выполняется поэтапно так, что синтаксический анализатор, выполнив разбор очередной конструкции языка, обращается к лексеру за следующей лексемой. При этом он может сообщить информацию о том, какую лексему следует ожидать. В процессе разбора при возникновении ошибки может происходить «откат назад», чтобы попытаться выполнить анализ текста на другой основе. И только, после того, как синтаксический анализатор успешно выполнит разбор очередной конструкции языка, лексический анализатор помещает найденные лексемы в таблицу лексем и продолжает разбор дальше в том же порядке.
Синтаксический анализатор (или парсер) - это часть компилятора, которая отвечает за выявление основных синтаксических конструкций входного языка. В задачу синтаксического анализа входит: найти и выделить основные синтаксические конструкции в тексте входной программы, установить тип и проверить правильность каждой синтаксической конструкции, наконец, представить синтаксические конструкции в виде, удобном для дальнейшей генерации текста результирующей программы. [4]
В основе анализатора лежит распознаватель текста кода программы на основе некой грамматики. Синтаксические конструкции языков могут быть описаны через контекстно-свободные (КС) грамматики, однако существуют и языки, описываемые с помощью регулярной грамматики. Чаще всего языки высокого уровня построены на основе синтаксиса именно КС-языков. [4]
Распознаватель дает ответ на вопрос о том, принадлежит или нет цепочка входных символов заданному языку - это основная задача синтаксического анализатора. Помимо этого синтаксический анализатор должен иметь некий выходной язык, с помощью которого он передает следующим фазам компиляции всю информацию о найденных и разобранных синтаксических структурах. [4]
Синтаксический разбор -- это основная часть компилятора на этапе анализа. Без выполнения синтаксического разбора работа компилятора бессмысленна, в то время как лексический разбор в принципе является необязательной фазой. Все задачи по проверке синтаксиса входного языка могут быть решены на этапе синтаксического разбора. Лексический анализатор только позволяет избавить сложный по структуре синтаксический анализатор от решения примитивных задач по выявлению и запоминанию лексем входной программы. [4]
Выходом лексического анализатора является таблица лексем (или цепочка лексем). Эта таблица образует вход синтаксического анализатора, который исследует только один компонент каждой лексемы -- ее тип. Остальная информация о лексемах используется на более поздних фазах компиляции при семантическом анализе, подготовке к генерации и генерации кода результирующей программы. Синтаксический анализ (или разбор) -- это процесс, в котором исследуется таблица лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка.[4]
Синтаксический анализатор воспринимает выход лексического анализатора и разбирает его в соответствии с грамматикой входного языка. Однако в грамматике входного языка программирования обычно не уточняется, какие конструкции следует считать лексемами. Примерами конструкций, которые обычно распознаются во время лексического анализа, служат ключевые слова, константы и идентификаторы. Но эти же конструкции могут распознаваться и синтаксическим анализатором. На практике не существует жесткого правила, определяющего, какие конструкции должны распознаваться на лексическом уровне, а какие надо оставлять синтаксическому анализатору. Обычно это определяет разработчик компилятора исходя из технологических аспектов программирования, а также синтаксиса и семантики входного языка.
Основу любого синтаксического анализатора всегда составляет распознаватель, построенный на основе какого-либо класса КС-грамматик. Поэтому главную роль в том, как функционирует синтаксический анализатор и какой алгоритм лежит в его основе, играют принципы построения распознавателей КС-языков. Без применения этих принципов невозможно выполнить эффективный синтаксический разбор предложений входного языка.
Каждый язык программирования имеет правила, которые предписывают синтаксическую структуру корректных программ. В Pascal, например, программа состоит из блоков, блок - из инструкций, инструкции - из выражений, выражения - из лексем и т.д. Синтаксис конструкций языка программирования может быть описан с помощью контекстно-свободных грамматик или нотации БНФ (форма Бэкуса Наура). Грамматики обеспечивают значительные преимущества разработчикам языков программирования и создателям компиляторов:
• Грамматика дает точную и при этом простую для понимания синтаксическую спецификацию языка программирования.
• Для некоторых классов грамматик можно автоматически построить эффективный синтаксический анализатор, который определяет, корректна ли структура исходной программы. Дополнительным преимуществом автоматического создания анализатора является возможность обнаружения синтаксических неоднозначностей и других сложных для распознавания конструкций языка, которые иначе могли бы остаться не замеченными на начальных фазах создания языка и его компилятора.
• Правильно построенная грамматика придает языку программирования структуру, которая способствует облегчению трансляции исходной программы в объектный код, выявлению ошибок. Для преобразования описаний трансляции, основанных на грамматике языка, в рабочие программы имеется соответствующий программный инструментарий.