目录
1.编译器和解释器
简单来说，一个编译器就是一个程序，它可以把以某一语言编写的程序(c代码写的源程序)翻译成一个等价的、另一种语言编写的程序(汇编代码的目标程序)
那么用户可以利用目标程序处理输入产生输出
但两者内部都是大同小异
1.1编译器结构
编译器的翻译过程可以看作两个部分：
- 分析部分，也被叫做编译器的前端，主要负责将字符输入流转为token，进一步转为ast抽象语法树，步骤包括：
- 词法分析 生成token/记号
- 语法分析 生成ast抽象语法树
-
语义分析 生成中间表示
image.png
-
综合部分，也被叫做编译器的后端，主要负责翻译成目标机器语言
image.png
1.2简单的编译器实例
2.词法分析
词法分析是编译的第一阶段，主要任务是读取字符流，将他们转为记号（也有说是token/单词等）流，记号是编译器内部定义的数据结构，编码所识别出的词法单元
如c程序
if (x > 5)
y = "hello";
else
z=1;
- IF 对应关键字if
- ()对应LPAREN和RPAREN
- x 对应 标识IDENT，同时还要携带上名字(x)
- 大于号对应GT
。。。。。。 - 最后加上文件结束符EOF
2.1 C语言中记号的数据结构定义
关键字、符号等被定义在枚举中
enum kind {IF,LPAREN,ID,...};
他们分别对应唯一的数字，这也是对单词的分类
struct token {
enum kind k;
char *lexeme;
}
token是这些记号在c语言中的结构体(lexeme是识别出的单词具体值,0标识没有赋予任何值，通常用于关键字)，那么如下语句
if (x>5)
就会被分析成如下伪代码
token{k=IF,lexeme=0}
token{k=LPAREN,lexeme=0}
token{k=IDENT,lexeme=x}
token{k=GT,lexeme=0}
token{k=RPAREN,lexeme=0}
2.2词法分析器的实现方法
主要两种：手工编码实现法和词法分析器的生成器
2.2.1手工编码实现法
利用转移图识别标识符、关键字和符号，来返回对应的token数据结构，这是手工编码的方法之一
2.2.1自动生成记号
从字符流->正则表达式->记号流的转换过程如下:
字符流->正则表达式RA->ANF->有限状态机DNF->记号流
这只是其中的一种例举手段，并不是所有语言全都这个流程
3.go词法分析
我们知道golang的编译器自身也是用golang语言开发的(自举)，也就意味着我们能在源码找到go的记号。在src的源码中有两处定义，一处是用于编译器前端解析的src/cmd目录下的源码，另一处就是src/go目录下的源码，两者实现逻辑不太一样但原理一样。官方的独立cli程序gofmt引用的就是后者，原理就是把代码解析成ast语法树，然后再把ast转回代码（这也是我们学习ast的目标），出于学习ast编程的目的，我们选择后者：
- go/token:Token类型以及相关结构体的定义
- go/scanner:词法分析成Token序列
3.1go的记号
go中的记号被叫做token，位于src/go/token/token.go和c语言中的一样使用整形“代替”
type token int
和上面c定义记号一样使用枚举，每个类型的字面值都有对应的token
const (
// Special tokens
ILLEGAL Token = iota
EOF
COMMENT
literal_beg
// Identifiers and basic type literals
// (these tokens stand for classes of literals)
IDENT // main
INT // 12345
FLOAT // 123.45
IMAG // 123.45i
CHAR // 'a'
STRING // "abc"
literal_end
operator_beg
// Operators and delimiters
ADD // +
SUB // -
MUL // *
QUO // /
REM // %
不难看出go中的token主要有标识符、关键字、运算符、分隔符等类型
-
标识符指go对各种变量、方法、函数等命名时使用的字符序列
image.png
前三个是特殊类型的token，分别是错误、文件结束和注释，当遇到不能识别的token时，即源文件存在词法错误，统一返回ILLEGAL
所有token还会被放入到一个string切片中，用于String方法被快速打印
func (tok Token) String() string {
s := ""
if 0 <= tok && tok < Token(len(tokens)) {
s = tokens[tok]
}
if s == "" {
s = "token(" + strconv.Itoa(int(tok)) + ")"
}
return s
}
var tokens = [...]string{
ILLEGAL: "ILLEGAL",
EOF: "EOF",
COMMENT: "COMMENT",
IDENT: "IDENT",
go/token/position.go当中定义了token相关位置，也就是属性，它也有String方法，可以被直接打印
type Position struct {
Filename string // filename, if any
Offset int // offset, starting at 0
Line int // line number, starting at 1
Column int // column number, starting at 1 (byte count)
}
顾名思义，标识token在文件中的位置，为什么要有这个属性？因为go程序可以由多个包链接成一个可执行文件，单个包又对应多个文件，因此position.go还定义了FilSet和File结构体，用于描述文件集和文件
type FileSet struct {
mutex sync.RWMutex // protects the file set
base int // base offset for the next file
files []*File // list of files in the order added to the set
last *File // cache of last file looked up
}
根据注释内容，我们得到以下信息：
- FileSet文件集代表一组源文件
- 文件集可能被多个协程同步调用，因此需要读写锁
-
base和size：这个base不是上面这个成员base。文件集中每个文件的字节偏移映射到不同的整数区间中[base，base+size]。base表示文件中的第一个字节,size表示大小image.png
- Pos：是上面一个区间中的一个值，通过确定pos值所属的区间，可以计算出文件的位置信息，即Pos值可以转换成token完整的position
type Pos int
- files切片中保存了一个文件集下所有的File文件，利用base来标识文件File的偏移量，base计算从1开始，因为第0个位置被EOF占了，因此调用FileSet.AddFile()函数来添加新文件时，必须提供文件基数file base，这个值可以是任何整数，但必须超过文件集中已存在的任何值。FileSet.Base()函数满足这样的值（FileSet.base），就是与Pos间隔的末位+1，通常也都是用这个函数作为参数输入AddFile中
FileSet常用函数的签名如下:
func NewFileSet() *FileSet
func (s *FileSet) AddFile(filename string, base, size int) *File
func (s *FileSet) Base() int
最后来看文件File
type File struct {
set *FileSet
name string // file name as provided to AddFile
base int // Pos value range for this file is [base...base+size]
size int // file size as provided to AddFile
// lines and infos are protected by mutex
mutex sync.Mutex
lines []int // lines contains the offset of the first character for each line (the first entry is always 0)
infos []lineInfo
}
type lineInfo struct {
Offset int
Filename string
Line, Column int
}
- File中的lines可以用来计算出Token的行号和列号
- lineinfo用于存储每个token的行列号
3.2词法分析部分
位于go/scanner/scanner.go中，该包提供了Scanner实现Token扫描，是在FileSet和File抽象文件集合基础上进行的，
type Scanner struct {
// immutable state
file *token.File // source file handle
dir string // directory portion of file.Name()
src []byte // source
err ErrorHandler // error reporting; or nil
mode Mode // scanning mode
// scanning state
ch rune // current character
offset int // character offset
rdOffset int // reading offset (position after current character)
lineOffset int // current line offset
insertSemi bool // insert a semicolon before next newline
nlPos token.Pos // position of newline in preceding comment
// public state - ok to modify
ErrorCount int // number of errors encountered
}
常用方法有三个
func (s *Scanner) Init(file *token.File, src []byte, err ErrorHandler, mode Mode)
func (s *Scanner) next()
func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string)
- Init就是对Scanner对象的赋值初始化，再内部调用next函数
- next是获取下一个要解析的字符，把它读进scanner.ch中，因为GOlang支持utf-8编码的源程序，所以next读取的是字符而不是字节
- Scan是词法分析的核心方法，如上面的解释，它是一个switch/case的状态机，每一次调用都返回一个token
3.2.1使用案例
我们看同目录下example.go下提供的案例来看如何解析"cos(x) + 1i*sin(x) // Euler"这句
func ExampleScanner_Scan() {
src := []byte("cos(x) + 1i*sin(x) // Euler")
var s scanner.Scanner
//创建文件集FileSet，token的位置必须通过文件集定位
fset := token.NewFileSet()
//向文件集中添加新文件File,文件名为空""
file := fset.AddFile("", fset.Base(), len(src))
//初始化扫描器，第三个参数表示自定义错误处理函数
//最后一个参数表示不用忽略注释token
s.Init(file, src, nil, scanner.ScanComments)
//循环读取字符流解析token
for {
pos, tok, lit := s.Scan()
if tok == token.EOF {
break
}
//打印token的位置
fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
}
// output:
// 1:1 IDENT "cos"
// 1:4 ( ""
// 1:5 IDENT "x"
// 1:6 ) ""
// 1:8 + ""
// 1:10 IMAG "1i"
// 1:12 * ""
// 1:13 IDENT "sin"
// 1:16 ( ""
// 1:17 IDENT "x"
// 1:18 ) ""
// 1:20 COMMENT "// Euler"
// 1:28 ; "\n"
}
这个Scanner对象就是词法分析器，它的主要方法是Scan，主流程如下，是一个switch case的有限状态确定机：
- 碰到字符扫调用sacnString扫描
- 碰到数字调用scanNumber方法扫描，同上
- 碰到计算符同上
。。。。。 - 每次返回一个被扫描的token,压缩表示的位置和字面值的字符串
代码太长就不贴出了，回头再看scanner对象
type Scanner struct {
// immutable state
file *token.File // source file handle
dir string // directory portion of file.Name()
src []byte // source
err ErrorHandler // error reporting; or nil
mode Mode // scanning mode
// 词法分析器使用的核心变量
ch rune // 当前字符
offset int // 字符偏移量
rdOffset int // 可以理解为ch的偏移量
lineOffset int // 当前的行偏移量
insertSemi bool // 在换行前插入分号
// public state - ok to modify
ErrorCount int // number of errors encountered
}
遍历完当前token后，ch会指向下一个字符，实际上就是scanner.next方法把下一个字符读进这个变量
3.3语法错误检验
词法分析只输出token，并不检测语法错误
func main() {
str :=
`
package main
func main() {
a = 1
}
`
src := []byte(str)
var s scanner.Scanner
fset := token.NewFileSet()
file := fset.AddFile("my.go", fset.Base(), len(src))
s.Init(file, src, func(pos token.Position, msg string) {
fmt.Print(msg)
}, scanner.ScanComments)
for {
pos, tok, lit := s.Scan()
if tok == token.EOF {
break
}
fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
}
}
my.go:2:1 package "package"
my.go:2:9 IDENT "main"
my.go:2:13 ; "\n"
my.go:4:1 func "func"
my.go:4:6 IDENT "main"
my.go:4:10 ( ""
my.go:4:11 ) ""
my.go:4:13 { ""
my.go:5:2 IDENT "a"
my.go:5:4 = ""
my.go:5:6 INT "1"
my.go:5:7 ; "\n"
my.go:6:1 } ""
my.go:6:2 ; "\n"
至此，go词法分析探索完结
