4.3.4. Выполнение семантических действий

В синтаксически управляемых трансляторах выполнение семантических процедур, перевод исходного текста всегда совмещен с процессом синтаксического анализа. Распознавание отдельного элемента или языковой конструкции влекло вызов подпрограмм и выполнение семантических действий. Это и привело к тому, что на практике возвратные алгоритмы анализа не нашли применения. Пройдя часть пути по одной из альтернатив той или иной продукции грамматики, и обнаружив расхождение, мы можем достаточно просто вернуться по пройденному тексту, и рассмотреть еще одну альтернативу. Но как аннулировать результаты семантических подпрограмм, которые уже были выполнены? Это принципиальное возражение теоретиков против возвратных алгоритмов трансляции. В рассматриваемом СП эта проблема достаточно просто решается введением еще одного просмотра – выполнения семантических действий, который осуществляется уже после корректного завершения синтаксического анализа. Это снижает эффективность проектируемого транслятора, увеличивает время трансляции, но это дает возможность рассматривать любые, в том числе и недетерминированные КС-языки, что зачастую и необходимо в учебных целях.

Файл семантических действий, формируемый в процессе синтаксического анализа, содержит протокол вызова процедур, реализующих семантические действия, и аргументы, с которыми они будут вызываться. В качестве аргумента семантической процедуры выступает последняя лексема исходного текста, сопоставленная с конструкцией грамматики непосредственно перед тем, как при грамматическом разборе в правой части продукции было встречено изображение оператора вызова данного семантического действия. Например, в результате успешного сопоставления продукций:

A  @_IDN_@ (_2_) 

или

A  <_B_> (_2_) 

B  @_IDN_@ 

семантическая процедура с кодом 2 будет вызываться с параметром-лексемой “идентификатор”, отождествлённым с синтермом IDN.

Если в грамматике несколько ссылок на семантические процедуры стоят подряд, то эти процедуры будут вызываться с одним и тем же аргументом.

Например, для случая:

A ::= ... @_INT_@ (_1_)(_3_)(_5_) 

семантические процедуры 1, 3, 5 будут вызываться с аргументом-лексемой “целое число”, отождествлённым с синтермом INT.

Семантика языков программирования – это тот раздел трансляции, который с очень большим трудом поддается формализации. Все известные автору попытки включения формального описания семантики в спецификацию языка не находят распространения. Формальное описание семантики слишком тяжеловесно и так называемые атрибутные или транслирующие грамматики чаще всего понятны только их составителям. В рассматриваемой системе написание набора семантических процедур возлагается на разработчика транслятора для конкретного языка.

В заключение раздела поясним принципы расстановки семантических атрибутов (номеров процедур) в спецификации языка для рассматриваемого СП на примере грамматики арифметических выражений:

Выражение ::= [_ <_ OTC _> (_0_) _] (_1_) <_ TEPM _> (_3_)

{_ <_ OTC _> (_2_) <_ TEPM _> (_3_) _} 

TEPM ::= <_ множитель _>

{_ <_ OTM _> (_2_) <_ множитель _> (_3_) _} 

множитель ::= ?_ ( <_ Выражение _> ) _|_ @_ IDN _@ (_4_) _|_

@_ REL _@ (_4_) _|_ @_ INT _@ (_4_) _? 

OTC ::= ?_ + _|_ - _? 

OTM ::= ?_  _|_ / _? 

Здесь семантические действия призваны перевести заданное арифметическое выражение в ПОЛИЗ:

0 - Отметить наличие унарного минуса.

1 - Если был унарный минус, поместить его обозначение – символ ‘@’ в семантический стек и сбросить признак минуса, установленный действием 0-ой процедуры. В противном случае поместить в семантический стек символ ‘n’;

2 - Поместить символ операции (, , ,  ) в семантический стек;

3 - Выгрузить символ из семантического стека и, если он отличен от ‘n’, поместить его в выходную строку;

4 - Поместить идентификатор или константу в выходную строку.

Упражнения на программирование.

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

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

4.3. Реализовать алгоритм нисходящего разбора с возвратами. Программа должна для заданной КС-грамматики и входной цепочки визуализировать шаги нисходящего разбора и построение дерева разбора.

4.4. Реализовать алгоритм восходящего разбора с возвратами. Программа должна для заданной КС-грамматики и входной цепочки визуализировать шаги восходящего разбора и построение дерева разбора.