Название алгоритма - сопоставление поддеревьев в AST
-
28-10-2019 - |
Вопрос
У меня есть набор 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.
Пример древовидного пути для получения всех функций, которые имеют в качестве возвращаемого значения переменную:
родовое слово- Так что же мне искать в существующей литературе?
- Есть другие советы?
- Существуют ли уже языки, которые могут запрашивать такие метааннотированные деревья? Библиотека C с открытым исходным кодом (не C ++) была бы идеальной.
Решение
1) Ваши S-деревья как XPath соответствуют некоторым T-деревьям.Почему бы не построить T-деревья заранее, а затем сопоставить их по шаблону?
2) Если вы хотите сопоставить шаблон со структурой, вы можете представить себе компиляцию шаблона в какой-то конечный автомат, который переходит при сопоставлении заданных частей дерева.Если конечный автомат когда-либо переходит в состояние принятия, вы нашли совпадение.Если у вас более одного шаблона, каждый из них можно рассматривать как конечный автомат, и вы можете запускать их «параллельно» (путем моделирования).Чтобы сделать это эффективным, вычислите перекрестное произведение всех конечных автоматов;теперь есть только один и только один переход на каждый вход.Эту идею я называю «продукты с образцами», и вы видите что-то подобное во множестве эффективных сопоставителей.Одним из близких к тому, что вы хотите сделать, является алгоритм повторного ввода , который отслеживает, какие "шаблоны"работают по мере изменения передаваемых в него данных.
Другие советы
Возможно, стоит изучить JXPath: http://commons.apache.org/jxpath/ Не знаю, на какой язык вы ориентируетесь, но, возможно, стоит попробовать.
В любом случае, если бы мне пришлось попробовать реализовать что-то подобное, моим первым побуждением было бы найти способ "сериализовать" оба дерева и свести проблему к одному из простых сопоставлений строк.