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

Question

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

---

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Вы когда-нибудь пробовали АНТЛР Студия?Он не генерирует график AST с дырками, но для обзора он уже весьма полезен.

Answer 5

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

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

Answer 6

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

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

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

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