对抽象语法树（AST）求值的思路(2)
改进此文档
03 May 2017
前言
上一篇解决了不同数据类型的加法， 减法、乘法、除法都类似，只是不能用于字符串， 或者说加法被扩展为连接字符串操作。 所以其他四则运算就忽略了，
现在考虑如何定义变量，引用变量以及调用函数。
定义变量和调用变量
定义变量以及调用变量，本质可以理解为一个用一种数据结构保存数据，并在需要的时候取数据， 所以用map比较合适，可以直接用变量名作为key，值作为value。
稍微麻烦一点的是考虑作用域(scope)，全局的作用域，函数内的作用域、闭包等等， 可以通过类似于一个stack的层次结构实现 (因为后进的变量，作用域更靠内，需要优先被查找)， 先在本作用域内找变量，找不到再到外层作用域找，直到全局内找到变量，或者没找到返回错误。
关于作用域，lexical scoping和dynamic scoping以及闭包的概念，可以参见：
http://www.yinwang.org/blog-cn/2012/08/01/interpreter
需要先了解一下Scheme或者Racket的语法。
定义变量与调用变量的实现
先不考虑作用域，将所有变量视为全局变量， 设计一个结构，存储这样的map，并提供取变量和存储变量的函数。
type Environment struct {
envName string
store map[string]NodeValue
}
func NewEnvironment(name string) *Environment {
return &Environment{
envName: name,
store: make(map[string]NodeValue),
}
}
func (e *Environment) SaveVariable(varName string, value NodeValue) {
e.store[varName] = value
}
func (e *Environment) GetVariable(varName string) NodeValue {
value, exists := e.store[varName]
if !exists {
panic("variable not found")
}
return value
}
声明变量与调用变量
//声明变量
type DeclarationNode struct {
varName string
val Node
env *Environment
}
func NewDeclarationNode(environment *Environment, name string, n Node) *DeclarationNode {
return &DeclarationNode{
varName: name,
val: n,
env: environment,
}
}
func (n *DeclarationNode) Eval() NodeValue {
value := n.val.Eval()
n.env.SaveVariable(n.varName, value)
return value
}
//获取变量
type VariableNode struct {
varName string
env *Environment
}
func NewVariableNode(environment *Environment, name string) *VariableNode {
return &VariableNode{
varName: name,
env: environment,
}
}
func (n *VariableNode) Eval() NodeValue {
return n.env.GetVariable(n.varName)
}
完整代码
package main
import "fmt"
type NodeValueType uint8
const (
TypeUnknown = NodeValueType(iota)
TypeInteger
TypeFloat
TypeString
TypeBool
)
type NodeValue struct {
Typ NodeValueType
Value interface{}
}
type Environment struct {
envName string
store map[string]NodeValue
}
func NewEnvironment(name string) *Environment {
return &Environment{
envName: name,
store: make(map[string]NodeValue),
}
}
func (e *Environment) SaveVariable(varName string, value NodeValue) {
e.store[varName] = value
}
func (e *Environment) GetVariable(varName string) NodeValue {
value, exists := e.store[varName]
if !exists {
panic("variable not found")
}
return value
}
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 DeclarationNode struct {
varName string
val Node
env *Environment
}
func NewDeclarationNode(environment *Environment, name string, n Node) *DeclarationNode {
return &DeclarationNode{
varName: name,
val: n,
env: environment,
}
}
func (n *DeclarationNode) Eval() NodeValue {
value := n.val.Eval()
n.env.SaveVariable(n.varName, value)
return value
}
//获取变量
type VariableNode struct {
varName string
env *Environment
}
func NewVariableNode(environment *Environment, name string) *VariableNode {
return &VariableNode{
varName: name,
env: environment,
}
}
func (n *VariableNode) Eval() NodeValue {
return n.env.GetVariable(n.varName)
}
//加法节点
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() {
globalEnv := NewEnvironment("global")
//var a = "this is a test[" + 123 + "]"
declareAst := NewDeclarationNode(globalEnv, "a",
NewAddNode(
NewAddNode(
NewStringNode("this is a test["),
NewIntegerNode(123)),
NewStringNode("]")))
declareAst.Eval()
// a + 456
ast := NewAddNode(
NewVariableNode(globalEnv, "a"),
NewIntegerNode(456))
fmt.Println("Start Eval:")
r := ast.Eval()
if r.Typ == TypeString {
fmt.Println(r.Value.(string))
}
}
调用函数
再写下一篇文章
-----EOF-----