- 自己动手写分布式搜索引擎
- 罗刚
- 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中。