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

虽然课程从头到尾没提到过 TINY 语言，但实验三全都围绕着 TINY 构造。

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

TINY 语言

TINY 语言是《编译原理及实践》（Compiler Construction: Principles and Practice，之后简称 CCPP）中用于演示的语言，杨某人课程中心实验包中也有其中译本 PDF 文档（虽然翻得不咋样）。

在该书的 1.7.1 节中，提到了 TINY 语言的特性：

没有过程，没有函数声明
所有变量都是整型，通过一个赋值定义
只有 if 语句和 repeat 控制语句
if 语句可选 else 分支，必须用 end 表示结束
有输入输出语句
表达式只有算术（加、减、乘、整除）和布尔表达式（仅有 < 和 =）
注释由花括号包裹

示例程序：

pascal

{ Sample program
  in TINY language -
  computes factorial
} 
read x; {input an integer} 
if 0 <x then { don't compute if x <= 0} 
  fact := 1; 
  repeat 
    fact := fact * x; 
    x := x - 1 
  until x = 0; 
  write fact {output factorial of x} 
end

该书同时提供了 TINY 语言编译器的源代码，见此网站。

词法分析器

TINY 语言的词法，书中已有明确的 DFA 描述。

TINY 词法分析器包含于 scan.c 和 scan.h 中，可以直接参考实现。这个词法分析器由语法分析器调用，并不会一次把源文件扫完，而是调用一次获取一个 token。这和下图中的配合方式有点像。

词法分析器中有三个函数：

getNextChar：读取下一个字符。它维护了一个 lineBuf，即当前正在读取的代码行，在当前行读完的时候，会自动读下一行。
ungetNextChar：撤销上个 “读取下一个字符” 操作。注意到上图的 DFA 中有几条 [other] 边，这类似于状态转换图中的星号，代表这条边只会 “peek” 而不会真正读进来。
GetToken：读取下一个 token，然后返回类型。

在原来的代码中有一个线性查找保留词表的函数，但似乎可以直接用 map 替代掉。话说 C++ STL 不是有 map 吗？

        go
        
    var reservedWords = map[string]tokenType{
    "if":     ifToken,
    "then":   thenToken,
    "else":   elseToken,
    "end":    endToken,
    "repeat": repeatToken,
    "until":  untilToken,
    "read":   readToken,
    "write":  writeToken,
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


var reservedWords = map[string]tokenType{
    "if":     ifToken,
    "then":   thenToken,
    "else":   elseToken,
    "end":    endToken,
    "repeat": repeatToken,
    "until":  untilToken,
    "read":   readToken,
    "write":  writeToken,
}

对于源文件的读入方式，我选择了使用 bufio.Scanner。这玩意可比 io.Reader 好用多了。

`getNextChar`

        go
        
    // getNextChar 从 lineBuf 中读取一个字符，
// 如果 lineBuf 为空则从输入流中读取一行
func getNextChar() (byte, error) {
    // 本行已经读取完毕
    if linePos >= len(lineBuf) {
        lineNo++
        ok := sourceScanner.Scan()
        if !ok { // 文件末尾
            err := sourceScanner.Err()
            if err == nil {
                // EOF 的话不会返回 err
                eof = true
                return 0, io.EOF
            } else {
                // 真的出现错误了
                lineBuf = ""
                linePos = 0
                return 0, err
            }
        }
        lineBuf = sourceScanner.Text()
        linePos = 1
        return lineBuf[0], nil
    } else {
        linePos++
        return lineBuf[linePos-1], nil
    }
}

 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


// getNextChar 从 lineBuf 中读取一个字符，
// 如果 lineBuf 为空则从输入流中读取一行
func getNextChar() (byte, error) {
    // 本行已经读取完毕
    if linePos >= len(lineBuf) {
        lineNo++
        ok := sourceScanner.Scan()
        if !ok { // 文件末尾
            err := sourceScanner.Err()
            if err == nil {
                // EOF 的话不会返回 err
                eof = true
                return 0, io.EOF
            } else {
                // 真的出现错误了
                lineBuf = ""
                linePos = 0
                return 0, err
            }
        }
        lineBuf = sourceScanner.Text()
        linePos = 1
        return lineBuf[0], nil
    } else {
        linePos++
        return lineBuf[linePos-1], nil
    }
}

这个 Scanner 的默认分隔符就是换行，如果读取到末尾，会返回一个 false，然后没有 err（想不通为什么不是 io.EOF）。

eof 的作用后面说。

`ungetNextToken`

        go
        
    // ungetNextChar 将 lineBuf 中的一个字符退回
func ungetNextChar() {
    if !eof {
        linePos--
    }
}

1
2
3
4
5
6


// ungetNextChar 将 lineBuf 中的一个字符退回
func ungetNextChar() {
    if !eof {
        linePos--
    }
}

不加 eof 判断的话 GetToken 会一直读最后一个字母，停不下来。

`GetToken`

这个函数是一个完整的状态机实现，包含的状态如上面 DFA 所示，每次走到 DONE 就代表识别完成了一个 token。代码太长了就不放在文章里了。

值得注意的是状态里面没有保留字，因为这个词法分析器会先将非数字开头的字符串作为变量名，然后检查是否匹配保留字，并据此返回词类型。

有一个 tokenString 变量，顾名思义。只有变量名和数字等才需要记录，而对于注释之类的对语义完全没有作用的东西可以直接忽略掉。

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.