Основы конструирования компиляторов

         

Элементы теории перевода


До сих пор мы рассматривали процесс синтаксического анализа только как процесс анализа допустимости входной цепочки. Однако, в компиляторе синтаксический анализ служит основой еще одного важного шага - построения дерева синтаксического анализа. В примерах 4.3 и 4.8 предыдущей главы в процессе синтаксического анализа в качестве выхода выдавалась последовательность примененных правил, на основе которой и может быть построено дерево. Построение

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

Определение. Пусть T - входной алфавит, а

- выходной алфавит. Переводом (или трансляцией) с языка L1

T*

на язык L2

*

называется отображение

: L1
L2. Если y =
(x), то цепочка y называется выходом для цепочки x.

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

управляемого перевода и атрибутные грамматики.



Содержание раздела