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

Question

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

---

РЕДАКТИРОВАТЬ - Моя главная задача состоит в том, чтобы получить график потока управления (CFG) из AST. Таким образом, я могу получить древовидное представление источника. Для пояснения, и исходный код, и язык реализации - это Java.

Answer 1

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

Поскольку ваш исходный и целевой языки одинаковы, шаг генерации кода отсутствует - вы уже сделали! Тем не менее, теперь вы можете ходить по AST. В каждом узле AST вы должны спросить себя: это «прыжковая» инструкция или нет? Вызовы метода и операторы if являются примерами инструкций перехода. То же самое относится и к конструкциям циклов (таким как for и while). Такие инструкции, как сложение и умножение, не являются прыжковыми.

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

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

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

Имеет ли это смысл?

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Я не думаю, что смогу ответить на ваш вопрос так, как вы, возможно, ищете, так как я не знаю ни одного способа в ANTLR производить CFG с или без AST. Но, вкратце, вы бы использовали то, что ANTLR производит для генерации отдельной Java-программы для генерации CFG. Вы должны использовать синтаксическое дерево, сгенерированное ANTLR, в качестве входных данных для генерации вашего CFG в отдельной программе Java вашего собственного создания. На данный момент вы, по сути, строите компилятор. Разница между вашим «компилятором» и JVM заключается в том, что ваши выходные данные представляют собой визуальное представление (CFG) того, как программа разветвляет свои различные пути выполнения, а JVM / Java-компилятор создает код для выполнения на реальной машине (CPU).

Аналогия в том, что если кто-то садится писать книгу (например, на английском языке), отдельные слова, используемые в предложениях, являются ЖЕСТКАМИ компьютерного языка, предложения формируются аналогично тому, как грамматики без контекста выражают действительный компьютерный код. и параграфы и целые романы рассказывают историю аналогичным образом, что семантический анализ / компиляторы / CFG могут создавать / представлять логически обоснованные программы, которые действительно делают что-то полезное и более или менее свободны от логических ошибок. Другими словами, как только вы преодолеете проблему правильного синтаксиса (правильной структуры предложений), любой может написать несколько предложений на странице, но только определенные комбинации предложений создают текст, который действительно что-то делает (рассказывает историю).

То, о чем вы спрашиваете, это последняя часть - как взять синтаксическое дерево и преобразовать или интерпретировать то, что AST фактически делает логически. И, конечно, вам нужно будет создать «компилятор» для каждого языка, для которого вы хотите это сделать. Наличие правильной грамматики не говорит вам , что делает программа - только то, что программа правильна с точки зрения грамматики.

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

Answer 5

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

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

Answer 6

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