Теория и реализация языков программирования
Обсуждение
Идея определения семантики с помощью синтезированных атрибутов, связанных с каждым нетерминальным символом и семантических правил, сопоставленных каждому правилу вывода, принадлежит Айронсу [6, 7]. Первоначально каждый нетерминальный символ имел ровно один атрибут, называвшийся его "трансляцией" . Эта идея использовалась Айронсом и позже другими авторами, особенно Маклюром [14] при построении "синтаксически управляемых компиляторов" , переводивших языки программирования в машинный код.
Как мы видели в разд. 2, синтезированных атрибутов достаточно (в принципе) для определения любой функции на дереве вывода. Но на практике применение наряду с синтезированными и унаследованных атрибутов, как описано в данной статье, приводит к значительным упрощениям. Определение Тьюрингола, например, показывает, что легко учитывается согласованность описаний и использований символов, а также между метками и операторами. Другой общей особенностью языков программирования, определение которой значительно упрощается в результате применения унаследованных атрибутов, является "блочная структура" . Вообще говоря, унаследованные атрибуты полезны всякий раз, когда часть значений некоторой конструкции определяется контекстом, в котором находится эта конструкция. Метод, приведeнный а разд. 2, показывает, как можно формально описывать унаследованные и синтезированные атрибуты, а в разд. 3 показано, что можно не принимать во внимание проблему зацикленности (являющуюся потенциальным источником трудностей при использовании атрибутов разных типов).
Автору к настоящему времени известно несколько работ, внесших принципиальный вклад в решение задачи формального описания семантики языков программирования. Это определение Алгола 60 средствами расширенного алгоритма Маркова, данное Дебаккером [1], определение Алгола 60 с помощью ?-исчисления, принадлежащее Ландину [9, 10, 11] (см. также Бeм [2, 3], определение Микро-Алгола с помощью рекурсивных функций, применяемых к программе и к _векторам состоянийї, принадлежащее Маккарти [12] (см.
также Маккарти и Пэинтер [13]; определение языка Эйлер средствами семантических правил, применяемых во время синтаксического анализа программы, предложенное Виртом и Вебером [16], и определение языка PL=I, данное Венской лабораторией фирмы IBM и основанное на работе Маккарти и Ландина, а также на понятии абстрактной машины, введ_нном Элготом [4, 5]. Наиболее существенная разница между предшествующими методами и описанием языка Тьюрингол, привед_нным в таблица 1, состоит в том, что остальные
определения представляют собой довольно сложные процессы, применяемые ко всей программе; можно сказать, что человек, прежде чем он поймeт описание языка, должен будет понять, как устроен его компилятор. Эта трудность особенно ощутима в работе Дебаккера, определяющего машину, подобную Марковским алгоритмам, но значительно более сложную. Эта машина имеет около 800 команд. На каждом шаге вычисления машины нужно выполнять последнюю применимую команду, так что мы не можем проверить, нужно ли выполнить команду номер 100, до тех пор, пока не убедимся, что остальные 700 команд неприменимы. Кроме того, в процессе работы машины список пополняется новыми командами. Ясно, что читателю чрезвычайно трудно понять работу такой машины или формально доказать ee основные свойства. Описание Тьюрингола, напротив, определяет каждую конструкцию языка только через еe "непосредственное окружение" , сводя тем самым к минимуму взаимосвязи между определениями разных частей языка. Определение составных операторов, операторов перехода и т.д. не влияет существенно на определение оператора печати; например, любое из правил 4.1, 4.2, 4.3, 4.4, 5.1, 5.3 можно выбросить, и получится строгое определение другого языка. Такая локализация и разделение семантических
правил помогает сделать определение более понятным и кратким. Хотя определения остальных авторов, упомянутые выше, не так сложны, как определение Дебаккера, в их работах всe-таки присутствуют относительно сложные зависимости между отдельными частями определения.
Рассмотрим, например, формальное определение языка Эйлер, данное Виртом и Вебером [16]. Это краткое описание весьма сложного языка и потому, безусловно, оно является одним из наиболее удачных формальных определений. И всe же, несмотря на то, что Вирт и Вебер проверили своe определение с помощью моделирования на вычислительной машине, весьма вероятно, что некоторые черты Эйлера удивят его создателей. Следующая программа на Эйлере синтаксически и семантически правильна, хотя после метки L нигде не встречаются двоеточия:
Результатом работы этой программы будет 1, 2, 2, 3! Промахи такого рода не являются неожиданностью при алгоритмическом определении языка. При использовании методов разд. 4 подобные ошибки менее вероятны.
Есть основания утверждать, что ни одна из предыдущих схем (формального определения семантики) не в состоянии дать такого же краткого и простого для понимания определения Тьюрингола, как то, которое представлено выше. Кроме того (хотя детали окончательно не проработаны), оказывается, что Алгол 60, Эйлер, Микро- Алгол и PL=1 также можно определить методами разд. 4, причeм все преимущества по сравнению с остальными методами сохраняются. Правда, здесь автор не может быть беспристрастным судьeй, поэтому для подтверждения такой точки зрения требуется некоторый дополнительный опыт.
Отметим, что семантические правила в том виде, в котором они даны в настоящей статье, не зависят от конкретно выбранного метода синтаксического анализа. На самом деле они привязаны даже к конкретным формам синтаксиса. Единственное от чего зависят семантические правила - это имя нетерминала в левой части синтаксического правила и имени нетерминалов в правой его части. Конкретные знаки пунктуации и порядок, в котором нетерминалы располагаются в правых частях правил, несущественны с точки зрения семантических правил. Таким образом, рассматриваемое здесь определение семантики хорошо сочетается с идеей Маккарти об "абстрактном синтаксисе" [12, 13].
Когда синтаксис неоднозначен в том смысле, что некоторые цепочки языка имеют более одного дерева вывода, семантические правила дают для каждого дерева вывода своe "значение" .
Предположим, например, что к грамматике (1.3) добавлены правила
Грамматика в результате становится синтаксически неоднозначной, но остаeтся по-прежнему семантически однозначной, поскольку атрибут v(N) имеет одно и то же значение для всех деревьев вывода. С другой стороны, если изменить правило 5.2 определения Тьюрингола с S
