1. 首頁 > 生活百科 > >

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

生活經驗編譯程序

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

All problems in computer science can be solved by another level of indirection. —— David John Wheeler
所以為了降低編譯器工程的復雜性，提高發展效率 ， 一般把編譯器分為兩個完全解耦的兩個部分
  • 編譯器前端 ：只負責理解代碼，不考慮各種CPU指令不兼容等問題
  • 編譯器后端 ：只負責生成可執行文件，不考慮各種語言特性
為了讓兩個部分可以連接在一起工作，所以必然存在一個部分的輸出是另一部分的輸入，很明顯，編譯器前端的輸出，就是編譯器后端的輸入 。
這樣，兩個部分只需要約定好數據格式，就可以大幅度提高編譯器的發展效率，編譯器整個工作流程也變得非常簡單清晰了，如下圖所示，如果對圖中的編譯器前端不理解沒關系，接下來的 第二節《編譯器前端的原理》 會對這部分進行講解
編譯程序中的詞法分析器的輸出是二元組

文章插圖
結論 ：所以編譯器前端就是編譯器中的前端部分，負責理解代碼并生成中間語言
二、編譯器前端的原理
既然編譯器前端的工作是理解代碼，那么它的原理是什么呢 ， 首先看下面一段簡單的C語言代碼
int age = 18;復制代碼從人類閱讀代碼的角度來看，我們是如何理解上述代碼的呢
1、局部理解
  1. 看到 int 關鍵字
  2. 看到 age 標識符
  3. 看到 = 賦值符號
  4. 看到 18 字面量數值
  5. 看到 ; 結束符
局部理解的過程，就是詞法分析的過程
2、全局理解
通過聯系孤立的、局部的理解結果 ， 可得到一個整體 int age = 18 ; ， 對其在腦海中進行全局理解后，發現它符合C語言的整型賦值語法
整型賦值語法 -> 關鍵字 標識符 賦值符號 字面量關鍵字 -> int | long標識符 -> [a-zA-Z_]+[a-zA-Z+_*0-9]*字面量 ->[0-9]+復制代碼所以通過全局理解，最終可知道上面代碼是一個整型的賦值語句
全局理解的過程，就是語法分析的過程
3、總結
結合人類理解代碼的過程，編譯器前端主要可以分為局部理解和全局理解兩個步驟，其中
  • 局部理解會生成一個一個的理解結果，稱為Token
  • 全局理解會把孤立的token聯系成為一個整體，進行語法規則匹配，如果符合語法則理解成功，否則理解失敗
三、詞法分析器的介紹
詞法分析器就是在做對字符序列的局部理解，每完成一次局部理解，就生成一個Token 。常見的Token包括操作符、符號、空白符、關鍵字、標識符、數字、浮點數、字符串、字符等 。
所以詞法分析器的工作內容也比較簡單，只要能把輸入的字符序列，生成一個有序的token列表即可 。
四、詞法分析器的原理
1、直接掃描法
直接掃描法的思路類似二重循環的暴力法，每一輪的掃描都是如下過程
  • 先第一層的掃描，根據第一個字符判斷屬于哪種類型的token
  • 進入第二層的掃描，向后依次讀?。?直到讀出一個完整的token為止，跳出第二層循環
  • 繼續開始第一層的掃描
(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; }}復制代碼(2) 缺點
  • 邏輯非常復雜
  • 可能存在回溯情況，可能需要記憶已匹配的前N個字符，效率低
  • 大量IF判斷 ， 可維護性差，擴展性差
2、DFA法
DFA即deterministic finite automaton有限狀態自動機 ， 其特點是可以實現狀態的自動轉移，可以用于解決字符匹配問題
(1) 核心構成
DFA的核心構成要素是狀態和狀態的轉移
  • 定義自動機所具備的N種狀態，并定義初始狀態
  • 定義上一個狀態轉移至下一個狀態的條件

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

文章插圖
(2) 應用實踐
如何用DFA實現詞法分析器呢，步驟如下
  • 先定義不同的狀態 ：如操作符狀態、數字狀態、符號狀態等
  • 再定義狀態轉移條件 ：如當前狀態是初始狀態 ， 遇到數字則轉移至數字狀態 ， 遇到符號則轉移至符號狀態
  • 如果字符讀取完成，則整個轉移過程結束
(3) 偽代碼
let state = 0; // 當前狀態, 也是初始狀態while ((ch = nextChar()) !== false) { let match = false; // 獲取下一個狀態, 如果下一個狀態不是初始狀態, 則說明匹配成功 let nextState = getNextState(ch, state); if (nextState) { match = true; } // 如果匹配成功, 則字符讀取序列的下標+1，并轉移至下一個狀態 if (match) { incrSeq(); flowtoNextState(ch, nextState); } else { // 不匹配則生成token，并轉移至初始狀態，開始重新匹配 produceToken(); flowtoResetState(); }}復制代碼(4) 優點
  • 邏輯清晰簡單
  • 可維護性高 ， 可擴展能力高
  • 時間復雜度為O(N)，效率高
(5) 一些例子
1) 匹配字符串
編譯程序中的詞法分析器的輸出是二元組

文章插圖
2) 匹配浮點數
編譯程序中的詞法分析器的輸出是二元組

文章插圖
3) 匹配字符
編譯程序中的詞法分析器的輸出是二元組

文章插圖
4) 匹配運算符
編譯程序中的詞法分析器的輸出是二元組

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