捕鱼修改版

書名：自己動手寫分布式搜索引擎
作者名：羅剛
本章字數： 3879字
更新時間： 2020-11-28 15:52:53

3.6.1 JavaCC

查詢解析器用到的詞法分析不深入處理普通查詢串，而只是處理像：和*這樣的特殊字符，以及像AND和OR這樣的特殊單詞。

查詢分析一般用兩步實現：詞法分析和語法分析。詞法分析階段根據用戶的輸入返回單詞符號序列，而語法分析階段則根據單詞符號序列返回需要的查詢串。

詞法分析的功能是從左到右掃描用戶輸入的查詢串，從而識別出查詢詞、運算符、數值等單詞符號，把識別結果返回到語法分析器，以供語法分析器使用。輸入的是用戶查詢串，輸出的是單詞符號串的識別結果。例如，定義詞的類型如下：

        public enum TokenType{
            AND, //與
            OR,  //或
            NOT, //非
            PLUS, //加
            MINUS, //減
            LPAREN, //左括號
            RPAREN, //右括號
            COLON,  //冒號
            TREM   //詞
        }

對于如下的輸入片斷：

        title:car site:http://www.lietu.com

詞法分析的輸出可能是：

        TREM title
        COLON :
        TREM car
        TREM site
        COLON :
        TREM http://www.lietu.com

可以把詞法分析的結果進一步轉換成語法樹，如圖3-18所示。

圖3-18 從詞法分析到語法樹

如果只滿足于用空格分開多個詞，那么Java的StringTokenizer對于解析任務就綽綽有余了。因為直接寫Lucene這樣的查詢語法的分析器代碼很麻煩，所以可以使用JavaCC生成查詢解析器源代碼。

QueryParser是使用JavaCC生成的詞法和語法解析器，它把字符串解釋成一個Query對象。文本文件QueryParser.jj中定義了如何做查詢串的詞法分析和語法解析。JavaCC(Java Compiler Compiler)是一個軟件工具，用于把QueryParser.jj轉換成Java源代碼。JavaCC的下載地址為http://javacc.java.net/。解壓后執行javacc.jar中的javacc類。

        java -cp javacc.jar javacc QueryParser.jj

JavaCC首先把用戶輸入定義的Token轉換成為與正規文法等價的形式，然后把正規文法轉換成NFA，再把NFA轉換成DFA，最后生成代碼模擬DFA，如圖3-19所示。

圖3-19 JavaCC的原理

詞法分析器采用有限狀態機實現。有限狀態機的狀態在這里稱為詞法狀態。至少會生成一個DEFAULT狀態，還可以自己定義一些詞法狀態。

當初始化詞法分析器時，它從DEFAULT狀態開始。當構造一個TokenManager對象時，也可以通過一個參數指定開始狀態。

        public QueryParserTokenManager(CharStream stream, int lexState){
          this(stream);
          SwitchTo(lexState);
        }

例如，匹配權重，也就是一個上箭頭加上一個數字。用DEFAULT和Boost兩個狀態實現。在DEFAULT狀態接收一個上箭頭以后就進入Boost狀態，在Boost狀態接收數值串后回到DEFAULT狀態，對應的有限狀態機如圖3-20所示。

圖3-20 有限狀態機

例如，輸入“^19”，詞法分析的輸出如下：

        CARAT ^
        NUMBER 19

用若干個正則表達式產生式定義詞法分析。有4種類型的產生式：SKIP、MORE、TOKEN和SPECIAL_TOKEN。產生式的分類依據是：成功匹配一個正則表達式后，接下來做什么。4種產生式的動作分別說明如下。

● SKIP：執行指定的詞法動作后，扔掉這個匹配的字符串。

● MORE：無論接下來的狀態是什么，都繼續拿著匹配的字符串，當前匹配的字符串將會成一個新的匹配的字符串的前綴。

● TOKEN：用匹配的字符串創建一個新的Token，并且返回給解析器或者調用者。

● SPECIAL_TOKEN：創建一個不參與分析的特殊Token。

例如，SKIP類型的產生式跳過空格/制表符/新行符：

        SKIP : { " " | "\t" | "\n" }

TOKEN類型的正則表達式表示會用匹配的字符串創建一個新的Token并且返回給解析器。查詢解析器只用到了SKIP和TOKEN兩種類型的正則表達式。

例如，用兩個TOKEN類型的正則表達式產生式實現這個詞法分析功能：

        <DEFAULT> TOKEN : {
          <CARAT:    "^" > : Boost
        }


        <Boost> TOKEN : {
          <NUMBER:   (<_NUM_CHAR>)+ ( "." (<_NUM_CHAR>)+ )? > : DEFAULT
        }

狀態名稱成為QueryParserConstants類中的整數：

        public interface QueryParserConstants {
          /** 詞法狀態 */
          int Boost = 0; //加權
          int Range = 1; //區間
          int DEFAULT = 2; //默認狀態
        }

但是QueryParser并沒有用到QueryParserConstants類中的這些常量，還存在其他類似這樣的無用代碼。

詞法狀態的列表描述了相應的正則表達式產生式適用的詞法狀態集合。如果寫成“<*>”表示適用于所有的詞法狀態。例如，一個TOKEN類型的產生式：

        <*> TOKEN : {
          <#_NUM_CHAR:   ["0"-"9"] >
        | <#_ESCAPED_CHAR: "\\" ~[] >
        | <#_TERM_START_CHAR: ( ~[ " ", "\t", "\n", "\r", "\u3000", "+", "-", "! ",
        "(", ")", ":", "^",
                                "[", "]", "\"", "{", "}", "~", "*", "? ", "\\", "/" ]
                            | <_ESCAPED_CHAR> ) >
        | <#_TERM_CHAR: ( <_TERM_START_CHAR> | <_ESCAPED_CHAR> | "-" | "+" ) >
        | <#_WHITESPACE: ( " " | "\t" | "\n" | "\r" | "\u3000") >
        | <#_QUOTED_CHAR: ( ~[ "\"", "\\" ] | <_ESCAPED_CHAR> ) >
        }

在標簽 _WHITESPACE之前的“#”表示它存在只是為了定義其他的Token。實際上，執行查詢解析器的時候不會進入這個<*>狀態。

當在<Range>狀態看到“]”時就切換到DEFAULT狀態。

        <Range> TOKEN : {
        <RANGE_TO: "TO">
        | <RANGEIN_END: "]"> : DEFAULT
        | <RANGEEX_END: "}"> : DEFAULT
        | <RANGE_QUOTED: "\"" (~["\""] | "\\\"")+ "\"">
        | <RANGE_GOOP: (~[ " ", "]", "}" ])+ >
        }

文法由若干個產生式組成，每個產生式對應若干個詞法狀態，詞法狀態的集合唯一定義這個產生式。例如，<DEFAULT, Range>產生式包含DEFAULT和Range兩個詞法狀態。可以接收的字符串用正則表達式定義。每個正則表達式都可以有一個名字，例如一個叫作AND的正則表達式匹配“AND”或者“&&”：

        <AND:      ("AND" | "&&") >

這樣，詞法分析返回的Token的類型就是QueryParserConstants.AND。

如果可以接收多個正則表達式，則用“|”隔開。例如，匹配布爾邏輯表達式：

        <DEFAULT> TOKEN : {
          <AND:      ("AND" | "&&") >
        | <OR:       ("OR" | "||") >
        | <NOT:      ("NOT" | "! ") >
        | <PLUS:     "+" >
        | <MINUS:    "-" >
        }

這里是一個TOKEN類型的產生式。

正則表達式產生式首先聲明詞法狀態名稱集合，然后是正則表達式類型，最后是正則表達式本身。例如：

        <DEFAULT, Range> SKIP : {
          < <_WHITESPACE>>
        }

表示在DEFAULT和Range狀態扔掉匹配的空格類型的字符串。

如果把查詢看成是一個簡單的語言，則可以用巴科斯范式(BNF)定義查詢語言的文法。

        Query ::= ( Clause )*
        Clause ::= ["+", "-"] [<TERM> ":"] ( <TERM> | "(" Query ")")

這里的中括號是可選的意思。Clause中的“+”“-”和<TERM> “:”可以出現，也可以不出現。

● ? ：是指操作符左邊的符號(或括號中的一組符號)是可選項(可以出現0到1次)。

● *：是指可以出現0到多次。

● +：是指可以出現1到多次。

例如，定義一個網站域名：

        (<_TERM_CHAR>)+ ( "." (<_TERM_CHAR>)+ )+

增加一個Website詞法狀態：

        <Website> TOKEN:{
        <SITEURL:   ("http://")? <_TERM_START_CHAR> (<_TERM_CHAR>)* ( "."
        (<_TERM_CHAR>)+ )+> : DEFAULT
        }

增加從DEFAULT詞法狀態轉移到Website詞法狀態：

        <DEFAULT> TOKEN : {
          <SITE:    ("SITE" | "site") <COLON>> : Website
        }

這個文法中的每個規則都是一個產生式。每個產生式由左邊的一個符號和右邊的多個符號組成，用右邊的多個符號來描述左邊的一個符號。符號有終結符和非終結符兩種。這里的終結符是“+”和“-”等，非終結符是子句和Query。例如，對于查詢表達式：“site:lietu.com”，可以表示成<TERM>“:”<TERM>的形式，最終歸約成一個有效的Query。但是這里的site是一個保留列名。

JavaCC把非終結符對應成Java中的方法。例如，非終結符Clause對應Clause()方法。JavaCC的．jj文件文法和標準的巴科斯范式的區別是：在JavaCC中，可以在每步推導的過程中執行一些相關的Java語句，在編譯原理中，把這些語句叫作動作。動作寫在{}中。例如，下面是QueryParser.jj中定義的BNF類型的產生式：

        int Conjunction() : {
          int ret = CONJ_NONE;
        }
        {
          [
            <AND> { ret = CONJ_AND; }
            | <OR>  { ret = CONJ_OR; }
          ]
          { return ret; }
        }

等價于：

        Conjunction ::= [<AND> | <OR>]

這里的中括號是可選的意思。如果AND和OR都不出現，則會有個默認的布爾邏輯。

可以在產生式中指定在選擇點做選擇前向前看的Token數量，這個值稱為LOOKAHEAD。LOOKAHEAD的默認值是1。例如，通過LOOKAHEAD(2)指定值是2。

為了同時匹配“car”和“title:car”以及“*:car”這樣的查詢，選擇前向前看2個Token。只有看到第二個Token是否為冒號，才能知道第一個Token是不是列名。

        Clause ::=  [ LOOKAHEAD(2) ( <TERM> <COLON> | <STAR> <COLON> ) ] Term

LOOKAHEAD的值越小，則解析器的速度越快。

JavaCC是一個自頂向下的解析器生成器。JavaCC可以用于詞法分析和語法分析。JavaCC根據輸入文件中定義的語法生成實際用于詞法分析和語法分析的程序源代碼，然后Lucene會調用其中的功能，如圖3-21所示。

圖3-21 用JavaCC生成查詢解析器Java源代碼

JavaCC生成的詞法分析器叫作TokenManager，其中的TokenManager. getNextToken()方法返回下一個Token。QueryParser.jj生成的類QueryParserTokenManager就是詞法分析器。而QueryParser則是語法分析。

和詞法分析相關的幾個類介紹如下。

● CharStream：字符流接口；

● FastCharStream:Lucene按照JavaCC的要求提供的CharStream實現類；

● QueryParserConstants：定義Token類型常量，也就是正則表達式編號；

● QueryParserTokenManager：詞法分析器；

● Token：詞和類型；

● TokenMgrError：詞法分析中出現的錯誤。

Token類用于說明詞對應的字符串和詞的類型。

        public class Token {
          public int kind; //Token類型
          public String image; //Token對應的字符串
        }

測試詞法分析器：

        String strQuery = " title:car site:http://www.lietu.com";  //查詢串
        QueryParserTokenManager tokenManager = new QueryParserTokenManager(
                  new FastCharStream(new StringReader(strQuery)));


        for (Token next = tokenManager.getNextToken(); ! next.toString().equals("");
                  next = tokenManager.getNextToken())
          System.out.println("'" + next.image + "' "+ next.kind); //輸出詞本身和類別

輸出結果：

        'title' 20
        ':' 16
        'car' 20
        'site' 20
        ':' 16
        'http' 20
        ':' 16
        '//' 24
        'www.lietu.com' 20

輸出結果說明QueryParserTokenManager沒有識別網址的功能，但可以處理“car AND price”這樣的查詢串中的邏輯運算符。

要在QueryParser.jj文件中定義語言，需要做以下5件事：

(1) 定義解析環境。

(2) 定義“空白”：例如在中文搜索中，全角空格也可以算空白。

(3) 定義Token。

(4) 按照Token定義語言本身的語法。

(5) 定義每個解析階段將發生的行為。

STATIC是一個布爾選項，默認值是真。如果是真，則在生成的解析器和Token管理器中，所有的方法和類變量都聲明成靜態的。這樣僅僅允許一個解析對象存在，但是查詢分析器應該可以同時有很多個實例，所以這個值應該設成假。

JavaCC的輸入文法文件．jj的格式：

        javacc_options
        PARSER_BEGIN ( <IDENTIFIER>1 )
              java編譯單元
        PARSER_END ( <IDENTIFIER>2 )
        ( 產生式 )*

產生式有如下4種。

(1) Java代碼產生式：這類產生式以保留字JAVACODE開始。

(2) 正則表達式產生式：QueryParser.jj定義了5個正則表達式產生式。

(3) BNF產生式：寫非終結符就像定義一個Java方法。因為會把每個非終結符都翻譯成一個方法。QueryParser.jj定義了6個BNF產生式，分別是Conjunction、Modifiers、TopLevelQuery、Query、Clause和Term。

(4) 詞法聲明產生式：詞法分析聲明以保留字TOKEN_MGR_DECLS開始，后跟一個“:”，然后是一組Java的聲明和語句(Java塊)。把這些聲明和語句寫入生成的TokenManager，并且在詞法動作內可以訪問到。QueryParser.jj并沒有定義這類產生式。

QueryParser.jj的開始處是選項：

        options {
          STATIC=false; //非靜態
          //把QueryParser.jj文件中包含的UNICODE轉義字符\u3000替換成實際的unicode字符
          JAVA_UNICODE_ESCAPE=true;
          //為Lucene自己實現的FastCharStream生成CharStream.java接口
          USER_CHAR_STREAM=true;
        }

然后是一些嵌入的Java代碼，位于PARSER_BEGIN(QueryParser)和PARSER_END (QueryParser)之間。最后是交給JavaCC處理的文法定義。

import聲明復制到QueryParser.java和QueryParserTokenManager.java文件。

FastCharStream需要實現的JavaCC生成的CharStream中的主要方法有：

        public interface CharStream {
          // 返回下一個字符
          char readChar() throws java.io.IOException;


          //標志Token開始
          char BeginToken() throws java.io.IOException;


          //返回從Token開始處到當前位置的字符串
          String GetImage();
        }

JavaCC會生成QueryParser(CharStream stream)和ReInit(CharStream stream)方法：

        public class QueryParser extends QueryParserBase {
          public QueryParserTokenManager token_source; // 生成的詞法分析器
        public Token token;  // 當前Token
        public Token jj_nt; // 下一個Token


        // 根據用戶提供的輸入串構造解析器
        protected QueryParser(CharStream stream) {
          //根據查詢串構造詞法分析器
          token_source = new QueryParserTokenManager(stream);
          token = new Token();
          //內部狀態處理
        }


        // 重新初始化
        public void ReInit(CharStream stream) {
          token_source.ReInit(stream);
          token = new Token();
          //內部狀態處理
        }
      }

匹配的字符串存放在一個叫作image的變量中，匹配以后執行的動作可以訪問到這個變量。例如：

        <DEFAULT> TOKEN : {
          <AND:      ("AND" | "&&") >
        | <OR:       ("OR" | "||") >
        | <NOT:      ("NOT" | "! ") >
        | <PLUS:     "+" >
        | <MINUS:    "-" >
        | <BAREOPER:   ("+"|"-"|"! ") <_WHITESPACE> >
        | <LPAREN:   "(" >
        | <RPAREN:   ")" >
        | <COLON:    ":" >
        | <STAR:     "*" >
        | <CARAT:    "^" > : Boost
        | <QUOTED:    "\"" (<_QUOTED_CHAR>)* "\"">
        | <TERM:     <_TERM_START_CHAR> (<_TERM_CHAR>)*  >
        | <FUZZY_SLOP:    "~" ( (<_NUM_CHAR>)+ ( "." (<_NUM_CHAR>)+ )? )? >
        | <PREFIXTERM:  ("*") | ( <_TERM_START_CHAR> (<_TERM_CHAR>)* "*" ) >
        | <WILDTERM:  (<_TERM_START_CHAR> | [ "*", "? " ]) (<_TERM_CHAR> | ( [ "*",
        "? " ] ))* >
        | <REGEXPTERM: "/" (~[ "/" ] | "\\/" )* "/" >
        | <RANGEIN_START: "[" > : Range
        | <RANGEEX_START: "{" > : Range
        }

匹配以后的動作是：取匹配的字符串中的第一個字符。

        term=<BAREOPER> { term.image = term.image.substring(0,1); }

6個BNF表達式如下：

        Conjunction ::= [<AND> | <OR>]
        Modifiers ::= [<PLUS> | <MINUS> | <NOT>]
        TopLevelQuery ::= Query <EOF>
        Query ::= Modifiers Clause ( Conjunction Modifiers Clause )*
        Clause ::=  [ LOOKAHEAD(2) ( <TERM> <COLON> | <STAR> <COLON> ) ]  (  Term |
        <LPAREN> Query <RPAREN> (<CARAT> <NUMBER>)?  )
        Term ::=
          (
            ( <TERM> | <STAR> | <PREFIXTERM> | <WILDTERM> | term=<REGEXPTERM> |
        <NUMBER> | <BAREOPER> )
            [ <FUZZY_SLOP> ]
            [ <CARAT> <NUMBER> [ <FUZZY_SLOP> ] ]
            | ( ( <RANGEIN_START> | <RANGEEX_START> )
                ( <RANGE_GOOP>|<RANGE_QUOTED> )
                [ <RANGE_TO> ]
                ( <RANGE_GOOP>|<RANGE_QUOTED> )
                ( <RANGEIN_END> | <RANGEEX_END>))
              [ <CARAT> <NUMBER> ]
            | <QUOTED>
              [ <FUZZY_SLOP> ]
              [ <CARAT> <NUMBER> ]
          )

根據QueryParser.jj生成代碼，在命令行運行：

        >javacc QueryParser.jj

jj_consume_token()方法接收一個Token類型作為參數，試著從詞法分析器得到一個指定類型的Token。JavaCC總是使用0編碼EOF類別的Token，所以jj_consume_token(0) 從詞法分析器得到一個EOF類別的Token。JavaCC把QueryParser.jj中的代碼：

        Query TopLevelQuery(String field) :
        {
            Query q;
        }
        {
            q=Query(field) <EOF>
            {
                return q;
            }
        }

轉變成：

        final public Query TopLevelQuery(String field) throws ParseException {
              Query q;
          q = Query(field); //自動生成的代碼
          jj_consume_token(0); //自動生成的代碼
                      {if (true) return q; }
            throw new Error("Missing return statement in function");
          }

QueryParser調用QueryParserBase中實現的handleBareTokenQuery()和handleQuotedTerm()等方法生成查詢對象。這些調用寫在QueryParser.jj中。

官术网_书友最值得收藏!

自己動手寫分布式搜索引擎

3.6.1 JavaCC