6.3. Семантические подпрограммы для перевода в тетрады

Попытаемся провести разбор выражения a(bc), используя грамматику простого предшествования для арифметических выражений (см. пример 5.15 и рис. 5.18), и сгенерируем тетрады

, b, c, M1

, a, M1, M2

по ходу дела составляя семантические подпрограммы. Логичнее всего генерировать первую тетраду в семантической подпрограмме для правила E  ET₁. Итак, будем выполнять восходящий разбор по алгоритму Вирта–Вебера до того момента, пока не возникнет необходимость в применении этого правила. На рис. 6.9 а приводятся сентенциальные формы, порождаемые на каждом шаге (подчеркнута основа), а на рис. 6.9 б показано частичное семантическое дерево, построенное к этому моменту.

На следующем шаге ET₁ приводится к E; одновременно с этим семантическая подпрограмма должна выдать тетраду. К сожалению, мы не можем ее построить, так как текущая сентенциальная форма не содержит информации об именах операндов E и T₁. Эта информация была потеряна, когда выполнялись редукции M  b и M  c.

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

Таким образом, семантическая подпрограмма, связанная с правилом M  i будет иметь вид:

INC(m); V[m]C[i]

Напомним, что C[i] – вершина синтаксического стека из алгоритма восходящего разбора, рассмотренного в разделе 5.2.1.

Точно также как и при переводе в ПОЛИЗ здесь будут отсутствовать семантические действия, связанные с правилами TM, T₁T, ET₁ и M(E). С остальными же правилами будет связана процедура формирования тетрады с четырьмя парамет­ра­ми – PutTetrad(O, X, Y, Z), где O – операция, X и Y – операнды, а Z – результат. В качестве результата Z будут использоваться генерируемые имена M₁, M₂,  , обозначающие подвыражения. Для этих целей будет использоваться счетчик n, который вначале имеет нулевое значение. Таким образом, семантическая подпрограмма связанная с правилом E  ET₁ будет иметь вид:

INC(n); PutTetrad(‘+’, V[m–1], V[m], M_n); DEC(m); V[m]:= M_n;

Суть семантических подпрограмм такого сорта состоит в том, что генерируется тетрада, где в качестве операндов используется два верхних значения из временного стека V, изначально хранящие имена идентификаторов и значения констант, помещенных туда при редукции по правилу M  i . После формирования тетрады два верхних значения из стека V (для бинарной операции) заменяются на имя результата тетрады. Полный перечень семантических действий по переводу в тетрады, связанный с правилами грамматики арифметических выражений, представлен на рис. 6.10.