#java #antlr #antlr4
#java #antlr #antlr4
Вопрос:
Я использую Antlr4 4.9.2
У меня есть требование выполнить несколько проходов одного и того же дерева синтаксического анализа на разных этапах моего анализа. Некоторые файлы, которые обрабатывает мое приложение, очень большие, поэтому я хотел бы иметь возможность не хранить дерево синтаксического анализа в памяти и иметь возможность каждый раз восстанавливать другой экземпляр дерева синтаксического анализа. Пока все хорошо.
Моя задача заключается в том, что мне нужен способ (а) сравнения узлов и (б) быстрого доступа к узлам, который работает с разными экземплярами эквивалентных деревьев синтаксического анализа.
Например, следующий псевдокод генерирует два отдельных экземпляра дерева синтаксического анализа, которые представляют один и тот же файл (поэтому деревья синтаксического анализа и их узлы эквивалентны)
ParseTree parseTree1 = parse(myFile, myGrammar)
ParseTree parseTree2 = parse(myFile, myGrammar)
Поскольку myFile и myGrammar одинаковы, оба parseTree1 и parseTree2 эквивалентны, однако являются разными экземплярами и не удовлетворяют Objects.equals()
В ANTLR, как мне представить координаты C узла таким образом, чтобы:
- C(node1) = C (node2), если узлы эквивалентны
- Я могу получить доступ к C (parseTree1) или C (parseTree2) без необходимости посещать деревья синтаксического анализа — так что я могу быстро расположиться на том же узле для любого экземпляра parsetree
Комментарии:
1. Что это
C(parseTree1)значит? Доступ к произвольному узлу в дереве синтаксического анализа?2. Да, это то, что я имел в виду, извините, если мое письмо было непонятным. Я в основном ищу что-то, что является инвариантным между экземплярами, и это позволяет мне а) быстро получать доступ к узлам и б) выяснить, совпадают ли два узла эквивалентных деревьев синтаксического анализа (т.е. Должны удовлетворять равным).
3. Разве C() не просто хэш-код? Вы можете определить его как угодно, основываясь на таких инвариантах, как номер строки / столбца, текст, тип токена, диапазон токенов, глубина дерева синтаксического анализа, строка XPath, представляющая узел в дереве синтаксического анализа и т.д. Вам нужно будет посетить дерево один раз, чтобы предварительно вычислить хэш-значения для всех узлов. Чтобы найти его в других экземплярах, используйте мультикарту. Будьте осторожны при использовании XPath.findAll() для поиска узла. Движок XPath — это средство обхода дерева. Я портировал гораздо более мощный движок XPath2 на C # для рефакторинга дерева / грамматики Antlr, но у меня не было времени перенести его на Java.
4. Да, то, что вы описываете, — это подход, который я использовал до сих пор. Мой инвариант: public class NodeInvariant { private final Необязательно<String> start; private final Необязательно<String> stop; private final Integer hashCode; private final Integer ruleIndex; private final Integer depth; private final Integer ChildCount; } Это работает, но кажется неоптимальным, и я хочу убедиться, что яне пропустил трюк
Ответ №1:
Вы можете использовать реализацию XPath ANTLR4 для прямого доступа к узлам в заданном пути дерева синтаксического анализа. Вот как я получаю все выражения запроса в коде MySQL после синтаксического анализа:
const expressions = XPath.findAll(tree, "/query/simpleStatement//queryExpression", this.parser);
Комментарии:
1. Это звучит интересно, спасибо, Майк! Я вижу, как я могу получить строку XPath для определения местоположения узла, но, учитывая узел в дереве синтаксического анализа, как я могу получить строку XPath, которая указывает на нее? Есть идеи?
2. Путь — это не что иное, как объединение правил синтаксического анализатора, которые ведут к определенному узлу. Если я вас правильно понял, вы хотите сравнить определенные узлы в одной и той же позиции синтаксического анализа в двух разных деревьях синтаксического анализа. Проверьте грамматику, чтобы узнать, какой путь ведет к этому узлу.
3. Я добился некоторого прогресса в генерации координат XPath из узла, однако я не могу найти способ выбрать конкретный дочерний элемент в правиле, что-то вроде /parent/child[2] не принимается. Есть идеи о том, как выбрать конкретного дочернего элемента в моем выражении ANTLR XPath?
4. Вероятно, реализована не полная спецификация XPath, но вы можете выбрать родительский узел, выбрать дочерний индекс и продолжить путь к югу, если это необходимо.
5. Отличная идея, спасибо Майку за указатель!