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

В модели компилятора синтаксический анализатор получает строку лексем с выхода лексического анализатора, как показано на рис. 21, и проверяет, может ли эта строка порождаться грамматикой исходного языка. Он также сообщает обо всех выявленных ошибках. Кроме того, он должен уметь обрабатывать обычно часто встречающиеся ошибки и продолжать работу с оставшейся частью программы.

Дерево

Рис. 21. Место синтаксического анализатора в модели компилятора

Имеется три основных типа синтаксических анализаторов грамматик.

1) Универсальные методы разбора, такие как алгоритмы Кока-Янгера-Касами или Эрли, могут работать с любой грамматикой. Однако эти методы слишком неэффективны для использования в промышленных компиляторах.

2) Нисходящие (сверху вниз) методы синтаксического анализа. Нисходящие синтаксические анализаторы строят дерево разбора сверху (от корня) вниз (к листьям). Входной по­ток синтаксического анализатора сканируется посимвольно слева направо.

3) Восходящие (снизу вверх) методы синтаксического анализа. Восходящие методы начинают построение дерева разбора с листьев и идут к корню. Входной по­ток также сканируется посимвольно слева направо.

Восходящие и нисходящие методы синтаксического анализа наиболее распространены в компиляторах.

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

Выходом синтаксического анализатора является некоторое представление дерева разбора входного потока лексем, выданного лексическим анализатором. На практике имеется множество задач, которые могут сопровождать процесс разбора, - например, сбор информации о различных лексемах в таблице символов, исполнение проверки типов и других видов семантического анализа, а также создание промежуточного кода.

Дата добавления: 2014-12-27