标记化和AST

Question

对你们所有人都有一个相当抽象的问题.我正在考虑参与静态代码分析项目.它使用C和C++作为开发语言,因此如果您的响应中的任何一种语言中的任何一种语言都很好.

我的问题:我需要了解一些用于处理静态分析代码的基本概念/结构.我听说人们使用AST和标记化等等.我只是想知道是否有什么可以澄清这些东西如何应用于创建静态分析工具？我更像是对标记化的解释,因为我真的不太了解它.我知道这是一种处理字符串的方法,但我对这个答案没有信心.此外,我知道我正在研究的项目在分析之前将代码传递给预处理器.有谁能解释一下？当然,如果是静态代码分析,它不需要预处理？

希望有人可以为我清除这一点.

干杯.

Answer 1

如果您对静态分析感兴趣,那么您不应该为语法分析(即lexing,解析,构建抽象语法树)而烦恼,因为这对您没有太多了解.

所以我建议你使用一些现有的解析基础设施.如果要分析C++源代码,尤其如此,因为编写C++解析器是一件困难的事情.

例如,您可以利用GCC编译器或LLVM/Clang编译器.请注意他们的开源许可证:GCC属于GPLv3,而Clang/LLVM具有类似BSD的许可证.GCC不仅能够处理C&C++,还能处理Fortran,Go,Ada,Objective-C.

由于GCC的GPLv3许可,您在其上的开发应该也是GPLv3下的免费软件.但是,这也意味着海湾合作委员会社区规模很大.如果您了解Ocaml并且只对C的静态分析感兴趣,您可以考虑使用Frama-C(LGPL许可)

实际上,我正在为GCC工作,提供MELT扩展框架(MELT也是GPLv3许可).MELT是一种扩展GCC的高级域特定语言,应该是使用GCC的强大框架和内部表示(Gimple,Tree,...)进行静态分析的理想选择.

(当然,LLVM人员也很高兴能够使用他们的工作;并且没有人知道LLVM和GCC,因为学习这么大的软件已经是一个挑战,因此人们必须选择他们投入的时间).

所以我的建议是加入现有的静态分析或编译工作,不要从头开始重新发明轮子(因为这意味着多年的努力,只是为了拥有一个好的解析器).

通过这样做,您将利用现有的基础架构(因此您不必担心AST-s和解析),并且您将改进一些现有项目.

如果您对MELT感兴趣,我将非常高兴.FWIW,2012 年1月24 ^日在巴黎举行了一场MELT教程,HiPEAC会议.

Answer 2

标记化是将源文本分解为诸如运算符、变量名称、数字等语言元素的行为。解析读取标记序列并构建抽象语法树，这是一种特定的程序表示。标记化和解析对于静态分析来说是必要的，但几乎没有什么有趣的，就像赌注是玩扑克所必需的，但无论如何都不是游戏中有趣的部分。

如果你正在构建一个静态分析器（你暗示你希望在一个用 C 或 C++ 实现的分析器上工作），你将需要编译的基本知识（除非你正在为要静态分析的语言构建一个解析器，否则解析不是那么多），但肯定是关于程序表示（AST、三元组、控制和数据流图，...）、类型和属性推断以及分析准确性的限制（保守分析的原因。程序表示是基本的，因为这些是数据结构大多数静态分析器确实处理；直接从程序文本中提取有用的事实实在是太难了。这些概念可用于在任何编程语言中实现静态分析功能以实现分析类型工具；在 C 或 C++ 中实现它们没有什么特别之处。

在第一部分，跑到最近的编译器类，不要走。如果你没有它，你将无法在工具构建中做任何有效的事情。您更可能在研究生计算机科学课程中找到第二部分。

如果您克服了基本知识问题，您将决定从头开始实施分析工具，或建立在现有分析工具基础架构上。很少有人决定从头开始构建一个；构建强大的解析器、流分析器等作为任何特定静态分析的基础需要大量的工作（数年或数十年）。大多数人尝试使用一些现有的基础设施。

有大量候选人名单：http : //en.wikipedia.org/wiki/List_of_tools_for_static_code_analysis

如果您坚持处理 C 或 C++ 并构建自己的自定义复杂分析，那么您真的，真的需要一个可以处理真实 C 和 C++ 代码的工具。恕我直言，优秀的候选人数量有限：

• GCC（以及各种移植，例如 Starynkevitch 的 MELT，我对此知之甚少）
• Clang（非常壮观的工具集）
• DMS（及其C 和 C++ 前端）[我公司的工具]
• Open64 编译器基础架构
• Rose 编译器基础架构（基于 EDG 的全行业前端）

每一个都是大系统，需要大量投资才能理解和开始使用。不要低估学习曲线。

还有很多其他工具可以处理 C 和 C++，但是“某种”对于静态分析目的来说毫无用处。

如果你打算简单地使用一个静态分析工具，你可以避免学习大部分的解析和程序表示问题；相反，您需要尽可能多地了解您打算使用的特定分析工具。有了上面的编译器背景，你仍然会好很多，因为你会理解这个工具做什么，为什么这样做，以及为什么它会产生它所做的那种答案（通常它会产生很多不令人满意的答案）由于对分析准确性的保守限制而导致的方法）。

最后，您应该清楚您了解静态分析和动态分析之间的区别[使用在运行时收集的数据来确定程序属性]。大多数最终用户并不关心您如何获取有关其代码的信息，并且每种分析方法都有其优点和缺点。