对抽象语法树（AST）求值的思路(4)
前言
原本此文想要接上一个议题，在实现代码内函数定义后， 如何进一步方便地注册一些有用的函数，作为运行时环境。
但我打算现在优先讨论Visitor设计模式，这个对于实现对AST的求值并不是必须的， 更多地是程序架构方面的问题。
回顾
先简单回顾一下，一个解释器如何设计才算比较好的架构，
首先是词法分析器（Tokenizer，Lexer）与语法分析器（Parser）的解耦。 词法分析负责最初的断词，例如判断哪些是字符串，哪些是关键字， 哪些是数值、哪些是注释等等。
由词法分析器获得断词后再交由语法分析器生成AST抽象语法树，
这样，如果我对现有词法不满意，例如，我希望注释是以#开头，而不是以//开头，
或者相关换一个关键字，那么，只需要换一个词法分析器即可，
词法分析用一个接口，GetToken(string) []Token，即可。
同样，如果对语法不满意，也可以换Parser，只要最终AST结构一致， 当然，我感觉改了Parser，AST结构应该多少有些变化。
大致的数据流是：
string -> 词法分析器 -> Tokens -> 语法分析器 -> AST
当然，也有可能不需要那么通用，也有可能词法分析、语法分析放在一起会好一点， 这个依实际情况而定。
现在在获得AST抽象语法树后，就可以像前文那样用ASTNode.eval()求值了，
然而，仔细思考一下，AST语法树是数据，eval()是针对该数据的操作，
事实上，针对AST抽象语法树的操作还可以有很多种，并不仅仅用与某一具体的求值操作。
例如，可以针对AST抽象语法树进行代码格式化，输出该脚本语言的string， 或者将该脚本翻译等效的其他编程语言，如Python或者Java之类。 所以，应考虑将数据与操作解耦，对应于Java中的Visitor访问者模式。
另一种专有名词是双分派，因为操作对于数据而言是多态的， 而数据对于操作而言而是多态的，
但Java和C++等语言没有原生支持多分派，所以用Visitor访问者模式来解决这一问题。
关于双分派，参见 https://en.wikipedia.org/wiki/Double_dispatch
实现
为了将问题集中到visitor模式，将问题简化，这里仅处理部分基本类型的加法，这在此系列第一篇文章中已经实现， 这里仅重构。
代码如下，可以看到对比原先每个节点实现Eval函数，这里将所有操作都集中在名为EvalNode的struct中， 该结构实现了名为ExpressionVisitor的接口。 这样一方面的好处是操作更集中，如何每个节点在不同文件中，很难确知其具体动作， 另一个好处是解耦，数据无需限制自己应该做怎样的操作，其操作既可以是求值，也可以是其他，例如格式化等等， 添加新的操作仅需实现ExpressionVisitor接口即可。
package main
import "fmt"
type NodeValueType uint8
const (
TypeUnknown = NodeValueType(iota)
TypeInteger
TypeFloat
TypeString
TypeBool
)
type NodeValue struct {
Typ NodeValueType
Value interface{}
}
func (r *NodeValue) ToString() string {
switch r.Typ {
case TypeInteger, TypeString, TypeFloat, TypeBool:
return fmt.Sprint(r.Value)
default:
return ""
}
}
func (r *NodeValue) ToFloat() float64 {
switch r.Typ {
case TypeFloat:
return r.Value.(float64)
case TypeInteger:
return float64(r.Value.(int64))
default:
panic("Unexcept Behavior.")
}
}
type ExpressionVisitor interface {
VisitIntegerNode(node *IntegerNode)
VisitFloat(node *FloatNode)
VisitAddNode(node *AddNode)
VisitStringNode(node *StringNode)
VisitBoolNode(node *BoolNode)
}
// 实现ExpressionVisitor接口
type EvalNode struct {
Value *NodeValue
}
func NewEvalNode() *EvalNode {
return &EvalNode{Value: nil}
}
func (e *EvalNode) VisitIntegerNode(node *IntegerNode) {
e.Value = &NodeValue{Typ: TypeInteger, Value: node.Val}
}
func (e *EvalNode) VisitFloat(node *FloatNode) {
e.Value = &NodeValue{Typ: TypeFloat, Value: node.Val}
}
func (e *EvalNode) VisitStringNode(node *StringNode) {
e.Value = &NodeValue{Typ: TypeString, Value: node.Val}
}
func (e *EvalNode) VisitBoolNode(node *BoolNode) {
e.Value = &NodeValue{Typ: TypeBool, Value: node.Val}
}
func (e *EvalNode) VisitAddNode(node *AddNode) {
node.Left.Accept(e)
leftEval := e.Value
node.Right.Accept(e)
rightEval := e.Value
switch {
case leftEval.Typ == TypeString || rightEval.Typ == TypeString:
e.Value = &NodeValue{
Typ: TypeString,
Value: leftEval.ToString() + rightEval.ToString(),
}
return
case leftEval.Typ == TypeFloat || rightEval.Typ == TypeFloat:
e.Value = &NodeValue{
Typ: TypeString,
Value: leftEval.ToFloat() + rightEval.ToFloat(),
}
return
case leftEval.Typ == TypeInteger && rightEval.Typ == TypeInteger:
e.Value = &NodeValue{
Typ: TypeInteger,
Value: leftEval.Value.(int64) + rightEval.Value.(int64),
}
return
default:
e.Value = &NodeValue{
Typ: TypeUnknown,
Value: nil,
}
}
}
type Node interface {
Accept(visitor ExpressionVisitor)
}
//整数节点
type IntegerNode struct {
Val int64
}
func NewIntegerNode(v int64) *IntegerNode {
return &IntegerNode{Val: v}
}
func (n *IntegerNode) Accept(visitor ExpressionVisitor) {
visitor.VisitIntegerNode(n)
}
//float节点
type FloatNode struct {
Val float64
}
func NewFloatNode(v float64) *FloatNode {
return &FloatNode{Val: v}
}
func (n *FloatNode) Accept(visitor ExpressionVisitor) {
visitor.VisitFloat(n)
}
//string节点
type StringNode struct {
Val string
}
func NewStringNode(v string) *StringNode {
return &StringNode{Val: v}
}
func (n *StringNode) Accept(visitor ExpressionVisitor) {
visitor.VisitStringNode(n)
}
//bool节点
type BoolNode struct {
Val bool
}
func NewBoolNode(v bool) *BoolNode {
return &BoolNode{Val: v}
}
func (n *BoolNode) Accept(visitor ExpressionVisitor) {
visitor.VisitBoolNode(n)
}
//加法节点
type AddNode struct {
Left Node
Right Node
}
func (n *AddNode) Accept(visitor ExpressionVisitor) {
visitor.VisitAddNode(n)
}
func NewAddNode(l, r Node) *AddNode {
return &AddNode{
Left: l,
Right: r,
}
}
func main() {
// "127.0.0.1:8080" + "/api/test"
ast := NewAddNode(NewStringNode("127.0.0.1:8080"), NewStringNode("/api/test"))
e := NewEvalNode()
fmt.Println("Start Eval")
ast.Accept(e)
r := e.Value
if r.Typ == TypeString {
fmt.Println("\"127.0.0.1:8080\" + \"/api/test\" = ", r.Value.(string))
}
// "str" + false + (1 + 1.2) + (3 + 4)
ast = NewAddNode(
NewAddNode(
NewAddNode(
NewStringNode("str"),
NewBoolNode(false)),
NewAddNode(
NewIntegerNode(1),
NewFloatNode(1.2))),
NewAddNode(
NewIntegerNode(3),
NewIntegerNode(4)))
e = NewEvalNode()
fmt.Println("Start Eval")
ast.Accept(e)
r = e.Value
if r.Typ == TypeString {
//结果为"str " + false + 2.2 + 7 -> "str false2.2" + 7 -> "str false2.27"
fmt.Println("\"str \" + false + (1 + 1.2) + (3 + 4) = ", r.Value.(string))
}
}
以下代码示意了将代码格式化，可以看到，想要添加新的操作是多么简单的一件事情， 完整演示的代码就不贴了，很简单。
不过通过这个代码看到另一个细节，Print内包含Buf这个字符串来处理中间结果， 而EvalNode通过内含Value这个NodeType来获得返回的中间结果， 这个是因不同需求而异的， 而原先没有visitor模式的实现中是直接将Eval函数返回NodeType， 而这里不可以，因为要保证接口一致，对于EvalNode可能想返回NodeType， 而Print想返回buf，所以这种特殊化的地方放在struct内部比较好。
// 实现ExpressionVisitor接口
type Print struct {
w io.Writer
Buf string
}
func NewPrint() *Print {
return &Print{
w: os.Stdout,
Buf: "",
}
}
func (p* Print) Print() {
fmt.Fprintln(p.w, p.Buf)
}
func (p *Print) VisitIntegerNode(node *IntegerNode) {
p.Buf += strconv.FormatInt(node.Val, 10)
}
func (p *Print) VisitFloat(node *FloatNode) {
p.Buf += strconv.FormatFloat(node.Val, 'g', -1, 64)
}
func (p *Print) VisitAddNode(node *AddNode) {
p.Buf += "("
node.Left.Accept(p)
p.Buf += " + "
node.Right.Accept(p)
p.Buf += ")"
}
func (p *Print) VisitStringNode(node *StringNode) {
p.Buf += strconv.Quote(node.Val)
}
func (p *Print) VisitBoolNode(node *BoolNode) {
p.Buf += strconv.FormatBool(node.Val)
}