Атрибутированное дерево разбора

Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.

Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующими примененным синтаксическим правилам.

Для каждого синтаксического правила p

P определим D(p) - граф зависимостей атрибутов символов, входящих в правило p, как ориентированный граф, вершинами которого служат атрибуты символов, входящих в правило p, и в котором идет дуга из вершины b(i) в вершину a(j) тогда и только тогда, когда синтаксическому правилу p сопоставлено семантическое правило

a(j) = fpa(j)(... , b(i), ...), i, j

[0, n]:

Граф зависимостей D(t) дерева разбора t цепочки, принадлежащей языку грамматики G, определим как ориентированный граф, полученный объединением графов зависимостей всех примененных в t синтаксических правил.

Содержание раздела