注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

网易杭研后台技术中心的博客

 
 
 
 
 

日志

 
 

从Hive到Antlr,再到DFA(确定有限状态机) 1  

来自fyzjhh   2012-06-25 23:56:38|  分类: Hadoop |举报 |字号 订阅

  下载LOFTER 我的照片书  |

概要

hive是对hadoop map/reduce 程序的sql封装,这里的sql称为 HiveQL 。也就是将 HiveQL 转换成map/reduce任务去hadoop里执行。
过程是 先解析 HiveQL语句的词法 , 再进行语义分析,最后产生 map/reduce任务去hadoop里执行。

分析Hive如何解析HiveQL语句的词法,需要Antlr ,可以在 hive的包中找到 antlr 相关的jar包。
这篇文章以hive的版本是hive-0.9.0 , 里面包含的 antlr的版本是 3.0.1 。在运行Hive时只需要antlr-runtime-3.0.1.jar 就可以了。
如果需要自己生产HiveQL的 分词器和解析器 ,需要单独去下载 antlr-3.0.1。




首先分析 Hive的执行过程

配置好hive之后,直接运行 $HIVE_HOME/bin/hive 脚本,分析脚本可以发现最后运行的是 $HIVE_HOME/bin/ext/cli.sh 里的 cli 函数,
这 个函数里 调用了 hadoop的命令,exec $HADOOP jar ${HIVE_LIB}/hive-cli-*.jar $CLASS $HIVE_OPTS "$@" ,这里的Class 是 org.apache.hadoop.hive.cli.CliDriver
可以发现 hive其实就是一个 hadoop的任务, 和 运行 ${HADOOP_HOME}/bin/hadoop jar hadoop-examples-0.20.2-cdh3u1.jar @* 没有什么两样。

进入 org.apache.hadoop.hive.cli.CliDriver 进行分析, 大概的执行流程是

CliDriver.main -> CliDriver.run -> CliDriver.processLine -> CliDriver.processCmd -> CliDriver.processLocalCmd ->
Driver.run -> Driver.execute -> Driver.launchTask ->
TaskRunner.start -> TaskRunner.runSequential ->
Task.executeTask -> Task.execute ->
JobClient.submitJob



我们要讨论的 HiveQL 解析 就在 Driver.run 里,这个方法里 先 int ret = compile(command); , 然后 ret = execute(); 。
在compile 方法中 , 我们关注下面三行代码,之后的代码是语义分析, 以便生成hadoop的任务。


      ParseDriver pd = new ParseDriver();
      ASTNode tree = pd.parse(command, ctx);
      tree = ParseUtils.findRootNonNullToken(tree);

    parse 的代码如下。

    public ASTNode parse(String command, Context ctx) throws ParseException {
...

    HiveLexerX lexer = new HiveLexerX(new ANTLRNoCaseStringStream(command));
    TokenRewriteStream tokens = new TokenRewriteStream(lexer);
    if (ctx != null) {
      ctx.setTokenRewriteStream(tokens);
    }
    HiveParserX parser = new HiveParserX(tokens);
    parser.setTreeAdaptor(adaptor);
    HiveParser.statement_return r = null;

    r = parser.statement();
...
    return (ASTNode) r.getTree();
  }


    这里就是对 command 进行语义分析。步骤就是 利用分词器分词 , 然后使用解析器对语句解析。到这里我们先来看看 antlr的一些基本知识。 parser.statement()这一句代码就是执行具体的解析。它开始一层一层的分析 Hive.g 所描述的文法。



    
antlr的介绍

ANTLR, ANother Tool for Language Recognition, 另外一种语言识别器工具,说白了就是生成一门编程语言的工具,可以理解成编译原理。
拿java语言来说, 它就是读入我们所写的java代码,进行分词,生成一颗语法树。至于后面生成class文件以及运行class文件,则是另外的工作了。当然这些工作是建立在前面的语法树基础上的。

那么 ANTLR 是如何工作的呢?

首先需要 antlr 的文法文件, 通常以 .g 结尾,hive要解析 HiveQL,也需要文法文件,这个文件在hive源码里,
$HIVE_HOME/src/ql/src/java/org/apache/hadoop/hive/ql/parse/Hive.g 。
我们需要运行antlr为这个文法文件生成对应的 词法分析器(Lexer),解析器(Parser)。 这时我们需要单独下载antlr-3.0.1 。
再antlr的home/lib目录下运行

 java -cp .\antlr-3.0.1.jar;.\antlr-2.7.7.jar;.\stringtemplate-3.1b1.jar org.antlr.Tool path/to/Hive.g



最后生成了我们需要的 HiveLexer.java 和 HiveParser.java。
顺便提一句,上面 parse 方法里的 HiveLexerX 和 HiveParserX 继承了 HiveLexer和HiveParser , 里面添加了错误信息的处理。


我们简单的看看 Hive.g 文件


grammar Hive;
声明这个Hive的文法文件

options
{
output=AST;
ASTLabelType=CommonTree;
backtrack=false;
k=3;
}
说明这个文法文件相关的选项,具体意义可以参考http://www.antlr.org/wiki/display/ANTLR3/Grammar+options

tokens {
TOK_INSERT;
TOK_QUERY;
TOK_SELECT;
TOK_SELECTDI;
TOK_SELEXPR;
TOK_FROM;
...
}
定义一些token

// Package headers
@header {
package org.apache.hadoop.hive.ql.parse;
}
@lexer::header {package org.apache.hadoop.hive.ql.parse;}

说明 HiveLexer和HiveParser 所在的package。

@members {
  Stack msgs = new Stack<String>();
}
定义具体的token解析开始和完成的时候的提示信息。

@rulecatch {
catch (RecognitionException e) {
 reportError(e);
  throw e;
}
}
定义解析过程中异常的处理方法。

// starting rule
statement
    : explainStatement EOF
    | execStatement EOF
    ;

看到了吧 这就是parse方法执行的规则


这个就是具体的文法说明部分,由于这里hive的语句比较多,以最常用的select语句的层次关系为例。
比如 select a , b from tab where a=1 limit 1;



statement->execStatement->queryStatementExpression->queryStatement->regular_body->selectStatement->
selectStatement
   :
   selectClause
   fromClause
   whereClause?
   groupByClause?
   havingClause?
   orderByClause?
   clusterByClause?
   distributeByClause?
   sortByClause?
   limitClause? -> ^(TOK_QUERY fromClause ^(TOK_INSERT ^(TOK_DESTINATION ^(TOK_DIR TOK_TMP_FILE))
                     selectClause whereClause? groupByClause? havingClause? orderByClause? clusterByClause?
                     distributeByClause? sortByClause? limitClause?))
   ;



   这里就大概可以看出 与 select a , b from tab where a=1 limit 1; 是匹配的了。这里很多表达式 后面都有 -> ^(...) , 这个是重写规则, 其实就是和前面的语法树描述。
  •     selectClause 对应  select a , b
  •     fromClause 对应 from tab
  •     whereClause 对应 where a=1
  •     limitClause 对应 limit 1
    中间带有?结尾的表示可有可无

另外一个入门的例子


这 里我们再举一个加法计算器的例子说明 antlr的使用过程。在上面的Hive里, 只有HiveQL 的语句的解析 , antlr没有做实际的map/reduce 任务。其实在antlr里可以加入action, 让其做一些具体的工作。而这个在antlr的学习和调试过程中非常有用。

文法文件


file Calculator.g

grammar Calculator;
 
options {
    output=AST;
    ASTLabelType=CommonTree;
}
 
plusExpr : INT PLUS^ INT ;
minusExpr : INT MINUS^ INT ;

MINUS : '-';
PLUS  : '+' ;
INT   : ('0'..'9')+ ;

file CalculatorTreeParser.g

tree grammar CalculatorTreeParser;
 
options {
  tokenVocab=Calculator;
  ASTLabelType=CommonTree;
}
 
expr returns [int value]
    : ^(PLUS a=INT b=INT)  
      {
          int aValue = Integer.parseInt($a.text);
          int bValue = Integer.parseInt($b.text);
          value = aValue + bValue;
      }
    ;

expr1 returns [int value]
    : ^(MINUS a=INT b=INT)
    {
     int aValue = Integer.parseInt($a.text);
     int bValue = Integer.parseInt($b.text);
     value = aValue - bValue;
    };



使用文法文件生成分词器和解析器

java -cp .\antlr-3.0.1\lib\antlr-2.7.7.jar;.\antlr-3.0.1\lib\antlr-3.0.1.jar;.\antlr-3.0.1\lib\antlr-runtime-3.0.1.jar;.\antlr-3.0.1\lib\stringtemplate-3.1b1.jar org.antlr.Tool .\Calculator.g
java -cp .\antlr-3.0.1\lib\antlr-2.7.7.jar;.\antlr-3.0.1\lib\antlr-3.0.1.jar;.\antlr-3.0.1\lib\antlr-runtime-3.0.1.jar;.\antlr-3.0.1\lib\stringtemplate-3.1b1.jar org.antlr.Tool .\CalculatorTreeParser.g




这样就生成了 lexer parser 和treeparse 3个java文件。 拷贝到相应的src下面。
然后在写测试代码 如下,就可以运行通过了。

        InputStream is = new FileInputStream("E:/Study/antlr/cal.txt");
        ANTLRInputStream input = new ANTLRInputStream(is);
        CalculatorLexer lexer = new CalculatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CalculatorParser parser = new CalculatorParser(tokens);

        CommonTree t = (CommonTree) parser.plusExpr().getTree();
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        CalculatorTreeParser walker = new CalculatorTreeParser(nodes);
        System.out.println(walker.expr());
       
        InputStream is1 = new FileInputStream("E:/Study/antlr/cal1.txt");
        ANTLRInputStream input1 = new ANTLRInputStream(is1);
        CalculatorLexer lexer1 = new CalculatorLexer(input1);
        CommonTokenStream tokens1 = new CommonTokenStream(lexer1);
        CalculatorParser parser1 = new CalculatorParser(tokens1);
       
        CommonTree t1 = (CommonTree) parser1.minusExpr().getTree();
        CommonTreeNodeStream nodes1 = new CommonTreeNodeStream(t1);
        CalculatorTreeParser walker1 = new CalculatorTreeParser(nodes1);
        System.out.println(walker1.expr1());

file cal.txt
3+11
file cal1.txt
32-1

输出的结果就是 14 和 31 。 初步完成了2个数的加法和减法计算。




下面就说说antlr是如何分词和解析的。这里就需要谈到有限状态机。这里我们以antlr里实现java语法的例子为参考。
文法文件 Java.g 在examples-v3\java\java 目录下。这是java 1.5 的文法描述文件。
入口表达式 是 compilationUnit,对通常的一个类而言,层次结构如下,跳过一些不重要的表达式

compilationUnit->packageDeclaration? importDeclaration* typeDeclaration*->typeDeclaration->

classOrInterfaceDeclaration->classOrInterfaceModifiers (classDeclaration | interfaceDeclaration)->

normalClassDeclaration->classBody->classBodyDeclaration->memberDecl

对于成员变量 ,memberDeclaration->fieldDeclaration->variableDeclarators->variableDeclarator-> variableDeclaratorId ('=' variableInitializer)?
对于方法函数 ,genericMethodOrConstructorDecl->genericMethodOrConstructorRest->(type | 'void') Identifier methodDeclaratorRest->formalParameters ('[' ']')* ('throws' qualifiedNameList)? (methodBody|';')



运行如下命令 生成 分词器JavaLexer和解析器JavaParser

E:\Study\antlr>java -cp .\antlr-3.0.1\lib\antlr-2.7.7.jar;.\antlr-3.0.1\lib\antlr-3.0.1.jar;.\antlr-3.0.1\lib\antlr-runtime-3.0.1.jar;.\antlr-3.0.1\lib\stringtemplate-3.1b1.jar org.antlr.Tool .\Java.g


然后利用写测试代码 用分词器JavaLexer和解析器JavaParser 来解析java的源文件,
需要将上面生成的分词器JavaLexer和解析器JavaParser放到src中来。


public static void parseFile(String f)
                                 throws Exception {
        try {
            if ( lexer==null ) {
                lexer = new JavaLexer();
            }
            lexer.setCharStream(new ANTLRFileStream(f));
            CommonTokenStream tokens = new CommonTokenStream();

            tokens.setTokenSource(lexer);
            tokens.LT(1);


            System.out.println(tokens);

            JavaParser parser = null;
            parser = new JavaParser(tokens);

            // start parsing
            parser.compilationUnit();
           
            System.err.println("finished "+f);
        }
        catch (Exception e) {
            System.err.println("parser exception: "+e);
            e.printStackTrace();  
        }
    }


我们的分析就从这个方法开始,来慢慢的了解antlr的内部是如何工作的。未完待续。。。
  评论这张
 
阅读(902)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017