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

можно рассматривать как суперпозицию меньших


Каждый орграф D(T) можно рассматривать как суперпозицию меньших орграфов Dp, соответствующих правилам Xp0
Xp1 ... Xpn грамматики, 1
p
m. В обозначениях разд. 2 орграф Dp имеет узлы (Xpj,
) для 0
j
np,
A(Xpj) и дуги из (Xpki ,
) в (Xpj ,
) для 0
j
np,
A0(Xpj), если j = 0,
A1(Xpj ), если j > 0, ki = ki(p, j,
),
i =
i(p, j,
), 1
i
t(p, j,
). Другими словами, Dp отражает связи, которые порождают все семантические правила, соответствующие p-му синтаксическому правилу. Например, шести правилам грамматики (таблица 1.1) соответствуют шесть следующих орграфов:


Рис. 3.2. 

Орграф (рис. 3.1) получается в результате "объединения" таких подграфов. Вообще, если T имеет в качестве метки корня терминал, D(T) не содержит дуг. Если корень дерева T помечен нетерминальным символом, T имеет вид


Рис. 3.3. 

для некоторого p, где Tj - дерево вывода, у которого корень помечен символом Xpj, где 1
j
np. В первом случае говорят, что T - дерево вывода типа 0, во втором случае T называется деревом вывода типа р. В соответствии с этим определением для того, чтобы по Dp, D(T1), ... , D(Tnp ) построить D(T), нужно для всех j, 1
j
np совместить узлы, соответствующие атрибутам символа Xpj графа Dp с соответствующими узлами (отвечающими тем же атрибутам корня дерева Tj) в графе D(Tj ).

Для проверки того, содержит ли граф D(T) ориентированный цикл, нам понадобится ещe одно понятие. Пусть p - номер правила вывода. Обозначим через Gj

произвольный орграф (1
j
np), множество узлов которого является подмножеством множества A(Xpj) атрибутов символа Xpj. Пусть

Dp[G1,..., Gnp ]

Пример 3.4.

(html, txt)

орграф, полученный из Dp добавлением дуг, идущих из (Xpj,
) в (Xpj,
0), если в графе Gj есть дуга из
в
0

Например, если



и если D4 - ориентированный граф из (3.2), то D4(G1, G2) имеет вид


Рис. 3.4. 

Теперь можно воспользоваться следующим алгоритмом. Для любого X
V S(X) будет некоторым множеством ориентированных графов с узлами из A(X). Сначала для всех X
N S(X) пусто, а для X =
N S(X) состоит из единственного графа с множеством узлов A(X) и не содержащего дуг.

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






Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий