ANTLR 4权威参考读书笔记（27）

前面我们主要处理的是数据，今天我们就来做些编程语言方面的事情。

生成调用关系图

软件很难编写和维护，这就是为什么我们试图构建工具去提高我们的生产力和工作效率。例如，在过去的十年里，我们已经看到测试框架、代码覆盖工具和代码分析器的激增，也很高心看到类层次结构的可视化树，以及大部分开发环境支持这个功能。其中有种可视化被称为调用图，它由函数作为节点，并且函数调用作为节点间的有向边。

这本节中，我们将使用Cymbol语法构建一个调用图生成器。考虑以下函数和函数调用集：

int main() { fact(); a(); }
float fact(int n) {
    print(n);
    if (n == 0) then return 1;
    return n * fact(n - 1);
}
void a() { int x = b(); if false then {c(); d();} }
void b() { c(); }
void c() { b(); }
void d() { }
void e() { }

我们将会把它可视化成如下的调用图：

cymbol-call-graph

可视化的好处是人眼可以很容易地挑出偏差。例如，e()节点是个孤立节点，它意味着没有函数调用它，因此它是一段死代码。一目了然，我们找到一个可以被丢弃的函数。我们还可以通过在图中寻找像fact() -> fact()和b() -> c() -> d()这样的循环非常容易地检测递归。

为了可视化调用图，我们需要读入一段Cymol程序和创建一个DOT文件。例如，以下是我们需要为t.cymbol生成的DOT文件。

digraph G {
    ranksep=.25;
    edge [arrowsize=.5]
    node [shape=circle, fontname="ArialNarrow",
    fontsize=12, fixedsize=true, height=.45];
    main; fact; a; b; c; d; e;
    main -> fact;
    main -> a;
    fact -> print;
    fact -> fact;
    a -> b;
    a -> c;
    a -> d;
    b -> c;
    c -> b;
}

上面的输出包括样本设置描述，例如ranksep=.25;和一列节点和边。为抓住孤立节点，我们需要确保为每个函数名生成节点定义，即使它没有出边和入边。否则它将不会出现在图中。注意在节点定义行末尾的e节点。

main; fact; a; b; c; d; e;

我们的策略很简单，当语法分析器找到一个函数声明时，应用会把当前函数名添加到一个列表，并且设置一个字段称为currentFunctionName。当语法分析器看到一个函数调用，应用会记录从currentFunctionName到被调用函数名的一条边。

开始之前，让我们给Cymbol.g中的一些规则选项打上标签，以便获得更精确的监听器方法。

expr: ID '(' exprList? ')'    # Call
    | expr '[' expr ']'       # Index
    | '-' expr                # Negate
    | '!' expr                # Not
    | expr '*' expr           # Mult
    | expr ('+'|'-') expr     # AddSub
    | expr '==' expr          # Equal
    | ID                      # Var
    | INT                     # Int
    | '(' expr ')'            # Parens
    ;

然后，作为语言应用的基础，把所有图相关的东西封装进一个类。

static class Graph {
    // I'm using org.antlr.v4.runtime.misc: OrderedHashSet, MultiMap
    Set<String> nodes = new OrderedHashSet<String>();    // list of functions
    MultiMap<String, String> edges = new MultiMap<String, String>();    // caller->callee
    public void edge(String source, String target) {
        edges.map(source, target);
    }

从节点和边的集合中，我们可以在类Graph的toDOT()中使用一些Java代码转储出适当的DOT代码。

public String toDOT() {
    StringBuilder buf = new StringBuilder();
    buf.append("digraph G {\n");
    buf.append("    ranksep=.25;\n");
    buf.append("    edge [arrowsize=.5]\n");
    buf.append("    node [shape=circle, fontname=\"ArialNarrow\",\n");
    buf.append("    fontsize=12, fixedsize=true, height=.45];\n");
    buf.append("    ");
    for (String node : nodes) {    // print all nodes first
        buf.append(node);
        buf.append("; ");
    }
    buf.append("\n");
    for (String src : edges.keySet()) {
        for (String trg : edges.get(src)) {
            buf.append("    ");
            buf.append(src);
            buf.append(" -> ");
            buf.append(trg);
            buf.append(";\n");
        }
    }
    buf.append("}\n");
    return buf.toString();
}

现在我们要做的是使用监听器填满这些数据结构，监听器需要两个字段用于记录。

static class FunctionListener extends CymbolBaseListener {
    Graph graph = new Graph();
    String currentFunctionName = null;

然后应用只需要监听两个事件。首先，在语法分析器发现函数声明时记录当前的函数名。

public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentFunctionName = ctx.ID().getText();
    graph.nodes.add(currentFunctionName);
}

其次，当语法分析器侦测到函数调用时，应用需要记录从当前函数到被调用函数的一条边。

public void exitCall(CymbolParser.CallContext ctx) {
    String funcName = ctx.ID().getText();
    // map current function to the callee
    graph.edge(currentFunctionName, funcName);
}

注意，函数调用不能隐藏在嵌套代码块或诸如a()这样的声明中。

void a() { int x = b(); if false then {c(); d();} }

无论什么时候，只要树遍历器发现函数调用就触发监听器方法exitCall()。

通过语法分析树和类FunctionListener，我们可以启动带有监听器的一个遍历器去产生输出。

ParseTreeWalker walker = new ParseTreeWalker();
FunctionListener collector = new FunctionListener();
walker.walk(collector, tree);
System.out.println(collector.graph.toString())

在转储DOT字符串前，该代码会打印出函数和边的列表。

antlr Cymbol.g
compile *.java
run CallGraph t.cymbol

以下是部分输出结果：

edges: {main=[fact, a], fact=[print, fact], a=[b, c, d], b=[c], c=[b]},
functions: [main, fact, a, b, c, d, e]
digraph G {
ranksep=.25;
edge [arrowsize=.5]
...

乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记（27）

生成调用关系图

Comments