Получить граф потока управления из абстрактного дерева синтаксиса

У меня есть AST, полученный из ANTLR Parser Generator для Java. То, что я хочу сделать, - это как-то построить граф потока управления исходного кода, где каждый оператор или выражение является уникальным Node. Я понимаю, что для этой идентификации должна быть какая-то рекурсивность, мне было интересно, что вы предложите в качестве наилучшего варианта, и если ANTLR имеет набор инструментов, который я могу использовать для этой работы. Ура, Крис

EDIT - Моя главная задача - получить граф потока управления (CFG) из AST. Таким образом, я могу получить древовидное представление источника. Чтобы уточнить, исходным кодом и языком реализации является Java.

Ответ 1

Обычно CFG вычисляются на представлении более низкого уровня (например, байт-код JVM). Кто-то сделал тезис о таких вещах несколько лет назад. Там может быть полезный способ, описанный здесь, как получить это представление.

Поскольку исходный и целевой языки одинаковы, нет шага генерации кода - вы уже сделали! Однако теперь вы можете пройти АСТ. В каждом node АСТ вы должны спросить себя: это "прыгающая" инструкция или нет? Вызов метода и если утверждения являются примерами инструкций прыжка. Так же существуют конструкции цикла (например, for и while). Инструкции, такие как сложение и умножение, не являются прыгающими.

Сначала ассоциируйте с каждым оператором java a node в CFG вместе с записью и выходом node. В первом приближении пройдите по дереву и:

Если текущий оператор является вызовом метода, выясните, где запись node предназначена для соответствующего тела этого вызова метода, и сделайте ребро, указывающее из текущего оператора на эту запись node. если оператор возвращает метод, перечислите места, которые могли бы вызвать его, и добавьте к ним ребро.
для каждого непересекающегося оператора, сделайте ребро между ним и следующим утверждением.

Это даст вам какой-то CFG. Процедура слегка волосатая на шаге 2, потому что вызванный метод может быть объявлен в библиотеке, а не в другом месте в AST - если это так, либо не делайте края, либо создавайте ребро для специального node, представляющего запись к этому библиотечному методу.

Это имеет смысл?

Ответ 2

Создание полного потока потока управления, который действительно учитывает весь язык проблемы сложнее, чем кажется. Вы не только должны определить, что представляется "базовыми блоками", но вам нужно идентифицировать вызовы функций (вроде легко, но определение цели может быть сложнее), где могут выполняться за кадром операции, такие как инициализаторы классов. и беспокоиться о точках, где могут возникать исключения и где управление идет, если возникает исключение.

Если вы внимательно изучите большинство языков, они также будут ясно о порядке оценки вычислений в выражениях, и это имеет значение, если у вас есть два побочных эффекта в выражении; поток управления должен отражать порядок (или не-порядок, если он не определен).

Возможно, вам нужна только абстракция потока управления имеющих базовые блоки и условные обозначения. Это очевидно, немного легче.

В любом случае (простой CFG или полный CFG) вам нужно пройти AST, в каждой точке, имеющей ссылку на возможные контрольные потоки потока (например, для большинства случаев, таких как операторы IF, существуют две задачи потока: предложения THEN и ELSE). В каждом node укажите ссылку node на подходящий целевой поток управления, возможно, заменяющий целевые показатели потока (например, когда вы сталкиваетесь с IF).

Сделать это для полной языковой семантики Java (или C) вполне много работы. Вы можете просто использовать инструмент, который вычисляет это с полки. См. http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html для чего это действительно выглядит, выходя из наших инструментов.

Ответ 3

Основываясь на некоторых комментариях, похоже, что OP действительно хочет сделать генерация кода - преобразовать AST в более низкий уровень последовательность инструкций на основе базовых блоков и точек перехода.

Генерация кода очень специфична для языка, и в эту тему много работы. Прежде чем создавать код, вам нужно знать свой целевой язык - будь то ассемблер или просто какой-то другой язык высокого уровня. Как только вы определили это, вам просто нужно пройти AST и сгенерировать последовательность инструкций, которые реализуют код в AST. (Я говорю, что это просто, но это может быть сложно - трудно обобщить, потому что здесь соображения довольно специфичны для языка.)

Представление, которое вы выбираете для генерации кода, будет содержать граф потока управления, неявно или явно. Если ваш целевой язык довольно низкоуровневый (рядом с ассемблером), то график потока управления должен быть относительно легко извлечен.

(Прошу прокомментировать, если вы хотите получить больше разъяснений.)

Ответ 4

Когда я делал это в прошлом, я использовал graphviz, в частности инструмент точечного, для генерации графика. Я создал файл ввода точек, фактически пройдя график потока управления во время компиляции.

Графическая компоновка - сложная проблема, и Graphviz выполняет отличную работу. Он может выводить на ps, pdf и различные форматы изображений, а макет, как правило, довольно интуитивно понятен. Я очень рекомендую его.

Ответ 5

Вы когда-нибудь пробовали ANTLR Studio? Он не генерирует диаграмму отверстий AST, но для обзора ее уже весьма полезно.