實現“代碼可視化”需要了解的前置知識-編譯器前端
1. 前言
“代碼可視化”的概念定義和業界案例在前文中已經進行了講述，綜述可閱讀淺析“代碼可視化”，更多相關知識可查看專欄“代碼可視化”。本文梳理了“代碼可視化”功能開發需要前置了解的編譯器前端部分知識，因能力有限若有解釋不清和錯誤的地方敬請諒解，如果想更深入正規的學習相關知識可以查看文后擴展閱讀。
2. 編譯器（Compiler）
主要了解前端和中端相關理論知識，后端部分和目標機器代碼、特定機器架構相關一般很少用到可視化中。本文主要講述前端部分內容，中端部分后面再另寫文章。
圖片
2.1 編譯器工作步驟
圖片
2.2 編譯器前端
2.2.1 詞法分析（Lexical Analysis，or Scanning）
2.2.1.1 理論知識
詞法分析又稱掃描(scanning)，通過讀入組成源程序的字符流，將它們組織成為有意義的詞素(lexeme)的序列。詞素是源程序中的最小語言單位，如關鍵字、標識符、常數、操作符和分隔符等。對于每個詞素，詞法分析器將產生對應的詞法單元(token)作為輸出。
token:<種別碼，屬性值>
圖片
詞法分析器的核心邏輯基于有限自動機（Finite Automata），可以理解為有限個狀態的自動執行機器，用來將掃描得到的字符映射到有限個的可能性上。類型包括：
?不確定性有限自動機（NFA）：在某狀態和輸入符號下可能存在多個可能的轉移狀態；
?確定性有限自動機（DFA）：在任何狀態和輸入符號下都只有一個唯一的轉移狀態。
整個自動構造過程見下圖，大致了解一下即可，如果想深入學習各種算法細節可自行查閱資料。
圖片
2.2.1.2 實踐一下
接下來我們練練手，使用Antlr對Java源碼進行詞法分析。Antlr是一個開源工具，支持根據規則文件生成詞法分析器和語法分析器，它自身是用 Java 實現的，Mac上可以使用Homebrew安裝或者直接使用idea插件antlr-v4。同時grammars-v4上提供了很多供參考的規則，我們這里也直接使用其中針對Java8定義的詞法分析規則練手。
?詞法規則定義：Java8Lexer.g4
# 截取內容
- 關鍵字定義
ABSTRACT : 'abstract';
ASSERT : 'assert';
BOOLEAN : 'boolean';
BREAK : 'break';
BYTE : 'byte';
CASE : 'case';
CATCH : 'catch';
CHAR : 'char';
...
- 字符串字面量定義
StringLiteral: '"' StringCharacters? '"';
fragment StringCharacters: StringCharacter+;
fragment StringCharacter: ~["\\\r\n] | EscapeSequence;
...?待解析的Java代碼
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World");
}
}?使用Antlr生成詞法分析器并執行分析操作
# ① 編譯詞法規則
antlr Java8Lexer.g4
# ② 編譯上一步生成的java文件（注意需要把Antlr的JAR文件設置到CLASSPATH環境變量，否則會報錯）
javac Java8Lexer.java
# ③ 調用生成的詞法分析器獲取分析結果
grun Java8Lexer tokens -tokens ./examples/helloworld.java
圖片
2.2.2 語法分析（Syntactic Analysis, or Parsing）
2.2.2.1 理論知識
語法分析又稱解析（parsing)，它在詞法分析后執行。它將tokens組織成語法結構，通常是一棵抽象語法樹（Abstract Syntax Tree, AST），這棵樹表示了源代碼的語法結構。語法分析器需要根據一組預定義的語法規則來分析詞法單元序列。這些規則通常以上下文無關文法（Context-Free Grammar, CFG）的形式定義，其中每個規則定義了語言中的一個結構如何由其他結構組成。
圖片
這里先簡單說一下CFG，如果想深入學習可以再查查資料。一個上下文無關文法由以下四個部分組成：
?非終結符（Non-terminals）：這些是文法的變量，表示一組字符串的集合。它們通常用大寫字母表示，如A,B,Expr等；
?終結符（Terminals）：這些是文法的基本符號，它們構成了語言的字符串。在編程語言中，終結符可以是關鍵字、操作符、標識符等。它們通常用小寫字母、數字或其他符號表示；
?產生式規則（Production rules）：這些規則定義了非終結符如何被終結符或其他非終結符的序列替換。規則的形式通常是A → B C，表示非終結符A可以被B C替換；
?開始符號（Start symbol）：這是一個特殊的非終結符，用于表示整個語言或文法的起始點。
-----舉個栗子-------
S → a S b
S → ε
-------解釋--------
·非終結符是S。
·終結符是a和b。
·產生式規則有兩條：S → a S b 表示 S 可以被 a S b 替換，S → ε 表示 S 可以被空字符串替換（ε 表示空字符串）。
·開始符號是S。
這個文法生成的語言是所有a和b的平衡字符串，例如：ab、aabb、aaabbb 等。語法分析的核心能力是給定文法G和句子s，回答s是否能夠從G推導出來。實現的方式可以大致分為自底向上和自頂向下的語法分析：
?自頂向下語法分析：從樹的頂部（即開始符號）開始構建解析樹的過程。在這種方法中，解析器嘗試找出輸入字符串可以從哪個產生式開始，并逐步展開這些產生式，直到獲得完整的輸入字符串。自頂向下解析的特點是直觀、易于實現，尤其是對于簡單的文法。然而，它們可能無法處理左遞歸文法，且對于復雜的文法可能不夠高效。常見的算法有“遞歸下降解析”和“LL解析”，算法的詳細過程這里就不分析了，大家可以查查資料或者問一下GPT。
?自底向上語法分析：從樹的底部（即輸入字符串）開始構建解析樹的過程。在這種方法中，解析器嘗試找出輸入字符串的哪些部分可以對應文法的某個產生式的右側，并將其規約為產生式的左側，逐步減少整體的長度，直到最終規約為開始符號。自底向上解析通常比自頂向下解析更強大，因為它們可以處理更復雜的文法，包括那些自頂向下解析器無法處理的文法。然而，它們的解析表通常更為復雜，且實現起來可能更為困難。常見的算法有“LR解析”。
2.2.2.2 實踐一下
了解了基本概念后我們還是練練手，使用Antlr對Java源碼進行語法分析。這次就不使用grammars-v4中定義的語法規則了，因為編程語言的語法規則比較復雜最后生成的AST可讀性比較差。
?語法規則定義（詞法規則定義：CommonLexer.g4；語法規則定義：PlayScript.g4。）
grammar PlayScript;
import CommonLexer; //導入詞法定義
/*下面的內容加到所生成的Java源文件的頭部，如包名稱，import語句等。*/
@header {
package antlrtest;
}
expression
: assignmentExpression
| expression ',' assignmentExpression
;
assignmentExpression
: additiveExpression
| Identifier assignmentOperator additiveExpression
;
assignmentOperator
: '='
| '*='
| '/='
| '%='
| '+='
| '-='
;
additiveExpression
: multiplicativeExpression
| additiveExpression '+' multiplicativeExpression
| additiveExpression '-' multiplicativeExpression
;
multiplicativeExpression
: primaryExpression
| multiplicativeExpression '*' primaryExpression
| multiplicativeExpression '/' primaryExpression
| multiplicativeExpression '%' primaryExpression
;?使用Antlr生成語法分析器并執行分析操作
# ① 編譯語法規則
antlr PlayScript.g4
# ② 編譯上一步生成的java文件（注意需要把Antlr的JAR文件設置到CLASSPATH環境變量，否則會報錯）
javac *.java
# ③ 調用生成的語法分析器獲取分析結果（輸入表達式后使用^D觸發AST圖生成）
grun antlrtest.PlayScript expression -gui
age + 10 * 2 + 10
^D
圖片
2.2.3 語義分析（Semantic Analyzer）
2.2.3.1 理論知識
語義分析(semantic analyzer)使用語法樹和符號表中的信息來檢查源程序是否和語言定義的語義一致。它同時也收集類型信息，并把這些信息存放在語法樹或符號表中，以便在隨后的中間代碼生成過程中使用。語義規則一般包括但不限于：
?類型檢查：確保操作數的類型與操作符兼容，例如不允許將整數賦值給字符串類型的變量；
?變量綁定：確保變量和函數的聲明與使用匹配，變量在使用前已被聲明，函數調用時參數的數量和類型與聲明相符；
?控制流檢查：確保程序中的控制流語句（如循環和條件語句）的使用是合法的；
?唯一性檢查：確保標識符的聲明在同一作用域內是唯一的，例如不允許在同一作用域內聲明兩個相同名稱的變量；
?權限和可訪問性檢查：確保對變量和函數的訪問符合其聲明的權限，例如私有成員只能在其類內部被訪問。
由于每種語言都有其獨特的語義規則和特性，例如類型系統、作用域規則、合法的操作符重載等都是語言特定的。因此，語義分析必須針對每種語言的規范來設計。
2.2.3.2 實踐一下
由于不同語言的語義分析實現差異較大，沒有通用的語義分析器生成工具。因此我們直接來閱讀一下Java編譯器中的相關源碼，了解一下實現邏輯。
javac中語義分析的源碼位于com.sun.tools.javac.code和com.sun.tools.javac.comp包中。
圖片
以下列舉了一些語義分析的類，源碼就不貼了，可以在langtools下載閱讀：
?Symbol：表示所有的語言符號，包括變量、方法、類等。這些符號在編譯過程中被創建并填充到符號表中；
?Scope：用于管理作用域，它保存了一個作用域內所有的符號。這對于解析變量名和方法名非常重要，以確保它們在當前上下文中是可見的和有效的；
?Type：代表Java語言中的所有類型，包括基本類型、類和接口類型、數組類型等。javac在類型檢查過程中使用這個類來確定類型兼容性和執行類型轉換；
?Attr：進行屬性分析的核心類，它負責將類型信息和其他屬性關聯到語法樹的節點上。它執行類型檢查、方法解析和變量捕獲等任務；
?Check：用于執行各種語義檢查，例如檢查類型是否存在循環繼承，或者一個類是否實現了其接口的所有方法；
?Resolve：用于解析方法調用、類型名和變量名。它在符號表中查找正確的符號，并處理如方法重載解析等復雜情況；
?Annotate：處理注解相關的語義分析，包括注解的解析和應用；
?Types：提供了一組用于類型操作的實用方法，如確定一個類型是否可以賦值給另一個類型，或者查找最近公共祖先類型等；
?Flow: 負責進行控制流分析，比如檢查變量在使用前是否已經被賦值，或者方法是否總是有返回值；
?LambdaToMethod：Java 8 引入了 Lambda 表達式，這個類負責將 Lambda 表達式轉換為匿名類或靜態方法；
?TransTypes和Lower: 這些類負責某些類型轉換，包括泛型的橋接方法和自動裝箱/拆箱。
