Контекстные условия

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

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

Разработчику транслятора необходимо иметь ориентированное на реализацию описание входного языка, которое он получает либо готовым, либо разрабатывает сам. В таком описании должны учитываться характеристики «абстрактной машины» - интерпретатора объектной программы. Однако, с другой стороны, объектный язык, как язык промежуточных форм, семантически эквивалентных программ входного языка, должен быть ориентирован на синтаксис и учитывать семантику входного языка. Хорошее согласование описания входного языка и выбор объектного языка определяет сложность описания входного языка и простоту реализации блока семантического анализа и синтеза в трансляторе. Аппарат атрибутных трансляционных грамматик позволяет описать входной язык с учетом перечисленных требований. Семантика входного языка в этом методе определяется только контекстными условиями, причем удобно выражать эти условия через соотношения атрибутов, которые называются контекстными.

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

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

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

2. Условие соответствия между определяющими и использующими вхождениями идентификаторов. Идентификатор имеет определяющее вхождение в некоторую конструкцию, если последняя описывает его, и использующее вхождение, если конструкция не описывает его. Например, идентификатор метки конечного оператора имеет определяющее вхождение, а идентификатор в операторе перехода goto – использующее. Идентификаторы переменных, входящих в некоторое выражение, или оператор присваивания имеют также использующее вхождение. Условие соответствия выполняется, если для использующего вхождения найдено определяющее вхождение идентификатора. Алгоритмы, проверяющие это условие, называются алгоритмами идентификации. В случае блочной структуры программ действия алгоритма идентификации заключается в папке определяющего вхождения идентификатора в минимальном блоке, содержащем использующие вхождения. В случае неудачи поиск выполняется в минимальном блоке, охватывающем рассмотренный и т.д. если в программе не найдено определяющее вхождение, то условие считается не выполненным, если в языке не используется правило определения идентификаторов по умолчанию.

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

3. Условия соответствия видов значений. Например, операндами в арифметических выражений могут быть только числовые константы, идентификаторы арифметических переменных, указатели арифметических функций, не допускается смешивать различные арифметические виды значений (real, integer). При переводе операторов процедур или указателей процедур-функций проверяется соответствие видов значений фактических и формальных параметров, а также их количественное равенство. Однако при переводе операторов внешних процедур проверка таких условий невозможна, из-за отсутствия описания процедуры; поэтому она может осуществляться во время интерпретации объектной программы.

4. Условия, определяющие количественные ограничения. Эти условия связаны с ограничениями, накладываемыми конкретной разработкой транслятора для входного языка (параметр, ограниченное число формальных параметров, ограниченная глубина вложенности блоков и т.д.)

Из всего сказанного о семантике, в частности о контекстных условиях входного языка, вытекают следующие правила для проектирования с помощью АТ – грамматик формального описания этого языка, а значит схемы его перевода в объектный язык:

а. Атрибуты, как переменные, служат для запоминания семантической информаций об объектах программы, определяемых синтаксическими структурами, выраженными в виде поддеревьев дерева вывода это программы;

б. Атрибуты должны нести информацию, необходимую для построения фрагментов объектной программы, семантически адекватных синтаксическими поддеревьями;

в. Контекстные условия должны выражаться через некоторые соотношения для атрибутов;

г. Семантические правила предназначаются для проверки контекстных соотношений и вычисления значений атрибутов, в том числе значения специального атрибута <объектная программа>, которое вместо со значениями других атрибутов, удовлетворяющими контекстным соотношениям, будет определять смысл исходной программы;

д. Семантические правила реализуются интерпретированными операционными символами как семантическими процедурами с атрибутами в качестве аргументов;

е. Нетерминалы необходимо интерпретировать, как вызовы рекурсивных процедур, реализующих специальные семантические правила, вычисляющие неявно специальный атрибут <объектная программа>. Очевидно, что аксиома грамматики входного языка <программа> вычисляется окончательное значение атрибута <объектная программа>;

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

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