???? 淺析 Go 語言的詞法分析器

章節目錄

簡介

Token

Scanner

例子

作者能力有限, 如果您在閱讀過程中發現任何錯誤, 還請您務必聯系本人,指出錯誤, 避免后來讀者再學習錯誤的知識.謝謝!

簡介##

在本文我們將簡單的走讀 Go 語言的詞法分析器實現(go/scanner/scanner.go).

本文基于 Go 1.11.4.

對于 Scanner 的作用, 就像 Java 中的 StringTokenizer 類型, 負責將一個輸入字符串按照特定的分隔符劃分為一個個獨立的單元. 不同的地方在于, 詞法分析器在劃分單元時依照的是 Go 語言的規范, 而不是指定的分隔符.

那么為什么要將源代碼進行劃分呢? 說來話長, 建議閱讀編譯原理相關書籍^-.

在寫下本文之前, 本人有幸剛剛閱讀了 Writing an interpreter in go , 感謝該書作者, 這本書對于我寫下這篇文章有很多的幫助, 在這兒分享給大家.

Token##

維基百科中對詞法分析描述如下:

詞法分析（英語：lexical analysis）是計算機科學中將字符序列轉換為標記（token）序列的過程。進行詞法分析的程序或者函數叫作詞法分析器（lexical analyzer，簡稱lexer），也叫掃描器（scanner）。詞法分析器一般以函數的形式存在，供語法分析器調用。

對于編譯原理有了解的讀者肯定深知, 詞法分析是編譯的第一步. 它的主要作用就是將源代碼(這里就是我們編寫的 Go 語言源文件)進行掃描, 將源代碼解析為一個個的詞法單元. 而詞法單元就對應于我們源代碼中的變量,函數,關鍵字等.

舉個例子, 當我們使用 Go 語言編程時, 寫下如下代碼:

var a bool = false

通過詞法解析器的解析, 我們將會得到如下 Token:

var // Go 語言關鍵字 a // 變量 bool // Go語言內置類型, 也屬于關鍵字 = // 賦值關鍵字 false // 常量關鍵字

正如你所看到的那樣, 我們在解析過程中不僅僅解析出了不同的程序組件, 而且每個組件都有特定的類型標記, 這些信息將被語法分析器使用. 比如可以用來檢測語法錯誤.

好了, 本人知識有限,概述到此結束, 我們來看一下 token.go 的實現(該文件位于 Go 源碼目錄 go/token/token.go).

為了減少篇幅, 這里省略了部分代碼.

type Token int// 所有 Go 語言支持的 Token 類型列表 const (// 該類型的 Token 標識源文件中存在詞法錯誤, 詞法分析無法成功的解析源文件.// 也就是說我們編寫了不符合 Go 語言語法的源代碼ILLEGAL Token = iota// 該類型的 Token 表示源文件已經被遍歷完成// 在遇到這種類型的 Token 時, 表示著詞法分析的完成EOF COMMENT // 這個 Token 不必多說, 標識源代碼中的注釋literal_beg// IDENT 標識一個標識符, 比如方法名稱, 類型名稱, 變量名稱等. // 常量, 關鍵字都不屬于這個類型IDENT // mainINT // 12345FLOAT // 123.45IMAG // 123.45iCHAR // 'a'STRING // "abc"literal_endoperator_beg// Operators and delimitersADD // +SUB // -MUL // *QUO // /REM // %// AND, OR, +=, -=, &=, ^= 等省略ARROW // <-// 這里省略了各種括號對應的 Token 類型定義operator_endkeyword_beg// 以下聲明 Go 語言關鍵字 Token 類型, 這里省略了絕大部分FUNCGOGOTOIFIMPORTSELECTSTRUCTSWITCHTYPEVARkeyword_end )// tokens map 的用處在于將詞法分析過程中解析出來的單詞或者詞組 // 與上面剛剛定義的 Token 類型對應起來 // 比如, 當詞法分析器從源代碼中解析出一個單詞 func 時, 他將創建一個 Token, // 而該 Token 的類型將是 FUNC. 這一項就存在于下面這個 tokens map 中. // 值得一提的時, 這個 map 中包含了幾項 Token 類型, 這些類型僅僅在用來 // 輔助詞法分析器, 程序中并不會出現這樣的詞法單元.這幾個類型: // ILLEFAL: 用來標識不符合 Go 語言語法的詞法單元出現在源程序中 // EOF: 用來標識源程序解析完畢 var tokens = [...]string{ILLEGAL: "ILLEGAL",EOF: "EOF",COMMENT: "COMMENT",FUNC: "func",GO: "go",GOTO: "goto",IF: "if",IMPORT: "import",SELECT: "select",STRUCT: "struct",SWITCH: "switch",TYPE: "type",VAR: "var", }// 該方法返回 Token 的字符串表示形式 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 }const (LowestPrec = 0 // non-operatorsUnaryPrec = 6HighestPrec = 7 )// 獲取當前 Token 的優先級 // 對于非操作符的 Token, 它的優先級最低, 為 LowestPrec. // 舉個例子說明以下. 比如我們在解析如下代碼: a := b + c * d // 我們會得到七個 Token. 分別對應 a, :=, b, +, c, *, d // 在語法分析中, 當我們要評估 a 在執行完該語句時,它的值是多少, // 我們就需要知道每個操作符 Token (:=, +, *) 的優先級, 以決定哪個操作將被優先執行, // 哪個操作實在另一個操作執行完之后執行. func (op Token) Precedence() int {switch op {case LOR:return 1case LAND:return 2case EQL, NEQ, LSS, LEQ, GTR, GEQ:return 3case ADD, SUB, OR, XOR:return 4case MUL, QUO, REM, SHL, SHR, AND, AND_NOT:return 5}return LowestPrec }var keywords map[string]Tokenfunc init() {keywords = make(map[string]Token)for i := keyword_beg + 1; i < keyword_end; i++ {keywords[tokens[i]] = i} }// 該方法用來判別一個解析出來的 Identifier 到底是一個 Identifier 還是一個關鍵字. // 關鍵字 map 在上一步已經被初始化了. func Lookup(ident string) Token {if tok, is_keyword := keywords[ident]; is_keyword {return tok}return IDENT }// 下面幾個方法很好理解, 不在贅述func (tok Token) IsLiteral() bool { return literal_beg < tok && tok < literal_end }func (tok Token) IsOperator() bool { return operator_beg < tok && tok < operator_end }func (tok Token) IsKeyword() bool { return keyword_beg < tok && tok < keyword_end }

Scanner##

了解了 Token 之后, 我們就可以來看看 Scanner 的實現了.

就如簡述中所述, 詞法分析器的作用是將源程序分解為一個個 Token, 以便于語法分析器使用. 它的輸入肯定就是源程序了, 輸出自然是一個 Token 的集合.

詞法分析器僅能檢測出很少部分的程序錯誤, 比如 if 語句后未使用花括號’{’, 非法的操作符’…’ 等. 對于類型或變量重定義, 函數調用參數個數不正確等錯誤都需要在編譯器后續過程中才能發現.

這里我們先簡述一下詞法分析器的工作原理, 這樣將有助于學習源碼.
詞法分析器往往是一個一個字符的讀取輸入的代碼, 通過當前讀取到的字符, 搭配一個解析詞法的狀態機來決定當前讀取到的 Token 的類型.有時, 一個字符并不能提供足夠的信息來做出這種判斷, 此時就需要預先讀取下一個或多個字符來輔助詞法分析器做出判斷.
正如 <> 中所說的一樣, 它的工作原理與 JSON 解析器或者 XML 解析器的工作原理大體上是一致的, 只是得到的結果略有不同而已.
而這里提到的解析詞法的狀態機就是我們將要學習的核心了.

下來我們就來看看 scanner.go 源代碼.
和上一小節相同, 我們只留下程序的主干部分, 細枝末節的代碼我們將省略掉以換取相對的清晰整潔.
我們同時也根據需要調整了方法或者變量的聲明位置.

type Scanner struct {file *token.File // source file handledir string // directory portion of file.Name()src []byte // 輸入字節數組// 詞法分析器使用的核心變量ch rune // 記錄當前字符offset int // 記錄當前讀取到了輸入字節的位置rdOffset int // reading offset (position after current character)lineOffset int // 記錄當前讀取到的字符在輸入字節的哪一行// 這里我們省略了記錄錯誤信息的相關變量或者方法, 我們不關注它 }// 初始化詞法分析器 // 正如你所看到的, 這里并沒有很多值得關注的地方 // 唯一值得一看的就是 next 方法 func (s *Scanner) Init(file *token.File, src []byte, err ErrorHandler, mode Mode) {// Explicitly initialize all fields since a scanner may be reused.if file.Size() != len(src) {panic(fmt.Sprintf("file size (%d) does not match src len (%d)", file.Size(), len(src)))}s.file = files.dir, _ = filepath.Split(file.Name())s.src = srcs.err = errs.mode = modes.ch = ' 's.offset = 0s.rdOffset = 0s.lineOffset = 0s.insertSemi = falses.ErrorCount = 0s.next()if s.ch == bom {s.next() // ignore BOM at file beginning} }// 讀取下一個字符. // 詞法分析器實質上就一個狀態機, 而該狀態機總是需要以當前字符作為輸入. // 這個方法的作用就是讀取輸入字節中下一個字符. // 因為 Go 支持 Unicode 編碼格式的源程序, // 所以我們將會看到這個方法讀取的是下一個字符, 而不是下一個字節. // 這個方法并沒有返回值, 而是更新了 Scanner 類型中的相關變量(ch, offset等) func (s *Scanner) next() {// 如果當前還未讀取到輸入字節的結束位置, 則讀取下一個字符到 ch, // 并更新 offset, rdOffset, lineOffset, if s.rdOffset < len(s.src) {s.offset = s.rdOffsetif s.ch == '\n' {s.lineOffset = s.offsets.file.AddLine(s.offset)}r, w := rune(s.src[s.rdOffset]), 1switch {case r == 0:s.error(s.offset, "illegal character NUL")case r >= utf8.RuneSelf:// not ASCIIr, w = utf8.DecodeRune(s.src[s.rdOffset:])if r == utf8.RuneError && w == 1 {s.error(s.offset, "illegal UTF-8 encoding")} else if r == bom && s.offset > 0 {s.error(s.offset, "illegal byte order mark")}}s.rdOffset += ws.ch = r} else {s.offset = len(s.src)if s.ch == '\n' {s.lineOffset = s.offsets.file.AddLine(s.offset)}s.ch = -1 // 當讀取到源程序的結束位置時, 將 ch 標記為 -1, 這代表了 EOF.} }// Scan 方法就是詞法分析器的核心實現了, 正如上面所說, 它是一個狀態機.// 從它的返回值我們可以看到, 對于 Scan 的每一次調用, 該方法將會返回一個 Token// 如果返回的 Token 是 literal (token.IDENT, token.INT, token.FLOAT, // token.IMAG, token.CHAR, token.STRING), 或者 Token.COMMENT, // 該方法的返回值 lit 將會包含該 Token 的值. // 這里需要注意的是, 返回值 Token 僅僅代表了當前解析出來的 Token 的類型, 并未包含 // Token 的值. 一些 Token 的類型就代表了它的值. 比如 '{', '+'等, // 而另外一些 Token 需要額外的返回值表示它的值. 比如當讀取到的 Token 是 INT 時, // 我們就需要使用返回值 lit 來取得讀取到的到底是 0 還是 1000 或者其他的合法整數值.// 如果當前讀取到的 Token 是 ILLEGAL, 那么返回值 lit 將會是未能成功解析的字符// 這里返回值 pos 可以暫時忽略func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) { scanAgain:// 很容易理解, 我們總是習慣于在代碼中插入空格空行等對于編譯器來說沒有意義的字符, // 這里使用 skipWhitespace 方法過濾掉.s.skipWhitespace() pos = s.file.Pos(s.offset)// 判斷當前 token 的類型, 根據當前字符 ch.switch ch := s.ch; {// 如果當前讀取到的是一個字母.(a-z, A-Z或者utf8編碼的字母), // 我們就將他解析為標識符(Identifier) token// 當然這個標識符可能是一個關鍵字,因此使用 token.Lookup // 來判斷當前標識符是否是關鍵字case isLetter(ch): lit = s.scanIdentifier()if len(lit) > 1 { // 關鍵字的長度都大于1, 因此小于1的情況下, 必然是標識符tok = token.Lookup(lit)} else {tok = token.IDENT}// 如果當前讀取到的是一個數字, 那就將他解析為數字, 具體是 INT, FLOAT // 在scanNumber方法中進行判斷, 我們回過頭來再來看該方法case '0' <= ch && ch <= '9':tok, lit = s.scanNumber(false)default:s.next() // 將 s.ch 更新為下一個字符, 我們將依賴于下一個判斷當前 token 類型switch ch { // 此處的 ch 是 s.ch 的前一個字符case -1:tok = token.EOFcase '\n': return pos, token.SEMICOLON, "\n"case '"': // 當前 token 是 string. 形式如 "abc..."tok = token.STRINGlit = s.scanString()case '\'': // 當前 token 是 char. 形式如 'a'tok = token.CHARlit = s.scanRune()case '`': // 當前 token 是 raw string. 形式如 `abc...`tok = token.STRINGlit = s.scanRawString()case ':': // 遇到 ':', 具體token 類型將和下一個字符有關. // 如果下一個字符是 '=', 那么當前 token 將是 ":=", 否則就是簡單的 ':'tok = s.switch2(token.COLON, token.DEFINE)case '.':// 當前 ch 是 '.', 且 s.ch 是數字, 那么我們目前所處的// token 的格式為 "*.1"形式, 只能是小數.if '0' <= s.ch && s.ch <= '9' {tok, lit = s.scanNumber(true)} else if s.ch == '.' { // 如果當前 ch 是 '.', 且 s.ch 也是 '.', 那么我們當前 token 的格式為 ".."// 因此當前 token 應為 "...". 否則為非法 token(但是這里并沒有處理這種情況).s.next()if s.ch == '.' {s.next()tok = token.ELLIPSIS}} else { // 如果不是 小數,':', ':=', 也不是 '...', 那么我們認為它是 '.'.// 比如 foo.Prop 中的點tok = token.PERIOD}case ',':tok = token.COMMAcase ';':tok = token.SEMICOLONlit = ";"case '(':tok = token.LPARENcase ')':tok = token.RPARENcase '[':tok = token.LBRACKcase ']':tok = token.RBRACKcase '{':tok = token.LBRACEcase '}':tok = token.RBRACEcase '+':// 如果當前 ch 是 '+', 那么所有可能結果是 '+', '+=', '++'. // 具體 token 類型仍然取決于 s.ch 的值tok = s.switch3(token.ADD, token.ADD_ASSIGN, '+', token.INC)case '-':tok = s.switch3(token.SUB, token.SUB_ASSIGN, '-', token.DEC)case '*':tok = s.switch2(token.MUL, token.MUL_ASSIGN)case '/':// 如果當前 ch 是 '/', 且 s.ch 是 '/' 或者 '*', 當前 token 是注釋.if s.ch == '/' || s.ch == '*' {comment := s.scanComment()tok = token.COMMENTlit = comment} else {// 如果不是注釋, 那么可能結果為除法操作符或者'/='.tok = s.switch2(token.QUO, token.QUO_ASSIGN)}case '%':// 可能結果為取模操作符或者 '%=' 操作符.tok = s.switch2(token.REM, token.REM_ASSIGN)case '^': tok = s.switch2(token.XOR, token.XOR_ASSIGN)case '<':if s.ch == '-' {s.next()tok = token.ARROW} else {tok = s.switch4(token.LSS, token.LEQ, '<', token.SHL, token.SHL_ASSIGN)}case '>':tok = s.switch4(token.GTR, token.GEQ, '>', token.SHR, token.SHR_ASSIGN)case '=':tok = s.switch2(token.ASSIGN, token.EQL)case '!':tok = s.switch2(token.NOT, token.NEQ)case '&':if s.ch == '^' {s.next()tok = s.switch2(token.AND_NOT, token.AND_NOT_ASSIGN)} else {tok = s.switch3(token.AND, token.AND_ASSIGN, '&', token.LAND)}case '|':tok = s.switch3(token.OR, token.OR_ASSIGN, '|', token.LOR)default:// next reports unexpected BOMs - don't repeatif ch != bom {s.error(s.file.Offset(pos), fmt.Sprintf("illegal character %#U", ch))}tok = token.ILLEGALlit = string(ch)}}return }func (s *Scanner) scanComment() string {// initial '/' already consumed; s.ch == '/' || s.ch == '*'offs := s.offset - 1 // position of initial '/'next := -1 // position immediately following the comment; < 0 means invalid commentnumCR := 0if s.ch == '/' {//-style comment// (the final '\n' is not considered part of the comment)s.next()for s.ch != '\n' && s.ch >= 0 {if s.ch == '\r' {numCR++}s.next()}// if we are at '\n', the position following the comment is afterwardsnext = s.offsetif s.ch == '\n' {next++}goto exit}/*-style comment */s.next()for s.ch >= 0 {ch := s.chif ch == '\r' {numCR++}s.next()if ch == '*' && s.ch == '/' {s.next()next = s.offsetgoto exit}}s.error(offs, "comment not terminated")exit:lit := s.src[offs:s.offset]// On Windows, a (//-comment) line may end in "\r\n".// Remove the final '\r' before analyzing the text for// line directives (matching the compiler). Remove any// other '\r' afterwards (matching the pre-existing be-// havior of the scanner).if numCR > 0 && len(lit) >= 2 && lit[1] == '/' && lit[len(lit)-1] == '\r' {lit = lit[:len(lit)-1]numCR--}// interpret line directives// (//line directives must start at the beginning of the current line)if next >= 0 /* implies valid comment */ && (lit[1] == '*' || offs == s.lineOffset) && bytes.HasPrefix(lit[2:], prefix) {s.updateLineInfo(next, offs, lit)}if numCR > 0 {lit = stripCR(lit, lit[1] == '*')}return string(lit) }func isLetter(ch rune) bool {return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_' || ch >= utf8.RuneSelf && unicode.IsLetter(ch) }func isDigit(ch rune) bool {return '0' <= ch && ch <= '9' || ch >= utf8.RuneSelf && unicode.IsDigit(ch) }// 讀取一個標識符. // 標識符的合法表示為以字符開頭可以包含數字的字符串 func (s *Scanner) scanIdentifier() string {offs := s.offsetfor isLetter(s.ch) || isDigit(s.ch) {s.next()}return string(s.src[offs:s.offset]) }func digitVal(ch rune) int {switch {case '0' <= ch && ch <= '9':return int(ch - '0')case 'a' <= ch && ch <= 'f':return int(ch - 'a' + 10)case 'A' <= ch && ch <= 'F':return int(ch - 'A' + 10)}return 16 // larger than any legal digit val }// 讀取一個字符串 // 這里的字符串是雙引號格式的. 對于``形式的字符串由scanRawString()方法解析 func (s *Scanner) scanString() string {// '"' opening already consumedoffs := s.offset - 1for {ch := s.chif ch == '\n' || ch < 0 {s.error(offs, "string literal not terminated")break}s.next()if ch == '"' {break}if ch == '\\' {s.scanEscape('"')}}return string(s.src[offs:s.offset]) }func (s *Scanner) scanRawString() string {// '`' opening already consumedoffs := s.offset - 1hasCR := falsefor {ch := s.chif ch < 0 {s.error(offs, "raw string literal not terminated")break}s.next()if ch == '`' {break}if ch == '\r' {hasCR = true}}lit := s.src[offs:s.offset]if hasCR {lit = stripCR(lit, false)}return string(lit) }func (s *Scanner) skipWhitespace() {for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !s.insertSemi || s.ch == '\r' {s.next()} }

例子##

上面我們已經簡單的了解了整個解析器的工作原理, 下面我們來跑幾個測試來驗證一下.

測試用例位于 go/scanner/scanner_test.go

輸入輸出對照表:

輸入Token 類型Token 值

/* a comment */	COMMENT	/* a comment */
// a comment	COMMENT	// a comment
foobar	IDENT	foobar
01234567	INT	01234567
0xcafebabe	INT	0xcafebabe
3.14159265	FLOAT	3.14159265
2.71828e-1000	FLOAT	2.71828e-1000
‘a’	CHAR	a
`foobar`	STRING	`foobar`
+	ADD	EMPTY
/	QUO	EMPTY
%=	REM_ASSIGN	EMPTY
,	COMMA	EMPTY
{	LBRACK	EMPTY
break	BREAK	break
case	CASE	case
fallthrough	FALLTHROUGH	EMPTY

省略部分測試用例

END!

總結

以上是生活随笔為你收集整理的Golang 词法分析器浅析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。