MLN是一款基于Lua的跨平台框架,伴随着使用范围的不断扩大,我们充分体会到跨平台框架给项目开发带来的灵活性和便捷性。但由于Lua语言是一种动态解释的轻量级语言,他自身的语法和语义都比较简单,也不支持面向对象,因此在使用MLN开发项目时,会遇到一些Lua语言本身的限制,比如不支持类型检查,不支持类和继承,不支持泛型,不支持重载等等,这些限制会给开发带来一些困难。尽管我们可以通过一些技巧来解决这些问题,比如通过元表来实现类和继承,通过闭包来实现泛型,通过函数指针来实现重载等等,但是这些技巧都有一些不可避免的限制,也给代码开发产生了许多麻烦,所以我们需要一种更加强大的方式来解决这些问题。
因此我们设计出一套基于Lua的强语言,他的语法接近于现代的Kotlin语言,支持类型检查,类和继承,泛型,重载等特性,并在Lua强语言的基础上,重新设计MLN的项目结构,提供对应的语言开发插件,从而让开发者能够更加专注于业务逻辑的开发,而不是在繁琐的代码实现上浪费太多的精力。在设计过程中,我们还考虑到了和旧项目的兼容问题,提供与Lua进行混合编译的能力,从而让开发者可以在不改动旧项目的情况下,逐步迁移项目到Lua强语言的实现上。
本文章会介绍Lua强语言的设计思路和编译器的具体实现,希望能够给大家带来一些启发。
在这里我们仅介绍一下Lua强语言的基础语法的设计原则,具体的语法规则可以参考语法规则。
基础语法接近现代的Kotlin语言,支持Int,Number,String,Boolean,Function等基础数据类型。
支持类型检查,类型检查需要在编译期完成,支持功能有限的运行时类型检查。
支持Null Safety,Nullable类型的变量在使用时需要进行非空判断。
支持类和继承,类的成员变量和方法都可以被继承。
支持泛型,泛型的类型参数可以是基础类型,也可以是类。
支持重载,重载的方法可以有不同的参数类型。
Lua强语言的设计目标包括让开发者能够在不改动旧项目的情况下,逐步迁移项目到Lua强语言的实现上。因此我们需要提供与Lua进行混合编译的能力。混合编译涉及到Lua文件的解析映射以及Lua和Lua强语言之间的相互调用。
Lua符号映射
根据lua文件所在目录确定包名,例如 views/cell/SampleCell.lua,包名就是 views.cell
lua文件内的全局变量或者全局函数,会被认为是该包名下的全局变量或者全局函数,名字不变
lua文件的返回值,被映射为该包名下的全局变量,变量名为 文件名_
Lua类型映射
从Lua文件中创建的符号类型,一律视为Bridged类型,可以通过cast方法来转换成需要的类型
可以通过注释来指定Lua文件中的符号类型,包括Int/Number/Boolean/String/Table/Bridged/Map/List;不在该范围的,一律默认为Bridged
对于简单的变量类型声明,可以通过类型推断识别
Lua强语言映射
一个Lua强语言文件将会被编译成多个Lua文件,一个是同名的Lua文件,包含该文件的全局变量和全局方法,另外会根据文件中的类定义,生成对应的同名Lua文件,包含类的定义和方法定义。
跨平台调用:Bridged接口
对于MLN中跨平台桥接类的调用,可以通过Bridged接口来实现,该接口定义如下,
Bridged接口标识该类型是从Lua文件解析过来的符号类型。
对Bridged类型做的后续操作,都会直接翻译成Lua调用,操作后返回的值也是Bridged类型
Bridged类型自带两个方法,用于转换为想要的特定类型
interface Bridged {
//unsafe cast
translate fun <T> cast(): T?
translate fun <T> safe(default: T): T
}
一套标准语言的编译器将会包含以下几个部分:
标准编译器流程
词法分析器:将源代码转换为Token流。
语法分析器:将Token流转换为AST(抽象语法树)。
语义分析器:对AST进行语义分析,生成符号表,检查语法错误和逻辑错误。
中间代码生成器:将AST转换为中间代码。
优化器:对中间代码进行优化。
代码生成器:将中间代码转换为Lua代码。
对于文本形式的源代码,我们首先会将文件的字节(Byte)流转换为为单词(Token)流,因为对于编译器而言,我们更关心的是Token,而不是Byte,Token是编译器的基本单位。这部分的工作就是词法分析器(Lexer),在我们项目里对应的是MuaLexer类。Token通常包含两个部分,一个是Token的类型,另一个是Token的值,例如对于a = b + c * 3这个表达式,我们可以将其分解如下Token流
词法分析器
接着我们会根据一定的语法规则和算法,将Token流转换为抽象语法树(AST),这部分的工作就是语法分析器(Parser),在我们项目里对应的是MuaParser类。语法规则定义了Token流的合法性,例如对于 expr -> num + num的规则,1 + 2这个表达式的Token流是合法的,而1 +这个表达式的Token流是不合法的。
语法分析算法有很多种,例如LL算法,LR算法等等,使用这些算法都会对Token流进行分析,校验Token流的合法性,最终将Token流转换为AST。
语法分析器
词法分析器和语法分析器是编译器中比较通用和常见的部分,我们使用了ANTLR4来实现这两个部分。ANTLR4是一个基于LL(*)算法的语法分析器生成器,它可以根据我们提供的语法规则,自动生成词法分析器和语法分析器,从而让我们能够专注于语言的设计。
具体的词法和语法规则可以参照MuaLexer.g4和MuaParser.g4,这里不再赘述。
语义分析器是编译器中比较复杂的部分,它需要对AST进行遍历,检查语义错误,同时还需要对AST进行一些优化,比如将一些常量表达式进行计算,将一些无用的代码进行删除等。
例如对于以下程序:
val a = 1
fun main(): Int {
val b = 2
return a + b + c
}
他的词法分析和语法分析的结果是正确的,但是语义分析的结果是错误的,因为c这个变量没有定义,所以这个程序是不合法的。
符号表
为了找出这些语义错误,我们首先要对AST中变量的声明和使用进行识别,确定程序在此处使用的确切变量,这部分的工作就需要维护一个符号表(Symbol Table),用于记录变量的类型,以及变量的作用域。
在我们的编译器中,符号表主要由Scope和Symbol两个类构成,Scope表示作用域,Symbol表示变量,
class Scope(
//所属的父Scope
val enclosingScope: Scope?,
//该Scope下的所有Symbol
val symbols: List<Symbol>
) {
//定义新的Symbol
fun define(symbol: String)
//嵌套解析对应的Scope
fun resolve(name: String): Symbol
}
class Symbol(
//Symbol名
val name: String,
//Symbol类型
val type: TypeSymbol
)
对于如下程序,Scope和Symbol之间的关系如图所示:
符号表
在之后编译器的分析中,我们会持续对符号表进行更新,例如更新类型推断后的符号类型,更新泛型指定后的新类型等等,从而确保在各处使用的符号都是正确的,这里先不展开。
类型推断和类型检查
构建出符号表之后,我们就可以对AST进行类型推断和类型检查了,类型推断是指在编译器中,我们可以根据变量的声明和使用,推断出变量的类型,而类型检查则是指在编译器中,我们可以根据变量的声明和使用,检查变量的类型是否正确。
在Mua语言中,我们使用了强类型,也就是说,变量的类型是确定的,不能随意改变,因此类型推断和类型检查是比较重要的部分。
例如,对于以下 E -> E1 op E2 规则,我们有以下的类型推断:
if (E1.type == E2.type) return E1.type
else error
那么对于以下程序:
val a: Int = 1
val b: Int = 2
val c: String = "hello"
val r1 = a + b
val r2: String = a + b
val r3 = a + c
在构建符号表的过程中,我们已经知道了a和b的类型是Int,根据规则,我们可以推断出
r1的类型是Int;
对于r2,根据右侧表达式可以推断出类型是Int,然而r2的类型声明是String,因此类型不匹配,语义错误;
对于r3,由于a和c的类型不匹配,类型推断出错。
再来看一个例子:
fun hello(name: String) {
print("hello " + name)
}
fun main() {
hello(1)
}
根据函数声明,我们知道hello函数的参数类型是String,但是在调用时传入了Int类型的参数,因此类型推断出错。
通过类型推断和类型检查,我们可以在编译器中发现大部分的语义错误,而不是在运行时才发现错误。
中间表示(Intermediate Representation),简称IR,它是编译器中的一种中间代码,主要用来将AST转换为更加适合于优化和代码生成的形式。在Lua强语言中,我们使用AST和符号表,生成基于树结构的IR,他的基本单位是MuaExpr,所有的IR都是由MuaExpr组成的。
class MuaExpr(
//父表达式
val enclosingExpr: MuaExpr,
//子表达式集合
val children: List<MuaExpr> = emptyList(),
//表达式类型
val inferredSymbol: Symbol? = null,
//对应的AST节点
val node: DefNode? = null,
)
从而一个标准的IR程序结构如下所示:
- `TopLevelExpr`:根节点
- `PropertyDefExpr`:全局变量定义
- `IdExpr`:变量名
- `MuaExpr`:变量值
- `FunctionExpr`:全局函数定义
- `IdExpr`:函数名
- `ParamExpr`:函数参数
- ...
- `BlockExpr`:函数体
- `MuaExpr`:指令列表1
- `MuaExpr`:指令列表2
- `CallExpr`: 函数调用
- `IdExpr`:函数名
- `MuaExpr`:参数1
- `MuaExpr`:参数2
- ...
- `ClassExpr`: 类定义
- `IdExpr`:类名
- `ParamExpr`:类参数
- `BlockExpr`:类体
- `FunctionExpr`:函数定义
- `PropertyDefExpr`:变量定义
- ...
相对于AST,IR进行了更进一步的分析,例如
val a = Map(2)
fun test() {
a["hello"] = 1
}
在AST中,a["hello"]是一个IndexingNode,而在IR中,a["hello"]是一个CallExpr,它的函数名是set,第一个参数是a,第二个参数是"hello",第三个参数是1。
目标代码生成是编译器的最后一步,它的作用是将IR转换为目标代码,例如汇编代码。在Lua强语言中,使用MuaTranslator类来实现目标Lua代码的生成。
首先会对IR进行遍历,根据堆栈生成对应的生成目标代码。
- `TopLevelExpr`:根节点
- `PropertyDefExpr`:全局变量定义
- `IdExpr`:a
- `MuaExpr`:
- `CallExpr`:
- `IdExpr`:Map`
- `LiteralExpr`:2
- `FunctionExpr`:全局函数定义
- `IdExpr`:test
- `BlockExpr`:
- `CallExpr`:
- `IdExpr`:a
- `IdExpr`:set
- `LiteralExpr`:"hello"
- `LiteralExpr`:1
上面的IR会被转换为下面的Lua代码:
local a = Map(2)
function test()
a:set("hello", 1)
end
在目标代码生成中,我们还会输出一些调试信息,例如源代码行号,调用堆栈映射等等,以便于在调试时更加方便地定位错误。
通过上述介绍,我们简单了解了一下Lua强语言编译器的设计思路和实现流程,但是由于篇幅的限制,我们没有详细介绍每一个部分的实现细节,如果大家有兴趣的话,可以参考我们的项目代码。在实现过程中,我们还发现了一些问题,例如高阶函数的规则定义不够明确,泛型推断不够完善等等。在未来的时间里,我们还会继续改进Lua强语言,并且开发出更多的功能。