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

Question

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

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

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

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

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

Добавление

Здесь будет дерево разбора T.

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

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

function[body[return[expr[@type="variable"]]]]]

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

Answer 1

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

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

Answer 2

Возможно, стоит заглянуть в JXPath: http://commons.apache.org/jxpath/ Я не уверен, на какой язык вы ориентируетесь, но, возможно, оно того стоит.

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