Anrlr4 生成C++版本的语法解析器
- 2019 年 10 月 17 日
- 笔记
一、 写在前面
我最早是在2005年，首次在实际开发中实现语法解析器，当时调研了Yacc&Lex，觉得风格不是太好，关键当时yacc对多线程也支持的不太好，接着就又学习了Bison&Flex，那时Bison的版本还是v1.x.y，对C++的支持比较差，最终选择了Biso++ & Flex++，两者支持C++版本并且跨平台支持Linux和windows。业务需求是实现全文检索Contains表达式的解析，包括调研、学习、实现和测试，大致用了2月，很多时间花费在解决语法冲突、内存管理等方面。
后来换了工作单位，在2012年再次需要实现Contains表达式语法，这时的Bison和Flex都稳定支持C++版本了，所以就直接采用Bison&Flex，大约用了不到2周，实现了Contains表达式解析和单元测试。
最近一次是在2018年，需要用Java版本的Contains表达式解析，这次采用的是Antlr4，开发和测试仅用了一个周六日在家的业余时间。感觉Antlr4明显比Bison&Flex简单，对语法规则的支持很直观易懂，用在语法冲突比较少的业务环境中非常合适，更关键的是：相对于Bison，Antlr4产生的Parser可以顺手生成对应规则的嵌套类，如果象我一样喜欢Visitor风格的话，完全可以做到语法文件与代码文件分离，从而大大缩短语法解析器的开发周期，并大大降低维护难度。
但是Antlr4最大的问题是对低版本C++的支持不太好，它需要高版本的GCC，在Centos7中的GCC为4.8.5无法编译通过，好在Centos8刚刚发布，它的GCC为8.2.1，正好来试验Antlr4的C++版本来实现Contains表达式语法。
网上的Antlr4生成C++版本语法解析器的资料较少，本文侧重整理与之相关的内容，并以Contains语法表达式为例，而具体的Antlr4的学习材料请见文尾的参考材料。
二、 搭建开发环境
1)、首先是安装Centos8的虚拟机环境，如上文所述，其gcc版本为8.2.1。
2)、Antlr4需要使用jdk，在Centos8中包含了jdk1.8和jdk11，我们选择安装jdk1.8
su yum install java-1.8.0-openjdk
安装完成后查看版本
java -version openjdk version "1.8.0_201" OpenJDK Runtime Environment (build 1.8.0_201-b09) OpenJDK 64-Bit Server VM (build 25.201-b09, mixed mode)
3)、下载Antlr4的Java包，用于根据语法文件生成C++版的解析器。
在antlr的下载页https://www.antlr.org/download.html中找到Complete ANTLR 4.7.2 Java binaries jar. Complete ANTLR 4.7.2 tool, Java runtime and ST 4.0.8, which lets you run the tool and the generated code.，注：随着时间的变化antlr4版本和下载链接都会变化呀。
mkdir libs curl https://www.antlr.org/download/antlr-4.7.2-complete.jar -o ./libs/antlr-4.7.2-complete.jar
验证
java -jar ./libs/antlr-4.7.2-complete.jar ANTLR Parser Generator Version 4.7.2 -o ___ specify output directory where all output is generated -lib ___ specify location of grammars, tokens files -atn generate rule augmented transition network diagrams -encoding ___ specify grammar file encoding; e.g., euc-jp -message-format ___ specify output style for messages in antlr, gnu, vs2005 -long-messages show exception details when available for errors and warnings -listener generate parse tree listener (default) -no-listener don't generate parse tree listener -visitor generate parse tree visitor -no-visitor don't generate parse tree visitor (default) -package ___ specify a package/namespace for the generated code -depend generate file dependencies -D<option>=value set/override a grammar-level option -Werror treat warnings as errors -XdbgST launch StringTemplate visualizer on generated code -XdbgSTWait wait for STViz to close before continuing -Xforce-atn use the ATN simulator for all predictions -Xlog dump lots of logging info to antlr-timestamp.log -Xexact-output-dir all output goes into -o dir regardless of paths/package
4)、下载Antltr4的C++运行库，采用编译安装的方式。
在antlr的下载页https://www.antlr.org/download.html中找到Linux and others use source distribution: antlr4-cpp-runtime-4.7.2-source.zip (.h, .cpp)，注：随着时间的变化antlr4版本和下载链接都会变化呀。
mkdir work url https://www.antlr.org/download/antlr4-cpp-runtime-4.7.2-source.zip -o ./work/antlr4-cpp-runtime-4.7.2-source.zip mkdir cpp
cd cpp unzip ../antlr4-cpp-runtime-4.7.2-source.zip mkdir build && mkdir run && cd build cmake .. -DANTLR_JAR_LOCATION=/home/ansible/libs/antlr-4.7.2-complete.jar -DWITH_DEMO=True make su make install ll /usr/local/include/antlr4-runtime/antlr4-runtime.h ll /usr/local/lib/libantlr4*
三、编写Contains表达式解析器
Contains函数完整语法如下：
Contains(column_name,query_expression[,score_flag])
其中query_expression是一个字符串表达式，它可以由SQL解析完成。
3.1、 基本功能
功能列表如下：
1)、显式的与（AND）操作符‘&’，例如 hello & world
2)、隐式的与（AND）操作符‘空格’，例如’hello world’
3)、或（OR）操作符‘|’, 例如 hello | world
4)、非（NOT）操作符‘-’, 例如 hello – world
5)、首字词操作符‘^’, 例如 ^hello
6)、尾字词操作符‘$’, 例如 mouse$
7)、词组查询操作符 “”，例如”南大”
8)、分组操作符（）,例如( hello world ) & (cat | dog)
9)、阀值匹配符 ‘/’, 例如 “the great wall is a wonderful place”/3
10)、 NEAR搜索函数 near((term1, term2), num，order), 例如 near((great, place), 2, 1), num表示词距，order 为 0 代表无词序， 为 1代表有词序
11)、 扩展选项,搜索表达式通过”:”分作基本表达式和扩展选项两个部分，总长度的限制为255字符，其中扩展选项可以为空，目前扩展选项仅支持rank=tf，表示相关度算法采用词频而不是缺省的bm25算法。例如”南大: rank=tf” 表示搜索南大，相关度为词频。
3.2、 语法规则
query_expression具体由Contains表达式解析器完成，其语法规则用Antlr4语法描述如下：
contains_param: contains_expr |contains_expr ':' fti_optstring ; fti_optstring : fti_opt | fti_opt '&' fti_optstring ; fti_opt: ID '=' string_value ; contains_expr: contains_string | CONST_STRING '/' NUMBER | func_near_expr | '(' contains_expr ')' | contains_expr contains_expr | contains_expr OPT_AND contains_expr | contains_expr OPT_OR contains_expr | contains_expr OPT_NOT contains_expr ; contains_string: string_value | SENTENCE_HEAD string_value | SENTENCE_HEAD string_value SENTENCE_TAIL | string_value SENTENCE_TAIL ; string_value: ID | STRING | CONST_STRING | NUMBER ; func_near_expr: NEAR '(' '(' near_term_list ')' ',' NUMBER near_order ')' ; near_term_list: near_term | near_term ',' near_term_list ; near_term: func_near_expr | contains_string ; near_order: | ',' NUMBER ;
3.3、 词法规则
CONST_STRING : DQuote ( EscSeq | ~["rn\] )* DQuote ; NEAR : N E A R ; SENTENCE_HEAD : '^' ; SENTENCE_TAIL : '$' ; OPT_AND : '&' ; OPT_OR : '|' ; OPT_NOT : '-' ; NUMBER : '0' | [1-9] DecDigit* ; ID: [a-zA-Z] ([a-zA-Z] | DecDigit | '_')* ;// Identifier STRING : NameChar + ; WS : ( Hws | Vws )+ -> skip; fragment DQuote : '"' ; fragment Esc : '\' ; fragment A : [aA]; fragment B : [bB]; fragment C : [cC]; fragment D : [dD]; fragment E : [eE]; fragment F : [fF]; fragment G : [gG]; fragment H : [hH]; fragment I : [iI]; fragment J : [jJ]; fragment K : [kK]; fragment L : [lL]; fragment M : [mM]; fragment N : [nN]; fragment O : [oO]; fragment P : [pP]; fragment Q : [qQ]; fragment R : [rR]; fragment S : [sS]; fragment T : [tT]; fragment U : [uU]; fragment V : [vV]; fragment W : [wW]; fragment X : [xX]; fragment Y : [yY]; fragment Z : [zZ]; fragment DecDigits : DecDigit+ ; fragment DecDigit : [0-9] ; fragment HexDigits : HexDigit+ ; fragment HexDigit : [0-9a-fA-F] ; fragment Hws : [ t] ; fragment Vws : 'r'? [nf] ; fragment NameChar : NameStartChar | '0'..'9' | '_' | 'u00B7' | 'u0300'..'u036F' | 'u203F'..'u2040' ; fragment NameStartChar : 'A'..'Z' | 'a'..'z' | 'u00C0'..'u00D6' | 'u00D8'..'u00F6' | 'u00F8'..'u02FF' | 'u0370'..'u037D' | 'u037F'..'u1FFF' | 'u200C'..'u200D' | 'u2070'..'u218F' | 'u2C00'..'u2FEF' | 'u3001'..'uD7FF' | 'uF900'..'uFDCF' | 'uFDF0'..'uFFFD' ; fragment UnicodeEsc : 'u' (HexDigit (HexDigit (HexDigit HexDigit?)?)?)? ; // Any kind of escaped character that we can embed within ANTLR literal strings. fragment EscSeq : Esc ( [btnfr"'\] // The standard escaped character set such as tab, newline, etc. | UnicodeEsc // A Unicode escape sequence | . // Invalid escape character | EOF // Incomplete at EOF ) ;
四、代码实现
Antlr4支持Visitor模式和Listener模式，一个是在语法分析完成后执行遍历语法树，一个是在语法分析过程中实时处理，相当于XML分析的DOM模式和SAX模式。在本次实验中因为表达式是相对简单的小对象，所以仅考虑Visitor模式。
由语法规则文件生成C++代码：
java -jar /home/ansible/libs/antlr-4.7.2-complete.jar -Dlanguage=Cpp FtiExpr.g4 -visitor -no-listener -o ./antlr4
在antlr4下生成cpp代码文件列表如下：
词法分析器 FtiExprLexer.h FtiExprLexer.cpp 语法分析器 FtiExprParser.h FtiExprParser.cpp Visitor模式访问语法树的抽象类 FtiExprVisitor.h FtiExprVisitor.cpp Visitor模式访问语法树的最简示例类 FtiExprBaseVisitor.h FtiExprBaseVisitor.cpp
对于Visitor模式，我们自然要从FtiExprVisitor派生出遍历语法树的类，同时一般还会从BaseErrorListener派生出合适的错误处理类，来收集错误信息。
驱动框架的代码如下：
///brief 分析Contains表达式 ///param strExpr 表达式字符串 ///param strOutput 如果符合语法，返回格式化后的表达式字符串，反之则返回分析过程中的错误信息 ///return 是否符合语法 true 符合；false 不符合 bool CTestFtiExprVisitorFixture::ParseString(const std::string &strExpr, std::string &strOutput) { bool bParse = false; ANTLRInputStream input(strExpr); FtiExprLexer lexer(&input); CommonTokenStream tokens(&lexer); FtiExprParser parser(&tokens); parser.removeErrorListeners(); CFtiExprErrorListener listenerError; parser.addErrorListener(&listenerError); FtiExprParser::Contains_paramContext *pParamContext = parser.contains_param(); if(listenerError.m_strErrMsg.empty()) { CTestFtiExprVisitor visitor; antlrcpp::Any strExpr = visitor.visit(pParamContext); strOutput = strExpr.as<std::string>(); bParse = true; } else { char cLine[32],cCol[32]; snprintf(cLine, 31, "%d", listenerError.m_nLine); snprintf(cCol, 31, "%d", listenerError.m_nPositionInLine); strOutput = "Line: " + std::string(cLine) + " Col: " + std::string(cCol) + " Msg:" + listenerError.m_strErrMsg; } return bParse; }
主要就是字符串=》词法分析器 =》Token串 =》语法规则
FtiExprParser::Contains_paramContext *pParamContext = parser.contains_param();
语法解析
antlrcpp::Any strExpr = visitor.visit(pParamContext);
进行语法树遍历。
其他测试的主要代码如下：
void CTestFtiExprVisitorFixture::TestParseOk(std::string strExpr, std::string strExpected) { std::string strOutput; ParseString(strExpr, strOutput); CPPUNIT_ASSERT_EQUAL(strExpected, strOutput); } void CTestFtiExprVisitorFixture::TestParseFail(std::string strExpr, std::string strExpected) { std::string strOutput; ParseString(strExpr, strOutput); CPPUNIT_ASSERT_EQUAL(strExpected, strOutput); } void CTestFtiExprVisitorFixture::TestParsePass(void) { TestParseOk("tianjin", "tianjin"); TestParseOk("中国", "中国"); TestParseOk("tianjin", "tianjin"); TestParseOk("12345", "12345"); TestParseOk(""tianjin"", ""tianjin""); TestParseOk("^tianjin", "^ tianjin"); TestParseOk("^tianjin$", "^ tianjin $"); TestParseOk("tianjin$", "tianjin $"); TestParseOk(""tianjin beijing"/ 12", ""tianjin beijing" / 12"); TestParseOk("tianjin beijing", "( tianjin ) & ( beijing )"); TestParseOk("tianjin & beijing", "( tianjin ) & ( beijing )"); TestParseOk("tianjin | beijing", "( tianjin ) | ( beijing )"); TestParseOk("tianjin - beijing", "( tianjin ) - ( beijing )"); TestParseOk("tianjin beijing | shangxi hebei", "( ( tianjin ) & ( beijing ) ) | ( ( shangxi ) & ( hebei ) )"); TestParseOk("(tianjin beijing) | (shangxi hebei)", "( ( ( tianjin ) & ( beijing ) ) ) | ( ( ( shangxi ) & ( hebei ) ) )"); TestParseOk("NEAR((tianjin , beijing),10)", "NEAR((tianjin,beijing),10)"); TestParseOk("NEAR((tianjin,beijing),10,1)", "NEAR((tianjin,beijing),10,1)"); } void CTestFtiExprVisitorFixture::TestParseNoPass(void) { TestParseFail("", "Line: 1 Col: 0 Msg:mismatched input '<EOF>' expecting {'(', CONST_STRING, NEAR, '^', NUMBER, ID, STRING}"); } void CTestFtiExprVisitorFixture::TestFtiOpt(void) { TestParseOk("NEAR((tianjin,beijing),10,1) : rank = wordcount", "NEAR((tianjin,beijing),10,1) : rank = wordcount"); TestParseOk("NEAR((tianjin,beijing),10,1) : rank = wordcount&mode=fast", "NEAR((tianjin,beijing),10,1) : rank = wordcount & mode = fast"); TestParseOk("NEAR((12tianjin,beijing),10,1) : rank = wordcount", "NEAR((12tianjin,beijing),10,1) : rank = wordcount"); TestParseFail("NEAR((tianjin,beijing),10,1) : 1rank = wordcount", "Line: 1 Col: 31 Msg:mismatched input '1rank' expecting ID"); }
完整代码示例在：https://github.com/ZhenYongFan/Blog/tree/master/TestFtiExpr
五、参考资料
官方资料，生成目标语言为C++的Antlr4
https://github.com/antlr/antlr4/blob/master/doc/cpp-target.md
ANTLR 4简明教程
https://www.cntofu.com/book/115/index.html
Antlr4 —词法规则
https://blog.csdn.net/yangguosb/article/details/85624640
antlr v4 使用指南连载4——词法规则入门之黄金定律
https://www.cnblogs.com/laud/p/antlr4_4.html
antlr v4 使用指南连载5——如何编写词法定义
https://www.cnblogs.com/laud/p/anltrv4_5.html
