6.2. Семантические подпрограммы перевода инфиксной записи в полиз и аспекты их реализации
Идею постановки соответствия семантических программ каждому правилу грамматики мы рассмотрим на примере грамматики арифметических выражений и семантических действий по переводу инфиксной записи в польскую. Мы предполагаем, что всякий раз, когда в сентенциальной форме найдена основа и ее можно привести к нетерминалу U, синтаксический распознаватель вызывает семантическую подпрограмму, связанную с правилом U . Подпрограмма осуществляет семантическую обработку символов в и выдает ту часть ПОЛИЗа, которая имеет отношение к . Здесь нам совершенно безразлично, какой восходящий распознаватель используется в данный момент. Важно помнить, что разбор канонический и если в основе встречается нетерминал V, то часть польской цепочки связанной с редукцией к V уже была сгенерирована.
Будем предполагать, что генерируемая строка ПОЛИЗа хранится в одномерном массиве P, а целая переменная p (вначале она имеет значение 1 или 0) содержит индекс, указывающий на первый свободный элемент массива P. Каждый элемент массива P может содержать один символ (идентификатор, константу или оператор). Предположим также, что семантические подпрограммы имеют доступ к символам основы C0 …Ci, находящимся в синтаксическом стеке C, который используется распознавателем (см., например, раздел 5.2.1).
Дальнейшие рассуждения будем строить, используя грамматику простого предшествования арифметических выражений из примера 5.15, для которой матрица предшествования представлена на рис. 5.18.
Рассмотрим семантическую подпрограмму, связанную с правилом Е1 E2 T. Если она вызвана, то мы можем считать, что польская запись для E2 и T уже получена. При этом массив P содержит
… код для E2 код для T
поскольку E2 расположено левее T. Правее T код еще не генерировался и справа от T в исходной программе расположены только терминалы, так как мы имеем дело с каноническим разбором слева направо. Следовательно, все, что требуется от данной семантической программы, – это занести в ПОЛИЗ знак “”. В результате инфиксная запись E2 T преобразуется в польскую запись E2 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 E1 , что делает грамматику арифметических выражений G пополненной грамматикой, полученной из G. Это новое начальное правило добавляется для того, чтобы связанная с ним свертка сигнализировала анализатору о завершении разбора и допуске цепочки.
Одну и ту же семантическую подпрограмму можно использовать для нескольких правил, схожих по смыслу. Так например, для правил 2, 3, 7 и 8 семантические действия можно заменить на один единственный фрагмент:
P p C i 1; INCp
где C i 1 – элемент синтаксического стека.
Вообще говоря, с каждым нетерминалом может быть связано несколько семантических атрибутов. Однако заметим, что после редукции с применением какого либо правила, например, E1 E2 T, вся информация, связанная с E2 и T становится не нужной. Обычно нужна только та семантическая информация, которая связана с нетерминалами, входящими в текущую сентенциальную форму. Идеальным местом размещения текущей сентенциальной формы в восходящих алгоритмах разбора является стек. Параллельно с синтаксическим стеком C могут работать несколько семантических стеков C1, C2, … (см. рис. 6.7), и семантические подпрограммы должны иметь доступ к каждому из них.
Если, например, C[i] содержит символ E, то C1[i], C2[i], … могут содержать тип выражения E, адрес результата выражения во время выполнения откомпилированной программы и т. д. На практике обычно вся эта информация храниться в одном стеке, каждый элемент которого представляет собой запись с отдельными полями для хранения синтаксического символа и его семантических атрибутов.
Каждую семантическую подпрограмму можно оформить в виде отдельной процедуры, но тогда синтаксический анализатор должен знать имя, а точнее адрес каждой процедуры, что ведет ко многим технологическим проблемам. Проще перенумеровать правила грамматики и написать одну–единственную процедуру, скажем SEMANTICS, при вызове которой номер правила передается в качестве аргумента. Когда синтаксический анализатор обращается к процедуре SEMANTICS, в качестве параметра выступает номер правила, определяющего редукцию. На рисунке 6.8 это иллюстрируется фрагментом программы на языке Паскаль, которая генерирует польскую инверсную запись для арифметического выражения в соответствии с семантическими подпрограммами с рисунка 6.6.
Стеки и строка ПОЛИЗа выступают здесь в роли глобальных переменных. В других языках программирования, где конструкция CASE отсутствует, для реализации этой процедуры можно использовать переключатель или вычислимое GO TO.