编译原理JavaCC学习心的.doc

JAVACC 的研究和应用目录：1,Javacc的初步入门. 1.1 Javacc的简介.1 1.2 Javacc输出什么文件.2 1.3 Token Manager.3 1.4 Javacc的安装.4 1.5Javacc的原理.52,Javacc的三个工具.6 2.1javaCC的使用.6 2.2jjTree的使用11 2.3jjDoc的使用143,Javacc的输入与输出文档154,jj文档的认识.185,javacc中碰到冲突时，如何解决？21 例如遇到Choice Confict怎么办？.226，JJTree的概述与节点的问题257,总结与归纳281.1,javacc简介 javacc是做编译器用的工具，compilers compiler ；javacc就是个语法分析器,可以自己构造合适的语法，用到的是上下文无关文法来做语法分析，可以自己添加相应的处理动作对语言的问题进行处理javacc可以用来生成语法分析器，相当于C中的yaccJava Compiler Compiler 是一个用JAVA开发的最受欢迎的语法分析生成器。这个分析生成器工具可以读取上下文无关且有着特殊意义的语法并把它转换成可以识别且匹配该语法的JAVA程序。它还提供JJTree等工具来帮助我们建立语法树。JavaCC plug-in：一个用于辅助JavaCC应用程序开发的Eclipse插件JavaCC是一个java语言分析器，就是按照“模版”，“装配”不同的语言分析程序的源代码。复杂语言的语法通常都是使用 BNF（巴科斯-诺尔范式，Backus-Naur Form）表示法或者其“近亲” EBNF（扩展的 BNF）描述的。自动化工具可以使用那些描述（我将使用通用的术语 BNF来指代这两种变体）或与它们近似的描述来为你生成解析代码。JavaCC 的长处在于它的简单性和可扩展性。要编译由 JavaCC 生成的 Java 代码，无需任何外部 JAR 文件或目录。仅仅用基本的 Java 1.2 版编译器就可以进行编译。而该语言的布局也使得它易于添加产生式规则和行为。该 Web 站点甚至描述了如何编制异常以便给出用户合适的语法提示最后，JavaCC可以处理任何语言，不仅仅只有程序语言，只要你能够描述那种语言的规则给JavaCC，他就可以对语言进行处理。JavaCC被用来做什么？JavaCC 已经用于为下面的语言产生语法分析程序，:即RTF, Visual Basic, Python, Rational Rose mdl files, XML, XML DTDs, HTML, C, C+, Java, JavaScript, Oberon, SQL, VHDL, VRML, ASN1, email headers,以及许多的私有语言。它同样可以用来构造文件读本, 还有计算器等等！ JavaCC不能做什么？Javacc不能自动的建立语法树（或者其他的特殊的语法分析程序输出），至少有2种建立语法树的工具，即JJTree 与JTB。在javacc的基础上，手动建立语法树在语法分析程序上很容易。Javacc不能够建立符号表，同样，如果你想要一种与语言的符号表，然而，他提供了很好的框架。Javacc不能够产生输出语言。然而，一旦你有语法树，很容易从中得到字符输出。1.2 JavaCC输出什么文件JavaCC 是一个程序生成器。它读入 .jj 文件, 只要.jj 文件中没有错误就可以了,产生一些列的JAVA源文件。在默认的情况下，它产生如下系列的文件：Boiler-plate files o SimpleCharStream.java 代表输入字符流o Token.java 代表单一的输入标记o TokenMgrError.java 从 token manager中抛出的错误o ParseException.java 一个异常指示，即输入不遵守语法分析程序中的语法 Custom files (XXX表示你所选择的文件名字). o XXX.java 语法分析程序的类名 o XXXTokenManager.java - the token manager class. o XXXConstants.java - an interface associating token classes with symbolic names. 下面我们通过如下的例子来说明：这个例子可以在javacc-4.0/doc/examples/SimpleExamples/Simple1.jj看到.PARSER_BEGIN(Simple1) public class Simple1 public static void main(String args) throws ParseException Simple1 parser = new Simple1(System.in);parser.Input(); PARSER_END(Simple1) void Input() : MatchedBraces() (n|r)* void MatchedBraces() : MatchedBraces() .设置好javacc的bin目录后,在命令提示符下输入javacc Simple1.jj然后javacc就会为你生成下面几个java源代码文件Simple1.java Simple1TokenManager.javaSimple1Constants.javaSimpleCharStream.javaToken.javaTokenMgrError.java 1.3 Token Manage Token Manage ,它读入一系列的字符串，最后产生一系列叫做标记的目标。这个规则用于将一系列的字符窜分解为一系列的标记。语法分析程序消耗一系列的标记，分析它的结构，语法分析程序产生的结果决定你自己。1.4Javacc的安装1. 安装jdk,安装完成后设置环境变量PATH路径。CLASSPATH C:Program FilesJavajdk1.6.0libtoools.jar;.PATH C:Program FilesJavajdk1.6.0bin;.2.下载javacc,直接在其官方网站上下载,地址。我下载的是4.0版本的javacc-4.0.zip。3.解压缩javacc-4.0.zip到任意目录（我是解压到桌面的），将其bin目录设置为环境变量PATH路径。4.打开dos，进入javacc的解压目录，然后进入其examplesMailProcessing目录。按照readme上面的指示运行：javacc Digest.jjjavacc Faq.jjjavac *.javajava Digest digestFilejava Faq sampleMailFile5.打开新生成的digestFile和sampleMailFile查看效果。1.5Javacc的原理JavaCC是一个java语言分析器，就是按照“模版”，“装配”不同的语言分析程序的源代码。JavaCC 代表“JavaCompiler Compiler”，是对 YACC（“Yet Another Compiler Compiler”）的继承（YACC 是 AT&T 为了构建 C 和其他高级语言解析器而开发的一个基于 C 的工具）。YACC 和其伙伴词法记号赋予器（tokenizer）“Lex”接收由常用的巴科斯-诺尔范式（Backus-Nauer form，又称 Bacchus Normal Form，BNF）形式的语言定义的输入，并生成一个“C”程序，用以解析该语言的输入以及执行其中的功能。JavaCC 与 YACC 一样，是为加快语言解析器逻辑的开发过程而设计的。但是，YACC 生成 C 代码，而 JavaCC 呢，正如您想像的那样，JavaCC 生成的是 Java 代码。Javacc可以同时完成对text的词法分析和语法分析的工作,使用起来相当方便.同样,它和lex和yacc一样,先输入一个按照它规定的格式的文件,然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序.同时,新版本的Javacc除了常规的词法分析和语法分析以外,还提供JJTree等工具来帮助我们建立语法树.总之,Javacc在很多地方做得都比lex和yacc要人性化,这个在后面的输入文件格式中也能体现出来.2,javacc的三个工具javaCC的功能和yacc相似，主要根据bnf范式生成解析程序，不过javaCC是集合了词法分析和语法分析生成java解析代码。 javaCC有三个工具1），javaCC 用来处理语法文件（jj）生成解析代码；2），jjTree 用来处理jjt文件，生成树节点代码和jj文件，然后再通过javaCC生成解析代码；3），jjDoc 根据jj文件生成bnf范式文档（html）2.1javaCC 的使用 javaCC生成的文件中，最主要的是Grammar.java这个就是解析器的主程序了了，Grammar名由jj中定义。现在根据例子说明jj文件的定义：BNF范式为：Expression:=( ( )* Simple_Expression )* Simple_Expression:=Term ( addop Term )*addop:=|Term:=Factor ( mulop Factor )*mulop:=|Factor:=| Simple_Expression /*这是一个整数的四则运算的例子*/* 运行 javaCC Grammar.jjjavac *.javajava Grammar 1+1*(1+1)3Z*/PARSER_BEGIN(Grammar) /*解析代码的入口*/public class Grammar public static final int PlusOP=1;public static final int MinusOP=2;public static final int TimersOP=3;public static final int OverOP=4; public static void main(String args) throws ParseException Grammar parser = new Grammar(System.in); parser.Expression(); PARSER_END(Grammar)SKIP : /* 不处理的字符*/ | t TOKEN : /*生成token的字符定义*/ | | | | | | | | void Expression() :/*完成 Expression :=( ( )* Simple_Expression )* 的配陪*/ int value=0; /* 这个中是Expression()的定义的局部变量*/ System.out.print(); ( ( /* 首先匹配NEWLINE 这个taken，完成后转到下一个解析*/ System.out.print(); /*在下的中为如果匹配到执行的java代码。*/ )* value= Simple_Expression() /*在换行之前Simple_Expression()解析表达式 ，输入换行后，一个预算解析完成*/ System.out.println(value); System.out.print();/*在下的中为完成表达式解析，匹配到执行的java代码。*/ )* /*系统定义的taken,输入结束符*/int Simple_Expression() :/*完成Simple_Expression :=bnf Term ( addop Term )*配陪 */* 这个中是Simple_Expression()的定义的局部变量*/ int value; int tValue; int op; value= Term () /*配陪Term 相*/ ( op=addop() tValue=Term() switch(op) case PlusOP: value=value+tValue; break; case MinusOP: value=value - tValue; break; )* /*匹配 ( addop Term )* */ return value; int addop() : return PlusOP; | return MinusOP; int Term() : int value; int tValue; int op; value=Factor() ( op=mulop() tValue=Factor() switch(op) case TimersOP: value=value * tValue; break; case OverOP: value=value / tValue; break; )* return value; int mulop() : return TimersOP; | return OverOP; int Factor() : int value; Token t; t= /*获得的解析的值*/ value=100; return value; | t= value= (Integer.valueOf(t.image).intValue(); return value; | t= value=0-Factor(); return value; | t= value=Factor(); return value; | value=Simple_Expression() return value; 根据例子： 基本上是一个taken下跟一个用于处理当前tabkn的java代码2.2jjTree的使用： JJTree在JavaCC源代码的不同地方嵌入语法树构建动作，可以理解为JavaCC的预处理工具。通过运行JavaCC创建解析器生成JJTree输出文件。这篇文档描述了如何使用JJTree，以及如何从中分离你的解析器。 JJTree默认为每个非终结符生成代码来创建语法分析树节点。这种行为可以被修改以便于一些非终结符不生成节点或者因为一部分内容扩充而生成一个节点。JJTree已经定义了一个所有语法分析树节点必须实现的接口Node，这个接口定义诸如：设置节点的父节点、增加子节点、重新获得子节点 等操作方法。 JJTree（为想要更多条件）可以设置“simple” 和 “multi”两种模式之一。在“simple”单一模式下语法分析树节点都是“SimpleNode”这个具体类型。而在“multi”多个模式下语法分析树节点类型取决于节点的名字。如果你不为“Node”接口提供实现JJTree会为你生成一些基于“SimpleNode”的样品实现，你可以修改这个实现以适应需求 要使用 JJTree，您需要能够：1. 创建 JJTree 作为输入获取的 .jjt 脚本 2. 编写客户机端代码以遍历在运行时生成的解析树并对其求值 本文演示了如何执行这两种操作。它并没有涵盖所有内容，但肯定能带您入门。JJTree 基础知识JJTree 是一个预处理器，为特定 BNF 生成解析器只需要简单的两步：1. 对所谓的 .jjt 文件运行 JJTree；它会产生一个中间的 .jj 文件 2. 用 JavaCC 编译该文件（第 1 部分中讨论了这个过程） jjTree的使用，需要根据实际情况写自己的Node类，但是都必须实现Node.java接口，jjTree提供一个SimpleNode.java的简单实现，也可以继承它，或者重写这个类。给出一个javaCC自己带例子，也是四则运算：语法定义：Start:=Expression ;Expression:=AdditiveExpressionAdditiveExpression:=( MultiplicativeExpression ( ( + | - ) MultiplicativeExpression )* )MultiplicativeExpression:=( UnaryExpression ( ( * | / | % ) UnaryExpression )* )UnaryExpression:=( Expression )|Identifier|IntegerIdentifier:=Integer:= options MULTI=true; VISITOR=true; /*实现匹配的visitor模式代码*/ NODE_DEFAULT_VOID=true; /* 解析函数默认不生成node类*/*jtt 默认的生成node类名，都带AST前缀加上当前解析的语意的名称*/PARSER_BEGIN(eg4)class eg4 public static void main(String args) System.out.println(Reading from standard input.); eg4 t = new eg4(System.in); try ASTStart n = t.Start(); eg4Visitor v = new eg4DumpVisitor(); n.jjtAccept(v, null); System.out.println(Thank you.); catch (Exception e) System.out.println(Oops.); System.out.println(e.getMessage(); e.printStackTrace(); PARSER_END(eg4)SKIP : | t| n| r| | TOKEN : /* LITERALS */ INTEGER_LITERAL: (l,L)? | (l,L)? | (l,L)? | | | TOKEN : /* IDENTIFIERS */ IDENTIFIER: (|)* | | ASTStart Start() #Start : /* #Start生成定义的节点类，名称为 前缀 Start.Java*/ Expression() ; return jjtThis; void Expression() : AdditiveExpression()void AdditiveExpression() : ( MultiplicativeExpression() ( ( + | - ) MultiplicativeExpression() )* ) #Add(1) /* Add # 当满足条件(1)，Add生成定义的节点类，名称为 前缀 Add.Java*/void MultiplicativeExpression() : ( UnaryExpression() ( ( * | / | % ) UnaryExpression() )* ) #Mult(1) /* # Mult 当满足条件(1)，Mult生成定义的节点类，名称为 前缀 Mult.Java*/void UnaryExpression() : ( Expression() ) | Identifier() | Integer()void Identifier() #MyOtherID : /* # MyOtherID生成定义的节点类，名称为 前缀 MyOtherID.Java*/ Token t; t= jjtThis.setName(t.image); void Integer() #Integer : /* # Integer生成定义的节点类，名称为 前缀 Integer.Java*/ 2.3jjDoc的使用jjDoc的使用比较简单，这里不做详细的介绍3.1, javacc输入文件Javacc 的输入文件格式做得比较简单.每个非终结符产生式对应一个Class中的函数,函数中可以嵌入相应的识别出该终结符文法时候的处理代码(也叫动作).这个与YACC中是一致的. Javacc 的输入文件中,有一系列的系统参数,比如其中lookahead可以设置成大于1的整数,那么就是说,它可以为我们生成LL(k)算法(k=1),而不是简单的递归下降那样的LL(1)算法了.要知道,LL(2)文法比起前面讨论的LL(1)文法判断每个非终结符时候需要看前面两个记号而不是一个,那么对于文法形式的限制就更少.不过LL(2)的算法当然也比LL(1)算法慢了不少.作为一般的计算机程序设计语言,LL(1)算法已经是足够了.就算不是LL(1)算法,我们也可以通过前面讲的左提公因式把它变成一个LL(1)文法来处理.不过既然javacc都把lookahead选择做出来了,那么在某些特定的情况下,我们可以直接调整一个lookahead的参数就可以,而不必纠正我们的文法. 下面我们来看看Javacc中自带的example中的例子. 例5.1 这个例子可以在javacc-3.2/doc/examples/SimpleExamples/Simple1.jj看到 PARSER_BEGIN(Simple1) public class Simple1 public static void main(String args) throws ParseException Simple1 parser = new Simple1(System.in); parser.Input(); PARSER_END(Simple1) void Input() : MatchedBraces() (n|r)* void MatchedBraces() : MatchedBraces() 设置好javacc的bin目录后,在命令提示符下输入 javacc Simple1.jj 然后 javacc 就会为你生成下面几个 java 源代码文件 Simple1.java Simple1TokenManager.java Simple1Constants.java SimpleCharStream.java Token.java TokenMgrError.java 其中Simple1就是你的语法分析器的对象,它的构造函数参数就是要分析的输入流,这里的是System.in. class Simple1 就定义在标记 PARSER_BEGIN(Simple1) PARSER_END(Simple1) 之间. 但是必须清楚的是,PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字(这里是Simple1). PARSER_END 下面的定义就是文法非终结符号的定义了. Simple1 的文法基本就是: Input - MatchedBraces (n|r)* MatchedBraces - “ “ MatchedBraces “ ” 从它的定义我们可以看到 , 每个非终结符号对于一个过程 . 比如 Input 的过程 void Input() : MatchedBraces() (n|r)* 在定义 void Input 后面记住需要加上一个冒号 ”:”, 然后接下来是两个块 的定义 . 第一个 中的代码是定义数据 , 初试化数据的代码 . 第二个 中的部分就是真正定义 Input 的产生式了 . 每个产生式之间用 ”|” 符号连接 . 注意 : 这里的产生式并非需要严格 BNF 范式文法 , 它的文法既可以是 BNF, 同时还可以是混合了正则表达式中的定义方法 . 比如上面的 Input - MatchedBraces (n|r)* 中 (“n”|”r”)* 就是个正则表达式 , 表示的是 n 或者 r 的 0 个到无限个的重复的记号 . 而 是 javacc 系统定义的记号 (TOKEN), 表示文件结束符号 . 除了 , 无论是系统定义的 TOKEN, 还是自定义的 TOKEN, 里面的 TOKEN 都是以 的方式表示 . 每个非终结符号 (Input 和 MatchedBraces) 都会在 javacc 生成的 Simple1.java 中形成 Class Simple1 的成员函数 . 当你在外部调用 Simple1 的 Input, 那么语法分析器就会开始进行语法分析了 . 3.2,javacc输出文件JavaCC 编译过程:当您对 .jj 文件运行 JavaCC 时，它会生成许多 Java 源文件。其中一个是主解析代码 Parser_1.java，当您有一个要解析的表达式时，您将从您的应用程序调用该代码。JavaCC 还创建了其它六个由解析器使用的辅助文件。JavaCC 总共生成了以下七个 Java 文件。前三个是特定于这个特殊语法的；后四个是通用的助手类 Java 文件，无论语法是怎么样的，都会生成这几个文件。 Parser_1.java Parser_1Constants.java Parser_1TokenManager.java ParseException.java SimpleCharStream.java Token.java TokenMgrError.java 一旦 JavaCC 生成了这七个 Java 源文件，则可以编译它们并将它们链接到您的 Java 应用程序中。然后可以从您的应用程序代码调用新的解析器，从而将表达式传递给它进行求值。下面是一个样本应用程序，它实例化您的解析器，并且为它提供了一个硬连接在应用程序顶部的表达式。4,.jj文档JavaCC的输入文档是一个词法和语法的规范文件，其中也包括一些动作的描述，它的后缀应该是jj。在例5.1 中，可以看到该文档的构成。简而言之，一个jj文档由下面几个部分构成：1、Options部分：这个部分对产生的语法分析器的特性进行说明，例如向前看的token的个数（用来解除冲突）。这一部分是可以省略的，因为每一个选项都有默认值，当我们没有对某个选项进行说明时，它就采用默认值。也可以把这些选项作为javacc命令的参数来启动javacc，可以达到同样的效果。2、分析器类的声明：这个部分指定了分析器类的名字，以及其他类中成员的声明。这个部分是必须有的。这个部分的声明如下：PARSER_BEGIN(classname)Class classname PARSER_END(classname)3、词法部分声明：这里面有四类：SKIP、TOKEN、SPECIAL_TOKEN、MORE。其中，SKIP用来说明被忽略的串，下面是一个例子：SKIP “ “| “n”| “r”TOKEN用来说明在词法层次上识别的token，下面是一个例子：TOKEN | 这个部分是可以省略的。4、在词法声明部分，以#开头的token只是在词法分析时使用，不能作为语法分析的输入，也就是说，它相对词法分析是局部的。5、语法声明和动作代码：这一部分生成的代码会直接插入分析器类声明的结束括号之前。一般而言，语法中的每一个非终结符都对应一个函数，其中函数的形式如下：Return_type function_name() 变量声明和一些初始化的动作上下文无关文法的右部分，其中每个组成部分的形式如下：语法部分 动作部分两个部分都可以省略。语法部分可以是一个字符串（简单的token常常可以这样处理），TOKEN中声明的token，或一个对某个非终结符对应的函数的调用。 以上说明的是jj文件的组成部分，下面再说明一下jj文件中语法的表示方法。Javacc中的语法表示吸收了UNIX中正规文法的一些记号，下面是一些：其中的内容是可选的。+：前面的内容出现一次或多次。-：前后构成的闭区间。*: 前面的内容出现0次或多次。?：前面的内容出现0次或一次。：后面的内容的补。|：前面或后面。()：改变运算的优先级，把其中的内容作为一个整体。5,javacc中碰到冲突时，如何解决？当在javacc中碰到冲突时，可以采用下面的方法之一解决问题： 1),修改语法，使之成为LL(1)语法。这个方法有一个问题：修改后的语法可能非常不直观了。 2),在jj文件中给javacc一些提示。这些提示可以根据展望的作用域分成全局提示和部分提示。要采用全局提示，只要将LOOKAHEAD=k写到Options块中即可（当然也可以写到javacc的命令行里），这样javacc产生的分析器就可以分析LL(K)语法生成的语言。也可以设置一个局部的LOOKAHEAD，这样既保持了LL(1)的高效性，又可以解决choice point中的。LOOKAHEAD的局部声明形式是LOOKAHEAD()，其中括号中的可以是数字（说明向后看多少个记号），或者是一个表示文法的串（当成功时选择）。LOOKAHEAD的完整形式为LOOKAHEAD(amount, expansion, java语言里的逻辑表达式)，它的含义是，如果到达amount个记号后，expansion如果仍然成立，且逻辑表达式也成立，则执行下面的展开。 采用第一种方法的好处是效率非常高，对机器友好，易于维护，采用第二种方法的好处是语法更加直观，但是却不易维护。有时候采用第一种方法是无法解决冲突的，第二种方法是唯一的选择。遇到Choice Confict怎么办？在javacc中最常见的错误会出现Choice Confict的错误信息，遇到这个错误，首先，我们应该仔细的阅读这个信息。我们要理解为什么会出现这个错误并且采取相应的措施，根据我个人的经验，在碰到这个错误需要采取的那个措施是使用Lookahead.下面我能来看下什么是Choice Confict,现在假设你有一个如下形式BNF产生式。void a(): b() | c() 当语法分析程序遇到这个问题的时候，它必须在expanding it to b() 与 expanding it to c()中间选择。产生如此选择的默认方法是看下一个token。但是如果下一个token是ID的那一种类的，任意选择正确，因此你有了Choice Confict，对于轮流的(i.e. |)，默认的选择是第一选择，也就是说，如果你忽视了它的警告，那么第一选择将会每次被采用，下一个标记将是任意的选择。在这个例子中，第二次选择是不可达的。 为了解决Choice Confict，你可以添加说明给第一选择。例如，如果非终结符b与非终结符c可以在token的后面一个token的基础上区分，然后语法分析程序仅仅需要向前看个tokens。你可以这样告诉javacc：void a(): LOOKAHEAD(2 ) b() | c() 但是，假如b与 c 开始一样，他们仅仅可以被他们如何结束来区分，没有预先确定的界限LOOKAHEAD会干什么。在这种情况下，你可以使用syntactic lookahead，这意味着你有语法分析程序向下看，在提交选择前，可以看一个特殊的syntactic pattern 是否匹配选择，在这种情况下你应该这样写：void a(): / Take the first alternative if an followed by a b() appears next LOOKAHEAD( b() ) b() | c() ID b()的序列可能被语法分析程序分析2次，一次是向前看，另一次是常规的语法分析。另一种解决冲突的方式是重写语法，上面的非终结符可以被写为：void a(): ( b() | c() ) 选择将会循环的遇见，考虑：void paramList(): param() ( param() )* ( ( )? )? 将会用一种选择是否停留在* loop 或者退出，处理选择 ELLIPSIS.但是依据下一个token做出选择的默认方法不会工作。一个 token 可以在循环体中看见。或者在循环体的后面看见，因为循环默认的选择停留在循环中。void paramList(): param() ( LOOKAHEAD(2) param() )* ( ( )? )? 或者：void paramList(): param() moreParamList() void moreParamList(): (param()moreParamList()| ) | ( )? 6,JJTree概述JJTree在JavaCC源代码的不同地方嵌入语法树构建动作，可以理解为JavaCC的预处理工具。通过运行JavaCC创建解析器生成JJTree输出文件。这篇文档描述了如何使用JJTre