1. 前言

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

2. 編譯器（Compiler）

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

圖片

2.1 編譯器工作步驟

圖片

2.2 編譯器前端

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

2.2.1.1 理論知識(shí)

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

token:<種別碼，屬性值>

圖片

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

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

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

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

圖片

2.2.1.2 實(shí)踐一下

接下來(lái)我們練練手，使用Antlr對(duì)Java源碼進(jìn)行詞法分析。Antlr是一個(gè)開(kāi)源工具，支持根據(jù)規(guī)則文件生成詞法分析器和語(yǔ)法分析器，它自身是用 Java 實(shí)現(xiàn)的，Mac上可以使用Homebrew安裝或者直接使用idea插件antlr-v4。同時(shí)grammars-v4上提供了很多供參考的規(guī)則，我們這里也直接使用其中針對(duì)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)境變量，否則會(huì)報(bào)錯(cuò)）
javac Java8Lexer.java
# ③ 調(diào)用生成的詞法分析器獲取分析結(jié)果
grun Java8Lexer tokens -tokens ./examples/helloworld.java

圖片

2.2.2 語(yǔ)法分析（Syntactic Analysis, or Parsing）

2.2.2.1 理論知識(shí)

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

圖片

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

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

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

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

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

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

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

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

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

2.2.2.2 實(shí)踐一下

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

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

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


/*下面的內(nèi)容加到所生成的Java源文件的頭部，如包名稱，import語(yǔ)句等。*/
@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生成語(yǔ)法分析器并執(zhí)行分析操作

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

圖片

2.2.3 語(yǔ)義分析（Semantic Analyzer）

2.2.3.1 理論知識(shí)

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

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

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

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

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

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

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

2.2.3.2 實(shí)踐一下

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

圖片

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

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

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

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

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

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

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

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

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

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

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

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