自己动手写编译器:自顶向下的自动状态机

本节我们介绍编译原理中一种新的数据结构叫自顶向下的自动状态机。前面我们在做词法解析时接触了大量自动状态机，他们存在一个缺陷那就是无法对要识别的字符串进行计数，因此当我们要判断括号对是否匹配时，使用在词法解析的状态机就处理不了，例如给定字符串"((())()))"，我们判断其中左右括号是否都能匹配上，以前的状态机就无法处理。

但如果我们匹配上一个数据结构，也就是“栈”，那么问题就能得到解决。我们把状态机跟一个栈组合在一起的情况就叫自顶向下的状态机(push-down automaton)也叫 PDA。这个结构很重要，后续我们的语法解析算法就得依赖它。

我们看看其运行的基本流程。在词法解析中，状态机的当前所处状态由上一个状态和输入字符共同决定，但是在 PDA 中，状态机的状态由堆栈顶部的元素决定，堆栈中存储的是状态机各个状态的状态值，同时状态机在接收到字符输入后，它输出的不再是下一个状态节点，而是对应要采取的行动，下一个状态节点要从堆栈的顶部获取。在状态机中有四种行动可以采取，分别为：
1，接收，当状态机采取该行动时表示当前接收字符所形成的字符串。
2，错误，当状态机采取该行动时表示当前接收字符形成的字符串不符合状态机的规则。
3，push N, 把状态机节点 n压入堆栈顶部。
4，pop, 从堆栈中取出顶部元素，该元素的取值对应状态机所在状态。

我们看看如何使用 PDA 来识别括号字符串是否满足括号匹配。首先状态表如：

我们使用 state_table来表示上表，在状态 0 就是起始状态，我们使用如下算法或流程来表示括号识别流程：

将初始状态节点压入堆栈
while(action=state_table[当前堆栈顶部节点数值][输入字符] != accept) {
    if(action == error) {
        print("括号字符串不匹配")
        return 1;
    }
    else {
        执行 action 对应操作
    }
}

我们看看如何使用代码实现上面算法，还是基于前面的dragon-compiler 项目来进行，在项目目录下新建一个 pda 文件夹，然后执行：

init pda

进行初始化模块，然后在给定目录创建代码文件 pda.go，并下输入代码如下：

package pda

import (
	"fmt"
)

const (
	ERROR = iota
	ACCEPT
	PUSH1
	POP
	EOF
)

type StateTable struct{}

func (s *StateTable) get(state int8, symbol int) int8 {
	if state == 0 {
		switch symbol {
		case '(':
			return PUSH1
		case ')':
			return ERROR
		case EOF:
			return ACCEPT
		}
	}

	if state == 1 {
		switch symbol {
		case '(':
			return PUSH1
		case ')':
			return POP
		case EOF:
			return ERROR
		}
	}

	panic("state can only 0 or 1")
}

type BracketPDA struct {
	stateTable *StateTable
	stack      []int8
}

func NewBracketPDA() *BracketPDA {
	pda := &BracketPDA{
		stateTable: &StateTable{},
		stack:      make([]int8, 0),
	}

	pda.stack = append(pda.stack, 0)

	return pda
}

func (b *BracketPDA) Parse(str string) {
	pos := 0
	for true {
		symbol := EOF
		if pos < len(str) {
			symbol = int(str[pos])
		}
		state := b.stack[len(b.stack)-1]
		action := b.stateTable.get(state, symbol)
		switch action {
		case ERROR:
			fmt.Printf("str: %s, is rejected\n", str)
			return
		case ACCEPT:
			fmt.Printf("str: %s, is accept\n", str)
			return
		case PUSH1:
			b.stack = append(b.stack, 1)
		case POP:
			b.stack = b.stack[:len(b.stack)-1]
		}

		pos += 1
		if symbol == EOF {
			return
		}
	}
}

上面代码中StateTable用来模拟状态表，它只有一个方法那就是 get，输入当前状态和读入的字符，它给出要采取的行动，如果返回 PUSH1，那么我们需要将状态值 1 压入堆栈，其他的依次类推。BracketPDA用来模拟整个 PDA，它包含一个堆栈 stack 用来存放状态节点，对应的 Parse 函数在输入括号字符串后启动匹配过程，Parse 函数遍历输入字符串的每个字符，然后获取堆栈顶部的状态节点值，通过 StateTable 的 get 函数获取要采取的动作，如果 get 返回 accept，那么进入接收状态，如果返回 ERROR，那么进入错误状态，返回 PUSH1 则将节点 1 压入堆栈，如果返回 POP，则将堆栈顶部的元素弹开。

在 main.go 中使用调用 PDA 的代码如下：

package main

import (
	"pda"
)

func main() {
	pdaParser := pda.NewBracketPDA()
	pdaParser.Parse("(())")
}

上面代码运行后所得结果如下：

str: (()), is accept

也就是输入的括号字符串"(())“能够匹配，我们可以去掉其中一个括号试试，例如 pdaParser.Parse(”(()"),所得结果如下：

str: ((), is rejected

由此可见我们实现的 PDA 能有效的识别输入的括号字符串是否匹配。更多调试演示和讲解视频请在 b 站搜索"coding 迪斯尼“，代码下载为：
https://github.com/wycl16514/compiler-push-down-automata.git