СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ДЛЯ ПЕРЕВОДА В ТЕТРАДЫ

Попытаемся провести разбор выражения 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.

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