5.1.5. Пример использования ат-грамматики
Чтобы показать, как используются наследуемые атрибуты и как АТ-грамматики можно применять при конструировании компиляторов, рассмотрим процесс обработки описаний переменных в некотором гипотетическом языке программирования. Допустим, что описание переменных имеет вид:
int X,Y,Z
и условимся, что
после обработки пакета описания на
входном языке лексический анализатор
строит таблицу символьного представления
идентификаторов (ТС)
и таблицу переменных (ТП).
Каждый элемент таблицы переменных
состоит из двух полей. В первое поле
заносится указатель на строку ТС,
в которой хранится идентификатор
переменной, а во втором поле должен
храниться указатель на строку таблицы
значений (ТЗ),
в которой должно находиться значение
переменной. Связи между этими таблицами
показаны на следующем рисунке:
На рисунке цифрами обозначены указатели на элементы соответствующих таблиц, а пунктирными линиями показаны указатели, значения которых должны быть записаны в ТП после синтаксического анализа. В результате обработки входной строки лексический анализатор заменяет идентификаторы лексемами, каждая из которых состоит из указателя класса переменных (V) и наследуемого атрибута, представляющего собой указатель на соответствующую строку ТП, и входная строка приобретает вид:
int V/10,V/12,V/14
5.2. Cинтаксический анализ, с использованием ат-грамматики
5.2.1. Процесс синтаксического анализа
Допустим, что задачей синтаксического анализа такой цепочки является выделение каждой переменной элемента памяти в виде строки ТЗ и занесение указателя этой строки в ТП. Исходными данными для выполнения этих действий является указатель на первый свободный элемент ТЗ. После завершения обработки описаний этот указатель должен изменить значение. Новое значение должно определять первый свободный элемент ТЗ после выделения памяти для переменных.Синтаксис цепочек рассматриваемого вида может быть задан следующей грамматикой с начальным символом <D>.
<D> int V <R> <R> , V <R> <R> $
Начальному символу <D> придадим два атрибута: наследуемый атрибут /b, начальное значение которого зададим в виде указателя на первый свободный элемент ТЗ, и синтезируемый атрибут %a, значением которого должен быть указатель на новый свободный элемент ТЗ после выделения памяти для переменных.Нетерминальному символу <R>, обозначающему продолжение списка также припишем два атрибута. Один атрибут /g должен быть наследуемым. Он должен передавать значение указателя на ТЗ следующему правилу при выводе. Другой атрибут %f- синтезированный. Он должен использоваться для передачи на выход указателя на первый свободный элемент после выделения памяти переменным. Для каждой переменной в описании нужно указатель на свободный элемент ТЗ записать в соответствующее поле ТП. Допустим, что эти действия выполняет символ действия ФОРМирование Указателя (ФОРМУ), который имеет два наследуемых атрибута, первый из которых определяет положение переменной в ТП, а второй является указателем на первый свободный элемент ТЗ. В простейшем случае указатель на элемент ТЗ для следующей переменной может быть получен путем прибавления единицы к предыдущему значению. В общем случае это может быть не так, поэтому примем, что новое значение указателя ТЗ определяется специальной функцией без аргументов СЛЕДующий УКазатель (СЛЕДУК),
Учитывая сказанное выше, грамматику, задающую перевод описаний значения таблицы ТП, можно записать так:
Г 5. 1 :
D%a/b int V/c{ФОРМУ}/d/eR%f/g
!! d := C; e := b; a := f; g := СЛЕДУК;
R%h/k , V/l{ФОРМУ}/m/nR%j/p
!! m := l; n := k; h := j; p := СЛЕДУК;
R%q/r $
!! q := r;
Построим с помощью правил этой грамматики совмещенный вывод цепочкиint V/10,V/12,V/14, записывая, справа от выводимой цепочки, отложенные вычисления, а под цепочкой – получаемые значения атрибутов. В качестве начального значения наследуемого атрибута b возьмем значение 44.
Результаты вывода Отложенные вычисления
1. D%a/442. int V/10{ФОРМУ}/10/44R%f/45 d := 10; e := 44; g := 45 a = f3. int V/10,{ФОРМУ}/10/44/,V/12{ФОРМУ} /12/45R%j/46 m = 12, n = 45, p = 46; a = f; f = j;4. int V/10,{ФОРМУ}/10/44,V/12,{ФОРМУ} /12/45,V/14{ФОРМУ}/14/46R%j'/47, m' = 14, n' = 46; p' = 47 a = f; f = j; j = j'5. int V/10,{ФОРМУ}/10/44,V/12,{ФОРМУ} /12/45,V/14{ФОРМУ}/14/46 a = f; f = j; j = j'; j' = 47; a = 47
В каждой строке приведенного примера показаны результаты очередного шага вывода, которые могут содержать символы действия с найденными значениями атрибутов. Учитывая, что атрибуты правой части каждого правила являются независимыми величинами, при повторном применении второго правила грамматики для обозначения атрибутов были использованы переменные с апострофами. Приведенные примеры показывают, что результатом вывода с помощью правил атрибутной грамматики является цепочка, состоящая из символов действия и входных символов, каждому из которых приписаны значения атрибутов. Если из заданной АТ-грамматики Г удалить все атрибуты, то получим транслирующую грамматику Г', а из каждой цепочки, выведенной в грамматике Г после удаления всех атрибутов, может быть получена цепочка, выводимая в грамматике Г'. Основываясь на этом соответствии, назовем множество пар, состоящих из цепочки входных символов, снабженных атрибутами, и цепочки выходных символов, имеющих атрибуты, атрибутным переводом, определяемым заданной атрибутной грамматикой.
