Дерево синтаксического разбора

Рассмотрим примеры применения дерева при решении некоторых реальных задач.

Они могут использоваться для представления таких конструкций реального
мира, например, как предложения естественного языка или математические
выражения (см. рис. 1).

а)	б)
Рисунок 1 – Применение дерева при решении реальных задач: а) дерево синтаксического разбора простого предложения; б) дерево синтаксического разбора выражения ((7+3)∗(5−2))

Дерево синтаксического разбора – результат синтаксического анализа, т.е. результат процесса сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой.

Синтаксический анализатор – это программа или часть программы, выполняющая синтаксический анализ.

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

Рисунок 2 – Преобразование исходных данных в древовидную структуру данных

Разбор арифметического выражения

Как транслятор (программа-переводчик, которая преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд) обрабатывает и выполняет арифметические и логические выражения, которые он встречает в программе?

Один из вариантов – представить это выражение в виде двоичного дерева.

Например, выражению (a + b) / (c - d + 1) соответствует двоичное дерево разбора, показанное на рисунке 3.

Рисунок 3 – Двоичное дерево разбора выражения (a + b) / (c - d + 1)

Формы записи выражений

 

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

Префиксная форма записи

 

Прямое прохождение дерева (корень – левое поддерево – правое поддерево) дает

то есть знак операции (корень) предшествует своим операндам. Такая форма записи арифметических выражений называется префиксной.

Инфиксная форма записи

 

Симметричный обход (левое поддерево – корень – правое поддерево) дает запись вида

,

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

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

Постфиксная форма записи

 

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

В такой записи знак операции стоит после обоих операндов: