published on March 26, 2021 in 编译

使程序语言支持变量

下面我们来让计算器程序支持变量的使用，使得程序可以设置和获取变量的值。从现在开始我将不掩藏我们要实现的是一个程序语言，因为出自计算器所以命名为 bkcalclang

这次的代码以上一篇《使计算器支持语句块》的代码为基础编写，如果发现不熟悉当下的内容可以回顾一下之前的篇章。

代码清单【go语言为例】

package main

import (
    "fmt"
    "strconv"
    "io/ioutil"
    "./bklexer"
)

var ValueDict map[string]float64

type Node interface {
    Eval() float64
}

type Block struct {
    statements []Node
}

func NewBlock() *Block {
    return &Block{}
}

func (block *Block) AddStatement(statement Node) {
    block.statements = append(block.statements, statement)
}

func (block *Block) Eval() {
    for _, statement := range block.statements {
        statement.Eval()
    }
}

type Number struct {
    value float64
}

func NewNumber(token *BKLexer.Token) *Number {
    value, _ := strconv.ParseFloat(token.Source, 64)
    return &Number{value: value}
}

func (number *Number) Eval() float64 {
    return number.value
}

type Name struct {
    name string
}

func NewName(token *BKLexer.Token) *Name {
    return &Name{name: token.Source}
}

func (name *Name) Eval() float64 {
    if value, found := ValueDict[name.name]; found {
        return value;
    }
    return 0.
}

type BinaryOpt struct {
    opt string
    lhs Node
    rhs Node
}

func NewBinaryOpt(token *BKLexer.Token, lhs Node, rhs Node) *BinaryOpt {
    return &BinaryOpt{opt: token.Source, lhs: lhs, rhs: rhs}
}

func (binaryOpt *BinaryOpt) Eval() float64 {
    lhs, rhs := binaryOpt.lhs, binaryOpt.rhs
    switch binaryOpt.opt {
        case "+": return lhs.Eval() + rhs.Eval()
        case "-": return lhs.Eval() - rhs.Eval()
        case "*": return lhs.Eval() * rhs.Eval()
        case "/": return lhs.Eval() / rhs.Eval()
    }
    return 0
}

type Assign struct {
    name string
    value Node
}

func NewAssign(token *BKLexer.Token, value Node) *Assign {
    return &Assign{name: token.Source, value: value}
}

func (assign *Assign) Eval() float64 {
    value := assign.value.Eval()
    ValueDict[assign.name] = value
    return value
}

type Echo struct {
    value Node
}

func NewEcho(value Node) *Echo {
    return &Echo{value: value}
}

func (echo *Echo) Eval() float64 {
    value := echo.value.Eval()
    fmt.Println(":=", value)
    return value
}

func parse(lexer *BKLexer.Lexer) *Block {
    block := NewBlock()
    token := lexer.NextToken()
    for token.TType == BKLexer.TOKEN_TYPE_NEWLINE {
        token = lexer.NextToken()
    }
    for token.TType != BKLexer.TOKEN_TYPE_EOF {
        statement := parse_statement(lexer)
        if statement == nil {
            return nil;
        }
        token = lexer.GetToken()
        if token.TType != BKLexer.TOKEN_TYPE_NEWLINE &&
           token.TType != BKLexer.TOKEN_TYPE_EOF {
            return nil;
        }
        block.AddStatement(statement)
        for token.TType == BKLexer.TOKEN_TYPE_NEWLINE {
            token = lexer.NextToken()
        }
    }
    return block
}

func parse_statement(lexer *BKLexer.Lexer) Node {
    token := lexer.GetToken()
    if token.Name == "SET" {
        name := lexer.NextToken()
        if name.Name != "NAME" {
            return nil
        }
        token = lexer.NextToken()
        if token.Name != "ASSIGN" {
            return nil
        }
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if value == nil {
            return nil
        }
        return NewAssign(name, value)
    } else if token.Name == "ECHO" {
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if (value == nil) {
            return nil
        }
        return NewEcho(value)
    }
    return parse_binary_add(lexer)
}

func parse_binary_add(lexer *BKLexer.Lexer) Node {
    lhs := parse_binary_mul(lexer)
    if lhs == nil {
        return nil
    }
    token := lexer.GetToken()
    for token.Source == "+" || token.Source == "-" {
        lexer.NextToken()
        rhs := parse_binary_mul(lexer)
        if rhs == nil {
            return nil
        }
        lhs = NewBinaryOpt(token, lhs, rhs)
        token = lexer.GetToken()
    }
    return lhs
}

func parse_binary_mul(lexer *BKLexer.Lexer) Node {
    lhs := factor(lexer)
    if lhs == nil {
        return nil
    }
    token := lexer.GetToken()
    for token.Source == "*" || token.Source == "/" {
        lexer.NextToken()
        rhs := factor(lexer)
        if rhs == nil {
            return nil
        }
        lhs = NewBinaryOpt(token, lhs, rhs)
        token = lexer.GetToken()
    }
    return lhs
}

func factor(lexer *BKLexer.Lexer) Node {
    token := lexer.GetToken()
    if token.Name == "LPAR" {
        lexer.NextToken()
        expr := parse_binary_add(lexer)
        if expr == nil {
            return nil
        }
        token := lexer.GetToken()
        if token.Name != "RPAR" {
            return nil
        }
        lexer.NextToken()
        return expr
    }
    if token.Name == "NUMBER" {
        number := NewNumber(token)
        lexer.NextToken()
        return number
    }
    if token.Name == "NAME" {
        name := NewName(token)
        lexer.NextToken()
        return name
    }
    return nil
}

func main() {
    lexer := BKLexer.NewLexer()
    lexer.AddRule("\\d+\\.?\\d*", "NUMBER")
    lexer.AddRule("[\\p{L}\\d_]+", "NAME")
    lexer.AddRule("\\+", "PLUS")
    lexer.AddRule("-", "MINUS")
    lexer.AddRule("\\*", "MUL")
    lexer.AddRule("/", "DIV")
    lexer.AddRule("\\(", "LPAR")
    lexer.AddRule("\\)", "RPAR")
    lexer.AddRule("=", "ASSIGN")
    lexer.AddIgnores("[ \\f\\t]+")
    lexer.AddIgnores("#[^\\r\\n]*")
    lexer.AddReserve("set")
    lexer.AddReserve("echo")

    bytes, err := ioutil.ReadFile("../test.txt")
    if err != nil {
        fmt.Println("read faild")
        return
    }
    code := string(bytes)
    lexer.Build(code)
    result := parse(lexer)
    if result == nil {
        fmt.Println("null result")
        return
    }
    ValueDict = make(map[string]float64)
    result.Eval()
}

引入需要使用的包

import (
    "fmt"
    "strconv"
    "io/ioutil"
    "./bklexer"
)

fmt 打印输出
strconv 字符串转换
io/ioutil 读取文件
./bklexer 用于词法解析

声明用于存储变量值的字典

var ValueDict map[string]float64

我们会使用一个map类型的对象来存取值，并以此实现变量赋值和取值的操作。

定义命名节点结构体

type Name struct {
    name string
}

func NewName(token *BKLexer.Token) *Name {
    return &Name{name: token.Source}
}

Name结构体用于变量取值相关操作，函数NewName接收参数*BKLexer.Token并实例化Name。

定义命名节点的运行方法

func (name *Name) Eval() float64 {
    if value, found := ValueDict[name.name]; found {
        return value;
    }
    return 0.
}

原本Node的GetValue方法改名为Eval，这一点同样作用于其它相关结构体，需要注意。Name的Eval方法会查找ValueDict中的对应值并返回，如果不存在则返回0。

定义赋值节点结构体

type Assign struct {
    name string
    value Node
}

func NewAssign(token *BKLexer.Token, value Node) *Assign {
    return &Assign{name: token.Source, value: value}
}

定义Assign结构用于存放赋值语句信息，name为变量名，value为对应值的节点结构。使用NewAssign函数可以实例化Assign结构。

定义赋值节点的运行方法

func (assign *Assign) Eval() float64 {
    value := assign.value.Eval()
    ValueDict[assign.name] = value
    return value
}

该方法在执行时会将成员value的执行结果存入到ValueDict中然后返回该值。

定义输出节点的结构

type Echo struct {
    value Node
}

func NewEcho(value Node) *Echo {
    return &Echo{value: value}
}

Echo结构存储一个类型为Node的成员value，我们使用NewEcho实例化它。

定义输出节点的运行方法

func (echo *Echo) Eval() float64 {
    value := echo.value.Eval()
    fmt.Println(":=", value)
    return value
}

在该方法中，我们先取得echo成员value的值然后将其打印输出，最后返回该值。

增加一个函数用于专门处理语句

由于我们使用parse_statement函数作为处理语句的函数，所以我们在某些地方需要做出相应的修改，如语法解析的入口parse函数:

    for token.TType != BKLexer.TOKEN_TYPE_EOF {
        statement := parse_statement(lexer)
        if statement == nil {
            return nil;
        }

我们定义如下函数处理语句

func parse_statement(lexer *BKLexer.Lexer) Node {
    token := lexer.GetToken()
    if token.Name == "SET" {
        name := lexer.NextToken()
        if name.Name != "NAME" {
            return nil
        }
        token = lexer.NextToken()
        if token.Name != "ASSIGN" {
            return nil
        }
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if value == nil {
            return nil
        }
        return NewAssign(name, value)
    } else if token.Name == "ECHO" {
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if (value == nil) {
            return nil
        }
        return NewEcho(value)
    }
    return parse_binary_add(lexer)
}

如果发现起头的token名称为SET则判断为赋值操作，取下一个token作为变量名，再取下一个判断是否为赋值符号，如果都成功则解析后面的内容并以此构建赋值节点。

    if token.Name == "SET" {
        name := lexer.NextToken()
        if name.Name != "NAME" {
            return nil
        }
        token = lexer.NextToken()
        if token.Name != "ASSIGN" {
            return nil
        }
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if value == nil {
            return nil
        }
        return NewAssign(name, value)

如果当前token名称为ECHO则判断为打印输出，需要跳过当前token并进行表达式解析。如果成功解析则用解析结果构建打印输出节点并返回，否则函数返回nil。

    } else if token.Name == "ECHO" {
        lexer.NextToken()
        value := parse_binary_add(lexer)
        if (value == nil) {
            return nil
        }
        return NewEcho(value)
    }

增加变量取值的解析

将之前的parse_number函数改名为factor【这并不是必要操作】:

func factor(lexer *BKLexer.Lexer) Node {

我们在factor函数中添加变量名解析代码:

    if token.Name == "NAME" {
        name := NewName(token)
        lexer.NextToken()
        return name
    }

定义词法解析器规则

lexer.AddRule("\\d+\\.?\\d*", "NUMBER")
lexer.AddRule("[\\p{L}\\d_]+", "NAME")
lexer.AddRule("\\+", "PLUS")
lexer.AddRule("-", "MINUS")
lexer.AddRule("\\*", "MUL")
lexer.AddRule("/", "DIV")
lexer.AddRule("\\(", "LPAR")
lexer.AddRule("\\)", "RPAR")
lexer.AddRule("=", "ASSIGN")
lexer.AddIgnores("[ \\f\\t]+")
lexer.AddIgnores("#[^\\r\\n]*")
lexer.AddReserve("set")
lexer.AddReserve("echo")

这里我们需要添加变量名规则、赋值符号规则以及增加set、echo这两个保留字。

读取文件进行解析计算

bytes, err := ioutil.ReadFile("../test.txt")
if err != nil {
    fmt.Println("read faild")
    return
}
code := string(bytes)
lexer.Build(code)
result := parse(lexer)
if result == nil {
    fmt.Println("null result")
    return
}
ValueDict = make(map[string]float64)
result.Eval()

需要注意，我们在执行result.Eval()之前必须先实例化ValueDict。

使用一段测试脚本进行测试

测试内容:

echo 1 + 2 # plus
echo 3 - 4

# here is a comment

echo 5 * 6 # mul
echo 7 / 8

echo 1 + (2 - 3) * 4 / 5 # composite

set pi = 3.14
set r = 5
echo 2 * pi * r * r

运行结果:

➜ go run calc.go 
:= 3
:= -1
:= 30
:= 0.875
:= 0.19999999999999996
:= 157

下篇支持If语句