Link

首页

Tweet

书单

about me

Command

Category

Golang实现微型数学运算解释器


对于一般的解释器来说,通常需要三个步骤:

  1. 词法分析
  2. 语法分析
  3. 指令执行

这篇文章所介绍的小型数学解释器则没有这么复杂的过程,原因在于语法设计及其简单。我们来看一下最终的使用效果。最终打包的可执行文件名称为mc。

linux ~ $ ./mc
Fatal error: no input file
linux ~ $

当没有任何参数输入时候,工具会提示错误。如果添加了对应代码文件,即可正常执行,如下:

linux ~ $ ./mc t.m
112
45
3015
45
14
linux ~ $ 

上面的实例中出现的数字都是我们计算后的结果,t.m文件真是我们的源代码,来看一下t.m文件内容:

MOV x 45
MOV y 67
ADD x y
OUT x
SUB x y
OUT x
MUT x y
OUT x
DIV x y
OUT x
MOV u 2
MOV i 7
MUT u i
OUT u

上面的代码我们后面还会继续讲解其作用,现在只需要知道的是所有大写字母均为设定的指令,当我们的指令编写错误怎么处理呢?我们将第四行执行修改为aOUT,这个修改后的指令是不存在的,再来运行一下查看效果:

linux ~ $ ./mc t.m
Error: line 4: unknown command: aOUT x
linux ~ $

此时可以看到,当解释器当遇到错误的时候会给我们一个相对友好的提示。由此我们来看一下这个即将要实现的数学计算解释器的功能:

  1. 从外部流读取源码
  2. 解释程序时需要错误检测
  3. 运行解释程序

指令设计

当前这个小解释器一共实现了6个指令,其中4个计算指令,2个流操作指令,指令使用也非常简单。

运算指令

ADD指令负责加法运算,指令包含两个参数,假如输入指令为ADD x y,则对应的伪代码为x = x + y。也就是说,两个参数相加后的结果会赋值给第一个参数。

同理,SUB指令负责减法运算,MUT指令负责乘法运算,DIV指令负责除法运算。对应的伪代码如下:

SUB x y 对应 x = x - y
MUT x y 对应 x = x * y
DIV x y 对应 x = x / y

赋值指令

赋值指令为MOV,与运算指令一样,也需要两个参数,它所执行的操作是将第二个参数的值赋值给第一个参数。在当前的版本中,所有的数字在实现的时候均使用int类型,当然你也可以将其修改为float类型,让整个计算过程支持小数。

打印指令

当我们计算完结果之后,需要将结果显示在终端里,这个操作类似于C当中的printf函数,这里我设计了OUT指令。该指令仅需要一个参数,会将该参数值打印出来。

解释器实现

源文件读取

读取源文件是非常简单的操作,在Golang中可以借助已有的io流操作可快速读取本地文本文件。在当前这个项目中,我们仅用一个函数完成对代码文件的读取。

func readFile() ([]byte, error) {
	if len(os.Args) == 1 {
		return nil, errors.New("nil")
	}
	f, err := os.Open(os.Args[1])
	if err != nil {
		return nil, err
	}
	return ioutil.ReadAll(f)
}

词法分析

说到词法分析,在当前这个项目里,由于语法设计超级简单,所以词法分析也非常简单,没有括号,不存在优先级,所生成的token也无需考虑后期的语法分析过程,因为根本就没有语法分析。这里所生成的token,事实上就是后面runtime所需要的指令集。

我们先来看一下最终要解析后的token结构:

type token struct {
	action int
	left   string
	right  string
}

当源代码字符串被传递进来后,我们先按照行进行拆分,因为每条指令都占用一行,所以再针对每一行代码进行分析,并解析生成对应的token,代码如下:

func line(str string) (token, bool) {
	strs := strings.Split(str, " ")

	var cmd token
	cmd.action = setcmd(strs[0])
	if cmd.action == 0 {
		return cmd, false
	}
	cmd.left = strs[1]
	if cmd.action != OUT {
		cmd.right = strs[2]
	}
	return cmd, true
}

func setcmd(str string) int {
	switch str {
	case "MOV":
		return MOV
	case "SUB":
		return SUB
	case "ADD":
		return ADD
	case "MUT":
		return MUT
	case "DIV":
		return DIV
	case "OUT":
		return OUT
	}
	return 0
}

func isNumber(str string) (int, bool) {
	num, err := strconv.Atoi(str)
	if err != nil {
		return 0, false
	}
	return num, true
}

var errorList []string

func la(str string) {
	errorList = make([]string, 0)
	strs := strings.Split(str, "\n")
	cmds = make([]token, len(strs))
	for i, val := range strs {
		var rel bool
		cmds[i], rel = line(val)
		if rel == false {
			var str = "Error: line " + strconv.Itoa(i+1) + ": unknown command: " + val
			errorList = append(errorList, str)
		}
	}
}

至此,我们的词法分析工作已经完成。

运行时

由于前面我们已经生成了token,并且token又是顺序执行的,这里runtime其实是遍历数组,按照顺序执行每一条指令。存在一个问题是,我们可以设定很多变量。这些变量并没有显式声明。我们创建一个map,当做程序运行时的堆,所有对象均放到这个堆中。来看一下实现代码:

var dui map[string]int

func runtime() {
	dui = make(map[string]int)
	for _, cmd := range cmds {
		switch cmd.action {
		case MOV:
			mov(cmd.left, cmd.right)
		case SUB:
			sub(cmd.left, cmd.right)
		case OUT:
			out(cmd.left)
		case ADD:
			add(cmd.left, cmd.right)
		case DIV:
			div(cmd.left, cmd.right)
		case MUT:
			mut(cmd.left, cmd.right)
		}
	}
}

针对每个指令,在编写不同的处理函数,这块实现也相对简单:

func mov(l string, r string) {
	num, bo := isNumber(r)
	if bo == true {
		dui[l] = num
	} else {
		dui[l] = dui[r]
	}
}

func sub(l string, r string) {
	num, bo := isNumber(r)
	if bo == true {
		dui[l] = dui[l] - num
	} else {
		dui[l] = dui[l] - dui[r]
	}
}
func add(l string, r string) {
	num, bo := isNumber(r)
	if bo == true {
		dui[l] = dui[l] + num
	} else {
		dui[l] = dui[l] + dui[r]
	}
}
func div(l string, r string) {
	num, bo := isNumber(r)
	if bo == true {
		dui[l] = dui[l] / num
	} else {
		dui[l] = dui[l] / dui[r]
	}
}
func mut(l string, r string) {
	num, bo := isNumber(r)
	if bo == true {
		dui[l] = dui[l] * num
	} else {
		dui[l] = dui[l] * dui[r]
	}
}
func out(l string) {
	fmt.Println(dui[l])
}

完成

到此为止,我们所有的逻辑都编写完成,接下来编写main函数,将所有逻辑串联起来:

func main() {
	code, err := readFile()
	if err != nil {
		fmt.Println("Fatal error: no input file")
		return
	}

	la(string(code))
	if len(errorList) != 0 {
		for _, val := range errorList {
			fmt.Println(val)
		}
		return
	}
	runtime()
}

存在的问题

这仅是一个小示例,里面存在很多不完善的地方。例如,当我们在源码中存在一个空行,那么运行时会报错,提示未定义的指令等等。但对于理解编译原理来说是个不错的尝试。

enjoy!