12
简单语法解析器实现参考
source link: http://www.cnblogs.com/yougewe/p/13774289.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
有时候，我们为了屏蔽一些底层的差异，我们会要求上游系统按照某种约定进行传参。而在我们自己的系统层则会按照具体的底层协议进行适配，这是通用的做法。但当我们要求上游系统传入的参数非常复杂时，也许我们会有一套自己的语法定义，用以减轻所有参数的不停变化。比如sql协议，就是一个一级棒的语法，同样是调用底层功能，但它可以很方便地让用户传入任意的参数。
如果我们自己能够实现一套类似的东西，想来应该蛮有意思的。
不过，我们完全没有必要要实现一整套完整的东西，我们只是要体验下这个语法解析的过程，那就好办了。本文就来给个简单的解析示例，供看官们参考。
1. 实现目标描述
目标：
基于我们自定义的一套语法，我们要实现一套类似于sql解析的工具，它可以帮助我们检查语法错误、应对底层不同的查询引擎，比如可能是 ES, HIVE, SPARK, PRESTO... 即我们可能将用户传入的语法转换为任意种目标语言的语法，这是我们的核心任务。
前提：
为简单化起见，我们并不想实现一整套的东西，我们仅处理where条件后面的东西。
定义：
$1234: 定义为字段信息, 我们可以通过该字段查找出一些更多的信息;
and/or/like...: 大部分时候我们都遵循sql语法, 含义一致;
#{xxx}: 系统关键字定义格式, xxx 为具体的关键字;
arr['f1']: 为数组格式的字段;
示例：
$15573 = 123 and (my_udf($123568, $82949) = 1) or $39741 = #{day+1} and $35289 like '%ccc'
将会被翻译成ES:(更多信息的字段替换请忽略)
$15573 = 123 and ( $123568 = 1 ) or $39741 = '2020-10-07' and $35289 like '%ccc'
实际上整个看下来，和一道普通的算法题差不太多呢。但实际想要完整实现这么个小东西，也是要费不少精力的。
2. 整体实现思路
我们要做一个解析器，或者说翻译器，首先第一步，自然是要从根本上理解原语义，然后再根据目标语言的表达方式，转换过去就可以了。
如果大家有看过一些编译原理方面的书，就应该知道，整个编译流程大概分为: 词法分析；语法分析；语义分析；中间代码生成；代码优化；目标代码； 这么几个过程，而每个过程往往又是非常复杂的，而最复杂的往往又是其上下文关系。不过，我们不想搞得那么复杂（也搞不了）。
虽然我们不像做一个编译器一样复杂，但我们仍然可以参考其流程，可以为我们提供比较好的思路。
我们就主要做3步就可以了：1. 分词；2. 语义分析； 3. 目标代码生成；而且为了进一步简化工作，我们省去了复杂的上下文依赖分析，我们假设所有的语义都可以从第一个关键词中获得，比如遇到一个函数，我就知道接下来会有几个参数出现。而且我们不处理嵌套关系。
所以，我们的工作就变得简单起来。
3. 具体代码实现
我们做这个解析器的目的，是为了让调用者方便，它仅仅作为一个工具类存在，所以，我们需要将入口做得非常简单。
这里主要为分为两个入口：1. 传入原始语法，返回解析出的语法树； 2. 调用语法树的translateTo 方法，将原始语法转换为目标语法；
具体如下：
import com.my.mvc.app.common.helper.parser.*;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.StringUtils;
import java.util.*;
/**
* 功能描述: 简单语法解析器实现示例
*
*/
@Slf4j
public class SimpleSyntaxParser {
/**
* 严格模式解析语法
*
* @see #parse(String, boolean)
*/
public static ParsedClauseAst parse(String rawClause) {
return parse(rawClause, true);
}
/**
* 解析传入词为db可识别的语法
*
* @param rawClause 原始语法, 如:
* $15573 = 123 and (week_diff($123568, $82949) = 1) or $39741 like '%abc%' (week_diff($35289)) = -1
* @param strictMode 是否是严格模式, true:是, false:否
* @return 解析后的结构
*/
public static ParsedClauseAst parse(String rawClause, boolean strictMode) {
log.info("开始解析: " + rawClause);
List<TokenDescriptor> tokens = tokenize(rawClause, strictMode);
Map<String, Object> idList = enhanceTokenType(tokens);
return buildAst(tokens, idList);
}
/**
* 构建抽象语法树对象
*
* @param tokens 分词解析出的tokens
* @param idList id信息（解析数据源参照）
* @return 构建好的语法树
*/
private static ParsedClauseAst buildAst(List<TokenDescriptor> tokens,
Map<String, Object> idList) {
List<SyntaxStatement> treesFlat = new ArrayList<>(tokens.size());
Iterator<TokenDescriptor> tokenItr = tokens.iterator();
while (tokenItr.hasNext()) {
TokenDescriptor token = tokenItr.next();
String word = token.getRawWord();
TokenTypeEnum tokenType = token.getTokenType();
SyntaxStatement branch;
switch (tokenType) {
case FUNCTION_SYS_CUSTOM:
String funcName = word.substring(0, word.indexOf('(')).trim();
SyntaxStatementHandlerFactory handlerFactory
= SyntaxSymbolTable.getUdfHandlerFactory(funcName);
branch = handlerFactory.newHandler(token, tokenItr, tokenType);
treesFlat.add(branch);
break;
case KEYWORD_SYS_CUSTOM:
branch = SyntaxSymbolTable.getSysKeywordHandlerFactory()
.newHandler(token, tokenItr, tokenType);
treesFlat.add(branch);
break;
case KEYWORD_SQL:
branch = SyntaxSymbolTable.getSqlKeywordHandlerFactory()
.newHandler(token, tokenItr, tokenType);
treesFlat.add(branch);
break;
case WORD_NORMAL:
case WORD_NUMBER:
case WORD_STRING:
case CLAUSE_SEPARATOR:
case SIMPLE_MATH_OPERATOR:
case WORD_ARRAY:
case COMPARE_OPERATOR:
case FUNCTION_NORMAL:
case ID:
case FUNCTION_SQL:
default:
// 未解析的情况，直接使用原始值解析器处理
branch = SyntaxSymbolTable.getCommonHandlerFactory()
.newHandler(token, tokenItr, tokenType);
treesFlat.add(branch);
break;
}
}
return new ParsedClauseAst(idList, treesFlat);
}
/**
* 语义增强处理
*
* 加强token类型描述，并返回 id 信息
*/
private static Map<String, Object> enhanceTokenType(List<TokenDescriptor> tokens) {
Map<String, Object> idList = new HashMap<>();
for (TokenDescriptor token : tokens) {
String word = token.getRawWord();
TokenTypeEnum newTokenType = token.getTokenType();
switch (token.getTokenType()) {
case WORD_NORMAL:
if(word.startsWith("$")) {
newTokenType = TokenTypeEnum.ID;
idList.put(word, word.substring(1));
}
else if(StringUtils.isNumeric(word)) {
newTokenType = TokenTypeEnum.WORD_NUMBER;
}
else {
newTokenType = SyntaxSymbolTable.keywordTypeOf(word);
}
token.changeTokenType(newTokenType);
break;
case WORD_STRING:
// 被引号包围的关键字，如 '%#{monthpart}%'
String innerSysCustomKeyword = readSplitWord(
word.toCharArray(), 1, "#{", "}");
if(innerSysCustomKeyword.length() > 3) {
newTokenType = TokenTypeEnum.KEYWORD_SYS_CUSTOM;
}
token.changeTokenType(newTokenType);
break;
case FUNCTION_NORMAL:
newTokenType = SyntaxSymbolTable.functionTypeOf(word);
token.changeTokenType(newTokenType);
break;
}
}
return idList;
}
/**
* 查询语句分词操作
*
* 拆分为单个细粒度的词如:
* 单词
* 分隔符
* 运算符
* 数组
* 函数
*
* @param rawClause 原始查询语句
* @param strictMode 是否是严格模式, true:是, false:否
* @return token化的单词
*/
private static List<TokenDescriptor> tokenize(String rawClause, boolean strictMode) {
char[] clauseItr = rawClause.toCharArray();
List<TokenDescriptor> parsedTokenList = new ArrayList<>();
Stack<ColumnNumDescriptor> specialSeparatorStack = new Stack<>();
int clauseLength = clauseItr.length;
StringBuilder field;
String fieldGot;
char nextChar;
outer:
for (int i = 0; i < clauseLength; ) {
char currentChar = clauseItr[i];
switch (currentChar) {
case '\'':
case '\"':
fieldGot = readSplitWord(clauseItr, i,
currentChar, currentChar);
i += fieldGot.length();
parsedTokenList.add(
new TokenDescriptor(fieldGot, TokenTypeEnum.WORD_STRING));
continue outer;
case '[':
case ']':
case '(':
case ')':
case '{':
case '}':
if(specialSeparatorStack.empty()) {
specialSeparatorStack.push(
ColumnNumDescriptor.newData(i, currentChar));
parsedTokenList.add(
new TokenDescriptor(currentChar,
TokenTypeEnum.CLAUSE_SEPARATOR));
break;
}
parsedTokenList.add(
new TokenDescriptor(currentChar,
TokenTypeEnum.CLAUSE_SEPARATOR));
char topSpecial = specialSeparatorStack.peek().getKeyword().charAt(0);
if(topSpecial == '(' && currentChar == ')'
|| topSpecial == '[' && currentChar == ']'
|| topSpecial == '{' && currentChar == '}') {
specialSeparatorStack.pop();
break;
}
specialSeparatorStack.push(
ColumnNumDescriptor.newData(i, currentChar));
break;
case ' ':
// 空格忽略
break;
case '@':
nextChar = clauseItr[i + 1];
// @{} 扩展id, 暂不解析, 原样返回
if(nextChar == '{') {
fieldGot = readSplitWord(clauseItr, i,
"@{", "}@");
i += fieldGot.length();
parsedTokenList.add(
new TokenDescriptor(fieldGot,
TokenTypeEnum.ID));
continue outer;
}
break;
case '#':
nextChar = clauseItr[i + 1];
// #{} 系统关键字标识
if(nextChar == '{') {
fieldGot = readSplitWord(clauseItr, i,
"#{", "}");
i += fieldGot.length();
parsedTokenList.add(
new TokenDescriptor(fieldGot,
TokenTypeEnum.KEYWORD_SYS_CUSTOM));
continue outer;
}
break;
case '+':
case '-':
case '*':
case '/':
nextChar = clauseItr[i + 1];
if(currentChar == '-'
&& nextChar >= '0' && nextChar <= '9') {
StringBuilder numberBuff = new StringBuilder(currentChar + "" + nextChar);
++i;
while ((i + 1) < clauseLength){
nextChar = clauseItr[i + 1];
if(nextChar >= '0' && nextChar <= '9'
|| nextChar == '.') {
++i;
numberBuff.append(nextChar);
continue;
}
break;
}
parsedTokenList.add(
new TokenDescriptor(numberBuff.toString(),
TokenTypeEnum.WORD_NUMBER));
break;
}
parsedTokenList.add(
new TokenDescriptor(currentChar,
TokenTypeEnum.SIMPLE_MATH_OPERATOR));
break;
case '=':
case '>':
case '<':
case '!':
// >=, <=, !=, <>
nextChar = clauseItr[i + 1];
if(nextChar == '='
|| currentChar == '<' && nextChar == '>') {
++i;
parsedTokenList.add(
new TokenDescriptor(currentChar + "" + nextChar,
TokenTypeEnum.COMPARE_OPERATOR));
break;
}
parsedTokenList.add(
new TokenDescriptor(currentChar,
TokenTypeEnum.COMPARE_OPERATOR));
break;
default:
field = new StringBuilder();
TokenTypeEnum tokenType = TokenTypeEnum.WORD_NORMAL;
do {
currentChar = clauseItr[i];
field.append(currentChar);
if(i + 1 < clauseLength) {
// 去除函数前置名后置空格
if(SyntaxSymbolTable.isUdfPrefix(field.toString())) {
do {
if(clauseItr[i + 1] != ' ') {
break;
}
++i;
} while (i + 1 < clauseLength);
}
nextChar = clauseItr[i + 1];
if(nextChar == '(') {
fieldGot = readSplitWord(clauseItr, i + 1,
nextChar, ')');
field.append(fieldGot);
tokenType = TokenTypeEnum.FUNCTION_NORMAL;
i += fieldGot.length();
break;
}
if(nextChar == '[') {
fieldGot = readSplitWord(clauseItr, i + 1,
nextChar, ']');
field.append(fieldGot);
tokenType = TokenTypeEnum.WORD_ARRAY;
i += fieldGot.length();
break;
}
if(isSpecialChar(nextChar)) {
// 严格模式下，要求 -+ 符号前后必须带空格, 即会将所有字母后紧连的 -+ 视为字符连接号
// 非严格模式下, 即只要是分隔符即停止字符解析(非标准分隔)
if(!strictMode
|| nextChar != '-' && nextChar != '+') {
break;
}
}
++i;
}
} while (i + 1 < clauseLength);
parsedTokenList.add(
new TokenDescriptor(field.toString(), tokenType));
break;
}
// 正常单字解析迭代
i++;
}
if(!specialSeparatorStack.empty()) {
ColumnNumDescriptor lineNumTableTop = specialSeparatorStack.peek();
throw new RuntimeException("检测到未闭合的符号, near '"
+ lineNumTableTop.getKeyword()+ "' at column "
+ lineNumTableTop.getColumnNum());
}
return parsedTokenList;
}
/**
* 从源数组中读取某类词数据
*
* @param src 数据源
* @param offset 要搜索的起始位置 offset
* @param openChar word 的开始字符，用于避免循环嵌套 如: '('
* @param closeChar word 的闭合字符 如: ')'
* @return 解析出的字符
* @throws RuntimeException 解析不到正确的单词时抛出
*/
private static String readSplitWord(char[] src, int offset,
char openChar, char closeChar)
throws RuntimeException {
StringBuilder builder = new StringBuilder();
for (int i = offset; i < src.length; i++) {
if(openChar == src[i]) {
int aroundOpenCharNum = -1;
do {
builder.append(src[i]);
// 注意 openChar 可以 等于 closeChar
if(src[i] == openChar) {
aroundOpenCharNum++;
}
if(src[i] == closeChar) {
aroundOpenCharNum--;
}
} while (++i < src.length
&& (aroundOpenCharNum > 0 || src[i] != closeChar));
if(aroundOpenCharNum > 0
|| (openChar == closeChar && aroundOpenCharNum != -1)) {
throw new RuntimeException("syntax error, un closed clause near '"
+ builder.toString() + "' at column " + --i);
}
builder.append(closeChar);
return builder.toString();
}
}
// 未找到匹配
return "";
}
/**
* 重载另一版，适用特殊场景 (不支持嵌套)
*
* @see #readSplitWord(char[], int, char, char)
*/
private static String readSplitWord(char[] src, int offset,
String openChar, String closeChar)
throws RuntimeException {
StringBuilder builder = new StringBuilder();
for (int i = offset; i < src.length; i++) {
if(openChar.charAt(0) == src[i]) {
int j = 0;
while (++j < openChar.length() && ++i < src.length) {
if(openChar.charAt(j) != src[i]) {
break;
}
}
// 未匹配开头
if(j < openChar.length()) {
continue;
}
builder.append(openChar);
while (++i < src.length){
int k = 0;
if(src[i] == closeChar.charAt(0)) {
while (++k < closeChar.length() && ++i < src.length) {
if(closeChar.charAt(k) != src[i]) {
break;
}
}
if(k < closeChar.length()) {
throw new RuntimeException("un closed syntax, near '"
+ new String(src, i - k, k)
+ ", at column " + (i - k));
}
builder.append(closeChar);
break;
}
builder.append(src[i]);
}
return builder.toString();
}
}
// 未找到匹配
return " ";
}
/**
* 检测字符是否特殊运算符
*
* @param value 给定检测字符
* @return true:是特殊字符, false:普通
*/
private static boolean isSpecialChar(char value) {
return SyntaxSymbolTable.OPERATOR_ALL.indexOf(value) != -1;
}
}
入口即是 parse() 方法。其中，着重需要说明的是：我们必须要完整解释出所有语义，所以，我们需要为每个token做类型定义，且每个具体语法需要有相应的处理器进行处理。这些东西，在解析完成时就是固定的了。但具体需要翻译成什么语言，需要由用户进行定义，以便灵活使用。
接下来我们来看看如何进行翻译：
import lombok.extern.slf4j.Slf4j;
import java.util.List;
import java.util.Map;
/**
* 功能描述: 解析出的各小块语句
*
*/
@Slf4j
public class ParsedClauseAst {
/**
* id 信息容器
*/
private Map<String, Object> idMapping;
/**
* 语法树 列表
*/
private List<SyntaxStatement> ast;
public ParsedClauseAst(Map<String, Object> idMapping,
List<SyntaxStatement> ast) {
this.idMapping = idMapping;
this.ast = ast;
}
public Map<String, Object> getidMapping() {
return idMapping;
}
/**
* 转换语言表达式
*
* @param sqlType sql类型
* @see TargetDialectTypeEnum
* @return 翻译后的sql语句
*/
public String translateTo(TargetDialectTypeEnum sqlType) {
StringBuilder builder = new StringBuilder();
for (SyntaxStatement tree : ast) {
builder.append(tree.translateTo(sqlType));
}
String targetCode = builder.toString().trim();
log.info("翻译成目标语言:{}, targetCode: {}", sqlType, targetCode);
return targetCode;
}
@Override
public String toString() {
return "ParsedClauseAst{" +
"idMapping=" + idMapping +
", ast=" + ast +
'}';
}
}
这里的翻译过程，实际上就是一个委托的过程，因为所有的语义都已被封装到具体的处理器中，所以我们只需处理好各细节就可以了。最后将所有小语句拼接起来，就得到我们最终要的目标语言了。所以，具体翻译的重点工作，需要各自处理，这是很合理的事。
大体的思路和实现就是如上，着实也简单。但可能你还跑不起来以上 demo, 因为还有非常多的细节。
4. token类型定义
我们需要为每一个token有一个准确的描述，以便在后续的处理中，能够准确处理。
/**
* 功能描述: 拆分的token 描述
*
*/
public class TokenDescriptor {
/**
* 原始字符串
*/
private String rawWord;
/**
* token类型
*
* 用于确定如何使用该token
* 或者该token是如何被分割出的
*/
private TokenTypeEnum tokenType;
public TokenDescriptor(String rawWord, TokenTypeEnum tokenType) {
this.rawWord = rawWord;
this.tokenType = tokenType;
}
public TokenDescriptor(char rawWord, TokenTypeEnum tokenType) {
this.rawWord = rawWord + "";
this.tokenType = tokenType;
}
public void changeTokenType(TokenTypeEnum tokenType) {
this.tokenType = tokenType;
}
public String getRawWord() {
return rawWord;
}
public TokenTypeEnum getTokenType() {
return tokenType;
}
@Override
public String toString() {
return "T{" +
"rawWord='" + rawWord + '\'' +
", tokenType=" + tokenType +
'}';
}
}
// ------------- TokenTypeEnum -----------------
/**
* 功能描述: 单个不可分割的token 类型定义
*
*/
public enum TokenTypeEnum {
LABEL_ID("基础id如$123"),
FUNCTION_NORMAL("是函数但类型未知（未解析）"),
FUNCTION_SYS_CUSTOM("系统自定义函数如week_diff(a)"),
FUNCTION_SQL("sql中自带函数如date_diff(a)"),
KEYWORD_SYS_CUSTOM("系统自定义关键字如datepart"),
KEYWORD_SQL("sql中自带的关键字如and"),
CLAUSE_SEPARATOR("语句分隔符，如'\"(){}[]"),
SIMPLE_MATH_OPERATOR("简单数学运算符如+-*/"),
COMPARE_OPERATOR("比较运算符如=><!=>=<="),
WORD_ARRAY("数组类型字段如 arr['key1']"),
WORD_STRING("字符型具体值如 '%abc'"),
WORD_NUMBER("数字型具体值如 123.4"),
WORD_NORMAL("普通字段可以是数据库字段也可以是用户定义的字符"),
;
private TokenTypeEnum(String remark) {
// ignore...
}
}
如上，基本可以描述各词的类型了，如果不够，我们可以视情况新增即可。从这里，我们可以准确地看出一些分词的规则。
5. 符号表的定义
很明显，我们需要一个统筹所有可被处理的词组的地方，这就是符号表，我们可以通过符号表，准确的查到哪些是系统关键词，哪些是udf，哪些是被支持的方法等等。这是符号表的职责。而且，符号表也可以支持注册，从而使其可扩展。具体如下：
import com.my.mvc.app.common.helper.parser.keyword.SysCustomKeywordAstHandler;
import com.my.mvc.app.common.helper.parser.udf.SimpleUdfAstHandler;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
* 功能描述: 语法符号表(提供查询入口)
*/
public class SyntaxSymbolTable {
/**
* 所有操作符
*/
public static final String OPERATOR_ALL = "'\"[ ](){}=+-*/><!";
/**
* 所有处理器
*/
private static final Map<String, SyntaxStatementHandlerFactory> handlers
= new ConcurrentHashMap<>();
private static final String SYS_CUSTOM_KEYWORD_REF_NAME = "__sys_keyword_handler";
private static final String SQL_KEYWORD_REF_NAME = "__sql_keyword_handler";
private static final String COMMON_HANDLER_REF_NAME = "__common_handler";
static {
// 注册udf, 也可以放到外部调用
registerUdf(
(masterToken, candidates, handlerType)
-> new SimpleUdfAstHandler(masterToken, candidates,
TokenTypeEnum.FUNCTION_SYS_CUSTOM),
"week_diff", "fact.week_diff", "default.week_diff");
// 注册系统自定义关键字处理器
handlers.putIfAbsent(SYS_CUSTOM_KEYWORD_REF_NAME, SysCustomKeywordAstHandler::new);
// 注册兜底处理器
handlers.putIfAbsent(COMMON_HANDLER_REF_NAME, CommonConditionAstBranch::new);
}
/**
* 判断给定词汇的 keyword 类型
*
* @param keyword 指定判断词
* @return 系统自定义关键字、sql关键字、普通字符
*/
public static TokenTypeEnum keywordTypeOf(String keyword) {
if("datepart".equals(keyword)) {
return TokenTypeEnum.KEYWORD_SYS_CUSTOM;
}
if("and".equals(keyword)
|| "or".equals(keyword)
|| "in".equals(keyword)) {
return TokenTypeEnum.KEYWORD_SQL;
}
return TokenTypeEnum.WORD_NORMAL;
}
/**
* 注册一个 udf 处理器实例
*
* @param handlerFactory 处理器工厂类
* tokens 必要参数列表，说到底自定义
* @param callNameAliases 函数调用别名, 如 wee_diff, fact.week_diff...
*/
public static void registerUdf(SyntaxStatementHandlerFactory handlerFactory,
String... callNameAliases) {
for (String alias : callNameAliases) {
handlers.put(alias, handlerFactory);
}
}
/**
* 获取udf处理器的工厂类 （可用于判定系统是否支持）
*
* @param udfFunctionName 函数名称
* @return 对应的工厂类
*/
public static SyntaxStatementHandlerFactory getUdfHandlerFactory(String udfFunctionName) {
SyntaxStatementHandlerFactory factory= handlers.get(udfFunctionName);
if(factory == null) {
throw new RuntimeException("不支持的函数操作: " + udfFunctionName);
}
return factory;
}
/**
* 获取系统自定义关键字处理器的工厂类 应固定格式为 #{xxx+1}
*
* @return 对应的工厂类
*/
public static SyntaxStatementHandlerFactory getSysKeywordHandlerFactory() {
return handlers.get(SYS_CUSTOM_KEYWORD_REF_NAME);
}
/**
* 获取sql关键字处理器的工厂类 遵守 sql 协议
*
* @return 对应的工厂类
*/
public static SyntaxStatementHandlerFactory getSqlKeywordHandlerFactory() {
return handlers.get(COMMON_HANDLER_REF_NAME);
}
/**
* 获取通用处理器的工厂类（兜底）
*
* @return 对应的工厂类
*/
public static SyntaxStatementHandlerFactory getCommonHandlerFactory() {
return handlers.get(COMMON_HANDLER_REF_NAME);
}
/**
* 检测名称是否是udf 函数前缀
*
* @param udfFunctionName 函数名称
* @return true:是, false:其他关键词
*/
public static boolean isUdfPrefix(String udfFunctionName) {
return handlers.get(udfFunctionName) != null;
}
/**
* 判断给定词汇的 keyword 类型
*
* @param functionFullDesc 函数整体使用方式
* @return 系统自定义函数，系统函数、未知
*/
public static TokenTypeEnum functionTypeOf(String functionFullDesc) {
String funcName = functionFullDesc.substring(0, functionFullDesc.indexOf('('));
funcName = funcName.trim();
if("my_udf".equals(funcName)) {
return TokenTypeEnum.FUNCTION_SYS_CUSTOM;
}
return TokenTypeEnum.FUNCTION_NORMAL;
}
}
实际上，整个解析器的完善过程，大部分时候就是符号表的一个完善过程。支持的符号越多了，则功能就越完善了。我们通过一个个的工厂类，实现了具体解析类的细节，屏蔽到内部的变化，从而使变化对上层的无感知。
以下为处理器的定义，及工厂类定义：
import java.util.Iterator;
/**
* 功能描述: 组合标签语句处理器 工厂类
*
* 生产提供各处理器实例
*
*/
public interface SyntaxStatementHandlerFactory {
/*
* 获取本语句对应的操作数量
*
* 其中, 函数调用会被解析为单token, 如 my_udf($123) = -1
* my_udf($123) 为函数调用, 算一个token
* '=' 为运算符，算第二个token
* '-1' 为右值, 算第三个token
* 所以此例应返回 3
*
* 此实现由具体的 StatementHandler 处理
* 从 candidates 中获取即可
*
*/
/**
* 生成一个新的语句处理器实例
*
* @param masterToken 主控token, 如关键词，函数调用...
* @param candidates 候选词组（后续词组）, 此实现基于本解析器无全局说到底关联性
* @param handlerType 处理器类型，如函数、关键词、sql...
* @return 对应的处理器实例
*/
SyntaxStatement newHandler(TokenDescriptor masterToken,
Iterator<TokenDescriptor> candidates,
TokenTypeEnum handlerType);
}
// ----------- SyntaxStatement ------------------
/**
* 功能描述: 单个小词组处理器
*
*/
public interface SyntaxStatement {
/**
* 转换成目标语言表示
*
* @param targetSqlType 目标语言类型 es|hive|presto|spark
* @return 翻译后的语言表示
*/
String translateTo(TargetDialectTypeEnum targetSqlType);
}
有了这符号表和处理器的接口定义，后续的工作明显方便很多。
最后，还有一个行号指示器，需要定义下。它可以帮助我们给出准确的错误信息提示，从而减少排错时间。
/**
* 功能描述: 行列号指示器
*/
public class ColumnNumDescriptor {
/**
* 列号
*/
private int columnNum;
/**
* 关键词
*/
private String keyword;
public ColumnNumDescriptor(int columnNumFromZero, String keyword) {
this.columnNum = columnNumFromZero + 1;
this.keyword = keyword;
}
public static ColumnNumDescriptor newData(int columnNum, String data) {
return new ColumnNumDescriptor(columnNum, data);
}
public static ColumnNumDescriptor newData(int columnNum, char dataChar) {
return new ColumnNumDescriptor(columnNum, dataChar + "");
}
public int getColumnNum() {
return columnNum;
}
public String getKeyword() {
return keyword;
}
@Override
public String toString() {
return "Col{" +
"columnNum=" + columnNum +
", keyword='" + keyword + '\'' +
'}';
}
}
6. 目标语言定义
系统可支持的目标语言是有限的，应当将其定义为枚举类型，以便用户规范使用。
/**
* 功能描述: 组合标签可被翻译成的 方言枚举
*
*/
public enum TargetDialectTypeEnum {
ES,
HIVE,
PRESTO,
SPARK,
/**
* 原始语句
*/
RAW,
;
}
如果有一天，你新增了一个语言的实现，那你就可以将类型加上，这样用户也就可以调用了。
7. 词义处理器实现示例
解析器的几大核心之一就是词义处理器，前面很多的工作都是准备性质的，比如分词，定义等。前面也看到，我们将词义处理器统一定义了一个接口: SyntaxStatement . 即所有词义处理，都只需实现该接口即可。但该词义至少得获取到相应的参数，所以通过一个通用的工厂类生成该处理器，也即需要在构造器中处理好上下文关系。
首先，我们需要有一个兜底的处理器，以便在未知的情况下，可以保证原语义正确，而非直接出现异常，除非确认所有语义已实现，否则该兜底处理器都是有存在的必要的。
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 功能描述: 通用抽象语法树处理器（分支）
*
*/
public class CommonConditionAstBranch implements SyntaxStatement {
/**
* 扩展词组列表（如 = -1, > xxx ...）
*
* 相当于词组上下文
*/
protected final List<TokenDescriptor> extendTokens = new ArrayList<>();
/**
* 类型: 函数, 关键词, 分隔符...
*/
protected TokenTypeEnum tokenType;
/**
* 主控词（如 and, my_udf($123)）
*
* 可用于确定该语义大方向
*/
protected TokenDescriptor masterToken;
public CommonConditionAstBranch(TokenDescriptor masterToken,
Iterator<TokenDescriptor> candidates,
TokenTypeEnum tokenType) {
this.masterToken = masterToken;
this.tokenType = tokenType;
for (int i = 0; i < getFixedExtTokenNum(); i++) {
if(!candidates.hasNext()) {
throw new RuntimeException("用法不正确: ["
+ masterToken.getRawWord() + "] 缺少变量");
}
addExtendToken(candidates.next());
}
}
/**
* 添加附加词组，根据各解析器需要添加
*/
protected void addExtendToken(TokenDescriptor token) {
extendTokens.add(token);
}
@Override
public String translateTo(TargetDialectTypeEnum targetSqlType) {
String separator = " ";
StringBuilder sb = new StringBuilder(masterToken.getRawWord()).append(separator);
extendTokens.forEach(r -> sb.append(r.getRawWord()).append(separator));
return sb.toString();
}
/**
* 解析方法固定参数数量，由父类统一解析
*/
protected int getFixedExtTokenNum() {
return 0;
}
@Override
public String toString() {
return "CTree{" +
"extendTokens=" + extendTokens +
", tokenType=" + tokenType +
", masterToken=" + masterToken +
'}';
}
}
该处理器被注册到符号表中，以 __common_handler 查找。
接下来，我们再另一个处理器的实现: udf。 udf 即用户自定义函数，这应该是标准sql协议中不存在的关键词，为业务需要而自行实现的函数，它在有的语言里，可以表现为注册后的函数，而在有语言里，我们只能转换为其他更直接的语法，方可运行。该处理器将作为一种相对复杂些的实现存在，处理的逻辑也是各有千秋。此处仅给一点点提示，大家可按需实现即可。
import com.my.mvc.app.common.helper.parser.*;
import java.util.Iterator;
/**
* 功能描述: 自定义函数实现示例
*/
public class SimpleUdfAstHandler
extends CommonConditionAstBranch
implements SyntaxStatement {
public SimpleUdfAstHandler(TokenDescriptor masterToken,
Iterator<TokenDescriptor> candidates,
TokenTypeEnum tokenType) {
super(masterToken, candidates, tokenType);
}
@Override
protected int getFixedExtTokenNum() {
// 固定额外参数
return 2;
}
@Override
public String translateTo(TargetDialectTypeEnum targetSqlType) {
// 自行实现
String usage = masterToken.getRawWord();
int paramStart = usage.indexOf('(');
StringBuilder fieldBuilder = new StringBuilder();
for (int i = paramStart; i < usage.length(); i++) {
char ch = usage.charAt(i);
if(ch == ' ') {
continue;
}
if(ch == '$') {
// 示例解析，只需一个id参数处理
fieldBuilder.append(ch);
while (++i < usage.length()) {
ch = usage.charAt(i);
if(ch >= '0' && ch <= '9') {
fieldBuilder.append(ch);
continue;
}
break;
}
break;
}
}
String separator = " ";
StringBuilder resultBuilder
= new StringBuilder(fieldBuilder.toString())
.append(separator);
// 根据各目标语言需要，做特别处理
switch (targetSqlType) {
case ES:
case HIVE:
case SPARK:
case PRESTO:
case RAW:
extendTokens.forEach(r -> resultBuilder.append(r.getRawWord()).append(separator));
return resultBuilder.toString();
}
throw new RuntimeException("unknown target dialect");
}
}
udf 作为一个重点处理对象，大家按需实现即可。
8. 自定义关键字的解析实现
自定义关键字的目的，也许是为了让用户使用更方便，也许是为了理解更容易，也许是为系统处理方便，但它与udf实际有异曲同工之妙，不过自定义关键字可以尽量定义得简单些，这也从另一个角度将其与udf区分开来。因此，我们可以将关键字处理归纳为一类处理器，简化实现。
import com.my.mvc.app.common.helper.parser.*;
import com.my.mvc.app.common.util.ClassLoadUtil;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.StringUtils;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
* 功能描述: 系统自定义常量解析类
*
*/
@Slf4j
public class SysCustomKeywordAstHandler
extends CommonConditionAstBranch
implements SyntaxStatement {
private static final Map<String, SysKeywordDefiner>
keywordDefinerContainer = new ConcurrentHashMap<>();
static {
try {
// 自动发现加载指定路径下所有关键字解析器 keyword 子包
String currentPackage = SysCustomKeywordAstHandler.class.getPackage().getName();
ClassLoadUtil.loadPackageClasses(
currentPackage + ".custom");
}
catch (Throwable e) {
log.error("加载包路径下文件失败", e);
}
}
public SysCustomKeywordAstHandler(TokenDescriptor masterToken,
Iterator<TokenDescriptor> candidates,
TokenTypeEnum tokenType) {
super(masterToken, candidates, tokenType);
}
@Override
public String translateTo(TargetDialectTypeEnum targetSqlType) {
String usage = masterToken.getRawWord();
String keywordName = parseSysKeywordName(usage);
SysKeywordDefiner definer = getKeywordDefiner(keywordName);
List<TokenDescriptor> mergedToken = new ArrayList<>(extendTokens);
mergedToken.add(0, masterToken);
if(definer == null) {
// throw new BizException("不支持的关键字: " + keywordName);
// 在未完全替换所有关键字功能之前，不得抛出以上异常
log.warn("系统关键字[{}]定义未找到,降级使用原始语句,请尽快补充功能.", keywordName);
return translateToDefaultRaw(mergedToken);
}
return definer.translate(mergedToken, targetSqlType);
}
/**
* 获取关键字名称
*
* 检测关键词是否是 '%%#{datepart}%' 格式的字符
* @return 关键字标识如 datepart
*/
private String parseSysKeywordName(String usage) {
if('\'' == usage.charAt(0)) {
String keywordName = getSysKeywordNameWithPreLikeStr(usage);
if(keywordName == SYS_CUSTOM_EMPTY_KEYWORD_NAME) {
throw new RuntimeException("系统关键词定义非法, 请以 #{} 使用关键词2");
}
return keywordName;
}
return getSysKeywordNameNormal(usage);
}
private static final String SYS_CUSTOM_EMPTY_KEYWORD_NAME = "";
/**
* 获取关键字名称（'%#{datepart}%'）
*
* @param usage 完整用法
* @return 关键字名称 如 datepart
*/
public static String getSysKeywordNameWithPreLikeStr(String usage) {
if('\'' != usage.charAt(0)) {
return SYS_CUSTOM_EMPTY_KEYWORD_NAME;
}
StringBuilder keywordBuilder = new StringBuilder();
int preLikeCharNum = 0;
String separatorChars = " -+(){}[],";
for (int i = 1; i < usage.length(); i++) {
char ch = usage.charAt(i);
if(ch == '%') {
preLikeCharNum++;
continue;
}
if(ch != '#'
|| usage.charAt(++i) != '{') {
return SYS_CUSTOM_EMPTY_KEYWORD_NAME;
}
while (++i < usage.length()) {
ch = usage.charAt(i);
keywordBuilder.append(ch);
if(i + 1 < usage.length()) {
char nextChar = usage.charAt(i + 1);
if(separatorChars.indexOf(nextChar) != -1) {
break;
}
}
}
break;
}
return keywordBuilder.length() == 0
? SYS_CUSTOM_EMPTY_KEYWORD_NAME
: keywordBuilder.toString();
}
/**
* 解析关键词特别用法法为一个个token
*
* @param usage 原始使用方式如: #{day+1}
* @param prefix 字符开头
* @param suffix 字符结尾
* @return 拆分后的token, 已去除分界符 #{}
*/
public static List<TokenDescriptor> parseSysCustomKeywordInnerTokens(String usage,
String prefix,
String suffix) {
// String prefix = "#{day";
// String suffix = "}";
String separatorChars = " ,{}()[]-+";
if (!usage.startsWith(prefix)
|| !usage.endsWith(suffix)) {
throw new RuntimeException("关键字使用格式不正确: " + usage);
}
List<TokenDescriptor> innerTokens = new ArrayList<>(2);
TokenDescriptor token;
for (int i = prefix.length();
i < usage.length() - suffix.length(); i++) {
char ch = usage.charAt(i);
if (ch == ' ') {
continue;
}
if (ch == '}') {
break;
}
if (ch == '-' || ch == '+') {
token = new TokenDescriptor(ch, TokenTypeEnum.SIMPLE_MATH_OPERATOR);
innerTokens.add(token);
continue;
}
StringBuilder wordBuilder = new StringBuilder();
do {
ch = usage.charAt(i);
wordBuilder.append(ch);
if (i + 1 < usage.length()) {
char nextChar = usage.charAt(i + 1);
if (separatorChars.indexOf(nextChar) != -1) {
break;
}
++i;
}
} while (i < usage.length());
String word = wordBuilder.toString();
TokenTypeEnum tokenType = TokenTypeEnum.WORD_STRING;
if(StringUtils.isNumeric(word)) {
tokenType = TokenTypeEnum.WORD_NUMBER;
}
innerTokens.add(new TokenDescriptor(wordBuilder.toString(), tokenType));
}
return innerTokens;
}
/**
* 解析普通关键字定义 #{day+1}
*
* @return 关键字如: day
*/
public static String getSysKeywordNameNormal(String usage) {
if(!usage.startsWith("#{")) {
throw new RuntimeException("系统关键词定义非法, 请以 #{} 使用关键词");
}
StringBuilder keywordBuilder = new StringBuilder();
for (int i = 2; i < usage.length(); i++) {
char ch = usage.charAt(i);
if(ch == ' ' || ch == ','
|| ch == '+' || ch == '-'
|| ch == '(' || ch == ')' ) {
break;
}
keywordBuilder.append(ch);
}
return keywordBuilder.toString();
}
/**
* 默认使用原始语句返回（）
*
* @return 原始关键字词组
*/
private String translateToDefaultRaw(List<TokenDescriptor> tokens) {
String separator = " ";
StringBuilder sb = new StringBuilder();
tokens.forEach(r -> sb.append(r.getRawWord()).append(separator));
return sb.toString();
}
/**
* 获取关键词定义处理器
*
*/
private SysKeywordDefiner getKeywordDefiner(String keyword) {
return keywordDefinerContainer.get(keyword);
}
/**
* 注册新的关键词
*
* @param definer 词定义器
* @param keywordNames 关键词别名（支持多个，目前只有一个的场景）
*/
public static void registerDefiner(SysKeywordDefiner definer, String... keywordNames) {
for (String key : keywordNames) {
keywordDefinerContainer.putIfAbsent(key, definer);
}
}
}
// ----------- SysKeywordDefiner ------------------
import com.my.mvc.app.common.helper.parser.TargetDialectTypeEnum;
import com.my.mvc.app.common.helper.parser.TokenDescriptor;
import java.util.List;
/**
* 功能描述: 系统关键词定义接口
*
* （关键词一般被自动注册，无需另外调用）
* 关键词名称，如: day, dd, ddpart ...
* day
* '%#{datepart}%'
*
*/
public interface SysKeywordDefiner {
/**
* 转换成目标语言表示
*
*
*
* @param tokens 所有必要词组
* @param targetSqlType 目标语言类型 es|hive|presto|spark
* @return 翻译后的语言表示
*/
String translate(List<TokenDescriptor> tokens,
TargetDialectTypeEnum targetSqlType);
}
// ----------- SyntaxStatement ------------------
import com.my.mvc.app.common.helper.parser.TargetDialectTypeEnum;
import com.my.mvc.app.common.helper.parser.TokenDescriptor;
import com.my.mvc.app.common.helper.parser.keyword.SysCustomKeywordAstHandler;
import com.my.mvc.app.common.helper.parser.keyword.SysKeywordDefiner;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.util.List;
/**
* 功能描述: day 关键词定义
*
* 翻译当天日期，做相应运算
*
*/
public class DayDefinerImpl implements SysKeywordDefiner {
private static final String KEYWORD_NAME = "day";
static {
// 自动注册关键词到系统中
SysCustomKeywordAstHandler.registerDefiner(new DayDefinerImpl(), KEYWORD_NAME);
}
@Override
public String translate(List<TokenDescriptor> tokens,
TargetDialectTypeEnum targetSqlType) {
String separator = " ";
String usage = tokens.get(0).getRawWord();
List<TokenDescriptor> innerTokens = SysCustomKeywordAstHandler
.parseSysCustomKeywordInnerTokens(usage, "#{", "}");
switch (targetSqlType) {
case ES:
case SPARK:
case HIVE:
case PRESTO:
int dayAmount = 0;
if(innerTokens.size() > 1) {
String comparator = innerTokens.get(1).getRawWord();
switch (comparator) {
case "-":
dayAmount = -Integer.valueOf(innerTokens.get(2).getRawWord());
break;
case "+":
dayAmount = Integer.valueOf(innerTokens.get(2).getRawWord());
break;
default:
throw new RuntimeException("day关键字不支持的操作符: " + comparator);
}
}
// 此处格式可能需要由外部传入，配置化
return "'"
+ LocalDate.now().plusDays(dayAmount)
.format(DateTimeFormatter.ofPattern("yyyy-MM-dd"))
+ "'" + separator;
case RAW:
default:
StringBuilder sb = new StringBuilder();
tokens.forEach(r -> sb.append(r.getRawWord()).append(separator));
return sb.toString();
}
}
}
关键词的处理，值得一提是，使用了一个桥接类，且自动发现相应的实现。（可参考JDBC的 DriverManager 的实现） 从而在实现各关键字后，直接放入相应包路径，即可生效。还算优雅吧。
9. 单元测试
最后一部分，实际也是非常重要的部分，被我简单化了。我们应该根据具体场景，罗列所有可能的情况，以满足所有语义，单测通过。样例如下:
import com.my.mvc.app.common.helper.SimpleSyntaxParser;
import com.my.mvc.app.common.helper.parser.ParsedClauseAst;
import com.my.mvc.app.common.helper.parser.TargetDialectTypeEnum;
import org.junit.Assert;
import org.junit.Test;
public class SimpleSyntaxParserTest {
@Test
public void testParse1() {
String rawClause = "$15573 = 123 and (week_diff($123568, $82949) = 1) or $39741 = #{day+1} and week_diff($35289) = -1";
ParsedClauseAst clauseAst = SimpleSyntaxParser.parse(rawClause);
Assert.assertEquals("解析成目标语言ES不正确",
"$15573 = 123 and ( $123568 = 1 ) or $39741 = '2020-10-07' and $35289 = -1",
clauseAst.translateTo(TargetDialectTypeEnum.ES));
}
}
以上，就是一个完整地、简单的语法解析器的实现了。也许各自场景不同，但相信思想总是相通的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK