- а) Устранение левой рекурсии
- б) Проектирование детерминированного транслятора
- а) Устранение левой рекурсии (из схемы трансляции)
Поскольку большинство арифметических операторов левоассоциативны, естественно использовать для выражений леворекурсивные грамматики.
Схема трансляции, представленная на рис. 1, преобразуется в схему (рис. 2), ко-торая порождает для выражения 9−5+2 аннотированное дерево разбора, показанное на рис. 3. Стрелки на рисунке указывают путь определения значения выражения.
Рис. 3 — Вычисление выражения 9−5+2
E > E1 — T { E. val := E1.val — T. val }
E > T{ E. val := T. val }
T > num { T. val := num. lexval }
E > T { R. i := T. val }
R { E. val := R. s }
R > ;
T { R1.i := R. i — T. val }
R1 { R. s := R1.s }
R > е { R. s := R. i }
T > num { T. val := num. val }
Наследуемый атрибут символа должен вычисляться действием, находящимся перед символом, а синтезируемый атрибут нетерминала в левой части — после вычисления всех атрибутов, от которых он зависит.
A > A1 Y { A. a := g (A1.a, Y. y) } (01).
A > X { A. a := f (X.x) }
Каждый грамматический символ имеет синтезируемые атрибуты, записанные с использованием соответствующих строчных букв, а f и g — произвольные функции. Устранив левую рекурсию получим грамматику:
A > X R (02).
R > Y R.
| е.
С учетом семантических действий запишем преобразованную схему в виде.
A > X { R. i := f (X.x) }
R { A. a := R. s }
R > Y { R1.i := g (R.i, Y. y) } (03).
R1 { R. s := R. i }
R > е { R. s := R. i }
E > T { R. i := T. nptr }
R { E. nptr := R. s }
R > + T { R1.i := mknode (`+', R. i, T. nptr)}
R1 { R. s := R. i }
R > - T { R1.i := mknode (`-', R. i, T. nptr)}
R1 { R. s := R. i }
R > е { R. s := R. i }
T > (E) { F.nptr := E. nptr }
T > id { mkid (id.entry)}
T > num { T. nptr := mknum (num.value)}
Рис. 5 Преобразованная схема трансляции для построения синтаксических деревьев
На рис. 6 показано, каким образом действия на рис. 5 строят синтаксическое дерево для выражения а-4+с. Синтезируемые атрибуты представлены справа от узлов грамматических символов, а наследуемые — слева. Листья синтаксического дерева создаются с помощью действий, связанных с продукциями Т > id и T > num. У крайнего слева T атрибут T. nptr указывает на лист для а. Указатель на узел для, а наследуется как атрибут R. i в правой части Е > Т R.
При применении продукции R > -TR1 к правому потомку корня, R. i указывает на узел для a, a T. nptr— на узел для 4. Узел для а-4 строится путем вызова функции mknode для оператора «-» и этих указателей.
И наконец, при использовании продукции R > е атрибут R. i указывает на корень синтаксического дерева в целом. Все дерево целиком возвращается как значение E. nptr, вычисляемое с помощью (не показанных на рис. 6) атрибутов s узлов для R.
