目錄
1.編譯器和解釋器
簡單來說皂岔，一個編譯器就是一個程序，它可以把以某一語言編寫的程序(c代碼寫的源程序)翻譯成一個等價的关划、另一種語言編寫的程序(匯編代碼的目標程序)
那么用戶可以利用目標程序處理輸入產(chǎn)生輸出
但兩者內(nèi)部都是大同小異
1.1編譯器結(jié)構(gòu)
編譯器的翻譯過程可以看作兩個部分：
- 分析部分，也被叫做編譯器的前端栓辜，主要負責將字符輸入流轉(zhuǎn)為token永高，進一步轉(zhuǎn)為ast抽象語法樹隧土，步驟包括：
- 詞法分析 生成token/記號
- 語法分析 生成ast抽象語法樹
-
語義分析 生成中間表示
image.png
-
綜合部分，也被叫做編譯器的后端命爬，主要負責翻譯成目標機器語言
image.png
1.2簡單的編譯器實例
2.詞法分析
詞法分析是編譯的第一階段曹傀，主要任務(wù)是讀取字符流，將他們轉(zhuǎn)為記號（也有說是token/單詞等）流饲宛，記號是編譯器內(nèi)部定義的數(shù)據(jù)結(jié)構(gòu)皆愉，編碼所識別出的詞法單元
如c程序
if (x > 5)
y = "hello";
else
z=1;
- IF 對應(yīng)關(guān)鍵字if
- ()對應(yīng)LPAREN和RPAREN
- x 對應(yīng) 標識IDENT，同時還要攜帶上名字(x)
- 大于號對應(yīng)GT
艇抠。幕庐。。家淤。异剥。。 - 最后加上文件結(jié)束符EOF
2.1 C語言中記號的數(shù)據(jù)結(jié)構(gòu)定義
關(guān)鍵字絮重、符號等被定義在枚舉中
enum kind {IF,LPAREN,ID,...};
他們分別對應(yīng)唯一的數(shù)字冤寿，這也是對單詞的分類
struct token {
enum kind k;
char *lexeme;
}
token是這些記號在c語言中的結(jié)構(gòu)體(lexeme是識別出的單詞具體值,0標識沒有賦予任何值，通常用于關(guān)鍵字)青伤，那么如下語句
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詞法分析器的實現(xiàn)方法
主要兩種：手工編碼實現(xiàn)法和詞法分析器的生成器
2.2.1手工編碼實現(xiàn)法
利用轉(zhuǎn)移圖識別標識符督怜、關(guān)鍵字和符號，來返回對應(yīng)的token數(shù)據(jù)結(jié)構(gòu)潮模，這是手工編碼的方法之一
2.2.1自動生成記號
從字符流->正則表達式->記號流的轉(zhuǎn)換過程如下:
字符流->正則表達式RA->ANF->有限狀態(tài)機DNF->記號流
這只是其中的一種例舉手段亮蛔，并不是所有語言全都這個流程
3.go詞法分析
我們知道golang的編譯器自身也是用golang語言開發(fā)的(自舉)，也就意味著我們能在源碼找到go的記號擎厢。在src的源碼中有兩處定義究流，一處是用于編譯器前端解析的src/cmd目錄下的源碼辣吃，另一處就是src/go目錄下的源碼，兩者實現(xiàn)邏輯不太一樣但原理一樣芬探。官方的獨立cli程序gofmt引用的就是后者神得，原理就是把代碼解析成ast語法樹，然后再把ast轉(zhuǎn)回代碼（這也是我們學(xué)習ast的目標）偷仿，出于學(xué)習ast編程的目的哩簿，我們選擇后者：
- go/token:Token類型以及相關(guān)結(jié)構(gòu)體的定義
- go/scanner:詞法分析成Token序列
3.1go的記號
go中的記號被叫做token，位于src/go/token/token.go和c語言中的一樣使用整形“代替”
type token int
和上面c定義記號一樣使用枚舉酝静，每個類型的字面值都有對應(yīng)的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主要有標識符节榜、關(guān)鍵字、運算符别智、分隔符等類型
-
標識符指go對各種變量宗苍、方法、函數(shù)等命名時使用的字符序列
image.png
前三個是特殊類型的token薄榛，分別是錯誤讳窟、文件結(jié)束和注釋，當遇到不能識別的token時敞恋，即源文件存在詞法錯誤丽啡，統(tǒng)一返回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相關(guān)位置硬猫，也就是屬性补箍，它也有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程序可以由多個包鏈接成一個可執(zhí)行文件盔性，單個包又對應(yīng)多個文件霞丧，因此position.go還定義了FilSet和File結(jié)構(gòu)體，用于描述文件集和文件
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
}
根據(jù)注釋內(nèi)容冕香，我們得到以下信息：
- FileSet文件集代表一組源文件
- 文件集可能被多個協(xié)程同步調(diào)用蛹尝，因此需要讀寫鎖
-
base和size：這個base不是上面這個成員base。文件集中每個文件的字節(jié)偏移映射到不同的整數(shù)區(qū)間中[base悉尾，base+size]突那。base表示文件中的第一個字節(jié),size表示大小image.png
- Pos：是上面一個區(qū)間中的一個值，通過確定pos值所屬的區(qū)間构眯，可以計算出文件的位置信息愕难，即Pos值可以轉(zhuǎn)換成token完整的position
type Pos int
- files切片中保存了一個文件集下所有的File文件，利用base來標識文件File的偏移量，base計算從1開始猫缭，因為第0個位置被EOF占了葱弟，因此調(diào)用FileSet.AddFile()函數(shù)來添加新文件時，必須提供文件基數(shù)file base猜丹，這個值可以是任何整數(shù)芝加，但必須超過文件集中已存在的任何值。FileSet.Base()函數(shù)滿足這樣的值（FileSet.base）射窒，就是與Pos間隔的末位+1藏杖，通常也都是用這個函數(shù)作為參數(shù)輸入AddFile中
FileSet常用函數(shù)的簽名如下:
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實現(xiàn)Token掃描脉顿，是在FileSet和File抽象文件集合基礎(chǔ)上進行的蝌麸，
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對象的賦值初始化，再內(nèi)部調(diào)用next函數(shù)
- next是獲取下一個要解析的字符艾疟，把它讀進scanner.ch中祥楣，因為GOlang支持utf-8編碼的源程序，所以next讀取的是字符而不是字節(jié)
- Scan是詞法分析的核心方法汉柒，如上面的解釋，它是一個switch/case的狀態(tài)機责鳍，每一次調(diào)用都返回一個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
//創(chuàng)建文件集FileSet碾褂，token的位置必須通過文件集定位
fset := token.NewFileSet()
//向文件集中添加新文件File,文件名為空""
file := fset.AddFile("", fset.Base(), len(src))
//初始化掃描器，第三個參數(shù)表示自定義錯誤處理函數(shù)
//最后一個參數(shù)表示不用忽略注釋token
s.Init(file, src, nil, scanner.ScanComments)
//循環(huán)讀取字符流解析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 "http:// Euler"
// 1:28 ; "\n"
}
這個Scanner對象就是詞法分析器历葛，它的主要方法是Scan正塌，主流程如下，是一個switch case的有限狀態(tài)確定機：
- 碰到字符掃調(diào)用sacnString掃描
- 碰到數(shù)字調(diào)用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詞法分析探索完結(jié)
