Название алгоритма - сопоставление поддеревьев в AST
У меня есть набор S "маленьких" деревьев S [i] , для которых мне нужно найти их позиции внутри большего , которые используются как шаблоны для поиска совпадающих поддеревьев в большем дереве T . Я знаю S до того, как я начну конструировать T (которое является деревом синтаксического анализа), поэтому я думаю об использовании метода плоскости разделения для сопоставления узлов как Я иду (поскольку синтаксический анализатор генерирует CST).
Деревья в S не те же AST, что и T - подумайте о XPath и XML - S содержит представление XPath в виде дерева, тогда как T является фактическим AST исходного кода - мне нужны карты между i и вектором совпадающих узлов T .
Однако я не уверен в названиях алгоритмов, которые я бы использовал.
В основном я знаю, что я хочу сделать, это похоже на " Divide et Impera для деревьев "со стопкой возможных кандидатов,при каждом сдвиге LALR-анализатора я дублирую верхнюю часть стека и исключаю кандидатов i из S [i] , которые все равно не совпадают, и после сокращения я выхожу из стек. Вначале все члены из S являются возможными кандидатами.
Обратите внимание на : это как раз о AST, ASG - это отдельная история ...
Приложение
Вот дерево синтаксического анализа T .
Функция синтаксического анализа будет знать список того, что я называю «древовидными путями», в канонической форме, также представленный в виде деревьев, хранящийся в S . Но они не будут выглядеть как дерево синтаксического анализа, у них есть собственный язык для представления, аналогичный XPath.
Пример древовидного пути для получения всех функций, которые имеют в качестве возвращаемого значения переменную:
function[body[return[expr[@type="variable"]]]]]
- Итак, что мне следует ищите в существующей литературе?
- Какие-либо другие советы?
- Существуют ли уже языки, которые могут запрашивать такие метааннотированные деревья? Библиотека C с открытым исходным кодом (не C ++) была бы идеальной.