↪️ ✊🏽 🥉 完美的SAST。解析器 👩‍🔬 🌾 ☝🏽

专为专家设计的一系列文章专门介绍了实现静态代码分析工具的最佳方法。工作的目的是在最大程度地提高工具性能的同时，将开发和支持/更换工具的复杂性降至最低的方法，模型和技术。本文讨论了一种加速解析器并减少内存消耗的方法。本文的结构使读者可以阅读Terrence Parr编写的手册。

充分利用ANTLR

ANTLR最好在大约1 kb和10 kb之间工作；此库将无法以最大速度解析较大的文件。而且，对大文件进行调试工作几乎变得不可能。您需要将解析器的输入数据保持在指定限制内的主要原因是ANTLR的分支预测算法会主动使用堆栈，因此，当一个规则通过许多其他规则（包括某些规则）调用自身时，无论如何，您都需要摆脱语法中的循环。对于这种连接的激活条件，请考虑一个示例：

var f = fun a(b) { b = 10; return b; }

可以使用以下语法描述此代码：

start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'

很容易注意到，在funDecl规则中调用了stmt，这形成了一个循环，在实际应用中，该循环可能导致100 kb文件需要4 GB RAM堆才能发挥最大性能，甚至无法工作，这是绝对不可接受的情况。

克服此缺点的一种方法是在创建令牌的过程中添加特殊的修改，即将{}块卷积到令牌中，稍后在新的解析器中对这些令牌进行处理，将折叠后的令牌发送到输入中。

为此，在ANTLR中，您可以覆盖lexer的org.antlr.v4.runtime.Lexer＃nextToken方法，可以在其中实现卷积功能：

  override def nextToken(): Token = super.nextToken() match {
      case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
      case x: Token => x
  }

  def buildFoldToken(start: RScanToken): RScanToken = {
    val (token, list) = createFoldBlockBody(
      mutable.MutableList[RScanToken]()
        ++ List(start.asInstanceOf[RScanToken])
    )
    val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
    result.setLine(start.getLine)
    result.setCharPositionInLine(start.getCharPositionInLine)
    result.setFoldedTokens(list)
    result
  }

  private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
    var current: RScanToken = null
    while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
      current = nextToken().asInstanceOf[RScanToken]
      list += current
    }
    if (current.getType == Token.EOF)
      throw new IllegalStateException()
    (current, list)
  }

语法应补充以下内容：

startJavaScript 
    :   HashBangLine? jsFileBody? EOF
    ;

startFoldBlock
   :   block EOF
   ;

block
    :   LBRACE stmtList? RBRACE
    |   FoldBlock 
//     ,
//     startFoldBlock
    ;

使用此方法，将不会再次处理卷积的内容，因为递归算法将吸收令牌并保存它们。

处理速度从原来的2倍增长到10倍，这种差异在缩小的js文件中尤为明显。

以几个javascript文件为例，所建议的优化对ANTLR操作的影响：

文件	大小kb	优化前，毫秒	优化后，毫秒
标准化并加载metadata.js	10	1839年	1372
rewrite-live-references.js	8	899	528
dom.umd.min.js	130	43852	6607
react.pure.umd.min.js	139	51668	6495
tsserver.js	8151	362857	117787

如果不进行优化，则工作将在一个线程中进行，如果可能的话，优化过程是并行的。

启动是在具有64 GB RAM的计算机，3.60GHz @Intel®Core（i）i7-9700K CPU，OpenJDK运行时环境AdoptOpenJDK（内部版本11.0.4 + 11）上进行的。

JVM启动密钥：-Xmx4G -XX：+ UseG1GC -XX：MaxHeapFreeRatio = 30 -XX：MinHeapFreeRatio = 10
对于tsserver.js文件，密钥为-Xmx32G，而内存消耗已达到22 GB！在并行模式下，分析优化后最大200 kb的最小文件的堆限制为128 mb，而无需垃圾收集器在处理器上加重，最大为2％！

分析

ANTLR支持在运行时对解析器/词法分析器进行概要分析，要启用它，您需要调用以下方法：org.antlr.v4.runtime.Parser＃setProfile，然后再执行任何规则。然后，您可以通过以下方式获取所有信息：

    private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {
      // do the actual parsing
      val parseInfo = parser.getParseInfo
      val atn = parser.getATN
      for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {
        val ds = atn.decisionToState.get(di.decision)
        val ruleName = parser.ruleName(ds.ruleIndex)
        log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)
        log.debug("=========================")
        log.debug(tokenStream.getText)
        log.debug("=========================")
      }
    }

这种方法的一个明显优点是减少了需要分析的数据量，因为卷积可以用{}代替，并且始终可以在局部卷积中工作，从而极大地加快了优化语法的过程。

结论

本文提出了一种优化使用ANTLR库实现的形式语法工作的方法，尽管该方法本身也可以尝试应用于其他库。优化的一个功能是减少为验证输入令牌流而进行的前移次数。它还使您能够以512 mb的内存成本分析大文件（大于1 mb）以进行单线程处理，而缺乏优化将需要50倍的内存才能使用相同的语法进行快速工作。github上

可用的源代码。该项目旨在演示优化工作。该项目已尽可能简化，建议在GrammarTester类中启动研究，为此已进行了启动配置，您只需要使用输入数据注册文件夹的路径。请注意rscan.tester.cache.dir键，临时文件将被写入此文件夹，成功的文件分析已修复在此文件夹中，并且不允许解析器第二次对其进行分析-便于修复错误。目前，该语法已在为核心react应用程序创建的node_modules的17,000个文件上进行了测试。仅嵌套的node_modules被忽略。

在下一篇文章中，我们将考虑组织数据的选项和R（反射）模型，以便以最小的内存消耗将源数据最佳地表示为分析对象，能够为复杂度为O（1）的元素实现搜索算法，并能够以序列化形式保存到磁盘工具的所有对象以及单元测试部分。

完美的SAST。解析器

充分利用ANTLR

分析

结论

More articles: