除了日本岛还有什么岛:JR 精品文章 - 使用JavaCC做语法分析[转]

来源:百度文库 编辑:偶看新闻 时间:2024/04/29 11:26:35
使用JavaCC做语法分析[转] shiwenliang 转贴   更新:2009-01-30 20:53:32  版本: 1.0   
大家看完后觉得好的话,顶一下

实用javacc   

前言 

本系列的文章的宗旨是让大家能够写出自己的编译器,解释器或者脚本引擎,所以每到理论介绍到一个程度后,我都会来讨论实践问题.理论方面,编译原理的教材已经是够多了,而实践的问题却很少讨论. 

  

前几节文章只讨论到了词法分析和LL文法分析,关键的LR文法分析这里却还没有讲,我们先不要管复杂的LR文法和算法,让我们使用LL算法来实际做一些东西后再说.本文将介绍一个在JAVA上广泛使用的LL算法分析工具Javacc.(这是我唯一能找到的使用LL算法的语法分析器构造工具).这一节的文章并非只针对JAVA开发者,如果你是C/C++开发者,那么也请你来看看这个JAVA下的优秀工具,或许你将来也用得着它. 

  

Lex 和yacc这两个工具是经典的词法分析和语法分析工具,但是它们都是基于C语言下面的工具,而使用JAVA的朋友们就用不上了.但是JAVA下已经有了lex和yacc的替代品javacc( Java Compiler Compiler ) . 同时javacc也是使用LL算法的工具,我们也可以实践一下前面学的LL算法. 

  

首先声明我不是一个JAVA专家,我也是刚刚才接触JAVA.Java里面或许有很多类似javacc一样的工具,但是据我所知,javacc还是最广泛,最标准的JAVA下的词法语法分析器. 

  

Javacc 的获取 
同lex和yacc一样,javacc也是一个免费可以获取的通用工具,它可以在很多JAVA相关的工具下载网站下载,当然,javacc所占的磁盘空间比起lex和yacc更大一些,里面有标准的文档和examples.相对lex和yacc来说,javacc做得更人性化,更容易一些.如果你实在找不到javacc,还是可以联系我,我这里有.现在最新的就是javacc 3.2版本. 

  

Javacc 的原理 

Javacc 可以同时完成对text的词法分析和语法分析的工作,使用起来相当方便.同样,它和lex和yacc一样,先输入一个按照它规定的格式的文件,然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序.同时,新版本的Javacc除了常规的词法分析和语法分析以外,还提供JJTree等工具来帮助我们建立语法树.总之,Javacc在很多地方做得都比lex和yacc要人性化,这个在后面的输入文件格式中也能体现出来. 

  

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, 那么语法分析器就会开始进行语法分析了 . 

  

例 5.2 

在 javacc 提供的 example 里面没有 .javacc 提供的 example 里面提供的例子中 SimpleExamples 过于简单 , 而其它例子又过于庞大 . 下面我以我们最常见的数学四则混合运算的文法来构造一个 javacc 的文法识别器 . 这个例子是我自己写的 , 十分简单 ,. 其中还包括了文法识别同时嵌入的构建语法树 Parse-Tree 的代码 . 不过由于篇幅的原因 , 我并没有给出全部的代码 , 这里只给了 javacc 输入部分相关的代码 . 而 Parse-tree 就是一个普通的 4 叉树 ,3 个 child,1 个 next( 平行结点 ), 相信大家在学习数据结构的时候应该都是学过的 . 所以这里就省略过去了 . 

  

在大家看这些输入代码之前 , 我先给出它所使用的文法定义 , 好让大家有个清楚的框架 . 

Expression -> Term{ Addop Term }
Addop -> "+" | "-"
Term -> Factor { Mulop Factor }
Mulop -> "*" | "/"
Factor -> ID | NUM | "("Expression")" 

这里的文法可能和BNF范式有点不同.{}的意思就是0次到无限次重复,它跟我们在学习正则表达式的时候的”*”符号相同,所以,在Javacc中的文法表示的时候,{…}部分的就是用(…)*来表示. 

为了让词法分析做得更简单 , 我们通常都不会在文法分析的时候 , 使用 ”(”,”)“ 等字符号串来表示终结符号 , 而需要转而使用 LPAREN , RPAREN 这样的整型符号来表示 . 

  

  

PARSER_BEGIN(Grammar) 

public class Grammar implements NodeType { 

  public ParseTreeNode GetParseTree(InputStream in) throws ParseException 

  { 

       Grammar parser =new Grammar(in); 

       return parser.Expression(); 

  } 

  



PARSER_END(Grammar) 

SKIP : 



  " " | "\t" | "\n" | "\r" 



TOKEN : 



  < ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* > 

|  < NUM: ( ["0"-"9"] )+ > 

|  < PLUS:   "+" > 

|  < MINUS:  "-" > 

|  < TIMERS: "*" > 

|  < OVER:   "/" > 

|  < LPAREN: "(" > 

|  < RPAREN: ")" > 



  

ParseTreeNode Expression() : 



         ParseTreeNode ParseTree = null; 

         ParseTreeNode node; 



{                 

 ( node=Simple_Expression() 

 { 

    if(ParseTree == null) 

               ParseTree =node; 

    else 

    { 

           ParseTreeNode t; 

           t= ParseTree; 

           while(t.next != null) 

                   t=t.next; 

               t.next = node; 

    } 

 } 

)* 

  { return ParseTree;} 

   



ParseTreeNode Simple_Expression() : 



         ParseTreeNode node; 

         ParseTreeNode t; 

         int op; 





  node=Term(){} 

  ( 

  op=addop() t=Term() 



                   ParseTreeNode newNode = new ParseTreeNode(); 

                   newNode.nodetype = op; 

                   newNode.child[0] = node; 

                   newNode.child[1] = t; 

                   switch(op) 

                   { 

                            case PlusOP: 

                            newNode.name = "Operator: +"; 

                            break; 

                            case MinusOP: 

                            newNode.name = "Operator: -"; 

                            break; 

                   } 

                   node = newNode; 

         } 

  )* 

  { return node; } 



int addop() : {} 



          { return PlusOP; } 

|    { return MinusOP; } 



ParseTreeNode Term() : 



         ParseTreeNode node; 

         ParseTreeNode t; 

         int op; 





  node=Factor(){} 

  ( 

  op=mulop() t=Factor() 



                   ParseTreeNode newNode = new ParseTreeNode(); 

                   newNode.nodetype = op; 

                   newNode.child[0] = node; 

                   newNode.child[1] = t; 

                   switch(op) 

                   { 

                            case TimersOP: 

                            newNode.name = "Operator: *"; 

                            break; 

                            case OverOP: 

                            newNode.name = "Operator: /"; 

                            break; 

                   } 

                   node = newNode; 

         } 

  )* 

  { 

       return node; 

  } 



int mulop() :{} 



          { return TimersOP; } 

         |  { return OverOP;   } 



ParseTreeNode Factor() : 



         ParseTreeNode node; 

         Token t; 





  t= 



           node=new ParseTreeNode(); 

           node.nodetype= IDstmt; 

           node.name = t.image; 

           return node; 

         } 

  | 

  t= 

  { 

      node=new ParseTreeNode(); 

           node.nodetype= NUMstmt; 

           node.name = t.image; 

           node.value= Integer.parseInt(t.image); 

           return node; 

    } 

  | 

   node=Simple_Expression()  

   { 

         return node; 

  } 



  

其中 SKIP 中的定义就是在进行词法分析的同时 , 忽略掉的记号 .TOKEN 中的 , 就是需要在做词法分析的时候 , 识别的词法记号 . 当然 , 这一切都是以正则表达式来表示的 . 

这个例子就有多个非终结符号 , 可以看出 , 我们需要为每个非终结符号写出一个过程 . 不同的非终结符号的识别过程中可以互相调用 . 

  

以 Simple_Expression() 过程为例 , 它的产生式是 Expression -> Term { addop Term }, 而在 javacc 的输入文件格式是,它的识别是这样写的 node=Term(){} ( op=addop() t=Term(){ … })* 前面说过,这里的 ”*” 符号和正则表达式是一样的,就是 0 次到无限次的重复 . 那么 Simple_Expression 等于文法 Term Addop Term Addop Term Addop Term … 而 Addop 也就相当于 PLUS 和 MINUS 两个运算符号 . 这里我们在写 Expression 的文法的时候,同时还使用了赋值表达式,因为这个和 Yacc 不同的时候, Javacc 把文法识别完全地做到了函数过程中,那么如果我们要识别 Simple_Expression 的文法,就相当于按顺序识别 Term 和 Addop 两个文法 , 而识别那个文法,就相当于调用那两个非终结符的识别函数 . 正是这一点,我觉得 Javacc 的文法识别处理上就很接近程序的操作过程 , 我们不需要像 YACC 那样使用严格的文法表示格式,复杂的系统参数了 . 

关于 Yacc 的使用,其实比 Javacc 要复杂,还需要考虑到和词法分析器接口的问题,这个我会在以后细细讲到 . 

  

至于其它的文法操作解释我就不再多说了 , 如果要说 , 就是再写上十篇这样的文章也写不完 . 本文只能给读者们一个方向 , 至于深入的研究 , 还是请大家看 javacc 提供的官方文档资料 . 

JavaCC 的下载地址是:https://javacc.dev.java.net/
同时它已经包含了很多语言的grammar模版了,譬如html,xml,python,vb…..等等,可以到http://www.cobase.cs.ucla.edu/pub/javacc/下载。