Название алгоритма - сопоставление поддеревьев в AST

Question

У меня есть набор S "маленьких" деревьев, S[i] , для которых мне нужно найти их позиции внутри более крупного , которые используются в качестве шаблонов для поиска совпадающих поддеревьев в более крупном древовидный кодовый код. Я знаю код T до того, как начну создавать код S (который является деревом синтаксического анализа), поэтому я думаю об использовании метода плоскости отсечения для сопоставления узлов по мере продвижения (поскольку синтаксический анализатор генерирует CST).

Деревья в T - это не те же AST, что и S - подумайте о XPath и XML - T содержит древовидное представление XPath, в то время как S - это фактический AST исходного кода - мне нужны карты между T и вектором совпадающих узлов кода сгенерированного тега.

Однако я не уверен в названиях алгоритмов, которые я бы использовал.

В основном я знаю, что хочу делать, это похоже на « разделять и действовать для деревьев» со стеком, в котором я храню возможных кандидатов для сопоставления, при каждом сдвиге парсера LALR, который я дублирую на вершину стека и исключить кандидатов i из T, которые все равно не будут совпадать, и после сокращения я выскакиваю из стека. Вначале возможными кандидатами являются все члены из i.

Обратите внимание : это как раз про AST, ASG - это отдельная история ...

<▪Addendum

Вот дерево синтаксического анализа, генерирующее код кода.

Функция синтаксического анализа будет знать список того, что я называю «древовидными путями», в канонической форме, также представленный в виде деревьев, хранящийся в S[i]. Но они не будут выглядеть как дерево синтаксического анализа, у них есть собственный язык для представления, аналогичный XPath.

Пример древовидного пути для получения всех функций, которые имеют в качестве возвращаемого значения переменную:

родовое слово

1. Так что же мне искать в существующей литературе?
2. Есть другие советы?
3. Существуют ли уже языки, которые могут запрашивать такие метааннотированные деревья? Библиотека C с открытым исходным кодом (не C ++) была бы идеальной.

Answer 1

1) Ваши S-деревья как XPath соответствуют некоторым T-деревьям.Почему бы не построить T-деревья заранее, а затем сопоставить их по шаблону?

2) Если вы хотите сопоставить шаблон со структурой, вы можете представить себе компиляцию шаблона в какой-то конечный автомат, который переходит при сопоставлении заданных частей дерева.Если конечный автомат когда-либо переходит в состояние принятия, вы нашли совпадение.Если у вас более одного шаблона, каждый из них можно рассматривать как конечный автомат, и вы можете запускать их «параллельно» (путем моделирования).Чтобы сделать это эффективным, вычислите перекрестное произведение всех конечных автоматов;теперь есть только один и только один переход на каждый вход.Эту идею я называю «продукты с образцами», и вы видите что-то подобное во множестве эффективных сопоставителей.Одним из близких к тому, что вы хотите сделать, является алгоритм повторного ввода , который отслеживает, какие "шаблоны"работают по мере изменения передаваемых в него данных.

Answer 2

Возможно, стоит изучить JXPath: http://commons.apache.org/jxpath/ Не знаю, на какой язык вы ориентируетесь, но, возможно, стоит попробовать.

В любом случае, если бы мне пришлось попробовать реализовать что-то подобное, моим первым побуждением было бы найти способ "сериализовать" оба дерева и свести проблему к одному из простых сопоставлений строк.