Go编译器源代码：词法分析

Bioit   in Hefei

  本文快速阅读需要有一点编译原理知识，还需要对Go有一定了解，读懂一般的Go代码

  水平有限，遇到错误请联系更改

# 一、词法分析

  只是概括一下词法分析相关知识

  首先、编译就是把机器看不懂的对人类友好源代码翻译成机器可以理解的指令

  源码阅读过程中，遇到错误处理等代码可以选择性忽略，减少我们注意点数量

  1. 词法分析就是把我们的源码解析为一个个Token（为接下来的语法分析做准备），源代码本质上就是一个个字符组成的一个字符串，词法分析的目的就是把源代码的字符分割，该在一起的字符放到一起组成一个Token（可以理解为一个单词，源代码就是一个个单词组成的一篇文章）。以下面的一串代码为例：我们人类能够很好的区分if是一个token，a是一个token。但是机器不知道，所以我们需要写一个词法解析器来把源代码解析成Token列表，供下一步使用
if a > 10 {}
  1. Token一般分为几大类：标识符及字面值、操作符、分隔符、关键字。如上面的代码中“if”是关键字，a是标识符，“>”是操作符，“{”是分隔符。需要注意的是我们的关键字和标识符会很类似，词法分析器需要给予关键字更高的优先级。如else不能识别为标识符
  2. 词法分析甚至语法分析都是很固定的一套方法论，我们词法分析可以依靠lex，antlr等分析工具很好的完成。我们只需要编写词法分析的正则文法（文法和正则文法可以查阅维基百科）就行。即词法分析可以用正则匹配来很好的解决，此时词法规则就是一条条正则文法，下面展现的是使用antlr编写Go词法分析的几条正则文法：antlr读者们可以自行学习一下，antlr中处理优先级的方法是把关键字Token正则文法写在前面，完整的antlr表示的词法规则在文章末尾给出了链接
lexer grammar GoLexer; // lexer代表是词法分析，因为antlr还能用于语法分析
BREAK                  : 'break' -> mode(NLSEMI);
DEFAULT                : 'default';
FUNC                   : 'func';
  1. 词法分析使用到的算法：有限自动机（FSA）（注意区分有限状态机，最大区别在于有限状态机的输出可以多种多样，FSA没有输出或者说输出是T/F，即是否匹配），即我们的词法规则是由正则文法表示的。
  • FSA分为确定的有限自动机（DFA）和 非确定的有限自动机（NFA）。区别在于NFA对于一个输入，可能有多个转移函数。正则可以和FSA相互转换
  • 如果查看antlr自动生成的词法分析器代码，可以看到其中NFA和DFA的操作
  • DFA与NFA的主要优缺点对比：DFA速度快、不用回溯，NFA占用内存少
  • 正则 --> NFA --> DFA 都有对应的算法，如果读者想从0手写词法分析器，可以自行学习来实现。（其实正则也是一个DSL，写一个正则引擎可以锻炼我们的编译原理知识）
  1. 我还想强调的一点是对于有相同前缀的Token生成词法规则，需要去处理。如“++”，这个大多数语言都有的自增操作。我们就不能识别为2个+。所以我们在用各种工具时，要按照对应规则书写出能够处理公共前缀的正则文法，如用antlr要注意词法规则先后关系

# 二、Go编译器词法分析源码解析

本文源码基于Go1.18刚发布的时候，源码变动很快，没有大改动的话不用一直追逐最新源码

  Go语言词法分析相关代码在src\cmd\compile\internal\syntax包中，这其中也包含了语法分析相关代码，由于源码太多，博客不能全部贴上，需要读者配合源码阅读，文末也给了注释版本的源码链接

  词法分析其实是最简单的内容、所以读者其实可以直接去阅读源码大概了解一下

  • Go词法分析器没有使用正则转变而来的DFA/NFA来处理，而是用一个很长的switch-case语句来处理，即直接扫描法。比较容易理解，且代码量不多。并且诟病的标识符Token需要2次扫描来区分关键字和标识符的Go用了类似Map快速的判断。对于速度的影响大大降低，标识符和关键字Go中的处理如下代码所示：
// hash函数把关键字变成了一个uint值（关键字数组下标）。所有关键字uint值不一样(要避免冲突)
func hash(s []byte) uint {
	return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
}
// keywordMap相当于一个map
var keywordMap [1 << 6]token // size must be power of two
// 初始化函数将所有关键字Token放入了一个临时实现的set中
func init() {
	// populate keywordMap
	// 每个Token对应一个int值
	for tok := _Break; tok <= _Var; tok++ {
		h := hash([]byte(tok.String()))
		if keywordMap[h] != 0 {
			panic("imperfect hash")
		}
		keywordMap[h] = tok
	}
}

// 在标识符识别函数中，有这样的一段代码，来快速判断是否是关键字
// 可以看到长度大于2的小心思，即长度为1不可能是关键字
if len(lit) >= 2 {
	if tok := keywordMap[hash(lit)]; tok != 0 && tokStrFast(tok) == string(lit) {
			// 一些代码
	}
}

  • Go词法分析主要文件：

    • token.go：存放Token信息。我们可以从这个文件了解所有Token的Token Name、Token对应的uint值（一个uint值代表一个Token）等信息
    • token_string.go：用于给定Token对应的uint值快速获取Token对应的源数据，如从_Var快速获取其对应的源码即为“var”
    • source.go：使用一个buf 缓存（[]byte），和维护的几个下标和行列信息，用于不断读取源代码字符。核心函数为nextch()
    • scanner.go：核心函数next()，用于读取一个Token，用于不断获取Token，词法分析器scanner继承于source，依赖source提供的nextch()函数，其也被语法分析器继承
  1. Go 的 Token：Token可以查阅token.go查看，Go的Token也分为四大类标识符及字面值、操作符、分隔符、关键字、用uint 常量表示。go1.18一共有46种Token。uint值从1到46。token.go文件中也注释了每个Token对应的源字符串。部分Token如下：
// 用无符号整数表示Token
type token uint
const (
	_    token = iota
	_EOF       // EOF
	// names and literals
	_Name    // name
	_Literal // literal

	// operators and operations 操作符和赋值等操作
	// _Operator is excluding '*' (_Star)
	_Operator // op 多于一个字符的操作符都是要特殊处理的
	_AssignOp // op= 多于一个字符的操作符都是要特殊处理的
	_IncOp    // opop 多于一个字符的操作符都是要特殊处理的
	_Assign   // =
	_Define   // := 多于一个字符的操作符都是要特殊处理的。看代码时可以看到，当遇到:时，后面要紧跟着判断是不是=
	_Arrow    // <- 多于一个字符的操作符都是要特殊处理的
	_Star     // *

	// delimiters 分隔符
	_Lparen    // (
	_Lbrack    // [
	// 省略
	
	// keywords 可以看出Go1.18有25个关键字
	_Break       // break
	_Case        // case
	// 省略
)
  • 关于Token的知识，需要注意的几个点：
    • _Star 代表 “*”，它既可以用在指针声明、指针变量取值。也可以用做乘法，所以注意语法分析中对其的特殊处理有很多
    • _Literal（代表基本字面量），有5种类型，所以scanner.go文件中的scanner结构体（词法解析器）需要有一个filed用来表示LitKind
type LitKind uint8
const (
	IntLit LitKind = iota
	FloatLit
	ImagLit
	RuneLit
	StringLit
)
  • 表达式中的操作符中不包括--、++、=、:= 、op=，它们的处理逻辑不在语法分析的表达式处理中，可以在学习语法分析时验证
  • Token.go文件中还把各属于_Operator Token的表达式分了优先级，代码有点多，可以直接看token.go文件中type Operator uint及其之后部分，操作符优先级是语法分析表达式分析中很重要的一部分
  • Go语言的位取反操作符为“^”，而不是其他语言的“~”，Go中的波浪号用在泛型逻辑中，表示相似类型
  1. 词法分析器结构体scanner：
type scanner struct {
	source // source.go中定义的结构体，能够帮助基于缓存读取源码，维护如行列等读取信息
	// 有关注释的、不用太关心、用于处理// go:等这些特殊注释
	mode   uint
	// 当nlsemi为true时，遇到换行转换为; token
	// 即有些Token后面必须跟着;，而go;可以省略不写，这时候就要判断有无换行了
	nlsemi bool // if set '\n' and EOF translate to ';'
	// current token, valid after calling next()
	// 注意区分source.go中的行列。这是保存每个token开头的行列
	line, col uint
	blank     bool // line is blank up to col
	// 获取的当前token
	tok token
	// 一个Token对应多个或者无限个原始字符串时就要考lit、op这些来记录
	// _Literal对应原始值千变万化，需要记录。
	// _Semi记录的原因是，它可能是换行或者EOF变来的
	lit string // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is true
	bad bool   // valid if tok is _Literal, true if a syntax error occurred, lit may be malformed
	// 字面量有很多种，kind就是用来标识字面量种类的
	kind LitKind // valid if tok is _Literal
	// 最后2个字段是配合使用的，_Operator对应的操作符有多种。要配合op来区分
	op Operator // valid if tok is _Operator, _AssignOp, or _IncOp
	// 记录操作符优先级
	prec int // valid if tok is _Operator, _AssignOp, or _IncOp
}

type source struct {
	in    io.Reader
	// 错误处理函数
	errh  func(line, col uint, msg string)
	buf   []byte // source buffer
	ioerr error  // pending I/O error, or nil
	// b,r,e是缓冲区源代码bytes的三个索引。b代表最近开始读取token的开头，r代表正在读的地方，其后是将要读的chr，e代表结束，其在读入缓冲的最后一个字节后面
	b, r, e int // buffer indices (see comment above)
	// 索引0开始的行列信息
	line, col uint // source position of ch (0-based)
	// 最近读取的字符
	ch rune // most recently read character
	// chw的宽度，即r - chw == r上一次指向
	chw int // width of ch
}
  • source结构体维护了一个buf，nextch函数每次读取字符时，当s.e -s.r 小于一个utf8最大字符所占字节时，就会调用fill函数来继续读取源代码到buf中，buf的使用能够让我们避免读取大文件时占用很多内存
  • 词法分析是由语法分析实时调用，初始化也是由语法分析来传参调用。其实next()不是不断调用一次处理完所有token。而是在语法分析中不断按语法需求来实时调用获取当前token
  • next函数解析：只列出部分代码，读者需要去scanner.go文件中查看源代码。
    • 建议读一读公共前缀处理逻辑（如-与--是如何区别处理的）、注释处理逻辑（其中多行注释也可以转变为“;”）、标识符和关键字处理逻辑、number处理逻辑（不同进制如何处理，小数、指数等如何处理的）、字符串处理逻辑（主要看看转义处理）。所有带注释源代码将在最后给出链接
    • 可以看出next中有大片case逻辑，这就是直接扫描法
    • next调用了一个lower函数，它用位运算巧妙的吧大小写字母统一变为小写字母
    • 读者可以产看一下有哪些token后面的换行需要转换为“;”
    • 其实可以看出Go词法分析不能检测出一些词法书写错误，会推迟到语法分析发现，比如我们看数字处理的源码，遇到非法字符不会报错，即123abc这种我们在词法分析阶段会产生为2个Token（123，abc）
// next()是词法分析核心函数，它每次读取一个Token
func (s *scanner) next() {
	nlsemi := s.nlsemi
	s.nlsemi = false // 保留上一个token是否需要“;”
redo:
	// skip white space 使用循环跳过空白换行等字符
	// 可以看出换行符只有上一个token不要求nlsemi(换行转变为;)时才跳过换行
	s.stop() // 每次读取Token的时候重置s.b。注意判别的是，s.r不是也一起变了。s.b会通过start函数开启新的segment的时候。移动到s.r附近
	startLine, startCol := s.pos() // 保存最开始时执行next时的行列位置
	for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {
		s.nextch()
	}
	// token start
	s.line, s.col = s.pos() // token的开始行列
	s.blank = s.line > startLine || startCol == colbase
	s.start() // 开启新的segment，即相当于开始获取一个token
	if isLetter(s.ch) || s.ch >= utf8.RuneSelf && s.atIdentChar(true) {
		s.nextch()
		s.ident()
		return
	}
	// 处理非标识符,关键字 token
	switch s.ch {
	case -1:
		if nlsemi {
			s.lit = "EOF"
			s.tok = _Semi
			break
		}
		s.tok = _EOF
	case '\n': // 这是不忽略的换行
		s.nextch()
		s.lit = "newline"
		s.tok = _Semi

	case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
		s.number(false)
	// 省略若干行
  • Go词法分析获取一个Token的过程总结：入口函数为next()函数，不断利用nextch()函数跳过无用字符（如\t \n等），前一个Token需要“;”则不能跳过换行符。然后调用start函数更新buf下标信息位置，让s.b移动到新Token的开头，准备开始读取新的可用Token。当前字符为标识符允许开头则分析为关键字或者标识符。其它情况则用switch-case获取当前token第一个字符来判断走哪个分支来分析出不同Token。其中buf的下标处理很重要，要考虑的面面俱到，特别是边界的时候
  1. 相关链接：

词法分析算是编译器中较为简单的部分、下一篇博客将会阅读语法分析源代码

一、词法分析
二、Go编译器词法分析源码解析