面试题：Go语言token解析与语法树构建

Question

在实现一个简单的Go语言表达式解析器时，如何利用token进行语法树的构建？请描述大致的算法思路和关键步骤。

Answer 1

1. 算法思路：
   • 词法分析将输入的表达式字符串转换为一个个token，例如数字、操作符等。
   • 基于这些token，通过递归下降分析或算符优先分析等方法来构建语法树。语法树的节点可以代表表达式中的操作数、操作符等元素，树的结构反映了表达式的语法结构。
2. 关键步骤：
   • 词法分析：
     • 使用正则表达式或状态机实现词法分析器，将输入字符串按规则切分成token序列。例如，对于表达式3 + 5 * 2，会生成类似[NUMBER:3, OPERATOR: +, NUMBER:5, OPERATOR: *, NUMBER:2]的token序列。
   • 语法树构建：
     • 递归下降分析：
       • 从token序列头部开始处理。如果第一个token是操作数（如数字），创建一个操作数节点。
       • 如果是操作符，创建一个操作符节点，然后递归处理操作符左右两侧的子表达式，分别创建子树并连接到操作符节点的左右子节点。例如对于3 + 5，先处理3创建数字节点，遇到+创建操作符节点，再处理5创建数字节点并连接到+操作符节点的左右子节点。
     • 算符优先分析：
       • 维护一个操作数栈和一个操作符栈。
       • 遍历token序列，若为操作数，压入操作数栈；若为操作符，比较其与操作符栈栈顶操作符的优先级。
       • 如果当前操作符优先级高于栈顶操作符，将当前操作符压入操作符栈；否则，从操作数栈弹出两个操作数，从操作符栈弹出一个操作符，创建一个操作符节点并将两个操作数节点作为子节点连接，再将新节点压入操作数栈，重复此比较和操作直到当前操作符可以压入操作符栈。
       • 遍历结束后，操作数栈中剩余的节点即为语法树的根节点（如果表达式合法）。