写在前面

目前反作弊项目的核心项目是规则引擎，实现规则引擎在类似 python/php/javascrip 之类的解释型语言中可以直接通过 eval 之类的函数来模拟实现，但是在编译型语言比如 Go 实现就没那么容易了。

原因在于解释型语言本身就是动态解释执行的，可以在运行时把输入的文本作为语言本身去解释执行，但是编译型语言是去运行编译之后的机器码，此时能动态执行的内容非常有限且必须依靠语言特性。比如在 Go 语言内只能通过反射实现一些有限的动态执行，反射是完全依靠 interface 的内部实现。

解释器过程

规则引擎其实可以看作一个简化的单行脚本语言，所以要通过 Go 实现一个规则引擎其实就是使用 Go 实现一个简化版的脚本语言解释器。

我们来看看实现一个解释器的基本流程：

词法分析(Lexical analysis)

词法分析（lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。

完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器，核心任务是扫描、识别单词且对识别出的 Token 给出定性、定长的处理。

词法分析器一般从左至右地对源程序进行扫描，按照语言的词法规则识别各类 Token 。

Token

Token 是用于描述与归类从文本中分解出来的最小描述单元的一种结构。

词法分析器通常只识别Token ，但是不会关心 Token 之间的关系。例如：词法分析器能够将括号识别为单词，但并不保证括号是否匹配。

Token 序列本身并没有实际意义，必须通过语法分析将 Token 作为输入进行语法分析来保证 Token 的可用性和有意义的。

语法分析(Syntax analysis)

在计算机科学中，语法分析（syntactic analysis）是根据某种给定的形式文法对由 Token 序列构成的输入文本进行分析并确定其语法结构的一种过程。

语法分析器（parser）通常是作为编辑器或者解释器的组件出现的，它的作用是进行语法检查、并构建由输入的 Token 组成的数据结构，比如抽象语法树（AST）等层次化的数据结构。

实现 INI 解析器

语法分析及词法分析是一个比较复杂庞大的话题，并且一般的脚本语法结构较多，想实现一个脚本解释器较为复杂。所以我们用文件格式比较简单的 INI 文件，现一个 INI 解释器来帮助理解。

这个文件输入的是一个 INI 格式的文本字符串，输出为结构化的数据，我们用 Go 语言实现就是一个 Go语言结构体。 首先我们来看下 INI 文件的格式。

INI 格式分析

[SectionName]
key1=value 1
key2=value 2

格式很好理解，主要包括三个元素：

Section ： 段

Key ： 键

Value ：值

每个 INI 文件可以包含多个段，每一个段可以若干键值对。 我们将 INI 文件最终结构化的 Go 结构体如下：

type KeyValuePair struct{
	Key string
	Value string
}
type Section struct{
	SectionName string
	KeyValuePairs []KeyValuePair
}
type IniFile struct{
	Sections []Section
}

将 INI 格式的文本字符串转换为结构化数据的过程，可以类比为将脚本通过词法分析，语法分析转化成语法树的过程。 不同的是脚本转换后的语法树会进行执行，我们的INI结构数据只需要输出即可。

INI 文件拆解

在将 INI 文件进行词法分析之前，我们需要进行 Token 结构体定义，该结构体需要描述当前 Token类型及对应的值：

type Token struct {
  Type TokenType
  Val string
}

从头开始分析 INI 文件：

• 每个段的段头部 是由 左括号 段名字符串 右括号三部分构成。
• 段体是由 键字符串 等于字符串 值字符串 三部分组成。
• 段与段之前通过 换行符 拆分。
• 文本扫描结束或者出错时后需要记录结束及出错。

最终我们可以得到以下 INI 文件内包含的Token类型：

type TokenType int

const (
  TOKEN_ERROR TokenType = iota    
  TOKEN_EOF     

  TOKEN_LEFT_BRACKET 
  TOKEN_RIGHT_BRACKET
  TOKEN_EQUAL_SIGN
  
  TOKEN_NEWLINE

  TOKEN_SECTION
  TOKEN_KEY
  TOKEN_VALUE
)

然后我们还需要找到可定位的特殊 Token 类型 在字符串内的原文表示。比如 左括号 肯定是 [ , 右括号是 ],那么词法分析器就会在 左括号 与 右括号直接找到段名。

为了后续方便程序处理，我们把这类Token的文本表示定义成为常量：

const LEFT_BRACKET string = "["
const RIGHT_BRACKET string = "]"
const EQUAL_SIGN string = "="
const NEWLINE string = "\n"

实现 INI 词法分析

有限状态机分析

词法分析时怎么把输入字符串断开成一个个的 Token ？分割的依据是什么呢？ 其实，我们实现词法分析器的过程，就是写出正则表达式，画出有限自动机的图形，然后根据图形直观地写出解析代码的过程。

我们以 section 头 [name]为例 , 词法分析扫描过程如下：

通过流程图分析，我们可以画出以下状态流转过程：

解释下图中4个状态：

1. 初始状态：刚开始启动词法分析的时候，程序所处的状态。
2. 左括号状态：在初始状态时，当第一个字符是 [ 的时候，迁移到状态 2。当后续字符是字母和数字时，就离开状态 2，记录该 Token，并进去状态 3。
3. 文本状态：在初始化状态或者状态2时，下一个字符为字母和数字时，进入状态3。 当后续字符是字母和数字时，保留在状态 3。如果不是，就离开状态 3，写下该 Token，并进入状态4。
4. 右括号状态：在初始化状态或者状态3时，下一个字符为 ] 时，进入状态4。

状态机定义

我们为每一个 Token 定义一个状态函数，然后根据当前 Token 状态返回下一个期望执行的状态函数，这就是有限状态机的雏形了，根据不同的状态来决定不同的扫描路径。

由此我们的状态函数类型定义如下：

type LexFn func(*Lexer) LexFn    //每个状态函数执行结果为下一个期望执行的状态函数

同时为了实现文本到 Token 的转化，我们还需要追踪一些信息，比如文本内容，当前分析文本的位置，以及当前分析的 Token 的开始和结束位置。

type Lexer struct {
  Input  string  // 输入文本
  Tokens []Token // 已经生成的token序列
  State  LexFn   // 状态函数

  Start int      // 每处理一个token的扫描开始位置
  Pos   int      // 词法器处理文本位置
  Width int      // 当前字符串宽度，我们的处理程序偏移量单位为字节，但是字符串可能存在中文等多字节字符
}

我们对 INI 文件的词法分析就是对INI文件内字符串的扫描和处理，所以我们需要准备一些字符串工具方法方便调用：比如获取扫描位置往后移动，读取扫描字符，跳过空格等。

// 在确定扫描完一个Token时，提交 Token 并设置 Start 位置为开始位置
func (this *Lexer) Emit(tokenType TokenType) {
  this.Tokens = append(this.Tokens,Token{Type:tokenType,Val:this.Input[this.Start:this.Pos]})
  this.Start = this.Pos
}

//读取下一个完整字符 并移动扫描位置
func (this *Lexer) Next() rune {
	if this.Pos >= utf8.RuneCountInString(this.Input) {
		this.Width = 0
		return EOF
	}

	result, width := utf8.DecodeRuneInString(this.Input[this.Pos:])

	this.Width = width
	this.Pos += this.Width
	return result
}
// 回退到上一个字符
func (this *Lexer) Backup() {
	this.Pos -= this.Width
}

// 返回从当前处理位置到字符串尾部的所有字符
func (this *Lexer) InputToEnd() string {
	return this.Input[this.Pos:]
}
// 扫描到输入尾部
func (this *Lexer) IsEOF() bool {
	return this.Pos >= len(this.Input)
}
// 判断是否空格
func (this *Lexer) IsWhitespace() bool {
	ch, _ := utf8.DecodeRuneInString(this.Input[this.Pos:])
	return unicode.IsSpace(ch)
}

/*
跳过所有空格
*/
func (this *Lexer) SkipWhitespace() {
  for {
    ch := this.Next()

    if !unicode.IsSpace(ch) {
      this.Backup()
      break
    }

    if ch == EOF {
      this.Emit(TOKEN_EOF)
      break
    }
  }
}

词法分析器将按照以下步骤执行直到结束：

1. 扫描字符串，知道扫描到特定标记的字符串。例如，在处理段头名称的词法分析器状态函数中，我们需要一直读取字符串直到右括号为止。
2. 将扫描的文本和令牌类型记录到Tokens内。
3. 返回下一个预期执行的状态函数。

启动

准备工作就是这些了，现在我们需要一个启动函数来启动扫描过程了。需要注意的是我们需要一个初始化状态函数来初始化我们的词法分析器,可能是一个特殊的字符或者关键字。比如在INI文件中可能是 [ 。我们直接创建一个名为 LexBegin 的通用状态函数作为初始化状态函数。

// 启动函数 初始化一个 lexer ，传入字符串和初始化状态函数
func StartLexing(input string) *Lexer {
	l := &Lexer{
		Input:  input,
		State:  LexBegin,
		Tokens: make([]Token, 0),
	}
	for state := l.State; state != nil; {
		state = state(l)
	}
	return l
}

段头

然后我们来看看第一个状态函数 LexBegin 。首先跳过空格，因为空格在 INI 文件的值或者节点名之外没有意义。

我们根据首个字符来确定接下来要进行的状态函数。如果是左括号，则进入左括号状态处理函数。其他情况我门都视为键值对中的 Key 。

func LexBegin(lexer *Lexer) LexFn {
  lexer.SkipWhitespace()

  if strings.HasPrefix(lexer.InputToEnd(), LEFT_BRACKET) {
    return LexLeftBracket
  } else {
    return LexKey
  }
}

接下来我们跟随一个 INI 文件的扫描进入 LexLeftBracket 状态函数，这个状态函数需要做什么呢？因为扫描到 LEFT_BRACKET 我们可以确定他就是一个独立的 Token ，所以首先将追踪器器的处理位置 Pos 移动到 LEFT_BRACKET 之后，然后提交这个 Token 。

func LexLeftBracket(lexer *Lexer) LexFn {
  lexer.Pos += len(LEFT_BRACKET)
  lexer.Emit(TOKEN_LEFT_BRACKET)
  return LexSection
}

Emit 函数会根据词法分析器位置将 Token 写入 Tokens。通过保持开始位置和当前位置来做到这一点。当执行 Emit 时，开始位置 Start 会前进到追踪器器的处理位置 Pos 。最后一步我们可以确定在 LexLeftBracket 状态之后是 Section 状态，所以我们返回下一个期望执行状态 LexSection 。

func LexSection(lexer *Lexer) LexFn {
  for {
    if lexer.IsEOF() {
      return lexer.Errorf(errors.LEXER_ERROR_MISSING_RIGHT_BRACKET)
    }

    if strings.HasPrefix(lexer.InputToEnd(), RIGHT_BRACKET) {
      lexer.Emit(TOKEN_SECTION)
      return LexRightBracket
    }

    lexer.Inc()
  }
}

LexSection 状态函数主体是一个循环，我们一直扫描输入字符串直到到达右括号 RIGHT_BRACKET ，每次扫描都会移动处理位置，在找到 RIGHT_BRACKET 时，这是 start:pos 扫描到的字符串就是 TOKEN_SECTION 的Val，我们直接提交即可。

注意这里有个错误处理，按照正常的 INI 格式 我们肯定会扫描到一个 RIGHT_BRACKET ，如果没有扫描到就到达文件结尾，说明这是一个格式错误的 INI 返回一个 错误处理状态。

LexSection 状态函数返回的是 LexRightBracket 状态函数，这个右括号状态函数和左括号处理函数基本一样。不同的是右括号结束的时候返回 LexBegin 。因为 INI 文件允许存在不包含键值对的空段。

func LexRightBracket(lexer *Lexer) LexFn {
  lexer.Pos += len(lexertoken.RIGHT_BRACKET)
  lexer.Emit(lexertoken.TOKEN_RIGHT_BRACKET)
  return LexBegin
}

键值对

键值对的格式是 key=some val xxx 。扫描 key 的过程跟上面扫描 section 名称 一样，循环扫描知道遇到等于号。最终返回的下一个状态函数是 LexEqualSign 。

func LexKey(lexer *Lexer) LexFn {
  for {
    if strings.HasPrefix(lexer.InputToEnd(), EQUAL_SIGN) {
      lexer.Emit(TOKEN_KEY)
      return LexEqualSign
    }

    lexer.Inc()

    if lexer.IsEOF() {
      return lexer.Errorf(LEXER_ERROR_UNEXPECTED_EOF)
    }
  }
}

等号的处理和 左右括号一致，最终返回的下一个状态函数是LexValue。

func LexEqualSign(lexer *Lexer) LexFn {
  lexer.Pos += len(EQUAL_SIGN)
  lexer.Emit(TOKEN_EQUAL_SIGN)
  return LexValue
}

最后就是键值对中的值部分了，值 是介于等号和换行符之间的部分，所以我们循环扫描直到遇到 换行符 NEWLINE 。

到这里一个完整的段扫描就结束了。所以下一个状态函数我们又从初识状态函数开始扫描。

func LexValue(lexer *Lexer) LexFn {
  for {
    if strings.HasPrefix(lexer.InputToEnd(), NEWLINE) {
      lexer.Emit(TOKEN_VALUE)
      return LexBegin
    }

    lexer.Inc()

    if lexer.IsEOF() {
      return lexer.Errorf(errors.LEXER_ERROR_UNEXPECTED_EOF)
    }
  }
}

到这里我们的词法分析就结束了，我们把解析 INI 文件产生的 Token 全部存放到了 Tokens 内。下一步我们将实现一个解析器将Tokens 解析到标准结构体内。

实现 INI 解析器

INI结构体

首先我们要确定目标结构体，在 「INI 格式分析」中我们已经确定了最终的结构体：

type KeyValuePair struct{
	Key string
	Value string
}
type Section struct{
	SectionName string
	KeyValuePairs []KeyValuePair
}
type IniFile struct{
	Sections []Section
}

解析器

首先我们需要创建一个 IniFile 来保存最终结果。

output := IniFile{Sections:make([]Section,0)}

然后我们需要一些变量来跟踪记录 token 的值 以及 目前的解析器状态。例如我们在处理获取键值对时需要知道当前在处理哪个键值对。

// 当前处理的 section
section := Section{}
// 当前处理的 key/val
key := ""

可以启动解析器了，因为解析INI的文件格式较为简单，我们直接使用一个循环依次读取 Token 进行解析。

解析器需要关注的 Token 类型首先是 EOF ，代表当前文件已经结束需要跳出循环。

然后需要关注三种令牌类型，分别是「段」 「键」 和 「值」 ：

如果我们遇到一个「段」标记，并且我们已经记录了「段」和「键值对」数据就进行保存然后重置跟踪变量用来存储将要扫描到的「段」数据。

如果遇到的 Token 类型是 「键」 则记录 「键」。这样当我们遇到「值」 时，我们可以设置「键」的「值」，然后将其保存到我们正在跟踪的「段」内。

func Parse(l *Lexer) (output IniFile) {
	output = IniFile{Sections: make([]Section, 0)}
	// 当前处理的 section
	section := Section{}
	// 当前处理的 key/val
	key := ""

	for _, token := range l.Tokens {
		// 扫描结束把 最后记录的 section 写入 output
		if token.Type == TOKEN_EOF || token.Type == TOKEN_ERROR {
			if token.Type == TOKEN_ERROR {
				fmt.Println(token.Val)
			}
			output.Sections = append(output.Sections, section)
			break
		}

		switch token.Type {
		case TOKEN_SECTION:
			// 扫描到一个新的 section 时 将已经扫描到的section写入 output
			if len(section.KeyValuePairs) > 0 {
				output.Sections = append(output.Sections, section)
			}

			// 重置 key 及 section 状态
			key = ""

			section.SectionName = strings.TrimSpace(token.Val)
			section.KeyValuePairs = make([]KeyValuePair, 0)

		case TOKEN_KEY:
			// 扫描到key 记录key
			key = strings.TrimSpace(token.Val)

		case TOKEN_VALUE:
			// 扫描到val 记录 key/val 写入 KeyValuePairs 后重置 key
			section.KeyValuePairs = append(section.KeyValuePairs, KeyValuePair{Key: key, Value: strings.TrimSpace(token.Val)})
			key = ""
		}
	}
	return output

}

到这里我们已经实现了一个完整的INI文件解析器。

和脚本解释器相比，这个INI文件解析器的分析器部分需要解析的Token类型只有三种并且只需要构建出结构树即可。而脚本解释器则需要处理更多的Token类型并且需要构建出可执行的 AST 语法树，这就需要一个完整的语法分析器了。