5.3.2. Форма простого присваивания АТ-грамматик
Вторым видом ограничений, накладываемых на АТ-грамматики, предназначенные для построения преобразователей, является запрещение использования в правилах вычисления атрибутов нетерминальных символов и некоторых атрибутов символов действия функциональных зависимостей. При выполнении этого запрета правила вычисления атрибутов должны иметь форму операторов присваивания с переменными в правой части. Грамматика с такими правилами называется АТ-грамматикой простого присваивания.
Чтобы сократить
число правил вычисления атрибутов, в таких грамматиках разрешается использовать
правила не только в виде простых операторов присваивания
Определение.
Множество копирующих правил
называется независимым тогда и только
тогда, когда источник каждого правила из этого множества не входит ни в
одно из других правил этого множества.
|
Определение.
АТ-грамматика имеет форму простого присваивания, если выполняются следующие условия: а) все правила вычисления атрибутов, за исключением правила вычисления синтезируемых символов действия, являются копирующими, б) для каждого правила грамматики
множество копирующих правил является независимым.
|
Утверждение:
|
Такое построение связано с исключением некопирующих правил вычисления атрибутов и добавлением вместо них операционных символов в правила грамматики.
Прежде чем описать
последовательность преобразования некопирующих правил, рассмотрим пример,
иллюстрирующий как такое преобразование выполняется. Допустим, что задано
некопирующее атрибутное правило в виде:
Затем включим новый символ действия в правило грамматики и заменим некопирующее правило вычисления атрибута с функцией f в правой части несколькими копирующими правилами, устанавливающими связь между атрибутами нового символа действия и аргументами
функции f.
После выполнения перечисленных действий может быть получено следующее атрибутное
правило:
Необходимо подчеркнуть,
что место включения нового нетерминального символа в правило грамматики
должно выбираться с таким расчетом, чтобы не нарушить свойств L
- атрибутности заданной грамматики. Если в рассматриваемом
примере поместить новый символ действия перед нетерминалом <B>,
то получим правило
Если же поместить
новый символ действия после символа <C>,
то получим правило
В общем случае в правиле может оказаться несколько позиций, пригодных для размещения нового символа действия. Если это так, то предпочтение следует отдать самой левой из возможных позиций, поскольку в некоторых случаях самые левые символы действия не нужно заносить в магазин преобразователя, производящего обработку.
Если же оказывается, что все позиции, в которых может быть расположен новый символ действия, являются непригодными и приводят к нарушению свойств L - атрибутности, то преобразовать такую грамматику невозможно.