從零寫(xiě)一個(gè)編譯器（七）：語(yǔ)義分析之符號(hào)表的數(shù)據(jù)結(jié)構(gòu)

項(xiàng)目的完整代碼在 C2j-Compiler <https://github.com/dejavudwh/C2j-Compiler>

前言

有關(guān)符號(hào)表的文件都在symboltable包里


前面我們通過(guò)完成一個(gè)LALR(1)有限狀態(tài)自動(dòng)機(jī)和一個(gè)reduce信息來(lái)構(gòu)建了一個(gè)語(yǔ)法解析表，正式完成了C語(yǔ)言的語(yǔ)法解析。接下來(lái)就是進(jìn)入語(yǔ)義分析部分，和在第二篇提到的一樣，語(yǔ)義分析的主要任務(wù)就是生成符號(hào)表來(lái)記錄變量和變量的類型，并且發(fā)現(xiàn)不符合語(yǔ)義的語(yǔ)句

描述變量

在C語(yǔ)言里對(duì)變量聲明定義里，主要有兩種描述

*
說(shuō)明符（Specifier）

說(shuō)明符也就是對(duì)應(yīng)C語(yǔ)言的一些描述變量類型或者像static，extern的關(guān)鍵字（像extern這些關(guān)鍵詞在這次實(shí)現(xiàn)的編譯器里并沒(méi)有用到，因?yàn)閑xtern可能還要涉及到多個(gè)源文件的編譯和鏈接）
*
修飾符（Declarator）


修飾符則是由變量名或者代表指針類型的星號(hào)，數(shù)組的中括號(hào)組成，修飾符屬于可以復(fù)雜的一部分，因?yàn)樾揎椃梢赃M(jìn)行組合。所以對(duì)于組合的修飾符就可以創(chuàng)建多個(gè)Declarator，按順序鏈接起來(lái)

這樣就可以完成兩個(gè)類，這兩個(gè)類的邏輯都比較簡(jiǎn)單：

Declarator類

* declareType：用來(lái)表示當(dāng)前的Declarator是一個(gè)指針還是數(shù)組或者函數(shù)
* numberOfElements、elements：如果當(dāng)前的類型是個(gè)數(shù)組的話，它們就表示數(shù)組的元素個(gè)數(shù)和數(shù)組元素 public class
Declarator { public static int POINTER = 0; public static int ARRAY = 1; public
static int FUNCTION = 2; private int declareType; private int numberOfElements
= 0; HashMap<Integer, Object> elements = null; public Declarator(int type) {
this.declareType = type; } ... }
Specifier類

Specifier的屬性會(huì)比較多一點(diǎn)，但是在后面編譯器可能只支持int, char, void, struct四種類型

*
basicType：用來(lái)表明當(dāng)前變量的類型

*

storageClass：表示變量的存儲(chǔ)方式（fixed，auto），這里我們把typedef的信息也放在這里，也就是說(shuō)如果遇見(jiàn)typedef，那么storageClass會(huì)被設(shè)置為T(mén)YPEDEF

*

constantValue和vStruct：這兩個(gè)屬于比較特殊的兩個(gè)屬性，它們表示枚舉類型和結(jié)構(gòu)體，之所以特殊是因?yàn)樗鼈冎笠M(jìn)行特殊處理。如果遇見(jiàn)枚舉類型相當(dāng)于構(gòu)造一個(gè)basicType是CONSTANT的Specifier，對(duì)應(yīng)的值也就是constantValue了
public class Specifier { /** * Variable types */ public static int NONE = -1;
public static int INT = 0; public static int CHAR = 1; public static int VOID =
2; public static int STRUCTURE = 3; public static int LABEL = 4; /** * storage
*/ public static int FIXED = 0; public static int REGISTER = 1; public static
int AUTO = 2; public static int TYPEDEF = 3; public static int CONSTANT = 4;
public static int NO_OCLASS = 0; public static int PUBLIC = 1; public static
int PRIVATE = 2; public static int EXTERN = 3; public static int COMMON = 4;
private int basicType; private int storageClass; private int outputClass =
NO_OCLASS; private boolean isLong = false; private boolean isSigned = false;
private boolean isStatic = false; private boolean isExternal = false; private
int constantValue = 0; private StructDefine vStruct = null; }
描述符號(hào)表

在前面定義兩個(gè)描述變量的類，但是僅靠這兩個(gè)類還是無(wú)法準(zhǔn)確的表達(dá)一個(gè)符號(hào)，所以我們需要包裝一下這兩個(gè)類，讓它更具表達(dá)力

編程很多時(shí)候都是根據(jù)特定的需求完成特定的數(shù)據(jù)結(jié)構(gòu)，符號(hào)表在計(jì)算機(jī)里本質(zhì)上也只是用來(lái)描述變量的數(shù)據(jù)結(jié)構(gòu)而已

這個(gè)數(shù)據(jù)結(jié)構(gòu)作為符號(hào)表有幾個(gè)基本的條件：

* 速度
因?yàn)榉?hào)表需要頻繁的插入和查找，所以查詢和插入速度必須要足夠的快
* 靈活
因?yàn)樽兞康亩x的可能會(huì)很復(fù)雜，比如說(shuō)多個(gè)修飾符再加上指針（(long int, long doube *)，所以在設(shè)計(jì)上必須足夠靈活
因?yàn)閷W(xué)習(xí)編譯器一直是跟著陳老師的課，所以符號(hào)表的設(shè)計(jì)也沿用老師的設(shè)計(jì)

為了保證上面兩個(gè)條件，我們選用鏈?zhǔn)焦１韥?lái)實(shí)現(xiàn)



這張圖是我網(wǎng)上找的，實(shí)際上沒(méi)有那么復(fù)雜


所有的變量都存儲(chǔ)到這個(gè)哈希表中，同名變量被哈希會(huì)被同一個(gè)地方，當(dāng)然它們要屬于不同作用域，而區(qū)分不同作用域就在于這張圖上面一部分，它會(huì)把同一個(gè)作用域的變量連接起來(lái)

symboltable.Symbol

這個(gè)類用來(lái)描述符號(hào)表里的一個(gè)符號(hào)

如果從github下載源文件的話，里面有許多是在后面代碼生成才需要用到的，現(xiàn)在可以忽略

主要屬性有：

* level: 用來(lái)表明變量的層次
* duplicate：是否是一個(gè)同名變量
* args：如果該符號(hào)對(duì)應(yīng)的是函數(shù)名,那么args指向函數(shù)的輸入?yún)?shù)符號(hào)列表
* next: 指向下一個(gè)同層次的變量符號(hào) public class Symbol { String name; String rname; int
level; boolean duplicate; Symbol args; Symbol next; }
這時(shí)候用Symbol加上之前的Specifier和Declarator就有足夠的表達(dá)力來(lái)描述一個(gè)符號(hào)，那么就需要把這三個(gè)類聯(lián)系起來(lái)，先增加一個(gè)TypeLink

TypeLink

TypeLink表示一個(gè)Specifier或者一個(gè)Declarator，這里用繼承來(lái)實(shí)現(xiàn)可能會(huì)顯得更好看一點(diǎn)
public class TypeLink { public boolean isDeclarator; /** * typedef int */
public boolean isTypeDef; /** * Specifier or Declarator */ public Object
typeObject; private TypeLink next = null; public TypeLink(boolean isDeclarator,
boolean typeDef, Object typeObj) { this.isDeclarator = isDeclarator;
this.isTypeDef = typeDef; this.typeObject = typeObj; } public Object
getTypeObject() { return typeObject; } public TypeLink toNext() { return next;
} public void setNextLink(TypeLink obj) { this.next = obj; } }
這樣在Symbol里就要加入兩個(gè)屬性

typeLinkBegin和typeLinkEnd就是用來(lái)描述變量的說(shuō)明符和修飾符的整個(gè)鏈表，也就是之前說(shuō)的把這些修飾符或者說(shuō)明符按順序連接起來(lái)
public class Symbol { String name; String rname; int level; boolean implicit;
boolean duplicate; Symbol args; Symbol next; TypeLink typeLinkBegin; TypeLink
typeLinkEnd; }
例子

這樣完成之后，例如
long int (*e)[10];
就可以這樣表示

Symbol declartor declartor specifer
name:e declareType = PONITER declareType = array basicType = INT isLong = TRUE
-> -> -> ->
結(jié)構(gòu)體符號(hào)的定義


StructDefine這個(gè)文件還沒(méi)講過(guò)，這個(gè)文件是用來(lái)描述結(jié)構(gòu)體的，因?yàn)榻Y(jié)構(gòu)體本身的復(fù)雜性，所以就需要對(duì)它進(jìn)行特殊處理，但是結(jié)構(gòu)體本質(zhì)上還是一堆變量的組合，所以依舊可以用上面的方法描述

* tag: 結(jié)構(gòu)體的名稱
* level: 結(jié)構(gòu)體的嵌套層次
* Symbol：對(duì)應(yīng)結(jié)構(gòu)體里的變量 public class StructDefine { private String tag; private
int level; private Symbol fields; public StructDefine(String tag, int level,
Symbol fields) { this.tag = tag; this.level = level; this.fields = fields; } }
例子

看一個(gè)結(jié)構(gòu)體定義的例子
struct dejavidwh { int array1[5]; struct dejavudwh *pointer1; } one;


小結(jié)

所以最后只需要
private HashMap<String, ArrayList<Symbol>> symbolTable = new HashMap<>();
private HashMap<String, StructDefine> structTable = new HashMap<>();
就可以描述一個(gè)符號(hào)表


symbolTable里的key相當(dāng)于變量的名字，而后面的ArrayList存放著同名變量，因?yàn)槊總€(gè)Symbol都有一個(gè)next指針來(lái)指向同級(jí)的其它Symbol，所以這樣的結(jié)構(gòu)就相當(dāng)于開(kāi)頭描述的那個(gè)哈希表

這一節(jié)主要是描述了符號(hào)表的數(shù)據(jù)結(jié)構(gòu)，兩個(gè)關(guān)鍵點(diǎn)是

*
描述變量

所以定義了修飾符和描述符來(lái)描述一個(gè)變量

*
關(guān)聯(lián)變量

定義了Symbol鏈表來(lái)串聯(lián)各個(gè)變量

另外我的github博客：https://dejavudwh.cn/ <https://dejavudwh.cn/>

• ? 上一篇：開(kāi)源題材征集 + MVC&EF Core 完整教程小結(jié)
• ? 下一篇：委托和lambda表達(dá)式，Action和Func