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

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

TINY 语言

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

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

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

示例程序：

{ 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吗？

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

// 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

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

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

GetToken

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

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

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