什么是AST，CFG，CLANG，我们如何使用它死code去除算法？ [英] What is AST,CFG,CLANG, how can we use it in deadcode removal algorithm?

问题描述

我对使用C语言与我们的团队在线事件写了一个死区code去除算法。

I am about to write a dead-code removal algorithm using C language for an online event with our team.

的要求是.....

1. 要读取一个C程序源文件，里面有死区codeS的多种形式。


2. 而我们的输出应该是一个文件，它是所有死区codeS免费的。

一边上网冲浪，我们遇到的SO链接...

While surfing the internet, we came across the SO links...

<一个href=\"http://stackoverflow.com/questions/4813947/how-can-i-know-which-parts-in-the-$c$c-are-never-used\">How我知道这是从来没有使用在code部分？

死code检测传统的C / C ++项目

看到这些环节之前，我们有基本的想法...
   读取输入的C文件，一行使用普通文件流和存储在字​​符串数组行。
   然后分析这些字符串，并确定非常基本的死codeS一样，如果（0），并且如果（1）等。
   并使得一个堆栈，用于保持括号。所以更多...

Before seeing these links,we had the basic idea... Reading the input C file, line by line using normal file stream and store in an string array. Then to analyze those strings and determine the very basic dead codes like if(0) and if(1) etc.. And making a stack, for maintaining the parenthesis. And so more...

但是，这有很大的问题，那这种想法会导致我们做更多的字符串操作，而不是去除死区codeS。

But this has a great problem, that this idea will lead us to do more with string operations rather than removing dead-codes.

但看到这些链接后...
我们来了解
铿锵库，抽象语法树，控制流图等...

But After seeing these link... We came to know about Clang library,Abstract Syntax Tree,Control-Flow-Graph etc...

但我们非常新手，这些库和这些概念。
我们才知道，他们是用来解析C $ C $角

But we are very newbie to those libraries and those concepts. We came to know that they are used to parse the C code.

因此​​，我们需要对这些AST，CFG和一些基本的指导，一些基本的想法，解释我们如何使用
在我们的code ...

Hence we need some basic ideas about these AST,CFG and some basic guidance, explaining how can we use that in our code...

我们能包括铛图书馆像math.h中一个正常的图书馆吗？

Can we include that clang library as a normal library like math.h?

我们在哪里可以下载该库？

Where can we download that library?

我们是否可以使用这些锵图书馆窗口？

Does we can use those Clang libraries in windows?

推荐答案

我可以向你解释的控制流图的概念，但我不熟悉的库本身。

I can explain to you the concept of control flow graphs, but I am not familiar with the library itself.

这个概念很简单。试想一下，code中的任何连续线（即无如果，转到或函数调用或标签）为一体图的节点。每个转到或函数调用创建从当前节点到了转到标签是节点或功能的定向链接它呼吁。请记住，函数本身可能是一个图形，而不是一个简单的节点，因为它可能有如果 s或其他函数中调用。每个函数调用还创建从功能（其中函数收益 S）的叶节点包含codeS函数调用之后的节点定向链接。 （可以创造大量的从函数图形导出链接，因为该函数可以在code的许多地方被称为）

The concept is simple. Imagine any sequential lines of code (that is without if, goto or function call or labels) as one node of a graph. Every goto or function call creates a directional link from the current node to the node where the goto label is or the function it is calling. Remember that a function itself could be a graph and not a simple node, because it may have ifs or other function calls inside. Each function call also creates a directional link from leaf nodes of the function (where the function returns) to the node containing the codes right after the function call. (That can create a lot of links outgoing from the function graph because the function can be called in many parts of the code)

同样的，如果你有一个如果，你必须从当前节点两个方向的链接均如果部分和其他的如果语句的一部分（除非您检测如果（0）或<如果（1）说，在这种情况下，只有一个链接到正确的位置）code>

Likewise, if you have an if, you have two direction links from the current node to both the if part and the else part of the if statement (unless you detect if(0) or if(1) like you said in which case there is only one link to the proper location)

您的图形的根是的切入点主要。现在，你必须做找死code是简单地遍历从（使用DFS或BFS为例）并在年底看到哪些未予访问节点根的位置图。这说明你的死codeS，那就是在code，不管你的程序需要什么样的方向，也不会到达这些地方的地方。

The root of your graph is the entry point of main. Now what you must do to find dead code is to simply traverse the graph from the root position (using DFS or BFS for example) and in the end see which nodes were NOT visited. This shows you the dead codes, that is places in the code that no matter what direction your program takes, it won't reach those locations.

如果你想自己实现，你可以采取一个递归的方法（类似于解析code，但简单）。例如，如果你看到一个如果你说：

If you want to implement this yourself, you can take a recursive approach (similar to parsing the code but simpler). For example if you see an if you say:

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
    ...
}

这篇关于什么是AST，CFG，CLANG，我们如何使用它死code去除算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！