Javacc的学习

标签: 正则表达式  ITeye  velocity  .net  Blog

最近公司会使用DSL描述一个domain service。所以趁这个机会也学习下高深的javacc,以前看到一堆的jj_xxx都很头痛,看代码基本都是跳过。

以前看过velocity, cobar的一下代码,都有使用类似jj_xxx,还有最近公司架构师做的一个anxiety,也使用了jj_xx自定义了一套btrace监控的语法:不需要我们自己写java文件,而是按照他的语法规则,它给我们自动生成btrace script。

还有就是万恶的大学,居然没给我们安排编译原理的课程,导致自己基础太差,理解起来颇为困难。没办法只能是硬着头皮先看一些编译原理的基本内容。

推荐一本书: 《编译原理》, 看完以后基本有了一些概念
  • 文法描述定义, 传说中的BNF
    1. 记号集合,终结符号
    2. 非终结符号
    3. 产生式集合  (这个中文版翻译的产生式还真TM的别扭,先不管)
    digi := [0-9] 
  • 词法分析,读入输入流,结合符号表转化为后端使用的符号流。 
    1. 剔除空白字符
    2. 常数处理
    3. 识别符号和关键词
  • 语法分析,构造语法树。
    1. 自定向下,自底向上。 (javacc采用的是自顶向下)
    2. 超前扫描(lookahead) , 根据非终结符查找对应的生产式,可能会导致匹配失败,需要进行回溯
    3. 预测分析法(递归下降法)。非终结符需要无二义性,可以唯一定义一条生产式,要避免出现左递归。 expr := expr + dis
  • 语法制导和翻译 
  • 代码生成和优化

Javacc语法:  http://javacc.java.net/doc/javaccgrm.html

一个javacc的例子,写的还不错:http://www.iteye.com/topic/359454

在学习之前,一定要先弄会BNF文法描述,感觉有点和离散数学的推导论类似。

BNF的一些语法规则,和正则有着类似的语法: http://blog.csdn.net/yethyeth/archive/2007/01/23/1491150.aspx

 

  • 在双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号。
  • 在双引号外的字(有可能有下划线)代表着语法部分。 
  • 尖括号( < > )内包含的为必选项。 
  • 方括号( [ ] )内包含的为可选项。 
  • 大括号( { } )内包含的为可重复0至无数次的项。 
  • 竖线( | )表示在其左右两边任选一项,相当于"OR"的意思。 
  • ::= 是“被定义为”的意思。 
试着分析anxiety的BNF定义,它的语法: 
import com.alibaba.service.template.*;
import com.alibaba.turbine.module.screen.TemplateScreen;
import com.alibaba.turbine.service.rundata.RunData;
import com.alibaba.webx.WebxException;
method=com.alibaba.manometer.module.screen.Shuffle.execute(RunData, TemplateContext)
method=java.lang.Long.valueOf(long)
method=java.util.concurrent.ConcurrentLinkedQueue.poll()

根绝这个目标语法需求,符号表可定义: 
TOKEN : 
{
     <METHOD  : "method">  
  |  <IMPORT  : "import">  
}

TOKEN :
{  
     <IDENT      : <ALPHA> (<ALPHA>|<NUM>)*> 
  |  <ALPHA      : (["a"-"z","A"-"Z"])>
  |  <NUM        : (["0"-"9"])>
  |  <COMMA      : ",">
  |  <SEMICOLON  : ";">
  |  <LPAREN     : "(">
  |  <RPAREN     : ")">  
  |  <DOMAIN     : ".">
  |  <ASSIGN     : "=">  
  |  <STAR       : "*">  
}

里面的IDENT代表一个java全限定类名或者方法名,支持数字+字母。理论上java的命名规则是可以支持其他的类似中文,下划线等等,这里先不考虑。

最后定义BNF表达式: 
param  ::= ((IDENT ('.' IDENT)* ) (IDENT)?)*     
method ::= IDENT ('.' IDENT)*                           
clazz  ::= IDENT ('.' IDENT)* (';')*                       
statMethod ::= METHOD '=' method '(' param (,param)* ')'
impPack ::= IMPORT '=' clazz
parse ::= (impPack|statMethod)
param的一个例子:java.util.String str
method的一个例子: java.lang.Long.valueOf
clazz的一个例子:  com.alibaba.turbine.service.rundata.RunData;

 

 

 


这里的clazz需要考虑 java.util.*的情况,会有个超前扫描的过程:  [ LOOKAHEAD( { getToken(1).kind == STAR && getToken(2).kind == SEMICOLON } ) <STAR> | <SEMICOLON> ]

根据这个表达式,最后的javacc的对应的java函数为: 

parse() : {}
{
    (
        (
           impPack() | statMethod()
        )
    )*
}
impPack() : {}
{
   (
     <IMPORT> clazz()
   )
}
statMethod() : {}
{
   (
        <METHOD><ASSIGN>method()<LPAREN>param()
        (
         <COMMA> param()
        )*
        <RPAREN>
   )
}
method() : {}
{
   (
     <IDENT>
     (
       <DOMAIN><IDENT>
     )*
   )
}
clazz() : {}
{
   (
     <IDENT>
     (         
        <DOMAIN>
        (
           <IDENT> | [ LOOKAHEAD( { getToken(1).kind == STAR && getToken(2).kind == SEMICOLON } ) <STAR> | <SEMICOLON> ]
        )
     )*
     (<SEMICOLON>)*
   )
}
String param() : {Token t;StringBuilder sb = new StringBuilder();}
{
    (
     (
      <IDENT>
      (
        <DOMAIN><IDENT>
      )*
     )
     (<IDENT>)? 
    )*
}
 
最后剩下的就是填充具体的方法实现了。

通过javacc进行编译生成对应的java文件:

 

最后

至于其他的jjdoc(用于编写BNF)和jjTree(构建语法树),后续有时间再学习下,javacc只是一些基本的词法分析+简单语义定义的使用。


原文链接:加载失败,请重新获取