Kotlin写一个解释器（1）---词法分析
Kotlin写一个解释器（1）---词法分析">
为什么学
最近对编译器很感兴趣，为什么要学习编译原理,于我而言是因为最近需要写一个DSL，需要一个解释器，而对于大部分程序员来说，学习编译器可能有一下三个方面：
（1）学习编译器设计，可以帮助更好的理解程序以及计算机是怎么运行的，同时编写编译器或者解释器需要大量的计算机技巧，对技术 也是一个提升。
（2）面试需要，所谓“工作拧螺丝，面试造火箭”。学习编译器设计有助于加强计算机基础能力，提高编码素养，更好的应对面试，毕竟你不知道你的面试官是不是对这个也感兴趣。
（3）工作需要，有的时候你可能需要创造一些领域特定语言或者发明一种新语言（这个需要不太多），这个时候你就需要写一个编译器或者解释器来满足你的需要了。
编译器与解释器
编译器将以某种语言编写的程序作为输入，产生一个等价的程序作为输出，通常这个输入语言可能就是C活着C++，等价的目标程序通常是某种处理器的指令集，然后可以直接运行该目标程序。解释器与编译器的不同就在于它直接执行由编程语言或者脚本编写的代码，并不会把源代码预编译成指令集，它会实时的返回结果。如下图所示
还有一种编译器，它将一种高级语言翻译成另一种高级语言，比如将php转为C++,这种编译器一般称为源到源的转换器。
目标
这个博客系列的目标其实很小，就是利用Kotlin去实现一个小型的解释器来进行正数的四则运算，因为本人目前也是学习阶段，所以只能先弄一个这样的小功能，等技术提高了再开新番。该系列只会涉及到词法分析、语法分析、抽象语法树等编译器前端相关的概念，至于编译器后端相关的代码优化以及代码生成不会涉及。
词法分析
词法分析的任务是将字符流变换为输入语言的单词流。每个单词都必须归类到某个语法范畴中，也叫词类。词法分析器是编译器中唯一会接触到程序中每个字符的一趟处理。这里有几个概念要说明，比如词类，列比我们平时的语言，我们会说“走”是动词，“跑”也是动词，“漂亮”是形容词，“美丽”也是形容词，这里动词和形容词，就是词类，代表着单词的分类，还有一个就是词素，前面说的“走”，“跑”,"漂亮“等其实就是词素，也就是具体的单词内容，实际的文本。词法分析的作用就是将源代码中的文件按字符读入，根据读入的字符识别单词组成一个词法单元，每个词法单元由词法单元名和词素组成，列如<形容词：漂亮>,其中形容词就是词法单元名，可以看做和词类相同，漂亮就是词素，而对于我们要实现的计算器来说可能就是<PLUS,+>,<NUMBER,9>这样的。
代码
定义词法单元
前面说过，词法单元由词法单元名和词素组成，所以我们定义一个类Token来代表词法单元，TokenType这个枚举类来代表词法单元名
data class Token(val tokenType: TokenType, val value: String) {
override fun toString(): String {
return "Token(tokenType=${this.tokenType.value}, value= ${this.value})"
}
}
enum class TokenType(val value: String) {
NUMBER("NUMBEER"), PLUS("+"), MIN("-"), MUL("*"), DIV("/"), LBRACKETS("("), RBRACKETS(")"), EOF("EOF")
}
复制代码可以看到我有8个TokenType，8个TokenType代表着8个词法单元名，也就是8个词类,其中EOF代表END OF FILE及源文件扫描结束。
定义词法分析器
import java.lang.RuntimeException
class Lexer(private val text: String) {
private var nextPos = 0
private val tokenMap = mutableMapOf<String, TokenType>()
private var nextChar: Char? = null
init {
TokenType.values().forEach {
if(it!=TokenType.NUMBER) {
tokenMap[it.value] = it
}
}
nextChar = text.getOrNull(nextPos)
}
fun getNextToken(): Token {
loop@ while (nextChar != null) {
when (nextChar) {
in '0'..'9' -> {
return Token(TokenType.NUMBER, getNumber())
}
' ' -> {
skipWhiteSpace()
continue@loop
}
}
if (tokenMap.containsKey(nextChar.toString())) {
val tokenType = tokenMap[nextChar.toString()]
if (tokenType != null) {
val token = Token(tokenType, tokenType.value)
advance()
return token
}
}
throw RuntimeException("Error parsing input")
}
return Token(TokenType.EOF, TokenType.EOF.value)
}
private fun getNumber(): String {
var item = ""
while (nextChar != null && nextChar!! in '0'..'9') {
item += nextChar
advance()
if ('.' == nextChar) {
item += nextChar
advance()
while (nextChar != null && nextChar!! in '0'..'9') {
item += nextChar
advance()
}
}
}
return item
}
private fun skipWhiteSpace() {
var nextChar = text.getOrNull(nextPos)
while (nextChar != null && ' ' == nextChar) {
advance()
nextChar = text.getOrNull(nextPos)
}
}
private fun advance() {
nextPos++
nextChar = if (nextPos > text.length - 1) {
null
} else {
text.getOrNull(nextPos)
}
}
}
复制代码先看成员变量，其中text代表的是源文件内容，nextPos代表着源代码中下一个字符的位置，nextChar代表着源代码中下一个字符，tokenMap代表着词素和词法单元是唯一对应的Map，其中key代表的是词素，TokenType代表的词法单元，可以看到在我们的定义中除了TokenType.NUMBER其他都是存在唯一对应的，因为对于数字来说，9对应的是词法单元是NUMBER，10对应的词法单元也是NUMBER，不存在唯一对应，所以需要我们单独识别。
构造方法很简单，为tokenMap和nextChar计算赋值
再看剩下的方法，其实这个词法解析器对外暴露的只有getNextToken方法用以返回Token，其他方法都是private的用以辅助返回Token，在getNextToken方法中，有一个while循环判断nextChar是否为null，如果为null代表着源文件已经处理完毕，返回Token(TokenType.EOF, TokenType.EOF.value)，否则的话就判断当前字符是不是数字，如果是数字，就返回Token(TokenType.NUMBER, getNumber())，其中getNumber方法用以获取数字内容直到nextChar不再为数字为止。如果nextChar为空格，就跳过空格skipWhiteSpce，然后继续当前循环，如果既不是数字也不是空格，那么就根据tokenMap获取相应的TokenType，看看是不是运算符号或者括号，如果也不存在，说明输入中存在非数字和四则运算符号以及括号的字符，抛出错误"Error parsing input”。
测试
import java.util.*
fun main() {
while(true) {
val scanner = Scanner(System.`in`)
val text = scanner.nextLine()
val lexer = Lexer(text)
var nextToken = lexer.getNextToken()
while (TokenType.EOF != nextToken.tokenType) {
println(nextToken.toString())
nextToken = lexer.getNextToken()
}
}
}
复制代码编写测试代码，打印相应的token，运行代码，在代码中输入数据并回车，查看结果
至此词法分析器基本完成，其实词法分析器还有很多概念可说，比如说正则表达式，然后由正则表达式生成NFA,NFA应用最小子集法生成DFA,再由DFA生成最小DFA，其中有很多概念，但是个人认为太多的概念会让人迷茫，不如先由简单的例子开始，然后逐步加深理解，熟悉概念
