GO/ast编程--编译原理学习之词法分析
1.编译器和解释器
简单来说，一个编译器就是一个程序，它可以把以某一语言编写的程序(c代码写的源程序)翻译成一个等价的、另一种语言编写的程序(汇编代码的目标程序)
image.png
那么用户可以利用目标程序处理输入产生输出
image.png
但两者内部都是大同小异
1.1编译器结构
编译器的翻译过程可以看作两个部分：
- 分析部分，也被叫做编译器的前端，主要负责将字符输入流转为token，进一步转为ast抽象语法树，步骤包括：
- 词法分析 生成token/记号
- 语法分析 生成ast抽象语法树
-
语义分析 生成中间表示
image.png
-
综合部分，也被叫做编译器的后端，主要负责翻译成目标机器语言
image.png
1.2简单的编译器实例
2.词法分析
词法分析是编译的第一阶段，主要任务是读取字符流，将他们转为记号（也有说是token/单词等）流，记号是编译器内部定义的数据结构，编码所识别出的词法单元
如c程序
if (x > 5)
y = "hello";
else
z=1;
image.png
- 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的记号
3.1go的记号
go中的记号被叫做token，位于src/go/token/token.go
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切片中，方便快速判断token类型
var tokens = [...]string{
ILLEGAL: "ILLEGAL",
EOF: "EOF",
COMMENT: "COMMENT",
IDENT: "IDENT",
go/token/position.go当中定义了token相关位置，也就是属性
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
}
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
}
- FileSet利用files切片保存一个文件集下所有的File文件，利用base来标识文件File的偏移量，base计算从1开始，因为第0个位置被EOF占了
- File中的lines可以用来计算出Token的行号和列号
- lineinfo用于存储每个token的行列号
image.png
除此之外还有一个关键变量Pos
type Pos int
FileSet把File的内容按字节顺序放在一个大数组中，而某个文件则属于数组的一个区间[base,base+size]，pos是这个区间中的一个小标，表示一个文件中的位置，当需要使用时，会根据pos从fileset中转换出完整的positon对象
3.2词法分析部分
位于go/scanner/scanner.go中，该包提供了Scanner实现Token扫描，是在FileSet和File抽象文件集合基础上进行的，我们看同目录下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"
