对抽象语法树（AST）求值的思路
前言
设计程序语言第一步是断词(Token)，分类得到字符串、整数、浮点数，关键字以及变量等等。
第二步由给定设计的语法将一句话翻译成一个数据结构，这个结构通常是抽象语法树， 当然也可以不是树，只要能恰当保存信息即可。
所以前期考虑的关键是用某种合适的结构保存有用的信息。
用生活中的例子来说，
我 正在 吃 饭。
将所有信息用一个结构保存起来就是：
主语：我
时间：现在
动作：吃
宾语：饭
解释编程语言也是同样的道理，也是将一句话（写的代码）翻译成一种保存所有信息的数据结构。
关于断词（Tokenizer）以及根据语法构造抽象语法树的过程可以参见：
http://llvm-tutorial-cn.readthedocs.io/en/latest/index.html
抽象语法树为什么是树
之所以很多时候会是树状是因为比如有很多二元操作符（或者更多元），例如加法，
3 + 4，就有两个操作数，就像一个根节点是+，子节点分别是3和4。
这是中缀写法，即语法上+在正中间。也有前缀写法（例如lisp语言），(+ 1 2 3)，就是1加2加3，
事实上前缀相对于中缀写法更好，例如可以更好地表达可变长参数，事实上func add(num ...int)，这种函数调用就是一种前缀写法，
“操作” add 在最左边。
抽象语法树为什么是抽象
其抽象的含义是指从一门具体的语言中抽取出与语言无关的语法树，例如1+1和one add one都可抽象成同一类语法树，也就是说与具体语言表现形式无关。
而我认为如果从另一层角度来说，语法树的节点类型也是抽象的。
以加法为例1 + 2，左右两边是数字，而1 * 2 + 3，加法左边子节点是*，右边子节点是3，*的子节点是1和2，
如果考虑random(100) + myvar，等等子节点的类型还可能是函数，是变量，这就更多了，所以需要用抽象来解决这个问题。
本文主题
问题在于何如实现对这样的抽象语法树的求解， 本文逐步分析， 实现一个解释器的以下功能：
- 加减乘除，实现加法后其他四则运算不难，所以只示例加法。
- 用
+作为字符串的连接符，或者说+针对string类型作为连接字符串的特殊操作。 - 普通变量的定义以及引用。
- 函数的定义与调用。
实现了以上功能，基本上已经把很多方面覆盖了， 更复杂的语法树的求值思路也是类似的， 本文采用golang实现。
分析
假设要解释3 * myvar + random(100)，作为例子，
假设执行到+节点了，它的左边是*，右边节点是random，一个函数调用，
所以第一步要能够判断左右节点类型，确知是乘法或者random函数，这是一种思路。
第二种就是无需判断左右节点类型，用多态的思路，不管节点是什么类型，只要节点用某个函数node.eval()
得到某种+方便处理的数据，这样的数据应该至少包含两个信息，类型和值。
比如3*myvar，假设myvar为整型10，那么理想条件下，左节点leftNode.eval()结果为node{type:Integer ,value:30}。
便得到类型为整型，值为30。
右边节点也是同样的道理。
值value要能够保存不同值类型，我尝试过用[]byte，但一时没成功，
float64与[]byte之间转换出问题，没深究，后采用interface{}解决。
当然，[]byte应该也是可以的，https://github.com/buger/jsonparser就是用[]byte保存不同类型。
实现
最简单的实现
先实现最简单的功能，只做整数加法，忽略error处理：
package main
import "fmt"
type NodeValueType uint8
const (
TypeUnknown = NodeValueType(iota)
TypeInteger
// TypeFloat
// TypeString
)
type NodeValue struct {
Typ NodeValueType
Value interface{}
}
type Node interface {
Eval() NodeValue
}
//整数节点
type IntegerNode struct {
intValue int64
}
func NewIntegerNode(v int64) *IntegerNode {
return &IntegerNode{
intValue: v,
}
}
func (an *IntegerNode) Eval() NodeValue {
return NodeValue{
Typ: TypeInteger,
Value: an.intValue,
}
}
//加法节点
type AddNode struct {
left Node
right Node
}
func NewAddNode(l, r Node) *AddNode {
return &AddNode{
left: l,
right: r,
}
}
func (an *AddNode) Eval() NodeValue {
leftEval := an.left.Eval()
rightEval := an.right.Eval()
switch {
case leftEval.Typ == TypeInteger && rightEval.Typ == TypeInteger:
return NodeValue{
Typ: TypeInteger,
Value: leftEval.Value.(int64) + rightEval.Value.(int64),
}
default:
return NodeValue{
Typ: TypeUnknown,
Value: nil,
}
}
}
func main() {
// (1 + 2) + (3 + 4)
ast := NewAddNode(NewAddNode(NewIntegerNode(1), NewIntegerNode(2)),
NewAddNode(NewIntegerNode(3), NewIntegerNode(4)))
fmt.Println("Start Eval...")
res := ast.Eval()
fmt.Println("result:")
if res.Typ == TypeInteger {
fmt.Println("(1 + 2) + (3 + 4) = ", res.Value.(int64))
}
}
将类型补充完整
假定根据需求有如下规则：
整数 + 整数 -> 整数
浮点数 + 浮点数 -> 浮点数
浮点数 + 整数 -> 浮点数
整数 + 浮点数 -> 浮点数
字符串 + 整数 -> 字符串
整数 + 字符串 -> 字符串
字符串 + 浮点数 -> 字符串
浮点数 + 字符串 -> 字符串
这样的分类让人很头疼，如果再多一个类型，比如bool类型，把所有情况再都列举一遍就更麻烦了， 当然，其实这样将所有情况列举出来也不难，情况应该不算多，还很清晰。
更进一步分析，可以看到某些类型有某种特定的“提升”类型的操作，
例如整数遇到浮点数会“提升”为浮点数，
整数遇到字符串，会“提升”为字符串，浮点数遇到字符串会“提升”为字符串。
而反过来字符串就不会自动“降为”整型。
利用这一个特点，要两个类型中有一个是字符串是就ToString()，
然后再判断当其中一个是浮点，就ToFloat()，
有些情况，比如bool不应该转化成float就输出error或者panic。
就用这种办法解决吧，如果用多态解决，Result再分成几个子类，看着很复杂，且不一定好。
代码：
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 Node interface {
Eval() NodeValue
}
//整数节点
type IntegerNode struct {
val int64
}
func NewIntegerNode(v int64) *IntegerNode {
return &IntegerNode{val: v}
}
func (n *IntegerNode) Eval() NodeValue {
return NodeValue{
Typ: TypeInteger,
Value: n.val,
}
}
//float节点
type FloatNode struct {
val float64
}
func NewFloatNode(v float64) *FloatNode {
return &FloatNode{val: v}
}
func (n *FloatNode) Eval() NodeValue {
return NodeValue{
Typ: TypeFloat,
Value: n.val,
}
}
//string节点
type StringNode struct {
val string
}
func NewStringNode(v string) *StringNode {
return &StringNode{val: v}
}
func (n *StringNode) Eval() NodeValue {
return NodeValue{
Typ: TypeString,
Value: n.val,
}
}
//bool节点
type BoolNode struct {
val bool
}
func NewBoolNode(v bool) *BoolNode {
return &BoolNode{val: v}
}
func (n *BoolNode) Eval() NodeValue {
return NodeValue{
Typ: TypeBool,
Value: n.val,
}
}
//加法节点
type AddNode struct {
left Node
right Node
}
func NewAddNode(l, r Node) *AddNode {
return &AddNode{
left: l,
right: r,
}
}
func (n *AddNode) Eval() NodeValue {
leftEval := n.left.Eval()
rightEval := n.right.Eval()
switch {
case leftEval.Typ == TypeString || rightEval.Typ == TypeString:
return NodeValue{
Typ: TypeString,
Value: leftEval.ToString() + rightEval.ToString(),
}
case leftEval.Typ == TypeFloat || rightEval.Typ == TypeFloat:
return NodeValue{
Typ: TypeString,
Value: leftEval.ToFloat() + rightEval.ToFloat(),
}
case leftEval.Typ == TypeInteger && rightEval.Typ == TypeInteger:
return NodeValue{
Typ: TypeInteger,
Value: leftEval.Value.(int64) + rightEval.Value.(int64),
}
default:
return NodeValue{
Typ: TypeUnknown,
Value: nil,
}
}
}
func main() {
// "127.0.0.1:8080" + "/api/test"
ast := NewAddNode(NewStringNode("127.0.0.1:8080"), NewStringNode("/api/test"))
fmt.Println("Start Eval")
r := ast.Eval()
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)))
fmt.Println("Start Eval")
r = ast.Eval()
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))
}
}
类型问题并没完全解决，因为这些还只是基本类型，而更复杂是是复合类型，留待解决。
接着的内容是定义变量，引用变量以及调用函数，写另一篇文章讨论。
补充
本文用枚举类型来描述Type，这只能针对基本类型，复合类型应该定义更复杂的类型，
另外，我发现最好不用枚举而是用string， 这是因为在后期，用visitor设计模式访问抽象语法树时，抽象语法树只存储数据， 不考虑数据怎么用，也就是说如果是复合类型，对于抽象语法树而言， 它只是一个string，一个Identifier，并不含任何意义，所以应该用string。 赋予它含义，那是visitor的事情了。