Синтаксические анализаторы

АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ТК

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

(синтаксический разбор) – это часть компилятора, которая отвечает за выявление

основных синтаксических конструкций входного языка.

Задачи синтаксического анализа:

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

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

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

ТЛ

Синтаксический анализатор

Дерево
синтаксического
разбора
(дерево вывода)

распознавателя КС-грамматики входного языка является последовательность правил грамматики, примененных для

построения входной цепочки.

По найденной последовательности, зная тип распознавателя, можно построить цепочку вывода или дерево вывода.

В этом случае дерево вывода выступает в качестве дерева синтаксического разбора и представляет собой результат работы СА в компиляторе.

Все же ни цепочка вывода, ни дерево синтаксического разбора
не являются целью работы компилятора.
Дерево вывода содержит массу избыточной информации,
которая для дальнейшей работы компилятора не требуется.
Эта информация включает в себя все нетерминальные символы,
содержащиеся в узлах дерева, – после того как дерево построено,
они не несут никакой смысловой нагрузки и не представляют
для дальнейшей работы интереса.

В синтаксическом дереве внутренние узлы (вершины) соответствуют операциям, а листья представляют собой операнды.

Структура синтаксического дерева отражает синтаксис языка программирования, на котором написана исходная программа.

Как правило, листья синтаксического дерева связаны с записями в ТИ.

могут быть построены компилятором для любой части входной программы.
Не

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

В том случае, когда синтаксическому дереву соответствует некоторая последовательность операций, влекущая порождение фрагмента объектного кода, говорят о дереве операций.

Дерево операций можно непосредственно построить из дерева вывода, порожденного СА. Для этого достаточно исключить из дерева вывода цепочки нетерминальных символов, а также узлы, не несущие семантической (смысловой) нагрузки при генерации кода (различные скобки, которые меняют порядок выполнения операций и операторов, но после построения дерева никакой смысловой нагрузки не несут, так как им не соответствует никакой объектный код).

Только разработчик компилятора может
четко определить, как при построении дерева операций
должны различаться операнды и сами операции,
а также то, какие операции являются семантически
незначащими для порождения объектного кода.

дерево построено для цепочки a/(b-a) языка, задающего грамматику арифметических выражений.

Грамматика для арифметических выражений над символами a и b задана:

G({+,-,/,*,a,b,“(“, “)”},{S,R,T,F,E},P,S)
P:
S→TR⏐T
R→+T⏐-T⏐+TR⏐-TR⏐/T⏐*T
T→EF⏐E
F→*E⏐/E⏐*EF⏐/EF⏐-E⏐+E
E→ (S) ⏐a⏐b

Семантически незначащими символами в этой грамматике являются скобки (они задают порядок операций и влияют на синтаксический разбор, но результирующего кода не порождают) и пустые строки. Знаки операций заданы символами +, -, /, *, остальные символы (a и b) являются операндами.

дерево вывода и дерево операций