images/blog-posts

使程序语言支持变量

by kk 0 Comments 词法分析 语法分析 变量 LL分析器 编程 编译原理 golang

返回教程主页

上篇 使计算器支持语句块

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

SUBSCRIBE

🔒 No spam. Unsubscribe any time.

About kk

kk

Vincenzo Antedoro is an engineer who helps those who want to invest in renewables. For the rest he enjoys teaching with the method of learning by doing..

» More about kk