当前位置：首页 > news >正文

读go语言自制解释器（二）解析ast

news 来源：原创 2024/9/20 0:00:27

简介

书中对这部分的介绍是对ast进行求值，但我感觉应该叫语义分析更加合适一点，单纯的ast是没有意义的，需要对其进行相关解析，生成符合自己需求的结果，才更加合适。

符号表（应该算是）

对象定义

package objectimport ("bytes""fmt""monkey/ast""strings"
)type ObjectType stringconst (NULL_OBJ  = "NULL"ERROR_OBJ = "ERROR"INTEGER_OBJ = "INTEGER"BOOLEAN_OBJ = "BOOLEAN"RETURN_VALUE_OBJ = "RETURN_VALUE"FUNCTION_OBJ = "FUNCTION"
)type Object interface {Type() ObjectTypeInspect() string
}type Integer struct {Value int64
}func (i *Integer) Type() ObjectType { return INTEGER_OBJ }
func (i *Integer) Inspect() string  { return fmt.Sprintf("%d", i.Value) }type Boolean struct {Value bool
}func (b *Boolean) Type() ObjectType { return BOOLEAN_OBJ }
func (b *Boolean) Inspect() string  { return fmt.Sprintf("%t", b.Value) }type Null struct{}func (n *Null) Type() ObjectType { return NULL_OBJ }
func (n *Null) Inspect() string  { return "null" }type ReturnValue struct {Value Object
}func (rv *ReturnValue) Type() ObjectType { return RETURN_VALUE_OBJ }
func (rv *ReturnValue) Inspect() string  { return rv.Value.Inspect() }type Error struct {Message string
}func (e *Error) Type() ObjectType { return ERROR_OBJ }
func (e *Error) Inspect() string  { return "ERROR: " + e.Message }type Function struct {Parameters []*ast.IdentifierBody       *ast.BlockStatementEnv        *Environment
}func (f *Function) Type() ObjectType { return FUNCTION_OBJ }
func (f *Function) Inspect() string {var out bytes.Bufferparams := []string{}for _, p := range f.Parameters {params = append(params, p.String())}out.WriteString("fn")out.WriteString("(")out.WriteString(strings.Join(params, ", "))out.WriteString(") {\n")out.WriteString(f.Body.String())out.WriteString("\n}")return out.String()
}

符号表定义

package objectfunc NewEnclosedEnvironment(outer *Environment) *Environment {env := NewEnvironment()env.outer = outerreturn env
}func NewEnvironment() *Environment {s := make(map[string]Object)return &Environment{store: s, outer: nil}
}type Environment struct {store map[string]Objectouter *Environment
}func (e *Environment) Get(name string) (Object, bool) {obj, ok := e.store[name]if !ok && e.outer != nil {obj, ok = e.outer.Get(name)}return obj, ok
}func (e *Environment) Set(name string, val Object) Object {e.store[name] = valreturn val
}

语义分析过程如下

package evaluatorimport ("fmt""monkey/ast""monkey/object"
)var (NULL  = &object.Null{}TRUE  = &object.Boolean{Value: true}FALSE = &object.Boolean{Value: false}
)func Eval(node ast.Node, env *object.Environment) object.Object {switch node := node.(type) {// Statementscase *ast.Program:return evalProgram(node, env)case *ast.BlockStatement:return evalBlockStatement(node, env)case *ast.ExpressionStatement:return Eval(node.Expression, env)case *ast.ReturnStatement:val := Eval(node.ReturnValue, env)if isError(val) {return val}return &object.ReturnValue{Value: val}case *ast.LetStatement:val := Eval(node.Value, env)if isError(val) {return val}env.Set(node.Name.Value, val)// Expressionscase *ast.IntegerLiteral:return &object.Integer{Value: node.Value}case *ast.Boolean:return nativeBoolToBooleanObject(node.Value)case *ast.PrefixExpression:right := Eval(node.Right, env)if isError(right) {return right}return evalPrefixExpression(node.Operator, right)case *ast.InfixExpression:left := Eval(node.Left, env)if isError(left) {return left}right := Eval(node.Right, env)if isError(right) {return right}return evalInfixExpression(node.Operator, left, right)case *ast.IfExpression:return evalIfExpression(node, env)case *ast.Identifier:return evalIdentifier(node, env)case *ast.FunctionLiteral:params := node.Parametersbody := node.Bodyreturn &object.Function{Parameters: params, Env: env, Body: body}case *ast.CallExpression:function := Eval(node.Function, env)if isError(function) {return function}args := evalExpressions(node.Arguments, env)if len(args) == 1 && isError(args[0]) {return args[0]}return applyFunction(function, args)}return nil
}func evalProgram(program *ast.Program, env *object.Environment) object.Object {var result object.Objectfor _, statement := range program.Statements {result = Eval(statement, env)switch result := result.(type) {case *object.ReturnValue:return result.Valuecase *object.Error:return result}}return result
}func evalBlockStatement(block *ast.BlockStatement,env *object.Environment,
) object.Object {var result object.Objectfor _, statement := range block.Statements {result = Eval(statement, env)if result != nil {rt := result.Type()if rt == object.RETURN_VALUE_OBJ || rt == object.ERROR_OBJ {return result}}}return result
}func nativeBoolToBooleanObject(input bool) *object.Boolean {if input {return TRUE}return FALSE
}func evalPrefixExpression(operator string, right object.Object) object.Object {switch operator {case "!":return evalBangOperatorExpression(right)case "-":return evalMinusPrefixOperatorExpression(right)default:return newError("unknown operator: %s%s", operator, right.Type())}
}func evalInfixExpression(operator string,left, right object.Object,
) object.Object {switch {case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:return evalIntegerInfixExpression(operator, left, right)case operator == "==":return nativeBoolToBooleanObject(left == right)case operator == "!=":return nativeBoolToBooleanObject(left != right)case left.Type() != right.Type():return newError("type mismatch: %s %s %s",left.Type(), operator, right.Type())default:return newError("unknown operator: %s %s %s",left.Type(), operator, right.Type())}
}func evalBangOperatorExpression(right object.Object) object.Object {switch right {case TRUE:return FALSEcase FALSE:return TRUEcase NULL:return TRUEdefault:return FALSE}
}func evalMinusPrefixOperatorExpression(right object.Object) object.Object {if right.Type() != object.INTEGER_OBJ {return newError("unknown operator: -%s", right.Type())}value := right.(*object.Integer).Valuereturn &object.Integer{Value: -value}
}func evalIntegerInfixExpression(operator string,left, right object.Object,
) object.Object {leftVal := left.(*object.Integer).ValuerightVal := right.(*object.Integer).Valueswitch operator {case "+":return &object.Integer{Value: leftVal + rightVal}case "-":return &object.Integer{Value: leftVal - rightVal}case "*":return &object.Integer{Value: leftVal * rightVal}case "/":return &object.Integer{Value: leftVal / rightVal}case "<":return nativeBoolToBooleanObject(leftVal < rightVal)case ">":return nativeBoolToBooleanObject(leftVal > rightVal)case "==":return nativeBoolToBooleanObject(leftVal == rightVal)case "!=":return nativeBoolToBooleanObject(leftVal != rightVal)default:return newError("unknown operator: %s %s %s",left.Type(), operator, right.Type())}
}func evalIfExpression(ie *ast.IfExpression,env *object.Environment,
) object.Object {condition := Eval(ie.Condition, env)if isError(condition) {return condition}if isTruthy(condition) {return Eval(ie.Consequence, env)} else if ie.Alternative != nil {return Eval(ie.Alternative, env)} else {return NULL}
}func evalIdentifier(node *ast.Identifier,env *object.Environment,
) object.Object {val, ok := env.Get(node.Value)if !ok {return newError("identifier not found: " + node.Value)}return val
}func isTruthy(obj object.Object) bool {switch obj {case NULL:return falsecase TRUE:return truecase FALSE:return falsedefault:return true}
}func newError(format string, a ...interface{}) *object.Error {return &object.Error{Message: fmt.Sprintf(format, a...)}
}func isError(obj object.Object) bool {if obj != nil {return obj.Type() == object.ERROR_OBJ}return false
}func evalExpressions(exps []ast.Expression,env *object.Environment,
) []object.Object {var result []object.Objectfor _, e := range exps {evaluated := Eval(e, env)if isError(evaluated) {return []object.Object{evaluated}}result = append(result, evaluated)}return result
}func applyFunction(fn object.Object, args []object.Object) object.Object {function, ok := fn.(*object.Function)if !ok {return newError("not a function: %s", fn.Type())}extendedEnv := extendFunctionEnv(function, args)evaluated := Eval(function.Body, extendedEnv)return unwrapReturnValue(evaluated)
}func extendFunctionEnv(fn *object.Function,args []object.Object,
) *object.Environment {env := object.NewEnclosedEnvironment(fn.Env)for paramIdx, param := range fn.Parameters {env.Set(param.Value, args[paramIdx])}return env
}func unwrapReturnValue(obj object.Object) object.Object {if returnValue, ok := obj.(*object.ReturnValue); ok {return returnValue.Value}return obj
}

测试用例如下

package evaluatorimport ("monkey/lexer""monkey/object""monkey/parser""testing"
)func TestEvalIntegerExpression(t *testing.T) {tests := []struct {input    stringexpected int64}{{"5", 5},{"10", 10},{"-5", -5},{"-10", -10},{"5 + 5 + 5 + 5 - 10", 10},{"2 * 2 * 2 * 2 * 2", 32},{"-50 + 100 + -50", 0},{"5 * 2 + 10", 20},{"5 + 2 * 10", 25},{"20 + 2 * -10", 0},{"50 / 2 * 2 + 10", 60},{"2 * (5 + 10)", 30},{"3 * 3 * 3 + 10", 37},{"3 * (3 * 3) + 10", 37},{"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},}for _, tt := range tests {evaluated := testEval(tt.input)testIntegerObject(t, evaluated, tt.expected)}
}func TestEvalBooleanExpression(t *testing.T) {tests := []struct {input    stringexpected bool}{{"true", true},{"false", false},{"1 < 2", true},{"1 > 2", false},{"1 < 1", false},{"1 > 1", false},{"1 == 1", true},{"1 != 1", false},{"1 == 2", false},{"1 != 2", true},{"true == true", true},{"false == false", true},{"true == false", false},{"true != false", true},{"false != true", true},{"(1 < 2) == true", true},{"(1 < 2) == false", false},{"(1 > 2) == true", false},{"(1 > 2) == false", true},}for _, tt := range tests {evaluated := testEval(tt.input)testBooleanObject(t, evaluated, tt.expected)}
}func TestBangOperator(t *testing.T) {tests := []struct {input    stringexpected bool}{{"!true", false},{"!false", true},{"!5", false},{"!!true", true},{"!!false", false},{"!!5", true},}for _, tt := range tests {evaluated := testEval(tt.input)testBooleanObject(t, evaluated, tt.expected)}
}func TestIfElseExpressions(t *testing.T) {tests := []struct {input    stringexpected interface{}}{{"if (true) { 10 }", 10},{"if (false) { 10 }", nil},{"if (1) { 10 }", 10},{"if (1 < 2) { 10 }", 10},{"if (1 > 2) { 10 }", nil},{"if (1 > 2) { 10 } else { 20 }", 20},{"if (1 < 2) { 10 } else { 20 }", 10},}for _, tt := range tests {evaluated := testEval(tt.input)integer, ok := tt.expected.(int)if ok {testIntegerObject(t, evaluated, int64(integer))} else {testNullObject(t, evaluated)}}
}func TestReturnStatements(t *testing.T) {tests := []struct {input    stringexpected int64}{{"return 10;", 10},{"return 10; 9;", 10},{"return 2 * 5; 9;", 10},{"9; return 2 * 5; 9;", 10},{"if (10 > 1) { return 10; }", 10},{`
if (10 > 1) {if (10 > 1) {return 10;}return 1;
}
`,10,},{`
let f = fn(x) {return x;x + 10;
};
f(10);`,10,},{`
let f = fn(x) {let result = x + 10;return result;return 10;
};
f(10);`,20,},}for _, tt := range tests {evaluated := testEval(tt.input)testIntegerObject(t, evaluated, tt.expected)}
}func TestErrorHandling(t *testing.T) {tests := []struct {input           stringexpectedMessage string}{{"5 + true;","type mismatch: INTEGER + BOOLEAN",},{"5 + true; 5;","type mismatch: INTEGER + BOOLEAN",},{"-true","unknown operator: -BOOLEAN",},{"true + false;","unknown operator: BOOLEAN + BOOLEAN",},{"true + false + true + false;","unknown operator: BOOLEAN + BOOLEAN",},{"5; true + false; 5","unknown operator: BOOLEAN + BOOLEAN",},{"if (10 > 1) { true + false; }","unknown operator: BOOLEAN + BOOLEAN",},{`
if (10 > 1) {if (10 > 1) {return true + false;}return 1;
}
`,"unknown operator: BOOLEAN + BOOLEAN",},{"foobar","identifier not found: foobar",},}for _, tt := range tests {evaluated := testEval(tt.input)errObj, ok := evaluated.(*object.Error)if !ok {t.Errorf("no error object returned. got=%T(%+v)",evaluated, evaluated)continue}if errObj.Message != tt.expectedMessage {t.Errorf("wrong error message. expected=%q, got=%q",tt.expectedMessage, errObj.Message)}}
}func TestLetStatements(t *testing.T) {tests := []struct {input    stringexpected int64}{{"let a = 5; a;", 5},{"let a = 5 * 5; a;", 25},{"let a = 5; let b = a; b;", 5},{"let a = 5; let b = a; let c = a + b + 5; c;", 15},}for _, tt := range tests {testIntegerObject(t, testEval(tt.input), tt.expected)}
}func TestFunctionObject(t *testing.T) {input := "fn(x) { x + 2; };"evaluated := testEval(input)fn, ok := evaluated.(*object.Function)if !ok {t.Fatalf("object is not Function. got=%T (%+v)", evaluated, evaluated)}if len(fn.Parameters) != 1 {t.Fatalf("function has wrong parameters. Parameters=%+v",fn.Parameters)}if fn.Parameters[0].String() != "x" {t.Fatalf("parameter is not 'x'. got=%q", fn.Parameters[0])}expectedBody := "(x + 2)"if fn.Body.String() != expectedBody {t.Fatalf("body is not %q. got=%q", expectedBody, fn.Body.String())}
}func TestFunctionApplication(t *testing.T) {tests := []struct {input    stringexpected int64}{{"let identity = fn(x) { x; }; identity(5);", 5},{"let identity = fn(x) { return x; }; identity(5);", 5},{"let double = fn(x) { x * 2; }; double(5);", 10},{"let add = fn(x, y) { x + y; }; add(5, 5);", 10},{"let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", 20},{"fn(x) { x; }(5)", 5},}for _, tt := range tests {testIntegerObject(t, testEval(tt.input), tt.expected)}
}func TestEnclosingEnvironments(t *testing.T) {input := `
let first = 10;
let second = 10;
let third = 10;let ourFunction = fn(first) {let second = 20;first + second + third;
};ourFunction(20) + first + second;`testIntegerObject(t, testEval(input), 70)
}func testEval(input string) object.Object {l := lexer.New(input)p := parser.New(l)program := p.ParseProgram()env := object.NewEnvironment()return Eval(program, env)
}func testIntegerObject(t *testing.T, obj object.Object, expected int64) bool {result, ok := obj.(*object.Integer)if !ok {t.Errorf("object is not Integer. got=%T (%+v)", obj, obj)return false}if result.Value != expected {t.Errorf("object has wrong value. got=%d, want=%d",result.Value, expected)return false}return true
}func testBooleanObject(t *testing.T, obj object.Object, expected bool) bool {result, ok := obj.(*object.Boolean)if !ok {t.Errorf("object is not Boolean. got=%T (%+v)", obj, obj)return false}if result.Value != expected {t.Errorf("object has wrong value. got=%t, want=%t",result.Value, expected)return false}return true
}func testNullObject(t *testing.T, obj object.Object) bool {if obj != NULL {t.Errorf("object is not NULL. got=%T (%+v)", obj, obj)return false}return true
}