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

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

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра ТК курс лекций по дисциплине Системное программное обеспечение Тема: Синтаксические анализаторы Преподаватель: к.т.н., доцент Карамзина А.Г.

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

Основные принципы работы синтаксического анализатора Преобразование дерева разбора в дерево операций

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

Основные принципы работы синтаксического анализатора Синтаксический анализатор ( синтаксический разбор ) – это часть компилятора, которая отвечает за выявление основных синтаксических конструкций входного языка. Задачи синтаксического анализа: • найти и выделить основные синтаксические конструкции в тексте входной программы; • установить тип и проверить правильность каждой синтаксической конструкции; • представить синтаксические конструкции в виде, удобном для дальнейшей генерации текста результирующей программы.

ТЛ	Синтаксический анализатор	Дерево
синтаксического
разбора
	(дерево вывода)
Системное программное обеспечение

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

Основные принципы работы синтаксического анализатора Результатом работы распознавателя КС-грамматики входного языка является последовательность правил грамматики , примененных для построения входной цепочки. По найденной последовательности, зная тип распознавателя, можно построить цепочку вывода или дерево вывода . В этом случае дерево вывода выступает в качестве дерева синтаксического разбора и

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

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

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

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

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

Преобразование дерева разбора в дерево операций

начало
–	есть узлы помеченные	+
НетерСим?	Выбрать	крайний
ТекУз:=КрЛевНетер			левый	узел	дерева,
	помеченный
1
	нетерминальным
символом грамматики
–	текущий узел	+	и сделать его текущим
	имеет только 1
нижележащий узел?	Удалить ТекУз;		Текущий узел необходимо
удалить из дерева, а
			НижЛежУз
связанный с ним узел
	присоединить
присоединить к узлу
	к ВышЛежУз
вышележащего уровня
	ТекУз имеет
–		НижЛежУз (лист),	+
	помеченный ТерСим,
который не несет
семантическую	Удалить лист
нагрузку?

1

ТекУз имеет 1

–

НижЛежУз (лист), помеченный

+

ТерСим, обозначающим знак

операции, а остальные помечены как

–

ТекУз имеет

+

операнды?

Удалить лист;

ТекУз пометить

НижЛежУз, помеченный

НетерСим?

этим знаком

ТекУз:=КрЛев

операции

1 конец

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

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

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

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

Преобразование дерева разбора в дерево операций

S	S
T	R	T	R
E	/	T	E	/	T
a	E	a	E
(	S	)	(	S	)
T	T
E	F	E	F
b	—	E	b	—	E
a	a

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

Преобразование дерева разбора в дерево операций

S	S
E	R	a	R
a	/	T	/	T
	E	E
(	S	)	(	S	)
T	T
E	F	E	F
b	—	E	b	—	E
a	a

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

Преобразование дерева разбора в дерево операций

S	S
a	R	a	R
	/			T	/	E
E	(	S	)
(				S	)	T
T	E	F
E			F
	b	—		E	b	—	E
a			a

Источник

Дерево разбора. Преобразование дерева разбора в дерево операций

Результатом работы распознавателя КС-грамматики входного языка является последовательность правил грамматики, примененных для построения входной цепочки. По найденной последовательности, зная тип распознавателя, можно построить цепочку вывода или дерево вывода. В этом случае дерево вывода выступает в качестве дерева синтаксического разбора и представляет собой результат работы синтаксического анализатора в компиляторе.
Однако ни цепочка вывода, ни дерево синтаксического разбора не являются целью работы компилятора. Дерево вывода содержит массу избыточной информации, которая для дальнейшей работы компилятора не требуется. Эта информация включает в себя все нетерминальные символы, содержащиеся и узлах дерева, — после того как дерево построено, они не несут никакой смысловой нагрузки и не представляют для дальнейшей работы интереса.
Для полного представления о типе и структуре найденной и разобранной синтаксической конструкции входного языка в принципе достаточно знать последовательность номеров правил грамматики, примененных для ее построения. Однако форма представления этой достаточной информации может быть различной как в зависимости от реализации самого компилятора, так от фазы компиляции. Эта форма напивается внутренним представлением программы.
В синтаксическом дереве внутренние узлы (вершины) соответствуют операциям, а листья представляют собой операнды. Как правило, листья синтаксического дерена сляпаны с записями в таблице идентификаторов. Структура синтаксического дерева отражает синтаксис языка программирования, на котором наш капа исходная программа.
Синтаксические деревья могут быть построены компилятором для любой части входной программы. Не всегда синтаксическому дереву должен соответствовать фрагмент кода результирующей программы — например, возможно построение синтаксических деревьев для декларативной части языка. В этом случае операции, имеющиеся в дереве, не требуют порождения объектного кода, но несут информацию о действиях, которые должен выполнить сам компилятор над соответствующими элементами. В том случае, когда синтаксическому дереву соответствует некоторая последовательность операций, влекущая порождение фрагмента объектного кода, говорят о дереве операций.
Дерево операций можно непосредственно построить из дерева вывода, порожденного синтаксическим анализатором. Для этого достаточно исключить из дерева вывода цепочки нетерминальных символов, а также узлы, не несущие семантической нагрузки при генерации кода. Примером таких узлов могут служить различные скобки, которые меняют порядок выполнения операции и операторов, но после построения дерева никакой смысловой нагрузки не несут, гак каким не соответствует никакой объектным код.
То, какой узел в дерене является операцией, а какой — операндом, никак невозможно определить из грамматики, описывающей синтаксис входного языка. Также ниоткуда не следует, каким операциям должен соответствовать объектный код в результирующей программе, а каким — нет. Все это определяется только исходя из семантики — «смысла» — языка входной программы. Поэтому только разработчик компилятора может четко определить, как при построении дерева операции должны различаться операнды и сами операции, а также то, какие операции являются семантически незначащими для порождения объектного кода.
Алгоритм преобразования дерева семантического разбора и дерево операции можно представить следующим образом.
Шаг 1. Если в дереве больше не содержится узлов, помеченных нетерминальными символами, то выполнение алгоритма завершено; иначе — перейти к шагу 2
Шаг. 2. Выбрать крайний левый узел дерена, помеченный нетерминальным символом грамматики и сделать его текущим. Перейти к шагу 3.
Шаг 3. Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерена, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерена цепочку) и вернуться к шагу 1; иначе – перейти к шагу 4.
Шаг 4. Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе — перейти к шагу 5.
Шаг 5. Если текущий узел имеет один нижележащий узел (лист дерева), помеченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо удалить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе — перейти к шагу 6.
Шаг 6. Если среди нижележащих узлов для текущего узла есть узлы, помеченные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим умом и перейти к шагу 3: иначе — выполнение алгоритма завершено.

Источник