編譯程序中的詞法分析器的輸出是二元組 _編譯程序

前言
一、什么是編譯器前端
讓機(jī)器理解代碼并生成可執(zhí)行文件，這是一件很困難的事情，所以編譯器是一個(gè)非常浩大的工程，它內(nèi)部工作過程十分復(fù)雜。
不過計(jì)算機(jī)科學(xué)中有句名言，任何一個(gè)問題都可以通過增加一個(gè)中間層/抽象層來解決，這也是最常用的計(jì)算機(jī)分層思想。

All problems in computer science can be solved by another level of indirection. —— David John Wheeler

所以為了降低編譯器工程的復(fù)雜性，提高發(fā)展效率，一般把編譯器分為兩個(gè)完全解耦的兩個(gè)部分

編譯器前端：只負(fù)責(zé)理解代碼，不考慮各種CPU指令不兼容等問題
編譯器后端：只負(fù)責(zé)生成可執(zhí)行文件，不考慮各種語言特性

為了讓兩個(gè)部分可以連接在一起工作，所以必然存在一個(gè)部分的輸出是另一部分的輸入，很明顯，編譯器前端的輸出，就是編譯器后端的輸入。
這樣，兩個(gè)部分只需要約定好數(shù)據(jù)格式，就可以大幅度提高編譯器的發(fā)展效率，編譯器整個(gè)工作流程也變得非常簡單清晰了，如下圖所示，如果對(duì)圖中的編譯器前端不理解沒關(guān)系，接下來的第二節(jié)《編譯器前端的原理》會(huì)對(duì)這部分進(jìn)行講解

文章插圖
結(jié)論：所以編譯器前端就是編譯器中的前端部分，負(fù)責(zé)理解代碼并生成中間語言
二、編譯器前端的原理
既然編譯器前端的工作是理解代碼，那么它的原理是什么呢，首先看下面一段簡單的C語言代碼
int age = 18;復(fù)制代碼從人類閱讀代碼的角度來看，我們是如何理解上述代碼的呢
1、局部理解

看到 int 關(guān)鍵字
看到 age 標(biāo)識(shí)符
看到 = 賦值符號(hào)
看到 18 字面量數(shù)值
看到 ; 結(jié)束符

局部理解的過程，就是詞法分析的過程

2、全局理解
通過聯(lián)系孤立的、局部的理解結(jié)果，可得到一個(gè)整體 int age = 18 ; ，對(duì)其在腦海中進(jìn)行全局理解后，發(fā)現(xiàn)它符合C語言的整型賦值語法

整型賦值語法 -> 關(guān)鍵字 標(biāo)識(shí)符 賦值符號(hào) 字面量關(guān)鍵字 -> int | long標(biāo)識(shí)符 -> [a-zA-Z_]+[a-zA-Z+_*0-9]*字面量 ->[0-9]+復(fù)制代碼

所以通過全局理解，最終可知道上面代碼是一個(gè)整型的賦值語句

全局理解的過程，就是語法分析的過程

3、總結(jié)
結(jié)合人類理解代碼的過程，編譯器前端主要可以分為局部理解和全局理解兩個(gè)步驟，其中

局部理解會(huì)生成一個(gè)一個(gè)的理解結(jié)果，稱為Token
全局理解會(huì)把孤立的token聯(lián)系成為一個(gè)整體，進(jìn)行語法規(guī)則匹配，如果符合語法則理解成功，否則理解失敗

三、詞法分析器的介紹
詞法分析器就是在做對(duì)字符序列的局部理解，每完成一次局部理解，就生成一個(gè)Token 。常見的Token包括操作符、符號(hào)、空白符、關(guān)鍵字、標(biāo)識(shí)符、數(shù)字、浮點(diǎn)數(shù)、字符串、字符等。
所以詞法分析器的工作內(nèi)容也比較簡單，只要能把輸入的字符序列，生成一個(gè)有序的token列表即可。
四、詞法分析器的原理
1、直接掃描法
直接掃描法的思路類似二重循環(huán)的暴力法，每一輪的掃描都是如下過程

先第一層的掃描，根據(jù)第一個(gè)字符判斷屬于哪種類型的token
進(jìn)入第二層的掃描，向后依次讀?。?直到讀出一個(gè)完整的token為止，跳出第二層循環(huán)
繼續(xù)開始第一層的掃描

(1) 偽代碼

let end = s.length-1;for(let i=0; i<=end; i=n){ let tokenType = justTokenType(s[i]); switch(tokenType){ case "string": let queue = []; for(let j = i; j<=end-1; ++j){ if(!match){ break; } queue.push(s[j]); } let token = queue.join(''); tokens.push(token); n=j+1; break; }}復(fù)制代碼

(2) 缺點(diǎn)

邏輯非常復(fù)雜
可能存在回溯情況，可能需要記憶已匹配的前N個(gè)字符，效率低
大量IF判斷，可維護(hù)性差，擴(kuò)展性差

2、DFA法
DFA即deterministic finite automaton有限狀態(tài)自動(dòng)機(jī) ，其特點(diǎn)是可以實(shí)現(xiàn)狀態(tài)的自動(dòng)轉(zhuǎn)移，可以用于解決字符匹配問題
(1) 核心構(gòu)成
DFA的核心構(gòu)成要素是狀態(tài)和狀態(tài)的轉(zhuǎn)移

定義自動(dòng)機(jī)所具備的N種狀態(tài)，并定義初始狀態(tài)
定義上一個(gè)狀態(tài)轉(zhuǎn)移至下一個(gè)狀態(tài)的條件

文章插圖
(2) 應(yīng)用實(shí)踐
如何用DFA實(shí)現(xiàn)詞法分析器呢，步驟如下

先定義不同的狀態(tài) ：如操作符狀態(tài)、數(shù)字狀態(tài)、符號(hào)狀態(tài)等
再定義狀態(tài)轉(zhuǎn)移條件：如當(dāng)前狀態(tài)是初始狀態(tài) ，遇到數(shù)字則轉(zhuǎn)移至數(shù)字狀態(tài) ，遇到符號(hào)則轉(zhuǎn)移至符號(hào)狀態(tài)
如果字符讀取完成，則整個(gè)轉(zhuǎn)移過程結(jié)束

(3) 偽代碼

let state = 0; // 當(dāng)前狀態(tài), 也是初始狀態(tài)while ((ch = nextChar()) !== false) { let match = false; // 獲取下一個(gè)狀態(tài), 如果下一個(gè)狀態(tài)不是初始狀態(tài), 則說明匹配成功 let nextState = getNextState(ch, state); if (nextState) { match = true; } // 如果匹配成功, 則字符讀取序列的下標(biāo)+1，并轉(zhuǎn)移至下一個(gè)狀態(tài) if (match) { incrSeq(); flowtoNextState(ch, nextState); } else { // 不匹配則生成token，并轉(zhuǎn)移至初始狀態(tài)，開始重新匹配 produceToken(); flowtoResetState(); }}復(fù)制代碼

(4) 優(yōu)點(diǎn)

邏輯清晰簡單
可維護(hù)性高，可擴(kuò)展能力高
時(shí)間復(fù)雜度為O(N)，效率高

(5) 一些例子
1) 匹配字符串

文章插圖
2) 匹配浮點(diǎn)數(shù)

文章插圖
3) 匹配字符

文章插圖
4) 匹配運(yùn)算符

文章插圖
五、詞法分析器的實(shí)現(xiàn)
詞法分析器的詳細(xì)實(shí)現(xiàn)及源碼講解，參見 ***/WGrape/lexer 項(xiàng)目
六、結(jié)束語
【編譯程序中的詞法分析器的輸出是二元組】本文已結(jié)束，感謝閱讀，點(diǎn)擊查看原文