Теория и реализация языков программирования
Незацикленные атрибутные грамматики
Атрибутная грамматика называется незацикленной, если графы зависимостей деревьев всех цепочек, принадлежащих языку, определяемому грамматикой G, не содержат циклов, и зацикленной, если существует хотя бы одна цепочка, принадлежащая языку, для дерева разбора которой граф D(t) содержит ориентированный цикл.
Теорема B.1. Задача определения того, является ли данная атрибутная грамматика зацикленной, имеет экспоненциальную временную сложность, то есть существует константа c > 0 такая, что любой алгоритм, проверяющий на зацикленность произвольную атрибутную грамматику размера n, должен работать более, чем 2cn/log n шагов на бесконечно большом числе грамматик [1, 2].
Кнутом [3] был предложен алгоритм проверки атрибутных грамматик на зацикленность.
Пусть D(p) - граф зависимостей атрибутов правила вывода p, а Gi - произвольный ориентированный граф, вершинами которого служат атрибуты символа Xi правой части правила вывода p. Обозначим
ориентированный граф, полученный из D(p) добавлением дуг, идущих из b(i) в a(i), если в графе Gi есть дуга из b в a. Через ?обозначим множество ориентированных графов с вершинами - атрибутами символа X, через
- ориентированный граф, вершинами которого служат атрибуты символа X в правиле вывода p : X0
и в котором идет дуга из вершины b в вершину a тогда и только тогда, когда в
Алгоритм B.1. (Алгоритм Кнута). Проверка атрибутной грамматики на зацикленность.
Теорема B.2. Атрибутная грамматика AG незациклена тогда и только тогда, когда ни один из графов Dp[G1 ... Gnp] не содержит ориентированных циклов, то есть когда алгоритм B.1. заканчивается со значением cycle = false.
Теорема B.3. Алгоритм Кнута проверки на зацикленность атрибутной грамматики размера n требует в общем случае exp(cn2) шагов.
