徒手撸一个表达式引擎
MLSQL在最近版本中添加了if/else分支语句支持。一个典型的代码样例如下:
set a = "wow,jack";
!if ''' split(:a,",")[0] == "jack" ''';
select 1 as a as b;
!else;
select 2 as a as b;
!fi;
select * from b as output;
比较复杂的条件表达式:
set a="jack,2";
!if '''
select split(:a,",")[0] as :name, split(:a,",")[1] as :num;
:name == "jack" and :num == 3;
''';
MLSQL的条件判断语句具有以下特色:
- 语法设计遵循SQL的一些原则。比如采用 and/or 替代 &&,||.使用select语句做变量赋值
- 兼容大部分SQL函数
- 支持多个语句,最后一条语句作为最后的条件
- 支持用户自定义函数
对If/Else的完整使用说明可以参考这篇:MLSQL 支持条件分支语句。
实际上,我们在实现MLSQL条件表达式时,选择了完全手写了Lexer/Parser/Codegen三个部分,最终,Codegen会把条件表达式翻译成可以运行在SQL引擎上的代码。
完整实现代码在这里:mlsql-lang
实现代码比较少,总共7个文件:
语法设计
MLSQL条件表达式支持赋值以及比较。
赋值语法如下:
select 值表单式 as 变量名称,值表单式 as 变量名称....
值表单式表达式支持三类基础变量:
- 字符串
- 数字
- 布尔值
以及任意SQL函数组合和一些特殊用法,典型如:
- [数字] 取数组元数
- cast (变量 as 类型)
比较语句语法如下:
值表达式 比较运算符 值表达式
多个比较语法可以通过 and/or连接。
为什么不采用通用语言设计
比如赋值,为啥不采用如下方式:
:variable1 = "jack"
这样看起来似乎更简洁。实际上,我们面向的受众是仅仅懂一些SQL语法的人而不是专业的编程人员。我们希望表达式设计更像SQL一点,让大家很快能找到参考,易于学习。这样包括连接符我们采用了 and
或者 or
而不是通用语言的 &&
或者 ||
,因为他们更符合SQL中的且或使用。
另外,用户可能会疑问,为什么使用如下语法:
!if ''' split(:a,",")[0] == "jack" ''';
而不是
if split(:a,",")[0] == "jack"
确实,下面的语法更加简洁。之所以采用上面的语法比如if关键字前面加了个!
是因为我们在增加条件表达式的时候,是完全兼容标准MLSQL语法的。 严格来说 !if
并不是关键字,他只是一个命令
,MLSQL引擎会自动将将上面的语法转化为如下的代码:
run command as IfCommand.`` where parameters='''['split(:a,",")[0] == "jack"' ]'''
也就是说,其实if/else也是利用MLSQL已经提供的扩展能力来实现的。在MLSQL语言层面,依然没有if/else语法结构,他们都只是一条一条命令而已。
Lexer/Tokenizer实现
上面说了一些设计思想,这里我们开始一些干货了。对于一个条件表达式,第一步是要实现一个词法分析器,其次是形成Ast树,最后根据场景需求,可能还有优化器,中间码,最后才是生成汇编代码,然后使用汇编器得到可执行二进制文件。 当然,在我们的场景里,仅仅会到中间码这一层,产生后会直接丢给我们的MLSQL Engine中的SQL引擎执行。
首先我们需要定义一个Scanner,这个Scanner会一个字符一个字符的扫描源码,然后将其解析成一个一个token. 在MLSQL条件表达式里,Token包含两个核心属性,一个是对应文本,一个是文本的所属类型。比如扫描如下语句
split(:a,",")[0] == "jack"
其中有一个Token,字面量(文本)会是:a
,同时他还会有一个类型属性,他是一个变量。下面是Scanner中我们定义的一些类型:
val EOF_INT = (-2).toChar
val EOF = Value("EOF")
val Ident = Value("Ident")//关键字
val Variable = Value("Variable")//变量
val Int = Value("Int") //整数类型
val Float = Value("Float") //浮点数类型
val Char = Value("Char")
val String = Value("String") //字符串
val RawString = Value("RawString") //多行文本
val Comment = Value("Comment") // 注释
当然,类型可以比这个广泛,比如每个关键字就是一个类型,在MLSQL 条件表达式里, select
目前是唯一的一个关键字。其次比如 左括号,右括号等等,都是单独的类型,我们需要一一罗列出来。
下面是目前实现中所有的枚举值,我去掉了大部分代码,只留下一部分,大家可以有个感觉。
object Scanner extends Enumeration {
type TokenType = Value
val EOF_INT = (-2).toChar
val EOF = Value("EOF")
....
val Lparen = Value("(") // (
val Lbrack = Value("[") // [
....
// keywords
val _SELECT = Value("select")
val _WHERE = Value("where")
// internal use only
val skipComment = Value("skipComment")
// operator
val AndAnd = Value("&&") // &&
val OrOr = Value("||") // ||
val Not = Value("!") // !
val Eql = Value("==") // ==
....
val _Or = Value("or")
val _Not = Value("not")
val _And = Value("and")
val _As = Value("as")
val OPERATOR_MAP = Map(
"&&" -> Scanner.AndAnd,
"||" -> Scanner.OrOr,
.....
)
val OPERATOR_SET = OPERATOR_MAP.values.toSet
val KEYWORD_MAP = Map(
"select" -> Scanner._SELECT,
"where" -> Scanner._WHERE
)
val KEYWORD_SET = KEYWORD_MAP.values.toSet
}
有了这些定义后,就可以定义一个Token了:
case class Token(t: Scanner.TokenType,
srcPos: Int, srcEnd: Int,
line: Int, column: Int,
scanner: Scanner) {
def text = {
(srcPos to srcEnd).map(scanner.srcChars(_)).mkString("")
}
}
我们并不记录Token的text值,而是通过位置得到的。Scanner的目标就是扫描字符串,然后将其转化为一个一个Token,Token包含了类型以及位置。整个过程是一个字符串不断匹配的过程。 因为我们对语法实现了严格的控制,可以做到只需要look ahead(多看几个字符),而不需要回溯(查看以前的字符),所以可以效率很高。
下面是一段典型的代码,大家有个感觉即可。
def scan: Scanner.TokenType = {
var ch = peek
while (whiteSpace(peek)) {
ch = next
}
ch = peek
lastTokenPos = srcPos
tok = Scanner.EOF
ch match {
case s if isVariable(ch, 1) =>
val tempSrcPos = srcPos
ch = scanVariable
tok = Scanner.Variable
if (srcPos - tempSrcPos == 1) {
error(": should be variable")
return Scanner.EOF
}
case s if isIdent(s, 1) =>
ch = scanIdent
tok = Scanner.Ident
val possibleKeyword = Scanner.KEYWORD_MAP.get(tokenString().toLowerCase())
if (possibleKeyword.isDefined) {
tok = possibleKeyword.get
} else {
val possibaleOperator = Scanner.OPERATOR_MAP.get(tokenString().toLowerCase)
if (possibaleOperator.isDefined) {
tok = possibaleOperator.get
}
}
最后整个用法可以通过一个测试用例来看:
test("tokenizer2") {
val items = Tokenizer.tokenize("""select split(:a,",") as :jack;""")
want(items, 0, Scanner._SELECT, "select")
want(items, 1, Scanner.Ident, "split")
want(items, 2, Scanner.Lparen, "(")
want(items, 3, Scanner.Variable, ":a")
want(items, 4, Scanner.Comma, ",")
want(items, 5, Scanner.String, "\",\"")
want(items, 6, Scanner.Rparen, ")")
want(items, 7, Scanner._As, "as")
want(items, 8, Scanner.Variable, ":jack")
//want(items,9,Scanner.Semi,";")
}
Parser
一旦我们得到了Token集合,此时他们是一个线性结构,无法体现实际的语义。比如 split(:a,",") 就被分成了split
,(
,:a
,',','","',')'等六个Token,这六个Token等价于对split函数操作。所以为了方便形成语义以及进行后续的操作,我们需要将其转化为树形结构。这个过程我们称为Parser阶段。
Parser是以语句为粒度的。语句的分割符是分号,对应的实现是StatementParser
,我们看下入口和签名:
class StatementParser(tokenizer: Tokenizer) extends Parser(tokenizer) {
def parseStatement(): TreeNode[_] = {
if (_match(Scanner.Semi))
return parseStatement()
if (_match(Scanner._SELECT))
return parseSelect()
parseExpression()
}
以Tokenizer为数据源,首先匹配分隔符,匹配上了意味着可以开始匹配一个完整语句了,其次匹配select语句,如果不是,那肯定就是比较表达式了。
在解析过程中,select 语句比较简单,多次匹配赋值语句即可:
比较困难的是中缀操作符,比如 a * (b + c)
,这意味着在解析过程中,我们可能需要一个中间存储,同时我们还需要知道操作符的优先级,并且我们只有遇到特定操作符的时候才能知道下一步该怎么办,比如遇到*
,那么我们应该继续往后处理,而且后面可能又会是一个完整的表达式。大部分情况我们可能会使用函数栈来保留这个结构,然后再反向弹出,先得到(b+c),再得到*,再得到a。 对于这个,有一个标准的操作范式叫Pratt Parsers
,用来解决这种表达式。我参考了这篇文章做的实现:Pratt Parsers: Expression Parsing Made Easy。具体就是一个for循环,不断的通过操作符不同得到对应的parser去解析,直到遇到终止条件。
在MLSQL条件表达式里,我们还支持and/or语法,所以这个是需要单独处理的地方。这些Parser处理后得到的都是表达式,他们会统一继承自Expression
:
我们实现了Variable,Literal,Leq,As等各种表达式,parser的最后产物就是这些表达式形成的一个树状结构。值得注意的是,每个表达式都具备给自己生成SQL代码的能力,比如数组下表的实现如下:
红框部分会产生一个合法的SQL代码片段。我们最终会通过CodeGen将这些代码片段以一定的方式拼接起来丢给SQL引擎执行实际的运行动作。
代码生成部分
代码生成部分,我们的抽象很简单:
case class VariableTable(
name:String,
variables:mutable.HashMap[String,Any],
types:mutable.HashMap[String,Any])
trait CodegenContext {
def execute(
exprs: List[Expression],
variableTable: VariableTable): Any
}
给我一个表达式集合(保证合法顺序),我们会利用变量表(每个表达式执行完成后都会更新该变量表,并且传递给后一个表达式用于计算)。我们实现SQL版本的运行时,只需要惊人的83行代码,参看这里 SQLGenContext.scala。
其基本思想是,所有的变量都会转成表,所有的表达式都会被转化为SQL算子,这样就将对变量的处理转化成了SQL算子对表的处理。
我们举一个非常简单的例子。对于下面的语句:
split(:a,",")[0] == "jack" and :b == 10
我们知道有个:a,:b变量,这两个变量来自set语法,set语法本质上是一个Map[String,String],SQLGenContext会将这个Map转换成一个实际的SQL视图表。
示例中的语句被解析后,实际上顶层是一个AndAnd表达式,left 和 right部分我们会分别计算,left 语句最后被转成了如下语句执行:
select split(a,",")[0] == "jack" from 变量表;
同理right部分,最后根据两者求且关系。对于比较复杂的有嵌套and/or,因为我们使用自底向上的策略,所以可以递归处理。整个核心代码如下:
总结
MLSQL分支语句中的条件表达式,尽管我们采用了hand-craft模式带来了一定的复杂度,但是这可以让我们实现更好的性能以及更好的掌控。我们成功的让表达式语句支持SQL引擎,从而能够复用各种函数的实现,降低了用户的学习成本。