HNU 软件编译原理实验 4（Go 实现）

编译器、解释器、虚拟机，或许只在杨氏编译原理里面是同义词。

代码已上传至 GitHub，为防止篇幅过长，没有内置所有代码，仅对个人认为值得讲述的地方进行说明，可以对比阅读。

TINY 语言编译器的部分到了中间代码生成部分就结束了，生成的是下面这样的 TM 虚拟机机器码，剩下的部分一直到运行，都由虚拟机来完成。

        text
        
      0:     LD  6,0(0) 
  1:     ST  0,0(0) 
  2:     IN  0,0,0 
  3:     ST  0,0(5) 
  4:    LDC  0,0(0) 
  5:     ST  0,0(6) 

1
2
3
4
5
6


  0:     LD  6,0(0) 
  1:     ST  0,0(0) 
  2:     IN  0,0,0 
  3:     ST  0,0(5) 
  4:    LDC  0,0(0) 
  5:     ST  0,0(6) 

在实验三中完成了词法分析器，实验四包括了语义分析和中间代码生成，至于指导书没提的语法分析，当然只能自己加上了。

TINY 编译器的 C 代码中，大致流程为：词法分析（scan.c）-> 语法分析（parse.c）-> 语义分析（analyze.c）-> 中间代码生成（code.c、cgen.c）。另外还有符号表管理（symtab.c）。本文的之后部分中，将其改写 + 优化为 Go 代码进行解释。

该编译器不含有独立的错误处理模块，错误处理在各模块中解决。

语法分析

该编译器的语法分析输出是一个语法树，树节点用以下的结构描述。

        go
        
    type treeNode struct {
    child   [3]*treeNode // 子节点
    sibling *treeNode    // 兄弟节点
    lineNo  int          // 行号
    op      tokenType    // 操作符
    val     int          // 值
    attr    string       // 属性
    stmt    stmtKind     // 语句类型
    expr    exprKind     // 表达式类型
    typ     exprType     // 表达式数值类型
    node    nodeKind     // 节点类型
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


type treeNode struct {
    child   [3]*treeNode // 子节点
    sibling *treeNode    // 兄弟节点
    lineNo  int          // 行号
    op      tokenType    // 操作符
    val     int          // 值
    attr    string       // 属性
    stmt    stmtKind     // 语句类型
    expr    exprKind     // 表达式类型
    typ     exprType     // 表达式数值类型
    node    nodeKind     // 节点类型
}

命名很乱是吧，我也是这么想的。

节点类型 nodeKind 分为表达式节点和语句节点，前者对应一个表达式（如 1+1），后者对应一整个或一行语句（如 write i）
语句类型 stmtKind 分为赋值、循环、条件分支、读、写几种
表达式类型 exprKind 是当前表达式节点的类型，分为运算符、常量、标识符变量
表达式值类型 exprType 分为整型表达式、布尔表达式和没有值的表达式（真的存在吗）

由于 Go 孱弱的类型系统，既没有泛型多态有没有类似 Rust 的 Trait（巧了，C 也没有），所以每个节点存储完整的信息，不会因表达式或是语句节点而使用不同的结构体。

对于一个 treeNode，同一个节点的某个 child 的 sibling 和其他 child 并不是并列的关系。对于某个语句节点，sibling 指向的是下一个语句，例如：

        text
        
    fact := fact * x; 
x := x - 1;

1
2


fact := fact * x; 
x := x - 1;

第二句作为一个赋值语句节点，就是第一句的 sibling。而 child 可以视为语句中的 “槽位”，如：

        text
        
    if 0 < x then
    fact := 1;
end

1
2
3


if 0 < x then
    fact := 1;
end

上面的 if-then-end 语句有两个槽，分别存放 0 < x 表达式节点和 fact := 1 语句节点，也就是这个条件分支语句节点的两个 child。因为槽最多的就是 if-then-else-end，有三个，所以 child 最大也仅需要三个。

Parse 函数用来启动语法分析，返回语法树根节点。它调用 stmtSequence() 函数，期望其返回时分析完整个源代码，如果最后识别到的 token 不为 eof，则文件中含有错误。

        go
        
    func Parse() (t *treeNode) {
    currToken= GetToken()
    t = stmtSequence()
    if currToken != eofToken {
        syntaxError("Code ends before file\n")
    }
    return
}

1
2
3
4
5
6
7
8


func Parse() (t *treeNode) {
    currToken= GetToken()
    t = stmtSequence()
    if currToken != eofToken {
        syntaxError("Code ends before file\n")
    }
    return
}

stmtSequence 函数用来识别位于同一作用域（如同一 if-clause，也就是 Python 中同一缩进等级）的一串语句，当找到 eof、end、else 和 until 这几个代表结束的词语时结束。

t 为 nil 这一个分支我也没看懂为什么在这里。

        go
        
    func stmtSequence() *treeNode {
    t := statement()
    p := t
    for currToken != eofToken && currToken != endToken && currToken != elseToken && currToken != untilToken {
        match(semicolonToken)
        q := statement()
        if q != nil {
            if t == nil {
                p = q
                t = p
            } else {
                p.sibling = q
                p = q
            }
        }
    }
    return t
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func stmtSequence() *treeNode {
    t := statement()
    p := t
    for currToken != eofToken && currToken != endToken && currToken != elseToken && currToken != untilToken {
        match(semicolonToken)
        q := statement()
        if q != nil {
            if t == nil {
                p = q
                t = p
            } else {
                p.sibling = q
                p = q
            }
        }
    }
    return t
}

statement 函数好理解，一次识别单个语句，根据识别出的 token 类型进入不同的识别函数。代码略。

各种不同语句的识别函数分为 if、repeat、赋值语句、read 和 write，此处只以 ifStatement 为例，其他看看代码应该就明白了。if 节点的三个域分别存放 expression（条件检验表达式）、then-statement（符合执行的语句串）和 else-statement（不符合执行的语句串）。

        go
        
    // if 语句的匹配
//
// if <expression> then <stmtSequence> [else <stmtSequence>] end
func ifStatement() *treeNode {
    t := newStatementNode(ifStmt)
    match(ifToken)
    t.child[0] = expression()
    match(thenToken)
    t.child[1] = stmtSequence()
    if currToken == elseToken {
        match(elseToken)
        t.child[2] = stmtSequence()
    }
    match(endToken)
    return t
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// if 语句的匹配
//
// if <expression> then <stmtSequence> [else <stmtSequence>] end
func ifStatement() *treeNode {
    t := newStatementNode(ifStmt)
    match(ifToken)
    t.child[0] = expression()
    match(thenToken)
    t.child[1] = stmtSequence()
    if currToken == elseToken {
        match(elseToken)
        t.child[2] = stmtSequence()
    }
    match(endToken)
    return t
}

语句的匹配在上面就结束了，而表达式的匹配需要考虑优先级问题。在这个编译器程序中，分为三个优先级：< 和 = 优先级最低，+ 和 - 优先级次之，* 和 / 更高，数字、标识符和括号则设为同一最高优先级。在形式化语言表示中，使用不同的符号（Expression、Term、Factor）区分不同的计算优先级。产生式有：

$Expression \to simpleExpression\ |\ simpleExpression \lt simpleExpression\ |\ simpleExpression \lt \simpleExpression$

$simpleExpression \to Term\ |\ Term+Term\ |\ Term-Term$

$Term \to Factor\ |\ Factor \times Factor\ |\ Factor / Factor$

仅贴出 Expression 的代码，其他类似。

        go
        
    // 表达式的匹配：处理 < 和 = 运算符
// 优先级最低
func expression() *treeNode {
    t := simpleExpression()
    if currToken == ltToken || currToken == eqToken {
        p := newExpressionNode(opExpr)
        p.child[0] = t
        p.op = currToken
        t = p
        match(currToken)
        t.child[1] = simpleExpression()
    }
    return t
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// 表达式的匹配：处理 < 和 = 运算符
// 优先级最低
func expression() *treeNode {
    t := simpleExpression()
    if currToken == ltToken || currToken == eqToken {
        p := newExpressionNode(opExpr)
        p.child[0] = t
        p.op = currToken
        t = p
        match(currToken)
        t.child[1] = simpleExpression()
    }
    return t
}

数字和标识符的处理（factor）如下：

        go
        
    // 表达式的匹配：处理数字、标识符和括号
func factor() (t *treeNode) {
    switch currToken {
    case numToken:
        t = newExpressionNode(constExpr)
        if currToken == numToken {
            var err error
            t.val, err = strconv.Atoi(tokenString)
            if err != nil {
                syntaxError("unexpected token -> %s"+ currToken.String())
            }
            match(numToken)
        }
    case idToken:
        t = newExpressionNode(idExpr)
        if currToken == idToken {
            t.attr = tokenString
        }
        match(idToken)
    case lparenToken:
        match(lparenToken)
        t = expression()
        match(rparenToken)
    default:
        syntaxError("unexpected token -> %s"+ currToken.String())
        currToken = GetToken()
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


// 表达式的匹配：处理数字、标识符和括号
func factor() (t *treeNode) {
    switch currToken {
    case numToken:
        t = newExpressionNode(constExpr)
        if currToken == numToken {
            var err error
            t.val, err = strconv.Atoi(tokenString)
            if err != nil {
                syntaxError("unexpected token -> %s"+ currToken.String())
            }
            match(numToken)
        }
    case idToken:
        t = newExpressionNode(idExpr)
        if currToken == idToken {
            t.attr = tokenString
        }
        match(idToken)
    case lparenToken:
        match(lparenToken)
        t = expression()
        match(rparenToken)
    default:
        syntaxError("unexpected token -> %s"+ currToken.String())
        currToken = GetToken()
    }
    return
}

符号表

原来的 C 版本编译器说白了也就是个自定义哈希函数的哈希表，是一个数组实现，封装了查找和插入，所以既然 Go 本身就有无序的字典 map，当然就用上了。

符号表项的键为符号名，值为内存地址（从 0 起）和出现的行数列表 的引用。

        go
        
    var symtab map[string]*struct {
    refLines []int // 引用行号列表
    memLoc   int   // 内存位置
} = make(map[string]*struct {
    refLines []int
    memLoc   int
})

1
2
3
4
5
6
7


var symtab map[string]*struct {
    refLines []int // 引用行号列表
    memLoc   int   // 内存位置
} = make(map[string]*struct {
    refLines []int
    memLoc   int
})

在原来的符号表实现中，新符号的地址是由词法分析器决定的（而且是简单的递增），此处由符号表模块自行管理。

查找很简单，判断是否存在罢了。

        go
        
    // 查找符号表
// 返回内存位置和是否找到
func lookupSymtab(name string) (location int, ok bool) {
    if item, ok := symtab[name]; ok {
        return item.memLoc, true
    }
    return 0, false
}

1
2
3
4
5
6
7
8


// 查找符号表
// 返回内存位置和是否找到
func lookupSymtab(name string) (location int, ok bool) {
    if item, ok := symtab[name]; ok {
        return item.memLoc, true
    }
    return 0, false
}

插入分两种情况，如果已经存在，则仅更新行数列表；否则，还要分配一个空间。要改变 map 中某个元素的值，需要将其取出、修改值，然后重新设立对应关系，所以在上面的定义中使用了引用，得以在不修改引用地址的情况下增加引用行列表。

        go
        
    func insertSymtab(name string, lineNo int) {
    if item, ok := symtab[name]; ok {
        item.refLines = append(item.refLines, lineNo)
    } else {
        symtab[name] = &struct {
            refLines []int
            memLoc   int
        }{[]int{lineNo}, memLoc}
        memLoc++
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func insertSymtab(name string, lineNo int) {
    if item, ok := symtab[name]; ok {
        item.refLines = append(item.refLines, lineNo)
    } else {
        symtab[name] = &struct {
            refLines []int
            memLoc   int
        }{[]int{lineNo}, memLoc}
        memLoc++
    }
}

语义分析

语义分析主要干两件事，类型检查和插入符号表。

定义了一个统一的 DFS 函数，通过传入不同的函数，执行前序和后序遍历的操作。类型检查需要后序遍历，插入符号表则需要前序遍历（看起来 TINY 是 lexical scoping）。

        go
        
    func traverse(t *treeNode, preProc func(*treeNode), postProc func(*treeNode)) {
    if t == nil {
        return
    }
    if preProc != nil {
        preProc(t)
    }
    for i := 0; i < 3; i++ {
        traverse(t.child[i], preProc, postProc)
    }
    if postProc != nil {
        postProc(t)
    }
    traverse(t.sibling, preProc, postProc)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func traverse(t *treeNode, preProc func(*treeNode), postProc func(*treeNode)) {
    if t == nil {
        return
    }
    if preProc != nil {
        preProc(t)
    }
    for i := 0; i < 3; i++ {
        traverse(t.child[i], preProc, postProc)
    }
    if postProc != nil {
        postProc(t)
    }
    traverse(t.sibling, preProc, postProc)
}

构建符号表需要对每个出现变量的地方都进行一次插入操作。因为在之前的符号表操作中已经做到了根据已经插入与否区分不同的行为，所以此处可以省去判断是否已经存在。

        go
        
    // 将某个语法树节点的信息插入符号表
func insertNode(t *treeNode) {
    switch t.node {
    case stmtNode: // 对于语句，只有赋值和读语句需要插入符号表
        if t.stmt == assignStmt || t.stmt == readStmt {
            insertSymtab(t.attr, t.lineNo)
        }
    case exprNode: // 对于表达式，其中的标识符都要记在符号表中
        if t.expr == idExpr {
            insertSymtab(t.attr, t.lineNo)
        }
    }
}

// 遍历，构建符号表
func BuildSymtab(t *treeNode) {
    traverse(t, insertNode, nil)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// 将某个语法树节点的信息插入符号表
func insertNode(t *treeNode) {
    switch t.node {
    case stmtNode: // 对于语句，只有赋值和读语句需要插入符号表
        if t.stmt == assignStmt || t.stmt == readStmt {
            insertSymtab(t.attr, t.lineNo)
        }
    case exprNode: // 对于表达式，其中的标识符都要记在符号表中
        if t.expr == idExpr {
            insertSymtab(t.attr, t.lineNo)
        }
    }
}

// 遍历，构建符号表
func BuildSymtab(t *treeNode) {
    traverse(t, insertNode, nil)
}

类型检查的思想就是，赋值语句和写语句后面要匹配 integer 类型，if 和 repeat 则要匹配 bool 类型。

        go
        
    // 对 t 做类型检查，反正就 bool 和 integer 两种类型
func checkNode(t *treeNode) {
    switch t.node {
    case exprNode:
        switch t.expr {
        case opExpr: // 运算符表达式，两个 child 类型均为 integer
            if t.child[0].typ != intExpr || t.child[1].typ != intExpr {
                typeError(t,"Op applied to non-integer")
            }
            if t.op == eqToken || t.op == ltToken { // 返回的是比较结果
                t.typ = boolExpr
            } else { // 返回的是计算结果
                t.typ = intExpr
            }
        default: // const 或 id，直接返回类型
            t.typ = intExpr
        }
    case stmtNode:
        switch t.stmt {
        case ifStmt: // if 语句，条件表达式类型为 bool
            if t.child[0].typ != boolExpr {
                typeError(t.child[0], "If test is not Boolean")
            }
        case assignStmt: // 赋值语句，表达式类型为 integer
            if t.child[0].typ != intExpr {
                typeError(t.child[0], "Assignment of non-integer value")
            }
        case writeStmt: // 写语句，表达式类型为 integer
            if t.child[0].typ != intExpr {
                typeError(t.child[0], "Write of non-integer value")
            }
        case repeatStmt: // repeat 语句，条件表达式类型为 bool
            if t.child[1].typ != boolExpr {
                typeError(t.child[1], "Repeat test is not Boolean")
            }
        }
    }
}

// 对整个语法树做类型检查
// 在进行完毕类型推导后，再做节点类型检查
func TypeCheck(t *treeNode) {
    traverse(t, nil, checkNode)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


// 对 t 做类型检查，反正就 bool 和 integer 两种类型
func checkNode(t *treeNode) {
    switch t.node {
    case exprNode:
        switch t.expr {
        case opExpr: // 运算符表达式，两个 child 类型均为 integer
            if t.child[0].typ != intExpr || t.child[1].typ != intExpr {
                typeError(t,"Op applied to non-integer")
            }
            if t.op == eqToken || t.op == ltToken { // 返回的是比较结果
                t.typ = boolExpr
            } else { // 返回的是计算结果
                t.typ = intExpr
            }
        default: // const 或 id，直接返回类型
            t.typ = intExpr
        }
    case stmtNode:
        switch t.stmt {
        case ifStmt: // if 语句，条件表达式类型为 bool
            if t.child[0].typ != boolExpr {
                typeError(t.child[0], "If test is not Boolean")
            }
        case assignStmt: // 赋值语句，表达式类型为 integer
            if t.child[0].typ != intExpr {
                typeError(t.child[0], "Assignment of non-integer value")
            }
        case writeStmt: // 写语句，表达式类型为 integer
            if t.child[0].typ != intExpr {
                typeError(t.child[0], "Write of non-integer value")
            }
        case repeatStmt: // repeat 语句，条件表达式类型为 bool
            if t.child[1].typ != boolExpr {
                typeError(t.child[1], "Repeat test is not Boolean")
            }
        }
    }
}

// 对整个语法树做类型检查
// 在进行完毕类型推导后，再做节点类型检查
func TypeCheck(t *treeNode) {
    traverse(t, nil, checkNode)
}

代码生成

生成代码已经是这个编译器做的最后一步了，没有优化，没有中间代码。TM 虚拟机读取的还不完全是三地址码，更别提 LLVM IR 那样高阶的东西了，而是有点类似于真实计算机的寄存器 + 内存的组合。寄存器有累加 AC1 和 AC2、程序计数器 PC，以及 GP 和 MP 寄存器。

在 codegen.go 中，使用 CodeGen() 初始化程序运行环境，调用 cGen 对 AST 根节点生成代码，然后挂起虚拟机。在 cGen 中，根据当前节点的类型调用 genStmt 或 genExp 生成语句或表达式，然后再对其兄弟节点调用 cGen，生成下一条语句对应的代码。

语句

对于 repeat <statement> until <expression>，先执行 statement，再判断 expression，判断结果会存放在 AC1 寄存器中。当 AC1 为 0 时代表条件成立，执行条件跳转指令，到 statement 之前，再次执行。

        go
        
        case repeatStmt:
        emitComment("-> repeat")
        p1 := t.child[0]
        p2 := t.child[1]
        // 保存循环前的位置
        savedLoc1 := emitSkip(0)
        emitComment("repeat: jump after body comes back here")
        // 执行语句
        cGen(p1)
        // 判断条件
        cGen(p2)
        // 如果符合，跳转到 savedLoc1，即循环前
        emitAbsRM("JEQ", ACCUMULATOR1, savedLoc1)
        emitComment("<- repeat")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


    case repeatStmt:
        emitComment("-> repeat")
        p1 := t.child[0]
        p2 := t.child[1]
        // 保存循环前的位置
        savedLoc1 := emitSkip(0)
        emitComment("repeat: jump after body comes back here")
        // 执行语句
        cGen(p1)
        // 判断条件
        cGen(p2)
        // 如果符合，跳转到 savedLoc1，即循环前
        emitAbsRM("JEQ", ACCUMULATOR1, savedLoc1)
        emitComment("<- repeat")

对于 if 语句，依次填入的指令为：

判断 expr
若不符合，跳转到 stmt2
执行 stmt1
跳转到 stmt2 结束
执行 stmt2

        go
        
        case ifStmt:
        // if <expr> then <stmt1> else <stmt2> end
        // 或 if <expr> then <stmt1> end
        emitComment("-> if")
        p1 := t.child[0]
        p2 := t.child[1]
        p3 := t.child[2]
        // 生成条件表达式的代码
        cGen(p1)
        // 空一个跳转 stmt1 末尾的位置
        savedLoc1 := emitSkip(1)
        emitComment("if: jump to else belongs here")
        // 生成 stmt1 的代码
        cGen(p2)
        // 空一个指令，供跳转到 stmt2 结束
        savedLoc2 := emitSkip(1)
        emitComment("if: jump to end belongs here")
        // 获得 stmt2 的开始位置
        currLoc := emitSkip(0)
        // 回到 expr 判断结束处，写入条件跳转语句
        emitBackup(savedLoc1)
        emitAbsRM("JEQ", ACCUMULATOR1, currLoc)
        emitComment("if: jmp to else")
        // 回到 stmt2 开始处
        emitRestore()
        // 生成 stmt2 语句的代码
        cGen(p3)
        // 获得 stmt2 结束后的位置
        currLoc = emitSkip(0)
        // 回到 stmt1 结束处，无条件跳转到 stmt2 结束处
        emitBackup(savedLoc2)
        emitAbsRM("LDA", PROGRAM_COUNTER, currLoc)
        emitComment("if: jmp to end")
        // 回到 stmt2 结束处
        emitRestore()
        emitComment("<- if")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


    case ifStmt:
        // if <expr> then <stmt1> else <stmt2> end
        // 或 if <expr> then <stmt1> end
        emitComment("-> if")
        p1 := t.child[0]
        p2 := t.child[1]
        p3 := t.child[2]
        // 生成条件表达式的代码
        cGen(p1)
        // 空一个跳转 stmt1 末尾的位置
        savedLoc1 := emitSkip(1)
        emitComment("if: jump to else belongs here")
        // 生成 stmt1 的代码
        cGen(p2)
        // 空一个指令，供跳转到 stmt2 结束
        savedLoc2 := emitSkip(1)
        emitComment("if: jump to end belongs here")
        // 获得 stmt2 的开始位置
        currLoc := emitSkip(0)
        // 回到 expr 判断结束处，写入条件跳转语句
        emitBackup(savedLoc1)
        emitAbsRM("JEQ", ACCUMULATOR1, currLoc)
        emitComment("if: jmp to else")
        // 回到 stmt2 开始处
        emitRestore()
        // 生成 stmt2 语句的代码
        cGen(p3)
        // 获得 stmt2 结束后的位置
        currLoc = emitSkip(0)
        // 回到 stmt1 结束处，无条件跳转到 stmt2 结束处
        emitBackup(savedLoc2)
        emitAbsRM("LDA", PROGRAM_COUNTER, currLoc)
        emitComment("if: jmp to end")
        // 回到 stmt2 结束处
        emitRestore()
        emitComment("<- if")

对于 assign 语句，就是计算表达式的值，查符号表得到内存地址，然后将值存进去：

        go
        
        case assignStmt:
        // <id> := <expr>
        emitComment("-> assign")
        // 计算表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 找到 id 的内存偏移
        loc, _ := lookupSymtab(t.attr)
        // 将表达式的值存入 id 的内存偏移
        emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("<- assign")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    case assignStmt:
        // <id> := <expr>
        emitComment("-> assign")
        // 计算表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 找到 id 的内存偏移
        loc, _ := lookupSymtab(t.attr)
        // 将表达式的值存入 id 的内存偏移
        emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("<- assign")

read 和 write 语句也会使用 AC1 作为中转，不同的是 write 计算表达式的值时会隐式地存入 AC1，表现倒是相同的：

        go
        
        case readStmt:
        // read <id>
        emitComment("-> read")
        // 读取输入，存入 ACCUMULATOR1
        emitRO("IN", ACCUMULATOR1, 0, 0)
        loc, _ := lookupSymtab(t.attr)
        // 将输入的值存入 id 的内存偏移
        emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("<- read")
    case writeStmt:
        emitComment("-> write")
        // 计算表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 将 ACCUMULATOR1 的值输出
        emitRO("OUT", ACCUMULATOR1, 0, 0)
        emitComment("<- write")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


    case readStmt:
        // read <id>
        emitComment("-> read")
        // 读取输入，存入 ACCUMULATOR1
        emitRO("IN", ACCUMULATOR1, 0, 0)
        loc, _ := lookupSymtab(t.attr)
        // 将输入的值存入 id 的内存偏移
        emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("<- read")
    case writeStmt:
        emitComment("-> write")
        // 计算表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 将 ACCUMULATOR1 的值输出
        emitRO("OUT", ACCUMULATOR1, 0, 0)
        emitComment("<- write")

表达式

此处每个表达式的结果最后都会存放在 AC1 寄存器中，这是一个约定用法。

常量表达式最简单，直接使用加载常量的指令，把值存入 AC1：

        go
        
        case constExpr:
        emitComment("-> Const")
        // 将常量存入 ACCUMULATOR1
        emitRM("LDC", ACCUMULATOR1, t.val, 0)
        emitComment("load const")
        emitComment("<- Const")

1
2
3
4
5
6


    case constExpr:
        emitComment("-> Const")
        // 将常量存入 ACCUMULATOR1
        emitRM("LDC", ACCUMULATOR1, t.val, 0)
        emitComment("load const")
        emitComment("<- Const")

加载一个变量也只需根据指针将其从内存中读出：

        go
        
        case idExpr:
        emitComment("-> Id")
        // 找到 id 的内存偏移
        loc, _ := lookupSymtab(t.attr)
        // 将该地址对应的值存入 ACCUMULATOR1
        emitRM("LD", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("load id value")
        emitComment("<- Id")

1
2
3
4
5
6
7
8


    case idExpr:
        emitComment("-> Id")
        // 找到 id 的内存偏移
        loc, _ := lookupSymtab(t.attr)
        // 将该地址对应的值存入 ACCUMULATOR1
        emitRM("LD", ACCUMULATOR1, loc, GLOBAL_POINTER)
        emitComment("load id value")
        emitComment("<- Id")

在计算一个带运算符（算术运算和比较）的表达式的值时，需要先求出左右子表达式的值。tmpOffset 的设置是为了让嵌套执行此处代码时，每一个 genExpr 的 tmpOffset 值都是不同的，从而在多层 opExpr 下能够将左子表达式的临时值存放在不同的位置；否则每次执行都会向同一个位置（即 MP）读写内容，从而覆盖外层求出的结果。

        go
        
        case opExpr:
        emitComment("-> Op")
        // 求左子表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 将 ACCUMULATOR1 的值存入内存偏移 tmpOffset
        emitRM("ST", ACCUMULATOR1, tmpOffset, MEMORY_POINTER)
        // 将 tmpOffset 加 1，即指向下一个内存偏移（当然后面存的不能重合了）
        tmpOffset--
        emitComment("op: push left")
        // 求右子表达式的值，存入 ACCUMULATOR1
        cGen(t.child[1])
        tmpOffset++
        // 将左子表达式的值存入 ACCUMULATOR2
        emitRM("LD", ACCUMULATOR2, tmpOffset, MEMORY_POINTER)
        emitComment("op: load left")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


    case opExpr:
        emitComment("-> Op")
        // 求左子表达式的值，存入 ACCUMULATOR1
        cGen(t.child[0])
        // 将 ACCUMULATOR1 的值存入内存偏移 tmpOffset
        emitRM("ST", ACCUMULATOR1, tmpOffset, MEMORY_POINTER)
        // 将 tmpOffset 加 1，即指向下一个内存偏移（当然后面存的不能重合了）
        tmpOffset--
        emitComment("op: push left")
        // 求右子表达式的值，存入 ACCUMULATOR1
        cGen(t.child[1])
        tmpOffset++
        // 将左子表达式的值存入 ACCUMULATOR2
        emitRM("LD", ACCUMULATOR2, tmpOffset, MEMORY_POINTER)
        emitComment("op: load left")

算术表达式的求解很简单，惟需注意上面执行完毕后左边对应 AC2，右边对应 AC1：

        go
        
            switch t.op {
        case plusToken:
            // AC1 = AC2 + AC1
            emitRO("ADD", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op +")
        case minusToken:
            // AC1 = AC2 - AC1
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op -")
        case timesToken:
            // AC1 = AC2 * AC1
            emitRO("MUL", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op *")
        case overToken:
            // AC1 = AC2 / AC1
            emitRO("DIV", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op /")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


        switch t.op {
        case plusToken:
            // AC1 = AC2 + AC1
            emitRO("ADD", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op +")
        case minusToken:
            // AC1 = AC2 - AC1
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op -")
        case timesToken:
            // AC1 = AC2 * AC1
            emitRO("MUL", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op *")
        case overToken:
            // AC1 = AC2 / AC1
            emitRO("DIV", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op /")

小于运算符的情况，如果 AC1<AC2，则 AC1=0；否则 AC1=1。

        go
        
            case ltToken:
            // AC1 = AC2 - AC1
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op <")
            // 若 AC1<AC2（新 AC1<0），则往后跳两个指令
            emitRM("JLT", ACCUMULATOR1, 2, PROGRAM_COUNTER)
            emitComment("br if true")
            // 若 AC1>=AC2，则 AC1=0
            emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
            emitComment("false case")
            // 无条件跳一条指令
            emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
            emitComment("unconditional jmp")
            // 若 AC1<AC2，则 AC1=1
            emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
            emitComment("true case")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


        case ltToken:
            // AC1 = AC2 - AC1
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op <")
            // 若 AC1<AC2（新 AC1<0），则往后跳两个指令
            emitRM("JLT", ACCUMULATOR1, 2, PROGRAM_COUNTER)
            emitComment("br if true")
            // 若 AC1>=AC2，则 AC1=0
            emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
            emitComment("false case")
            // 无条件跳一条指令
            emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
            emitComment("unconditional jmp")
            // 若 AC1<AC2，则 AC1=1
            emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
            emitComment("true case")

等于的情况类似，仅当 AC1=AC2 时 AC1=0：

        go
        
            case eqToken:
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op ==")
            emitRM("JEQ", ACCUMULATOR1, 2, PROGRAM_COUNTER)
            emitComment("br if true")
            emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
            emitComment("false case")
            emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
            emitComment("unconditional jmp")
            emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
            emitComment("true case")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


        case eqToken:
            emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
            emitComment("op ==")
            emitRM("JEQ", ACCUMULATOR1, 2, PROGRAM_COUNTER)
            emitComment("br if true")
            emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
            emitComment("false case")
            emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
            emitComment("unconditional jmp")
            emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
            emitComment("true case")