3.5. Синтаксически-управляемый перевод и синтаксический анализ

Основной задачей синтаксического анализа является выявление синтакси­ческой структуры исходной программы. Как было показано ранее, одним из способов решения этой задачи является моделирование левого или правого вывода в грамматике, описывающей входной язык программирования, с помо­щью допускающего МП-автомата (МП-распознавателя). При этом МП-авто­мат моделирует, по существу, процесс построения дерева вывода. Однако собственно дерево вывода существует лишь во время функционирования МП-распознавателя в виде шагов его работы. Для получения «физического» пред­ставления дерева вывода в конструкцию и систему команд МП-распознавателя необходимо внести следующие изменения:

· снабдить его выходной лентой, на которую будет выполняться вы­дача информации о дереве вывода;

· определить дополнительные операции по построению дерева вы­вода на выходной ленте.

МП-распознаватель, снабженный выходной лентой, называют обычно МП-преобразователем. Для выдачи информации на выходную ленту МП-преобразователь использует специальную команду ВЫДАТЬ (X), где X — выводимая информация.

Структура МП-преобразователя показана на рис. 3.17.

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

Существуют различные способы линейного представления дерева вывода (основные из них будут рассмотрены), однако в любом случае для построе­ния таких представлений требуется выполнить определенные действия (опе­рации). Если эти операции ввести в систему команд МП-преобразователя, то это существенно усложнит разработку его управляющих таблиц и будут по­теряны все преимущества определения МП-автомата как абстрактного устройства по переработке информации. Но есть и другая возможность, а имен­но, возложить на МП-преобразователь не выполнение действий (операций) по построению линейного представления дерева вывода, а лишь только по­лучение такой последовательности действий (операций). И лишь после вы­полнения полученной последовательности действий с помощью другого устройства (интерпретатора), будет получено линейное представление дере­ва вывода-описание структуры программы (в данном контексте мы их будем отождествлять). При таком подходе нет необходимости вводить в систему ко­манд МП-автомата команды, реализующие построение дерева. Достаточно лишь команды ВЫДАТЬ (X), где X — операционный символ, который для МП-пре­образователя не имеет ни какого семантического смысла и является чисто син­таксической единицей. Другое преимущество такого определения — независимость описания работы МП-преобразователя от семантики опера­ционных символов, трудоемкости выполнения этих операций, способа их ре­ализации и т.д. Важен лишь их перечень и последовательность выполнения. Таким образом, в изложенной выше трактовке МП-преобразователь осуще­ствляет перевод входной цепочки в выходную цепочку операционных симво­лов, интерпретация (выполнение) которой обеспечит построение линейного представления дерева вывода. А так как перевод осуществляется с учетом синтаксиса входной цепочки, то такой перевод обычно называют синтакси­чески-управляемым переводом.

Рис. 3.17. Структура МП-преобразователя

Источником, по которому можно построить МП-преобразователь, являет­ся аппарат, получивший название синтаксически-управляемые схемы пере­вода. Воспроизведем основные формальные определения, применяемые при построении МП-преобразователя рассмотренного вида с использованием этого аппарата [4].

Определение 3.5.1. Пусть G = <N, T, P, S> — КС-грамматика и — множество операционных символов. Каждому правилу:

где Ai N, xi+1 T*, 0 i n будет соответствовать правило:

Простой синтаксически-управляемой схемой (СУ-схемой) называется пятерка D = (T, , N, R, S), где R — множество пар правил:

Обозначим пару таких правил через ( , ). Множество пар терминальных цепочек (x, y), синхронно выводимых из пары цепочек (S, S) с помощью СУ-правил ( , ), называется простым управляемым переводом (D) = (x, y), x T*, >. СУ-правила будем записывать в виде (подразумевая пару правил ( )).

Процесс синтаксического анализа также можно представить в виде СУ-перевода, в котором выходная цепочка — это последовательность номеров под­становок, используемых при левом выводе входной цепочки (нисходящий анализ), или обращенной последовательности номеров подстановок, исполь­зуемых при правом выводе (для восходящего анализа).

Пусть G = <N, Т, Р, S> — исходная КС грамматика, в которой все подста­новки из множества правил Р пронумерованы числами 1, 2, …, р. Схема СУ-перевода для синтаксического анализа определяется как четверка [4]:

где схема подстановок R включает правила вида такие, что если — подстановкой из множества P с номером i, то , где — цепочка из которой устранены все терминальные символы.

Пример 3.5.1. Схема СУ-перевода для грамматики простых арифметических выражений определяется следующим образом:

где множество R состоит из подстановок:

На рис. 3.18 изображена пара деревьев вывода, задающая перевод цепочки i*(i+i) в выходную цепочку, отвечающую левому выводу ее в исходной грамматике.

Функциональным интерпретатором схемы СУ-перевода является МП-пре­образователь. Дадим формальное определение допускающего МП-преоб­разователя.

Определение 3.5.2. Недетерминированным МП-преобразователем называ­ется восьмерка:

M = <Q, A, , Г, , q0, z0, F>,

где Q — множество состояний;

A, , Г — входной, выходной и магазинный алфавиты соответственно;

q0 Q — начальное состояние;

z0 Г — начальный символ магазинной памяти;

F Q — множество заключительных состояний;

— отображения вида : Qx >>xГ QxГ*x *. Если отображение задается в виде совокупности команд МП-преобразователя, то команды будем записывать в виде:

Интерпретируется команда обычным путем (также как и для МП-распозна­вателя), но помимо перехода автомата в состояние q’ при входном символе х и верхнем символе в магазине у и записи в магазин цепочки z*, на выходную ленту выдается операционная цепочка W*.

Процедура для построения нисходящего и восходящего МП преобразовате­лей по простой схеме СУ-перевода для синтаксического анализа определяется следующими теоремами.

Рис. 3.18. Перевод цепочки i*(i+i) СУ-схемой: а – вход СУ схемы; б – выход СУ схемы

Теорема 3.5.1. [4] Пусть G = <N, T, P, S> — КС-грамматика в нормальной форме Грейбах, в которой правила пронумерованы числами 1, 2, …, р, и М = <Q, A, , Г, , q0, z0, F> — расширенный недетерминированный МП-преобразователь, у которого:

8) (q, a, A) = (q, , i), если (A a ) P с номером i;

9) (q, b, b) = (q, , ) для всех b T и (A b ) P;

10) (q, , #) = (ДОПУСТИТЬ, , );

11) (q, x, y) = (ОТВЕРГНУТЬ, , ) для всех ситуаций, не перечисленных в п.п. 8 – 10.

Тогда недетерминированный МП-преобразователь М является функциональным интерпретатором простой схемы СУ-перевода

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

Данная теорема утверждает, что если входная цепочка символов является допустимой в грамматике G, то на выходе построенного указанным образом МП-преобразователя будет выдана последовательность номеров подстановок из множества Р, которая отвечает левому выводу входной цепочки.

Пример 3.5.2. Пусть D = <, , , S = > – простая СУ-схема перевода с правилами R:

МП-преобразователь для данной простой СУ-схемы имеет компоненты:

(q, real, S) = (q, L’, 1);

(q, x, y,) = (ОТВЕРГНУТЬ, , ).

Последовательность конфигураций МП-преобразователя при переводе цепочки real i, i следующая: