拿着ANTLR都能做什么事（1）

拿着ANTLR都能做什么事（1）

关于ANTLR的文章已经有不少，这里不再介绍了，用ANTLR做关键字可以搜出一些入门资料。

ANTLR相对于yacc来说比较平易近人一些，降低了开发门槛，而且开源社区已经贡献了大量编程语言的ANTLR语法代码。我们来看看跨过这个门槛之后，能做些什么有趣以致高大上一点的东西。

1. 自定义静态扫描

我知道Lint，只是意图、场景和难易程度不太一样，这里姑且算作另一个手段吧。

看完这一节，你会看到只要相应的ANTLR语法代码就位，按照这里介绍的模式就能快速开发一个针对目标开发语言的自定义静态扫描工具，或大或小都行。

想象一下你的代码库里面几千几万个代码文件，比如说java，有一天需要了解对于某个接口或者类，我们叫Target吧，直接或间接实现或者继承它的接口或者类都有哪些，也就是说它的子孙接口或者类都有哪些。

为什么需要这个信息？有可能Target出了bug或者安全漏洞（例如最近的Log4j或者Logback），又或者需要做比较大的改动，动手之前想看看影响有多大。如果可以，还想看看这些类都重载、引用了什么。

全文搜索行不行，直接搜“Target”？如果这个名字不太独特，找出来的无关结果就太多了，可以是变量类型、new表达式、字符串的文本内容、注释......那关键词改为“extends Target”或者更强大的正则表达式呢？会少很多无关结果，但是如果有个类或者接口（比如叫SubTarget）继承了Target，然后很多其他类继承了SubTarget，那就会漏掉很多结果。如果像SubTarget这样的类很多的话......想想都吓人。这种情况还是比较普遍的，比如要实现一个插件接口IPlugin，有人实现了一个Pluginbase，其他人写的类都继承自Pluginbase，然后不同部门的人分别实现了自己的Pluginbase，你也不知道都还有哪些Pluginbase，是不是还有继承了Pluginbase的其他Pluginbase......十年的老代码嘛，难免的，别光顾着骂了，关注于问题本身吧。

可见问题的解决不在于怎么挑选搜索关键词，而是你要搜索的目标携带着语言本身的特性，比如在这里就是类继承。所以我们来看看怎样用ANTLR来帮忙找到Target的所有子孙类。

两种办法，一种是利用根语法树对象向下遍历所有的类语法对象，提取类的名字和父类名字；另一种是实现一个Listener接口，在遍历到类语法对象的时候试图提取类的名字和父类名字。不管哪种方法，得到类和父类的名字的时候，把这些对应关系加入到邻接表里面，表示一个包含类名字的节点可以抵达包含父类名字的另一个节点。全部代码扫描完毕之后，问题就转化为，根据邻接表所表达的一张/多张有向无环图，从Target这个节点，能够从哪些其他节点抵达？这些节点的列表就是我们一开始需要的答案。

求有向无环图的可达节点可以用Floyd-Warshall算法，从Target节点开始深度遍历、从任一类向父类上溯至祖先类也行，具体就不展开了，这里只讨论跟ANTLR相关的部分， 以java的ANTLR语法代码为例。

第一种遍历根语法树的办法，从扫描一个java源代码文件开始，应该会得到根语法树对象root。

// code变量是java代码的文本字符串
var stream = new AntlrInputStream(code);
var lexer = new JavaLexerLexer(stream);
var tokens = new CommonTokenStream(lexer);
var parser = new JavaParserParser(tokens);
var root = parser.compilationUnit();

按ANTLR语法代码的描述，

classDeclaration
    : CLASS identifier typeParameters?
      (EXTENDS typeType)?
      (IMPLEMENTS typeList)?
      (PERMITS typeList)? // Java17
      classBody
    ;

从root出发向下一层一层遍历，最终能找到classDeclaration语法对象（注意classDeclaration在多个地方被引用，需要一一处理，这里只是其中一种从typeDeclaration引用的情况）：

var classDeclaration = typeDeclaration.classDeclaration();

拿到classDeclaration对象，按照前面ANTLR语法代码的描述，identifier就是它自己的名字EXTENDS和IMPLEMENTS后面的typeType或者typeList就是它的父类/接口的名字，记录下来加到邻接表就好了。注意typeType有可能是带有命名空间分量的，需要展开为带有全部命名空间的类/接口名字。

typeType
    : annotation* (classOrInterfaceType | primitiveType) (annotation* '[' ']')*
    ;

...

classOrInterfaceType
    : identifier typeArguments? ('.' identifier typeArguments?)*
    ;

而且，因为EXTENDS和IMPLEMENTS部分后面带有问号，这表示在某个类里面它们可能不存在（当然可能了，一个类定义可以不带有extends或者implements的），所以要先检查classDeclaration.EXTENDS()或者classDeclaration.IMPLEMENTS()是否为空。如果为空，就不需要加入邻接表了。

邻接表嘛，用Dictionary>就好了，key表示类/接口自身的名字，value表示父类/接口的名字列表。如果你的代码库不是故意要弄很大，邻接表还是能在内存放得下的，这就是个小工具，不是在服务器长期运行的。

第二种办法，Listener类：

public class SubclassListener : IJavaParserParserListener
{
    ...
    public void ExitClassDeclaration(JavaParserParser.ClassDeclarationContext context)
    {
        var identifer = context.identifier();

        if (context.EXTENDS() != null)
        {
            var extends = context.typeType();
        }

        if (context.IMPLEMENTS() != null)
        {
            // 注意语法代码中有两个typeList 
            var implements = context.typeList()[0];
        }
    }
}

这个类实现了Listener的接口，它的每个接口函数会在ANTLR运行时解析源代码文本时分别调用，比如说上面的ExitClassDeclaration函数会在解析类语法对象结束了的时候被调用，这个时候类名、类要extend或者implement的类名都已经准备妥当可以提供了，接下来我们要做的就是把extends和implements对象所指示的名字提取出来加入到邻接表之中，与第一种方法一样，不再累述。

这个SubclassListener类该如何使用呢？

var subclassListener = new SubclassListener();
...
// code变量是java代码的文本字符串
var stream = new AntlrInputStream(code);
var lexer = new JavaLexerLexer(stream);
var tokens = new CommonTokenStream(lexer);
var parser = new JavaParserParser(tokens);

// 注册subclassListener
parser.AddParseListener(subclassListener);

// 这里不需要根语法树，只是想触发subclassListener的函数而已
parser.compilationUnit();

// subclassListener里面的邻接表应该已包含code里面的所有父子类继承关系了

两种方法相比，在这个场景下，我更喜欢Listener类，相对简单，跳过了手工语法树遍历的部分。不过在其他场景下，你不得不手工遍历语法树。所以，看情况。

最外层代码别忘了：遍历代码库文件夹里面的所有java文件，逐个对其使用parser.compilationUnit，注意，确保邻接表能包含每个文件里面的类名，所以得让邻接表对象的生命周期让最外层代码管理，SubclassListener可以带有对邻接表对象得引用，从而对其添加父子类名字项。

拿到所有子孙类名字了，我们还能知道他们重载引用了什么。这时既然都知道类名和所在文件了，再用ANTLR扫描一遍，这次要遍历的语法对象是成员变量和函数定义，还有函数体里面的引用了。有了第一种方法的铺垫，这里就不展开了。注意，同样的遍历代码在Listener类里面也可以使用，只要是在Exit开头的函数里面实现就可以了。

下一篇文章，我们来看看如何利用ANTLR在没有反射（reflection）特性的语言，比如C/C++，实现类似NUnit的C/C++ Unit。