1. 前言

“代碼可視化”的概念定義和業(yè)界案例在前文中已經(jīng)進(jìn)行了講述，綜述可閱讀淺析“代碼可視化”，更多相關(guān)知識可查看專欄“代碼可視化”。本文梳理了“代碼可視化”功能開發(fā)需要前置了解的編譯器前端部分知識，因能力有限若有解釋不清和錯誤的地方敬請諒解，如果想更深入正規(guī)的學(xué)習(xí)相關(guān)知識可以查看文后擴(kuò)展閱讀。

2. 編譯器（Compiler）

主要了解前端和中端相關(guān)理論知識，后端部分和目標(biāo)機(jī)器代碼、特定機(jī)器架構(gòu)相關(guān)一般很少用到可視化中。本文主要講述前端部分內(nèi)容，中端部分后面再另寫文章。

圖片

2.1 編譯器工作步驟

圖片

2.2 編譯器前端

2.2.1 詞法分析（Lexical Analysis，or Scanning）

2.2.1.1 理論知識

詞法分析又稱掃描(scanning)，通過讀入組成源程序的字符流，將它們組織成為有意義的詞素(lexeme)的序列。詞素是源程序中的最小語言單位，如關(guān)鍵字、標(biāo)識符、常數(shù)、操作符和分隔符等。對于每個詞素，詞法分析器將產(chǎn)生對應(yīng)的詞法單元(token)作為輸出。

token:<種別碼，屬性值>

圖片

詞法分析器的核心邏輯基于有限自動機(jī)（Finite Automata），可以理解為有限個狀態(tài)的自動執(zhí)行機(jī)器，用來將掃描得到的字符映射到有限個的可能性上。類型包括：

?不確定性有限自動機(jī)（NFA）：在某狀態(tài)和輸入符號下可能存在多個可能的轉(zhuǎn)移狀態(tài)；

?確定性有限自動機(jī)（DFA）：在任何狀態(tài)和輸入符號下都只有一個唯一的轉(zhuǎn)移狀態(tài)。

整個自動構(gòu)造過程見下圖，大致了解一下即可，如果想深入學(xué)習(xí)各種算法細(xì)節(jié)可自行查閱資料。

圖片

2.2.1.2 實踐一下

接下來我們練練手，使用Antlr對Java源碼進(jìn)行詞法分析。Antlr是一個開源工具，支持根據(jù)規(guī)則文件生成詞法分析器和語法分析器，它自身是用 Java 實現(xiàn)的，Mac上可以使用Homebrew安裝或者直接使用idea插件antlr-v4。同時grammars-v4上提供了很多供參考的規(guī)則，我們這里也直接使用其中針對Java8定義的詞法分析規(guī)則練手。

?詞法規(guī)則定義：Java8Lexer.g4

# 截取內(nèi)容
- 關(guān)鍵字定義
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生成詞法分析器并執(zhí)行分析操作

# ① 編譯詞法規(guī)則
antlr Java8Lexer.g4 
# ② 編譯上一步生成的java文件（注意需要把Antlr的JAR文件設(shè)置到CLASSPATH環(huán)境變量，否則會報錯）
javac Java8Lexer.java
# ③ 調(diào)用生成的詞法分析器獲取分析結(jié)果
grun Java8Lexer tokens -tokens ./examples/helloworld.java

圖片

2.2.2 語法分析（Syntactic Analysis, or Parsing）

2.2.2.1 理論知識

語法分析又稱解析（parsing)，它在詞法分析后執(zhí)行。它將tokens組織成語法結(jié)構(gòu)，通常是一棵抽象語法樹（Abstract Syntax Tree, AST），這棵樹表示了源代碼的語法結(jié)構(gòu)。語法分析器需要根據(jù)一組預(yù)定義的語法規(guī)則來分析詞法單元序列。這些規(guī)則通常以上下文無關(guān)文法（Context-Free Grammar, CFG）的形式定義，其中每個規(guī)則定義了語言中的一個結(jié)構(gòu)如何由其他結(jié)構(gòu)組成。

圖片

這里先簡單說一下CFG，如果想深入學(xué)習(xí)可以再查查資料。一個上下文無關(guān)文法由以下四個部分組成：

?非終結(jié)符（Non-terminals）：這些是文法的變量，表示一組字符串的集合。它們通常用大寫字母表示，如A,B,Expr等；

?終結(jié)符（Terminals）：這些是文法的基本符號，它們構(gòu)成了語言的字符串。在編程語言中，終結(jié)符可以是關(guān)鍵字、操作符、標(biāo)識符等。它們通常用小寫字母、數(shù)字或其他符號表示；

?產(chǎn)生式規(guī)則（Production rules）：這些規(guī)則定義了非終結(jié)符如何被終結(jié)符或其他非終結(jié)符的序列替換。規(guī)則的形式通常是A → B C，表示非終結(jié)符A可以被B C替換；

?開始符號（Start symbol）：這是一個特殊的非終結(jié)符，用于表示整個語言或文法的起始點(diǎn)。

-----舉個栗子-------
S → a S b
S → ε
-------解釋--------
·非終結(jié)符是S。
·終結(jié)符是a和b。
·產(chǎn)生式規(guī)則有兩條：S → a S b 表示 S 可以被 a S b 替換，S → ε 表示 S 可以被空字符串替換（ε 表示空字符串）。
·開始符號是S。
這個文法生成的語言是所有a和b的平衡字符串，例如：ab、aabb、aaabbb 等。

語法分析的核心能力是給定文法G和句子s，回答s是否能夠從G推導(dǎo)出來。實現(xiàn)的方式可以大致分為自底向上和自頂向下的語法分析：

?自頂向下語法分析：從樹的頂部（即開始符號）開始構(gòu)建解析樹的過程。在這種方法中，解析器嘗試找出輸入字符串可以從哪個產(chǎn)生式開始，并逐步展開這些產(chǎn)生式，直到獲得完整的輸入字符串。自頂向下解析的特點(diǎn)是直觀、易于實現(xiàn)，尤其是對于簡單的文法。然而，它們可能無法處理左遞歸文法，且對于復(fù)雜的文法可能不夠高效。常見的算法有“遞歸下降解析”和“LL解析”，算法的詳細(xì)過程這里就不分析了，大家可以查查資料或者問一下GPT。

?自底向上語法分析：從樹的底部（即輸入字符串）開始構(gòu)建解析樹的過程。在這種方法中，解析器嘗試找出輸入字符串的哪些部分可以對應(yīng)文法的某個產(chǎn)生式的右側(cè)，并將其規(guī)約為產(chǎn)生式的左側(cè)，逐步減少整體的長度，直到最終規(guī)約為開始符號。自底向上解析通常比自頂向下解析更強(qiáng)大，因為它們可以處理更復(fù)雜的文法，包括那些自頂向下解析器無法處理的文法。然而，它們的解析表通常更為復(fù)雜，且實現(xiàn)起來可能更為困難。常見的算法有“LR解析”。

2.2.2.2 實踐一下

了解了基本概念后我們還是練練手，使用Antlr對Java源碼進(jìn)行語法分析。這次就不使用grammars-v4中定義的語法規(guī)則了，因為編程語言的語法規(guī)則比較復(fù)雜最后生成的AST可讀性比較差。

?語法規(guī)則定義（詞法規(guī)則定義：CommonLexer.g4；語法規(guī)則定義：PlayScript.g4。）

grammar PlayScript;
import CommonLexer;   //導(dǎo)入詞法定義


/*下面的內(nèi)容加到所生成的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生成語法分析器并執(zhí)行分析操作

# ① 編譯語法規(guī)則
antlr PlayScript.g4
# ② 編譯上一步生成的java文件（注意需要把Antlr的JAR文件設(shè)置到CLASSPATH環(huán)境變量，否則會報錯）
javac *.java
# ③ 調(diào)用生成的語法分析器獲取分析結(jié)果（輸入表達(dá)式后使用^D觸發(fā)AST圖生成）
grun antlrtest.PlayScript expression -gui
age + 10 * 2 + 10
^D

圖片

2.2.3 語義分析（Semantic Analyzer）

2.2.3.1 理論知識

語義分析(semantic analyzer)使用語法樹和符號表中的信息來檢查源程序是否和語言定義的語義一致。它同時也收集類型信息，并把這些信息存放在語法樹或符號表中，以便在隨后的中間代碼生成過程中使用。語義規(guī)則一般包括但不限于：

?類型檢查：確保操作數(shù)的類型與操作符兼容，例如不允許將整數(shù)賦值給字符串類型的變量；

?變量綁定：確保變量和函數(shù)的聲明與使用匹配，變量在使用前已被聲明，函數(shù)調(diào)用時參數(shù)的數(shù)量和類型與聲明相符；

?控制流檢查：確保程序中的控制流語句（如循環(huán)和條件語句）的使用是合法的；

?唯一性檢查：確保標(biāo)識符的聲明在同一作用域內(nèi)是唯一的，例如不允許在同一作用域內(nèi)聲明兩個相同名稱的變量；

?權(quán)限和可訪問性檢查：確保對變量和函數(shù)的訪問符合其聲明的權(quán)限，例如私有成員只能在其類內(nèi)部被訪問。

由于每種語言都有其獨(dú)特的語義規(guī)則和特性，例如類型系統(tǒng)、作用域規(guī)則、合法的操作符重載等都是語言特定的。因此，語義分析必須針對每種語言的規(guī)范來設(shè)計。

2.2.3.2 實踐一下

由于不同語言的語義分析實現(xiàn)差異較大，沒有通用的語義分析器生成工具。因此我們直接來閱讀一下Java編譯器中的相關(guān)源碼，了解一下實現(xiàn)邏輯。
javac中語義分析的源碼位于com.sun.tools.javac.code和com.sun.tools.javac.comp包中。

圖片

以下列舉了一些語義分析的類，源碼就不貼了，可以在langtools下載閱讀：

?Symbol：表示所有的語言符號，包括變量、方法、類等。這些符號在編譯過程中被創(chuàng)建并填充到符號表中；

?Scope：用于管理作用域，它保存了一個作用域內(nèi)所有的符號。這對于解析變量名和方法名非常重要，以確保它們在當(dāng)前上下文中是可見的和有效的；

?Type：代表Java語言中的所有類型，包括基本類型、類和接口類型、數(shù)組類型等。javac在類型檢查過程中使用這個類來確定類型兼容性和執(zhí)行類型轉(zhuǎn)換；

?Attr：進(jìn)行屬性分析的核心類，它負(fù)責(zé)將類型信息和其他屬性關(guān)聯(lián)到語法樹的節(jié)點(diǎn)上。它執(zhí)行類型檢查、方法解析和變量捕獲等任務(wù)；

?Check：用于執(zhí)行各種語義檢查，例如檢查類型是否存在循環(huán)繼承，或者一個類是否實現(xiàn)了其接口的所有方法；

?Resolve：用于解析方法調(diào)用、類型名和變量名。它在符號表中查找正確的符號，并處理如方法重載解析等復(fù)雜情況；

?Annotate：處理注解相關(guān)的語義分析，包括注解的解析和應(yīng)用；

?Types：提供了一組用于類型操作的實用方法，如確定一個類型是否可以賦值給另一個類型，或者查找最近公共祖先類型等；

?Flow: 負(fù)責(zé)進(jìn)行控制流分析，比如檢查變量在使用前是否已經(jīng)被賦值，或者方法是否總是有返回值；

?LambdaToMethod：Java 8 引入了 Lambda 表達(dá)式，這個類負(fù)責(zé)將 Lambda 表達(dá)式轉(zhuǎn)換為匿名類或靜態(tài)方法；

?TransTypes和Lower: 這些類負(fù)責(zé)某些類型轉(zhuǎn)換，包括泛型的橋接方法和自動裝箱/拆箱。