8.5.3. Распознавание древовидных структур

Для того чтобы обрабатывать древовидные структуры, необходимо слегка модифицировать наше определение грамматики. Грамматика деревьев определяется как пятерка

где и как и раньше, — множества нетерминалов и терминалов соответственно, — начальный символ, который вообще

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

В качестве примера грамматики деревьев рассмотрим электрическую схему, представленную на рис. 8.3,б. Грамматика, порождающая этот объект, состоит из следующих элементов:

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

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