软件课程设计语法树.docx

软件课程设计报告姓名：陈达学号：0906840211班级：09062301院系：计算机科学与技术学院 2012年 6 月一、概述在现代编译器的构造过程中，经常使用抽象语法树（Abstract Syntax Tree）作为一种中间形式，这样做可以把翻译过程从语法分析过程中分离出来，使得层次非常清晰。引入抽象语法树是基于多方面原因的，其中的一个原因在于适于语法分析的文法可能并不反映语言成分的自然层次结构。比如Fortran的文法可能把子程序看成是简单的语句序列，而这并不能反映出DO循环的嵌套。如果我们采用能够反映DO循环嵌套的树形表示，那么子程序的语义分析将会更容易一些。因此，很多编译器经常要构造语法树。在这里我们之所以称其为“抽象”语法树，是因为抽象语法树的结构不依赖于被编译语言的原文法，也就是语法分析阶段所采用的文法。在语法分析过程中，为了能够适应摸中分析方法的需要，有时需要对文法进行等价的转换（比如，消除左递归，避免回溯等），这些转换在采用特定的分析方法进行语法分析时是有必要的，但是这样做同时也会带来一些问题。比如，会引入多余的非终结符和多余的产生式等，所有这些多余的成分都会对下面的编译阶段产生一定的限制，甚至会使各阶段变得非常混乱。按照这些文法进行推导时，每一个正确的输入在理论上都对应一个依赖于这些文法的具体分析树。但是正如上面提到的，这种分析数不大适合直接使用，所以我们引入了抽象语法树。抽象语法树在语法分析和后面的各编译阶段之间建立了一个清晰的接口，它能够反映源程序本身的语法结构。基于以上原因，抽象语法树在现代编译器的构造中使用得越来越广泛，本系统也构造了抽象语法树。下面我们先简单的介绍一下语法分析树和抽象语法树，并对它们做以简单的比较。语法分析树也称为具体语法树，因为这种树中的一切都是明示的，完全而又具体，显示了如何根据相应上下文无关文法推导出特定的单词序列。在我们知道了一个单词序列为合法之后，后续的编译阶段就不再需要语法分析树上的许多信息了。因此，语法分析结束以后，一般会将这种语法分析树转换为一棵抽象语法树（又称AST，简称语法树），删除树内部的大部分“人为”结点，并对剩下的结点标注有用的信息。附在特定节点上的标注被称为它的属性。graphviz是贝尔实验室几个计算机牛人设计的一个开源的图表(计算机科学中数据结构中的图)可视化项目，主要用C语言实现，主要实现了一些图布局算法。通过这些算法，可以将图中的节点在画布上比较均匀的分布，缩短节点之间的边长，并且尽量的减少边的交叉。自从使用了graphviz以后，一直想着把这个好东西移植到java下来，大概的思想跟graphviz类似：解析dot脚本，生成图的对象，这个图中包括节点，边以及子图等对象，这些对象上都绑定着相应的属性将解析出来的图对象发送给layout engine进行处理，layout engine可以选择布局策略，比如流布局等从layout engine中得到布局后的图对象，并交给image engine处理，得到最终结果，负责展示或者保存等本实验就是通过graphviz将设计好的语法树程序对测试代码以图像的形式呈现出来二、设计思想1、抽象语法树的创建 1.1 抽象语法树的节点类 抽象语法树的每一个节点是一个类的对象，代表一个类型的语句，给予Java语言的抽象语法树文法中包含了86条文法规则，规则的左部出现的符号成为非终结符号，对应为抽象语法树的符合节点；规则中不属于非终结符号集合的符号成为终结符号，对应的树叶节点，因此在我们设计的解释器中，节点类包含了这86条规则对应的基本类。 ASTCompilationUnit等基本类都继承于SimpleNode类，SimpleNode类实现了接口Node。接口Node定义了setParent()、addChild()等基本操作。 1.2 词法分析器的设计 词法分析器的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，单词符号是一个程序语言的基本，包括关键字、标识符、常数运算符号、界符等。 语法分析是解释过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，建立一棵与输入串相匹配的语法分析树。在JavaParser类中， 每个节点类都对应一个调用方法，用于创建这个节点类的对象。例如：根节点类ASTCompilationUnit对应了方法CompilationUnit()，类ASTPackageDeclaration对应了方法PackageDeclaration()，这些方法之间的互相调用，依据抽象语法树的文法规则来予以确认。2、抽象语法树的遍历 在遍历过程中，可能涉及到多个操作，这些操作大多要求对不同的节点进行不同的处理，我们可以采用Visitor模式，将每一个类中相关的操作封装在一个独立的对象Visitor对象传递给当前访问的节点。当一个节点接受该访问者时，该节点向访问者发送一个包含自身类信息的请求，该请求同时也将该节点本身作为一个参数，然后访问者将对该节点执行某一类型操作。 三、具体实现1、开发平台 eclipse-java-helios-win32-x86_642、程序的设计步骤和主要代码实现 2.1 读取测试的java代码的路径String content = ; try File file = new File(D:chen.txt); FileReader fr = new FileReader(file); BufferedReader br = new BufferedReader(fr); String record = null; int recCount = 0; while (record = br.readLine() != null) recCount+; content = content + record; br.close(); fr.close(); catch (IOException e) e.printStackTrace(); 2.2 创建语法树ASTParser parsert = ASTParser.newParser(AST.JLS3); /创建解析器 parsert.setSource(content.toCharArray(); /设定解析器的源代码字符 CompilationUnit root = (CompilationUnit) parsert.createAST(null); /使用解析器进行解析并返回AST上下文结果(CompilationUnit为根节点) AST ast = root.getAST(); 2.3 在ASTVisitor()中完成语法树的遍历public static String ic=new String();public int id=0;private String getNodeAsString(ASTNode node) node.setFlags(id+);String idstring = ;if(node.getParent()!= null)idstring = node.getParent().getFlags()+-+node.getFlags();String className = node.getClass().getName();int index = className.lastIndexOf(.);if (index 0)className = className.substring(index+1);String value = ;value = className ;value = node.getFlags()+label = + value.replace(, ) +;n+idstring;return value;private String getNodeAsString1(ASTNode node) node.setFlags(id+);String idstring = ;if(node.getParent()!= null)idstring = node.getParent().getFlags()+-+node.getFlags();String className = node.getClass().getName();int index = className.lastIndexOf(.);if (index 0)className = className.substring(index+1);String value = ;value = className + + node.toString()+ ;value = node.getFlags()+label = + value.replace(, ) +;n+idstring;return value; 2.4 将得到的语法树写入.gv中public static boolean writeText(String data) boolean flag=false; File filePath=new File(D:); if(!filePath.exists() /判断文件路径是否有效 filePath.mkdirs(); try FileWriter fw =new FileWriter(D:chen.gv); fw.write(data); flag=true; if(fw!=null) fw.close(); catch (IOException e) e.printStackTrace(); return flag; 2.5 通过graphic将.gv转变成.jpg格式 myvisitor jv = new myvisitor(); root.accept(jv); SuppressWarnings(static-access)String data =digraph ast+ jv.ic +; if(writeText(data)SuppressWarnings(unused)Process process = Runtime.getRuntime().exec(dot D:chen.gv -Tjpg -o D:chen.jpg );System.out.println(succeed); 四、测试测试的代码class chen public static void main(String args) int s=0;int i=0; for(i=0;i=12label =SimpleNamechen;1-23label =MethodDeclaration;1-34label =Modifierpublic;3-45label =Modifierstatic;3-56label =PrimitiveTypevoid;3-67label =SimpleNamemain;3-78label =SingleVariableDeclaration;3-89label =ArrayType;8-910label =SimpleType;9-1011label =SimpleNameString;10-1112label =SimpleNameargs;8-1213label =Block;3-13转换得到的.jpg图片五、遇到的一些问题刚开始的时候eclipse不能打开，提示路径不对，于是修改环境变量，经过上网查阅等方法终于找到问题并成功解决出现can run program “dot”结果发现graphviz的安装在eclipse之前就不能顺利的调用该软件，于是重新安装了该软件五、收获和体会学完编译原理之后，虽然初步地了解了什么是语法树。我从网上去查阅相关资料。找了许多的相关信息后，我逐渐发现写语法树是有迹可循的，大家所提供的思路和想法异曲同工，于是我就选取了其中一种作为基本模版，然后根据自己的理解进行改善。，接下来就是代码具体实现了，有些代码不会当然也是上网查询，在这其中，我也学习了一些方法的固定写法。比如从文件读取java代码，建立抽象语法树的初始步骤等，初步完成后，程序仍然不可以运行，结果发现graphviz的安装在eclipse之前就不能顺利的调用该元件，我向陈龙涛和张君等好友请教，在他们指导下我将程序中的错误一一改正，并加以优化。此程序的编写让我更加了解AST的特点，进一步地掌握了语法树的创建和遍历。该程序设计要求我们有良好的心态，严谨的思维，和丰富的知识基础。在编写程序过程中，小的疏忽就会引起程序很大的错误，因此我必须集中全部精力。编写程序不仅对学识有要求有提高，对科学态度的培养也有很大的益处。 此次收获最大的就是善于通过一切可以利用的渠道学习，上网查询，请教好友，同学间的相互讨论都是很好的学