Тетрады и триады

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

<оператор>, <операнд ₁>, < операнд ₂>, <результат>

где <операнд ₁> и <операнд ₂> специфицируют аргументы, а <результат> – результат выполнения оператора над аргументами. Таким образом, A*B мы могли бы представить, как

*, A, B, M

где M – некоторая временная переменная, которой присваивается результат вычисления A*B. Аналогично A*B+C*D представляется в виде следующей последовательности тетрад:

*, A, B, M1

*, C, D, M2

+, M1, M2, M3

Важно отметить, что в отличии от обычной инфиксной записи тетрады располагаются в том порядке, в котором они должны выполняться. Унарные операторы также оформляются в виде тетрад, но <операнд ₂> остается в них пустым. Так, вместо -A появится тетрада “ -, A,, M ”, что означает “присвоить M значение -A ”. Унарный минус, также как и в ПОЛИЗе, мы могли бы заменить другим символом (кодом), чтобы отличать его от бинарного.

Кроме традиционной арифметики в виде тетрад можно представить и любой другой оператор, имевший место в польской записи. Оператор присваивания A:=B представим в виде тетрады “ :=, B,, A ”, а оператор УПЛ запишется в виде тетрады “ УПЛ, <выр>, <m>, ”, где <m> – номер тетрады, на которую будет осуществляться переход, если значение логического выражения (<выр>) – равно нулю (ложно).

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

<оператор> <операнд ₁>, < операнд ₂>

В триаде нет поля для результата. Если позднее какой–либо операнд окажется результатом данной операции, то он будет непосредственно на нее ссылаться (на операцию, а точнее соответствующую триаду). Например, выражение A+B*C будет представлено следующим образом:

(1) * B, C

(2) + A, (1)

Здесь (1) – ссылка на результат первой триады, а не константа, равная 1. Выражение 1+B*C будет записываться так:

(1) * B, C

(2) + 1, (1)

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

Достоинства использования тетрад и триад с точки зрения машинно–независимой оптимизации по сравнению с ПОЛИЗом очевидны. Представляя их в виде таблицы (односвязного или двухсвязного списка), тетрады или триады можно легко переставлять или удалять “лишние”.

6.2. СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ПЕРЕВОДА ИН­ФИКС­НОЙ ЗАПИСИ В ПОЛИЗ И АСПЕКТЫ ИХ РЕАЛИЗАЦИИ

Идею постановки соответствия семантических программ каждому правилу грамматики мы рассмотрим на примере грамматики арифметических выражений и семантических действий по переводу инфиксной записи в польскую. Мы предполагаем, что всякий раз, когда в сентенциальной форме w найдена основа a и ее можно привести к нетерминалу U, синтаксический распознаватель вызывает семантическую подпрограмму, связанную с правилом U ® a. Подпрограмма осуществляет семантическую обработку символов в a и выдает ту часть ПОЛИЗа, которая имеет отношение к a. Здесь нам совершенно безразлично, какой восходящий распознаватель используется в данный момент. Важно помнить, что разбор канонический и если в основе a встречается нетерминал V, то часть польской цепочки связанной с редукцией к V уже была сгенерирована.

Будем предполагать, что генерируемая строка ПОЛИЗа хранится в одномерном массиве P, а целая переменная p (вначале она имеет значение 1 или 0) содержит индекс, указывающий на первый свободный элемент массива P. Каждый элемент массива P может содержать один символ (идентификатор, константу или оператор). Предположим также, что семантические подпрограммы имеют доступ к символам основы C[0] …C[i], находящимся в синтаксическом стеке C, который используется распознавателем (см., например, раздел 5.2.1).

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

Рассмотрим семантическую подпрограмму, связанную с правилом Е₁ ® E₂ + T. Если она вызвана, то мы можем считать, что польская запись для E₂ и T уже получена. При этом массив P содержит

… <код для E₂>< код для T>

поскольку E₂ расположено левее T. Правее T код еще не генерировался и справа от T в исходной программе расположены только терминалы, так как мы имеем дело с каноническим разбором слева направо. Следовательно, все, что требуется от данной семантической программы, – это занести в ПОЛИЗ знак “ + ”. В результате инфиксная запись E₂ + T преобразуется в польскую запись E₂ T +. Схематично такую семантическую программу (а точнее семантические действия) можно представить в виде:

P [ p ]:= ‘ + ’; INC(p).

Семантическая подпрограмма для правила M ® i, где под i понимается произвольный идентификатор (или константа), также предельно проста. В соответствии с правилами польской записи (см. раздел 6.1.1) идентификаторы и константы предшествуют своим операторам; более того, они встречаются в том же порядке, что и в исходной инфиксной записи. Все что необходимо сделать, – это занести идентификатор (константу) в массив P. Семантическая программа при этом имеет вид:

P [ p ]:= C [ i ]; INC (p)

где C[i] – верхний символ стека.

Семантическая подпрограмма, связанная с правилом M ® (E) вообще пуста (не делает ничего), так как скобок в ПОЛИЗе нет, а для E польская запись уже сгенерирована.

Совершенно аналогично строятся и остальные семантические подпрограммы, которые представлены на рис. 6.6 вместе с правилами грамматики простого предшествования для арифметических выражений. Грамматика из примера 5.15 дополнена правилом S ® E₁, что делает грамматику арифметических выражений G пополненной грамматикой, полученной из G. Это новое начальное правило добавляется для того, чтобы связанная с ним свертка сигнализировала анализатору о завершении разбора и допуске цепочки.

Одну и ту же семантическую подпрограмму можно использовать для нескольких правил, схожих по смыслу. Так например, для правил 2, 3, 7 и 8 семантические действия можно заменить на один единственный фрагмент:

P [p]:= C [i -1]; INC(p)

где C [i -1] – элемент синтаксического стека.

Вообще говоря, с каждым нетерминалом может быть связано несколько семантических атрибутов. Однако заметим, что после редукции с применением какого либо правила, например, E₁ ® E₂ + T, вся информация, связанная с E₂ и T становится не нужной. Обычно нужна только та семантическая информация, которая связана с нетерминалами, входящими в текущую сентенциальную форму. Идеальным местом размещения текущей сентенциальной формы в восходящих алгоритмах разбора является стек. Параллельно с синтаксическим стеком C могут работать несколько семантических стеков C1, C2, … (см. рис. 6.7), и семантические подпрограммы должны иметь доступ к каждому из них.

Если, например, C[i] содержит символ E, то C1[i], C2[i], … могут содержать тип выражения E, адрес результата выражения во время выполнения откомпилированной программы и т. д. На практике обычно вся эта информация храниться в одном стеке, каждый элемент которого представляет собой запись с отдельными полями для хранения синтаксического символа и его семантических атрибутов.

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

Стеки и строка ПОЛИЗа выступают здесь в роли глобальных переменных. В других языках программирования, где конструкция CASE отсутствует, для реализации этой процедуры можно использовать переключатель или вычислимое GO TO.

Поиск по сайту: