Теория и реализация языков программирования



         

Проверка на зацикленность


Рассмотрим теперь алгоритм, проверяющий, является ли корректной система семантических правил, определeнная в предыдущем разделе. Другими словами, мы хотим знать, когда семантические правила позволяют вычислить значение любого атрибута любого узла произвольного дерева вывода. Можно считать, что грамматика не содержит "бесполезных" правил вывода, то есть что каждое правило из P участвует в выводе хотя бы одной терминальной цепочки.

Пусть T - произвольное дерево вывода, соответствующее данной грамматике; метками концевых узлов могут быть только терминальные символы, корню же разрешим иметь меткой не только аксиому, но и любой символ из V . Тогда можно определить ориентированный граф D(T), соответствующий T, взяв в качестве его узлов упорядоченные пары (X,

), где X - узел дерева T, а
- атрибут символа, служащего меткой узла X. Дуга из (X1;
1) в (X2,
2) проводится в том и только в том случае, когда семантическое правило, вычисляющее атрибут
2, непосредственно использует значение атрибута
1. Например, если T - дерево (рис. 1.2), а в качестве семантических правил взяты правила (таблица 1.1), то орграф D(T) будет иметь такой вид:


Рис. 3.1. 

Другими словами, узлами графа D(T) служат атрибуты, значения которых нужно вычислить, а дуги определяют зависимости, подразумевающие, какие атрибуты вычисляются раньше, а какие позже (рис. 1.6).

Ясно, что семантические правила являются корректными тогда и только тогда, когда ни один из орграфов D(T) не содержит ориентированного цикла. Дело в том, что если в графе нет ориентированных циклов, то можно применить хорошо известную процедуру, позволяющую присвоить значения всем атрибутам. Если же в некотором графе D(T) есть ориентированный цикл, то ввиду того что грамматика не содержит бесполезных правил, можно утверждать, что существует ориентированный цикл в некотором графе D(T), у которого меткой корня дерева T служит S. Для такого дерева T все атрибуты вычислить не уда_тся. Таким образом, задача "Являются ли семантические правила корректным?" сводится к задаче "Содержат ли орграфы D(T) ориентированные циклы?"




Содержание  Назад  Вперед