Что такое AST,CFG,CLANG, как мы можем использовать его в алгоритме удаления мертвых кодов?

Я собираюсь написать алгоритм удаления мертвого кода с использованием языка Си для онлайн-мероприятия с нашей командой.

Требования.....

  1. Чтобы прочитать исходный файл программы на С, который имеет много форм мертвых кодов.
  2. И наш вывод должен быть файл, который свободен от всех мертвых кодов.

Во время серфинга в интернете мы натолкнулись на SO ссылки...

Как я могу узнать, какие части в коде никогда не используются?

Обнаружение мертвого кода в устаревшем проекте C/C++

Прежде чем увидеть эти ссылки, у нас была основная идея... Чтение входного файла C, построчно, используя обычный файловый поток, и сохранение в массиве строк. Затем проанализировать эти строки и определить базовые мертвые коды, такие как if(0), if(1) и т. Д. И составление стека для сохранения скобок. И так далее...

Но в этом есть большая проблема: эта идея заставит нас больше делать со строковыми операциями, а не удалять мертвые коды.

Но увидев эти ссылки... мы узнали о библиотеке C lang, абстрактном синтаксическом дереве,Control-Flow-Graph и т. Д.

Но мы очень новички в этих библиотеках и в этих концепциях. Мы узнали, что они используются для разбора кода Си.

Следовательно, нам нужны некоторые основные идеи об этих AST,CFG и некоторые основные рекомендации, объясняющие, как мы можем использовать это в нашем коде...

Можем ли мы включить эту библиотеку clang как обычную библиотеку вроде math.h?

Где мы можем скачать эту библиотеку?

Можем ли мы использовать эти библиотеки C lang в Windows?

Источник

2 ответа

Решение

Я могу объяснить вам концепцию потоковых графов управления, но я не знаком с самой библиотекой.

Концепция проста. Представьте себе любые последовательные строки кода (то есть без if, goto или вызов функции или метки) как один узел графа. каждый goto или вызов функции создает прямую ссылку от текущего узла к узлу, где goto метка или функция, которую она вызывает. Помните, что сама функция может быть графом, а не простым узлом, потому что она может иметь ifs или другие вызовы функций внутри. Каждый вызов функции также создает направленную ссылку из конечных узлов функции (где функция returns) к узлу, содержащему коды, сразу после вызова функции. (Это может создать много ссылок, исходящих из графа функции, потому что функция может быть вызвана во многих частях кода)

Аналогично, если у вас есть ifу вас есть две ссылки направления от текущего узла к обоим if часть и else часть if заявление (если вы не обнаружите if(0) или же if(1) как вы сказали, в этом случае есть только одна ссылка на правильное местоположение)

Корень вашего графика - это точка входа main, Теперь, что вы должны сделать, чтобы найти мертвый код, это просто пройти по графику из корневой позиции (например, используя DFS или BFS) и в конце увидеть, какие узлы НЕ были посещены. Это показывает вам мертвые коды, то есть места в коде, которые, независимо от того, в каком направлении движется ваша программа, не достигнут этих мест.

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

typedef char *line;
FlowGraph *get_flow_graph(line *code)
{
    FlowGraph *current_node = malloc(sizeof *current_node);
    current_node->flow_to = malloc(some_maximum * sizeof *current_node->flow_to);
    current_node->flow_to_count = 0;
    ...
    if (is_if_statement(code[0]))
    {
        FlowGraph *if_part = get_flow_graph(code + 1);
        FlowGraph *else_part = get_flow_graph(code + find_matching_else(code));
        current_node->flow_to[current_node->flow_to_count++] = if_part;
        current_node->flow_to[current_node->flow_to_count++] = else_part;
    }
    else
    ...
}
Источник

Вы можете увидеть примеры графиков управления и потоков данных, извлеченных с помощью DMS Software Reengineering Toolkit.

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

Источник
Другие вопросы по тегам