Назначение синтаксического анализатора

Тема 4. Синтаксические анализаторы

4.1. Основные принципы работы синтаксических анализаторов. 2

4.1.1. Назначение синтаксического анализатора. 2

4.1.2. Обработка синтаксических ошибок. 4

4.1.3. Стратегии восстановления после ошибок. 5

4.2. Контекстно-свободные языки. 7

4.2.1. Свойства и распознаватели КС-языков. 7

4.2.1.1. Автоматы с магазинной памятью – распознаватели КС-языков. 7

4.2.1.2. Свойства КС-языков. 10

4.2.1.3. Контрольные вопросы.. 12

4.2.2. Преобразование КС-грамматик. 12

4.2.2.1. Цели преобразований грамматик. 12

4.2.2.2. Приведённые грамматики. 13

4.2.2.3. Контрольные вопросы.. 18

4.2.3. КС-грамматики в нормальной форме. 19

4.2.3.1. Нормальная форма Хомского. 19

4.2.3.2. Левая рекурсия. Нормальная форма Грейбах. 21

4.2.3.3. Контрольные вопросы.. 24

4.3. Виды распознавателей КС-языков. 24

4.3.1. Распознаватели КС-языков с возвратом.. 24

4.3.1.1. Нисходящий распознаватель с возвратом.. 25

4.3.1.2. Распознаватель на основе алгоритма «сдвиг-свёртка». 30

4.3.2. Табличные распознаватели КС-языков. 35

4.3.3. Распознаватели КС-языков без возвратов – основные принципы.. 39

4.3.4. Контрольные вопросы.. 39

4.4. Специальные классы КС-языков и грамматик. 40

4.4.1. Нисходящие распознаватели без возвратов. 40

4.4.1.1. Метод рекурсивного спуска. 40

4.4.1.2. Разбор для LL(k)-грамматик. 44

4.4.2. Восходящие распознаватели без возвратов. 53

4.4.2.1. LR(k)-грамматики. 53

4.4.2.2. Грамматики предшествования. 57

4.4.3. Контрольные вопросы.. 60

Основные принципы работы синтаксических анализаторов

Синтаксис конструкций языка про­граммирования может быть описан с помощью контекстно-свободных грамматик. Грамматики обеспечивают значительные преимущества разработ­чикам языков программирования и создателям компиляторов.

· Грамматика дает точную и при этом простую для понимания синтаксиче­скую спецификацию языка профаммирования.

· Для некоторых классов грамматик мы можем автоматически построить эффективный синтаксический анализатор, который определяет синтакси­ческую структуру исходной программы. Дополнительным преимуществом автоматического создания анализатора является возможность обнаружения синтаксических неоднозначностей и других сложностей, которые иначе могли бы остаться незамеченными на начальных фазах создания языка и его компилятора.

· Правильно построенная грамматика придает языку программирования структуру, которая способствует облегчению трансляции исходной программы в корректный объектный код и выявлению ошибок.

· Грамматика позволяет языку итеративно эволюционировать, обогащаясь новыми конструкциями для решения новых задач. Добавление этих новых конструкций в язык оказывается более простой задачей, если существую­щая реализация языка основана на его грамматнческом описании.

Назначение синтаксического анализатора

Синтаксический анализатор (синтаксический разбор) — это часть компилятора, которая отвечает за выявление и проверку синтаксических конструкций входно­го языка. В задачу синтаксического анализа входит:

· поиск и выделение синтаксических конструкций в тексте исходной программы;

· установка типа и проверка правильности каждой синтаксической конструкции;

· представление синтаксических конструкций в виде, удобном для дальней­шей генерации текста результирующей программы.

· выдача сообщений обо всех выявленных ошибках

Синтаксический анализатор — это основная часть компилятора на этапе анали­за. Схема работы синтаксического анализатора приведена на рис. 4.1. Синтаксический анализатор получает строку токенов от лексического анализатора, и проверяет, может ли эта строка имен токенов порождаться грамматикой исходного языка. Мы также ожидаем от синтаксического анализатора сообщений обо всех выявленных ошиб­ках, причем достаточно внятных и полных, а кроме того, умения обрабатывать обычные, часто встречающиеся ошибки и продолжать работу с оставшейся ча­стью программы. Концептуально в случае корректной программы синтаксический анализатор строит дерево разбора и передает его следующей части компилятора для дальнейшей обработки. В действительности явное построение дерева разбо­ра не требуется, поскольку проверки и действия трансляции, могут выполняться в процессе синтаксического анализа. Таким образом, синтак­сический анализатор и прочие части начальной стадии компилятора могут быть реализованы в виде единого модуля.

Имеется три основных типа синтаксических анализаторов гррамматик: универ­сальные, восходящие и нисходящие. Универсальные методы разбора могут работать с любой грамматикой. Однако эти обобщенные методы слишком неэф­фективны для использования в промышленных компиляторах.

Методы, обычно применяемые в компиляторах, можно классифицировать как

нисходящие (сверху вниз — top-down) или восходящие (снизу вверх — bottom-up). Как явствует из названий, нисходящие синтаксические анализаторы строят дерево разбора сверху {от корня) вниз (к листьям), тогда как восходящие начина­ют с листьев и идут к корню. В обоих случаях входной поток синтаксического анализатора сканируется посимвольно слева направо.

Наиболее эффективные нисходящие и восходящие методы работают только с подклассами грамматик, однако нехоторые из этих классов, такие как LL- и LR-грамматикн, достаточно выразительны для описания большинства синтаксиче­ских конструкций явыков рограммирования. Реализованные вручную синтакси­ческие анализаторы чаше работают с LL-грамматиками. Синтаксические анализаторы для большего класса LR-rpамматик обычно создаются с помощью автоматизированных инструментов.

В схеме на рис. 4 выходом синтаксического анализатора является дерева разбора потока токенов от лексического ана­лизатора. На практике имеется множество задач, которые могут сопровождать процесс разбора, такие как сбор информации о различных токенах в таблицу символов, выполнение проверки типов и других видов семантического анализа, а также генерация промежуточного кода. Все эти задачи на рис. 4.1 представлены одним блоком "Остальная часть начальной стадии". Детальнее они будут рассмотрены в последующих главах.

Дата добавления: 2015-07-12