4.3.6. Порядок построения детерминированного магазинного преобразователя.

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

1. Построить грамматику, описывающую цепочки входного языка.

2. Проверить принадлежность этой грамматики классу LL(1)- грамматик. Если условия LL(1) - грамматики не выполняются, то попытаться выполнить преобразование или вернуться к п.1 и построить другую грамматику.

3. Построить простую СУ-схему, используя построенную грамматику в качестве входной грамматики СУ - схемы.

4. Построить транслирующую грамматику для полученной СУ -схемы.

5. Используя правила построения, найти команды преобразования для разных групп правил транслирующей грамматики.

6. Убедиться, что построенный преобразователь реализует заданный перевод, выполняя несколько примеров построения выходных цепочек с помощью команд преобразователя.

5. Атрибутные транслирующие грамматики

5.1. Атрибутные транслирующие грамматики.

5.1.1. Атрибутные транслирующие грамматики.

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

Для задания семантики применяются различные приемы: W -грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики (АТ-грамматики).

Рассматриваемые в настоящем разделе АТ-грамматики отличаются от транслирующих грамматик тем, что символам грамматики приписываются атрибуты, отражающие семантическую информацию, а правилам грамматики сопоставляются правила вычисления значений атрибутов. Чтобы пояснить назначение атрибутов, приведем несколько примеров. Если входной язык предусматривает использование констант C, то в качестве атрибута константы можно взять ее значение. Условимся записывать значение константы за ее обозначением с разделителем в виде косой черты, например, C/5. Если в Т-грамматике используются операционные символы {сложить}, то в качестве атрибутов таких  символов можно взять значения операндов и результата. Обозначая атрибуты символами x, y, z, операционный символ с атрибутами запишем в виде {сложить}/x/y/z.

5.1.2. Определение ат-грамматик

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

Определение.  Транслирующую грамматику называют атрибутной грамматикой или АТ-грамматикой если: 1. Символам грамматики приписаны один или несколько атрибутов и для каждого атрибута определено множество допустимых значений.2. Атрибуты могут быть наследуемыми и синтезируемыми.3. Для каждого правила грамматики должны быть заданы правила вычисления атрибутов в виде оператора присваивания с функцией в правой части, определяющей значение атрибута, расположенного слева. Такие функции для вычисления атрибутов могут зависеть от атрибутов правой или левой частей рассматриваемого правила.4. Для наследуемых атрибутов начального символа должны быть заданы начальные значения.5.Функции, вычисляющие значения синтезируемых атрибутов символов действия, должны зависеть от других атрибутов этого символа.