抽象语法树文献综述_V1详解.doc

抽象语法树 姓名：刘乐 学号：2101470 日期：2011/10/16 抽象语法树(AST) AST的基本概念 图一 源代码语法树 和抽象语法树相对的是具体语法树（concrete syntax tree），通常称作分析树（parse tree）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。 语法分析和语法树 语法分析指的是将代码扫描到一个容器中，然后对该容器中的字符在词法分析的基础上将字段组合成各类语法短语，在结构上分析判断源程序。使用语法分析可以解决词法分析中较难解决的字段的多重意义的问题。[4] 图二 词法分析[5] 语法树是在语法分析的基础上，将代码的结构转化成树的形式，可以解决字段的上下文相关的问题。而语法树可以通过许多词法语法解析器自动生成，也解决了手工识别的效率问题。 AST的作用 在现代编译器的构造过程中，前端主要实现从源程序到中间形式（Intermediate Representation）的转换，而编译器的后端用来完成从中间形式到具体目标机代码的转换，这是一种广泛采用的编译器构造模型。虽然源程序到目标程序的直接转换是可行的，但是使用独立于具体目标平台的中间形式有以下优点： （1）使用中间形式可以比较容易地构造面向不同目标平台和不同语言的编译器。在不改动已有编译器前端的情况下，为新的目标平台构造一个生成该平台目标程序的后端，就可以构造出新平台的编译器。同样对于一个新的语言，在不改动已有编译器后端的情况下，为新语言构造一个识别该语言的前端，就可以构造出新语言的编译器。 （2）针对中间形式，可以进行独立于目标平台的代码优化。这样可以生成较高质量的目标代码，在此基础上可以对目标代码进行平台相关的优化，进而生成更高质量的目标代码。 使用中间形式的主要缺点是，产生中间代码的编译过程与不产生中间代码的编译过程相比在效率上会显得有些低。这是因为中间代码还要进行再一次的翻译才能生成目标代码。但是，增加一层中间形式可以使编译器更好地模块化，并且可以在中间形式上做很多优化，这些足以抵消两次翻译所带来的低效率。所以，很多现代的编译器都使用了中间形式，比较常见的中间形式有逆波兰表示，N元表示和树形表示三种。抽象语法树作为中间形式JavaCC(Java Compiler Compiler)是一个用JAVA开发的最受欢迎的语法分析生成器。这个分析生成器工具可以读取上下文无关且有着特殊意义的语法并把它转换成可以识别且 匹配该语法的JAVA程序。JavaCC可以在Java虚拟机(JVM) V1.2或更高的版本上使用，它是100%的纯Java代码，可以在多种平台上运行。JavaCC还提供JJTree工具来帮助我们建立语法树，JJDoc工具为我们的源文件生成BNF范式(巴科斯-诺尔范式) 文档(Html) 图四 ANTLR生成的语法树 AST在本课题中的重要性 我们自然科学基金的主要研究内容是网络知识互联，所以对源代码进行研究是十分有必要的，而AST是我们最好的研究对象，理由见2。我们可以对源代码进行挖掘，对学生提交的代码进行整理分类。  附录一 while (b ≠ 0) { if (a b) a?= a ? b; else b?= b ? a; return a; } 附录二 1+2-3*4/5^6 参考文献 [1] baidubaike-javacc [2] C_C_安全检查工具中抽象语法树的设计与实现.nh [3] 维基百科官方网站：/wiki/Knowledge_discovery [4] /lddongyu/article/details/4293811 [5] 基于专家系统的程序代码知识点自动识别方法研究.nh [6] Pete Chapman, Julian Clinton Randy Kerber, Thomas Khabaza, Thomas Reinartz, Colin Shearer and Rüdiger Wirth,“CRISP-DM 1.0-Step-by-step data mining guide”，2000 SPSS Inc. CRISPMWP-1104 [7] Ronen Feldman, James Sanger，“The text mining handbook: advanced approaches in analyzing unstructured data”，Cambridge University Press, 2007 [8]R. Agrawal. ect. Database Mining: A performance perspective. IEEE Transa