Lua强语言的设计与实现
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 casttranslate fun <T> cast(): T?translate fun <T> safe(default: T): T}
编译器实现
一套标准语言的编译器将会包含以下几个部分：
' fill='%23FFFFFF'%3E%3Crect x='249' y='126' width='1' height='1'%3E%3C/rect%3E%3C/g%3E%3C/g%3E%3C/svg%3E)
标准编译器流程
词法分析器：将源代码转换为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 = 1fun main(): Int {val b = 2return a + b + c}
他的词法分析和语法分析的结果是正确的，但是语义分析的结果是错误的，因为c这个变量没有定义，所以这个程序是不合法的。
符号表
为了找出这些语义错误，我们首先要对AST中变量的声明和使用进行识别，确定程序在此处使用的确切变量，这部分的工作就需要维护一个符号表(Symbol Table)，用于记录变量的类型，以及变量的作用域。
在我们的编译器中，符号表主要由Scope和Symbol两个类构成，Scope表示作用域，Symbol表示变量，
class Scope(//所属的父Scopeval enclosingScope: Scope?,//该Scope下的所有Symbolval symbols: List<Symbol>) {//定义新的Symbolfun define(symbol: String)//嵌套解析对应的Scopefun 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.typeelse error
那么对于以下程序：
val a: Int = 1val b: Int = 2val c: String = "hello"val r1 = a + bval r2: String = a + bval 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强语言，并且开发出更多的功能。
