一、Lucene的查詢語法
Lucene所支持的查詢語法可見http://lucene.apache.org/java/3_0_1/queryparsersyntax.html
(1) 語法關鍵字
+ - && || ! ( ) { } [ ] ^ " ~ * ? : \
如果所要查詢的查詢詞中本身包含關鍵字，則需要用\進行轉義
(2) 查詢詞(Term)
Lucene支持兩種查詢詞，一種是單一查詢詞，如"hello"，一種是詞組(phrase)，如"hello world"。
(3) 查詢域(Field)
在查詢語句中，可以指定從哪個域中尋找查詢詞，如果不指定，則從默認域中查找。
查詢域和查詢詞之間用:分隔，如title:"Do it right"。
:僅對緊跟其后的查詢詞起作用，如果title:Do it right，則僅表示在title中查詢Do，而it right要在默認域中查詢。
(4) 通配符查詢(Wildcard)
支持兩種通配符：?表示一個字符，*表示多個字符。
通配符可以出現在查詢詞的中間或者末尾，如te?t，test*，te*t，但決不能出現在開始，如*test，?test。
(5) 模糊查詢(Fuzzy)
模糊查詢的算法是基于Levenshtein Distance，也即當兩個詞的差別小于某個比例的時候，就算匹配，如roam~0.8，即表示差別小于0.2，相似度大于0.8才算匹配。
(6) 臨近查詢(Proximity)
在詞組后面跟隨~10，表示詞組中的多個詞之間的距離之和不超過10，則滿足查詢。
所謂詞之間的距離，即查詢詞組中詞為滿足和目標詞組相同的最小移動次數。
如索引中有詞組"apple boy cat"。
如果查詢詞為"apple boy cat"~0，則匹配。
如果查詢詞為"boy apple cat"~2，距離設為2方能匹配，設為1則不能匹配。
| (0) | boy | apple | cat |
| (1) |
| boy apple | cat |
| (2) | apple | boy | cat |
如果查詢詞為"cat boy apple"~4，距離設為4方能匹配。
| (0) | cat | boy | apple |
| (1) |
| cat boy | apple |
| (2) |
| boy | cat apple |
| (3) |
| boy apple | cat |
| (4) | apple | boy | cat |
(7) 區間查詢(Range)
區間查詢包含兩種，一種是包含邊界，用[A TO B]指定，一種是不包含邊界，用{A TO B}指定。
如date:[20020101 TO 20030101]，當然區間查詢不僅僅用于時間，如title:{Aida TO Carmen}
(8) 增加一個查詢詞的權重(Boost)
可以在查詢詞后面加^N來設定此查詢詞的權重，默認是1，如果N大于1，則說明此查詢詞更重要，如果N小于1，則說明此查詢詞更不重要。
如jakarta^4 apache，"jakarta apache"^4 "Apache Lucene"
(9) 布爾操作符
布爾操作符包括連接符，如AND，OR，和修飾符，如NOT，+，-。
默認狀態下，空格被認為是OR的關系，QueryParser.setDefaultOperator(Operator.AND)設置為空格為AND。
+表示一個查詢語句是必須滿足的(required)，NOT和-表示一個查詢語句是不能滿足的(prohibited)。
(10) 組合
可以用括號，將查詢語句進行組合，從而設定優先級。
如(jakarta OR apache) AND website
Lucene的查詢語法是由QueryParser來進行解析，從而生成查詢對象的。
通過編譯原理我們知道，解析一個語法表達式，需要經過詞法分析和語法分析的過程，也即需要詞法分析器和語法分析器。
QueryParser是通過JavaCC來生成詞法分析器和語法分析器的。
二、JavaCC介紹
本節例子基本出于JavaCC tutorial的文章，http://www.engr.mun.ca/~theo/JavaCC-Tutorial/
JavaCC是一個詞法分析器和語法分析器的生成器。
所謂詞法分析器就是將一系列字符分成一個個的Token，并標記Token的分類。
例如，對于下面的C語言程序：
| int main() { return 0 ; } |
將被分成以下的Token:
| “int”, “ ”, “main”, “(”, “)”, “”,“{”, “\n”, “\t”, “return” “”,“0”,“”,“;”,“\n”, “}”, “\n”, “” |
標記了Token的類型后如下：
| KWINT, SPACE, ID, OPAR, CPAR, SPACE, OBRACE, SPACE, SPACE, KWRETURN, SPACE, OCTALCONST, SPACE, SEMICOLON, SPACE, CBRACE, SPACE, EOF |
EOF表示文件的結束。
詞法分析器工作過程如圖所示：
此一系列Token將被傳給語法分析器(當然并不是所有的Token都會傳給語法分析器，本例中SPACE就例外)，從而形成一棵語法分析樹來表示程序的結構。
JavaCC本身既不是一個詞法分析器，也不是一個語法分析器，而是根據指定的規則生成兩者的生成器。
2.1、第一個實例——正整數相加
下面我們來看第一個例子，即能夠解析正整數相加的表達式，例如99+42+0+15。
(1) 生成一個adder.jj文件
此文件中寫入的即生成詞法分析器和語法分析器的規則。
(2) 設定選項，并聲明類
| /* adder.jj Adding up numbers */ options { STATIC = false ; } PARSER_BEGIN(Adder) class Adder { static void main( String[] args ) throws ParseException, TokenMgrError { Adder parser = new Adder( System.in ) ; parser.Start() ; } } PARSER_END(Adder) |
STATIC選項默認是true，設為false，使得生成的函數不是static的。
PARSER_BEGIN和PARSER_END之間的java代碼部分，此部分不需要通過JavaCC根據規則生成java代碼，而是直接拷貝到生成的java代碼中的。
(3) 聲明一個詞法分析器
| SKIP : { " " } SKIP : { "\n" | "\r" | "\r\n" } TOKEN : { < PLUS : "+" > } TOKEN : { < NUMBER : (["0"-"9"])+ > } |
第一二行表示空格和回車換行是不會傳給語法分析器的。
第三行聲明了一個Token，名稱為PLUS，符號為“+”。
第四行聲明了一個Token，名稱為NUMBER，符號位一個或多個0-9的數的組合。
如果詞法分析器分析的表達式如下：
- “123 + 456\n”，則分析為NUMBER, PLUS, NUMBER, EOF
- “123 - 456\n”，則報TokenMgrError，因為“-”不是一個有效的Token.
- “123 ++ 456\n”，則分析為NUMBER, PLUS, PLUS, NUMBER, EOF，詞法分析正確，后面的語法分析將會錯誤。
(4) 聲明一個語法分析器
| void Start() : {} { <NUMBER> ( <PLUS> <NUMBER> )* <EOF> } |
語法分析器使用BNF表達式。
上述聲明將生成start函數，稱為Adder類的一個成員函數
語法分析器要求輸入的語句必須以NUMBER開始，以EOF結尾，中間是零到多個PLUS和NUMBER的組合。
(5) 用javacc編譯adder.jj來生成語法分析器和詞法分析器
最后生成的adder.jj如下：
| options
{
static = false;
} PARSER_BEGIN(Adder)
package org.apache.javacc; public class Adder
{
public static void main(String args []) throws ParseException
{
Adder parser = new Adder(System.in);
parser.start();
}
}
PARSER_END(Adder) SKIP :
{
" "
| "\r"
| "\t"
| "\n"
} TOKEN : /* OPERATORS */
{
< PLUS : "+" >
} TOKEN :
{
< NUMBER : ([ "0"-"9" ])+ >
} void start() :
{}
{
<NUMBER>
(
<PLUS>
<NUMBER>
)*
} |
用JavaCC編譯adder.jj生成如下文件：
- Adder.java：語法分析器。其中的main函數是完全從adder.jj中拷貝的，而start函數是被javacc由adder.jj描述的規則生成的。
- AdderConstants.java：一些常量，如PLUS, NUMBER, EOF等。
- AdderTokenManager.java：詞法分析器。
- ParseException.java：用于在語法分析錯誤的時候拋出。
- SimpleCharStream.java：用于將一系列字符串傳入詞法分析器。
- Token.java：代表詞法分析后的一個個Token。Token對象有一個整型域kind，來表示此Token的類型(PLUS, NUMBER, EOF)，有一個String類型的域image，來表示此Token的值。
- TokenMgrError.java：用于在詞法分析錯誤的時候拋出。
下面我們對adder.jj生成的start函數進行分析：
| final public void start() throws ParseException { //從詞法分析器取得下一個Token，而且要求必須是NUMBER類型，否則拋出異常。 //此步要求表達式第一個出現的字符必須是NUMBER。 jj_consume_token(NUMBER); label_1: while (true) { //jj_ntk()是取得下一個Token的類型，如果是PLUS，則繼續進行，如果是EOF則退出循環。 switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { case PLUS: ; break; default: jj_la1[0] = jj_gen; break label_1; } //要求下一個PLUS字符，再下一個是一個NUMBER，如此下去。 jj_consume_token(PLUS); jj_consume_token(NUMBER); } } |
(6) 運行Adder.java
如果輸入“123+456”則不報任何錯誤。
如果輸入“123++456”則報如下異常：
| Exception in thread "main" org.apache.javacc.ParseException: Encountered " "+" "+ "" at line 1, column 5.
Was expecting:
<NUMBER> ...
at org.apache.javacc.Adder.generateParseException(Adder.java:185)
at org.apache.javacc.Adder.jj_consume_token(Adder.java:123)
at org.apache.javacc.Adder.start(Adder.java:24)
at org.apache.javacc.Adder.main(Adder.java:8) |
如果輸入“123-456”則報如下異常：
| Exception in thread "main" org.apache.javacc.TokenMgrError: Lexical error at line 1, column 4. Encountered: "-" (45), after : ""
at org.apache.javacc.AdderTokenManager.getNextToken(AdderTokenManager.java:262)
at org.apache.javacc.Adder.jj_ntk(Adder.java:148)
at org.apache.javacc.Adder.start(Adder.java:15)
at org.apache.javacc.Adder.main(Adder.java:8) |
2.2、擴展語法分析器
在上面的例子中的start函數中，我們僅僅通過語法分析器來判斷輸入的語句是否正確。
我們可以擴展BNF表達式，加入Java代碼，使得經過語法分析后，得到我們想要的結果或者對象。
我們將start函數改寫為：
| int start() throws NumberFormatException : { //start函數中有三個變量 Token t ; int i ; int value ; } { //首先要求表達式的第一個一定是一個NUMBER，并把其值付給t t= <NUMBER> //將t的值取出來，解析為整型，放入變量i中 { i = Integer.parseInt( t.image ) ; } //最后的結果value設為i { value = i ; } //緊接著應該是零個或者多個PLUS和NUMBER的組合 ( <PLUS> //每出現一個NUMBER，都將其付給t，并將t的值解析為整型，付給i t= <NUMBER> { i = Integer.parseInt( t.image ) ; } //將i加到value上 { value += i ; } )* //最后的value就是表達式的和 { return value ; } } |
生成的start函數如下：
| final public int start() throws ParseException, NumberFormatException { Token t; int i; int value; t = jj_consume_token(NUMBER); i = Integer.parseInt(t.image); value = i; label_1: while (true) { switch ((jj_ntk == -1) ? jj_ntk() : jj_ntk) { case PLUS: ; break; default: jj_la1[0] = jj_gen; break label_1; } jj_consume_token(PLUS); t = jj_consume_token(NUMBER); i = Integer.parseInt(t.image); value += i; } { if (true) return value; } throw new Error("Missing return statement in function"); } |
從上面的例子，我們發現，把一個NUMBER取出，并解析為整型這一步是可以共用的，所以可以抽象為一個函數：
| int start() throws NumberFormatException : { int i; int value ; } { value = getNextNumberValue() ( <PLUS> i = getNextNumberValue() { value += i ; } )* { return value ; } } int getNextNumberValue() throws NumberFormatException : { Token t ; } { t=<NUMBER> { return Integer.parseInt( t.image ) ; } } |
生成的函數如下：
| final public int start() throws ParseException, NumberFormatException { int i; int value; value = getNextNumberValue(); label_1: while (true) { switch ((jj_ntk == -1) ? jj_ntk() : jj_ntk) { case PLUS: ; break; default: jj_la1[0] = jj_gen; break label_1; } jj_consume_token(PLUS); i = getNextNumberValue(); value += i; } { if (true) return value; } throw new Error("Missing return statement in function"); } final public int getNextNumberValue() throws ParseException, NumberFormatException { Token t; t = jj_consume_token(NUMBER); { if (true) return Integer.parseInt(t.image); } throw new Error("Missing return statement in function"); } |
2.3、第二個實例：計算器
(1) 生成一個calculator.jj文件
用于寫入生成計算器詞法分析器和語法分析器的規則。
(2) 設定選項，并聲明類
| options { STATIC = false ; } PARSER_BEGIN(Calculator) import java.io.PrintStream ; class Calculator { static void main( String[] args ) throws ParseException, TokenMgrError, NumberFormatException { Calculator parser = new Calculator( System.in ) ; parser.Start( System.out ) ; } double previousValue = 0.0 ; } PARSER_END(Calculator) |
previousValue用來記錄上一次計算的結果。
(3) 聲明一個詞法分析器
| SKIP : { " " } TOKEN : { < EOL:"\n" | "\r" | "\r\n" > } TOKEN : { < PLUS : "+" > } |
我們想要支持小數，則有四種情況：沒有小數，小數點在中間，小數點在前面，小數點在后面。則語法規則如下：
| TOKEN { < NUMBER : (["0"-"9"])+ | (["0"-"9"])+ "." (["0"-"9"])+ | (["0"-"9"])+ "." | "." (["0"-"9"])+ > } |
由于同一個表達式["0"-"9"]使用了多次，因而我們可以定義變量，如下：
| TOKEN : { < NUMBER : <DIGITS> | <DIGITS> "." <DIGITS> | <DIGITS> "." | "." <DIGITS>> } TOKEN : { < #DIGITS : (["0"-"9"])+ > } |
(4) 聲明一個語法分析器
我們想做的計算器包含多行，每行都是一個四則運算表達式，語法規則如下：
| Start -> (Expression EOL)* EOF |
| void Start(PrintStream printStream) throws NumberFormatException : {} { ( previousValue = Expression() <EOL> { printStream.println( previousValue ) ; } )* <EOF> } |
每一行的四則運算表達式如果只包含加法，則語法規則如下：
| Expression -> Primary (PLUS Primary)* |
| double Expression() throws NumberFormatException : { double i ; double value ; } { value = Primary() ( <PLUS> i= Primary() { value += i ; } )* { return value ; } } |
其中Primary()得到一個數的值：
| double Primary() throws NumberFormatException : { Token t ; } { t= <NUMBER> { return Double.parseDouble( t.image ) ; } } |
(5) 擴展詞法分析器和語法分析器
如果我們想支持減法，則需要在詞法分析器中添加：
| TOKEN : { < MINUS : "-" > } |
語法分析器應該變為：
| Expression -> Primary (PLUS Primary | MINUS Primary)* |
| double Expression() throws NumberFormatException : { double i ; double value ; } { value = Primary() ( <PLUS> i = Primary() { value += i ; } | <MINUS> i = Primary() { value -= i ; } )* { return value ; } } |
如果我們想添加乘法和除法，則在詞法分析器中應該加入：
| TOKEN : { < TIMES : "*" > } TOKEN : { < DIVIDE : "/" > } |
對于加減乘除混合運算，則應該考慮優先級，乘除的優先級高于加減，應該先做乘除，再做加減：
| Expression -> Term (PLUSTerm | MINUSTerm)* Term -> Primary (TIMES Primary | DIVIDE Primary)* |
| double Expression() throws NumberFormatException : { double i ; double value ; } { value = Term() ( <PLUS> i= Term() { value += i ; } | <MINUS> i= Term() { value -= i ; } )* { return value ; } } |
| double Term() throws NumberFormatException : { double i ; double value ; } { value = Primary() ( <TIMES> i = Primary() { value *= i ; } | <DIVIDE> i = Primary() { value /= i ; } )* { return value ; } } |
下面我們要開始支持括號，負號，以及取得上一行四則運算表達式的值。
對于詞法分析器，我們添加如下Token：
| TOKEN : { < OPEN PAR : "(" > } TOKEN : { < CLOSE PAR : ")" > } TOKEN : { < PREVIOUS : "$" > } |
對于語法分析器，對于最基本的表達式，有四種情況：
其可以是一個NUMBER，也可以是上一行四則運算表達式的值PREVIOUS，也可以是被括號括起來的一個子語法表達式，也可以是取負的一個基本語法表達式。
| Primary –> NUMBER | PREVIOUS | OPEN_PAR Expression CLOSE_PAR | MINUS Primary |
| double Primary() throws NumberFormatException : { Token t ; double d ; } { t=<NUMBER> { return Double.parseDouble( t.image ) ; } | <PREVIOUS> { return previousValue ; } | <OPEN PAR> d=Expression() <CLOSE PAR> { return d ; } | <MINUS> d=Primary() { return -d ; } } |
(6) 用javacc編譯calculator.jj來生成語法分析器和詞法分析器
最后生成的calculator.jj如下：
| options
{
static = false;
} PARSER_BEGIN(Calculator)
package org.apache.javacc.calculater;
import java.io.PrintStream ;
class Calculator {
static void main( String[] args ) throws ParseException, TokenMgrError, NumberFormatException {
Calculator parser = new Calculator( System.in ) ;
parser.start( System.out ) ;
}
double previousValue = 0.0 ;
}
PARSER_END(Calculator) SKIP : { " " }
TOKEN : { < EOL: "\n" | "\r" | "\r\n" > }
TOKEN : { < PLUS : "+" > }
TOKEN : { < MINUS : "-" > }
TOKEN : { < TIMES : "*" > }
TOKEN : { < DIVIDE : "/" > }
TOKEN : { < NUMBER : <DIGITS> | <DIGITS> "." <DIGITS> | <DIGITS> "." | "." <DIGITS>> }
TOKEN : { < #DIGITS : (["0"-"9"])+ > }
TOKEN : { < OPEN_PAR : "(" > }
TOKEN : { < CLOSE_PAR : ")" > }
TOKEN : { < PREVIOUS : "$" > } void start(PrintStream printStream) throws NumberFormatException :
{}
{
(
previousValue = Expression()
{ printStream.println( previousValue ) ; }
)*
} double Expression() throws NumberFormatException :
{
double i ;
double value ;
}
{
value = Term()
(
<PLUS>
i= Term()
{ value += i ; }
|
<MINUS>
i= Term()
{ value -= i ; }
)*
{ return value ; }
} double Term() throws NumberFormatException :
{
double i ;
double value ;
}
{
value = Primary()
(
<TIMES>
i = Primary()
{ value *= i ; }
|
<DIVIDE>
i = Primary()
{ value /= i ; }
)*
{ return value ; }
} double Primary() throws NumberFormatException :
{
Token t ;
double d ;
}
{
t=<NUMBER>
{ return Double.parseDouble( t.image ) ; }
|
<PREVIOUS>
{ return previousValue ; }
|
<OPEN_PAR> d=Expression() <CLOSE_PAR>
{ return d ; }
|
<MINUS> d=Primary()
{ return -d ; }
} |
生成的start函數如下：
final public void start(PrintStream printStream) throws ParseException, NumberFormatException {
label_1:
while (true) {
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case MINUS:
case NUMBER:
case OPEN_PAR:
case PREVIOUS:
;
break;
default:
jj_la1[0] = jj_gen;
break label_1;
}
previousValue = Expression();
printStream.println( previousValue ) ;
}
}
final public double Expression() throws ParseException, NumberFormatException {
double i ;
double value ;
value = Term();
label_2:
while (true) {
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case PLUS:
case MINUS:
;
break;
default:
jj_la1[1] = jj_gen;
break label_2;
}
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case PLUS:
jj_consume_token(PLUS);
i = Term();
value += i ;
break;
case MINUS:
jj_consume_token(MINUS);
i = Term();
value -= i ;
break;
default:
jj_la1[2] = jj_gen;
jj_consume_token(-1);
throw new ParseException();
}
}
{if (true) return value ;}
throw new Error("Missing return statement in function");
}
final public double Term() throws ParseException, NumberFormatException {
double i ;
double value ;
value = Primary();
label_3:
while (true) {
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case TIMES:
case DIVIDE:
;
break;
default:
jj_la1[3] = jj_gen;
break label_3;
}
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case TIMES:
jj_consume_token(TIMES);
i = Primary();
value *= i ;
break;
case DIVIDE:
jj_consume_token(DIVIDE);
i = Primary();
value /= i ;
break;
default:
jj_la1[4] = jj_gen;
jj_consume_token(-1);
throw new ParseException();
}
}
{if (true) return value ;}
throw new Error("Missing return statement in function");
}
final public double Primary() throws ParseException, NumberFormatException {
Token t ;
double d ;
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
case NUMBER:
t = jj_consume_token(NUMBER);
{if (true) return Double.parseDouble( t.image ) ;}
break;
case PREVIOUS:
jj_consume_token(PREVIOUS);
{if (true) return previousValue ;}
break;
case OPEN_PAR:
jj_consume_token(OPEN_PAR);
d = Expression();
jj_consume_token(CLOSE_PAR);
{if (true) return d ;}
break;
case MINUS:
jj_consume_token(MINUS);
d = Primary();
{if (true) return -d ;}
break;
default:
jj_la1[5] = jj_gen;
jj_consume_token(-1);
throw new ParseException();
}
throw new Error("Missing return statement in function");
}