從零寫一個編譯器（七）：語義分析之符號表的數據結構

• 2019 年 10 月 3 日
• 筆記

項目的完整程式碼在 C2j-Compiler

前言

有關符號表的文件都在symboltable包里

前面我們通過完成一個LALR(1)有限狀態自動機和一個reduce資訊來構建了一個語法解析表，正式完成了C語言的語法解析。接下來就是進入語義分析部分，和在第二篇提到的一樣，語義分析的主要任務就是生成符號表來記錄變數和變數的類型，並且發現不符合語義的語句

描述變數

在C語言里對變數聲明定義里，主要有兩種描述

• 說明符（Specifier）

  說明符也就是對應C語言的一些描述變數類型或者像static，extern的關鍵字（像extern這些關鍵詞在這次實現的編譯器里並沒有用到，因為extern可能還要涉及到多個源文件的編譯和鏈接）

• 修飾符（Declarator）

  修飾符則是由變數名或者代表指針類型的星號，數組的中括弧組成，修飾符屬於可以複雜的一部分，因為修飾符可以進行組合。所以對於組合的修飾符就可以創建多個Declarator，按順序鏈接起來

這樣就可以完成兩個類，這兩個類的邏輯都比較簡單：

Declarator類

• declareType：用來表示當前的Declarator是一個指針還是數組或者函數
• numberOfElements、elements：如果當前的類型是個數組的話，它們就表示數組的元素個數和數組元素

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的屬性會比較多一點，但是在後面編譯器可能只支援int, char, void, struct四種類型

• basicType：用來表明當前變數的類型

• storageClass：表示變數的存儲方式（fixed，auto），這裡我們把typedef的資訊也放在這裡，也就是說如果遇見typedef，那麼storageClass會被設置為TYPEDEF

• constantValue和vStruct：這兩個屬於比較特殊的兩個屬性，它們表示枚舉類型和結構體，之所以特殊是因為它們之後要進行特殊處理。如果遇見枚舉類型相當於構造一個basicType是CONSTANT的Specifier，對應的值也就是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;  }

描述符號表

在前面定義兩個描述變數的類，但是僅靠這兩個類還是無法準確的表達一個符號，所以我們需要包裝一下這兩個類，讓它更具表達力

編程很多時候都是根據特定的需求完成特定的數據結構，符號表在電腦里本質上也只是用來描述變數的數據結構而已

這個數據結構作為符號表有幾個基本的條件：

1. 速度
   因為符號表需要頻繁的插入和查找，所以查詢和插入速度必須要足夠的快
2. 靈活
   因為變數的定義的可能會很複雜，比如說多個修飾符再加上指針（(long int, long doube *)，所以在設計上必須足夠靈活

因為學習編譯器一直是跟著陳老師的課，所以符號表的設計也沿用老師的設計

為了保證上面兩個條件，我們選用鏈式哈希表來實現

這張圖是我網上找的，實際上沒有那麼複雜

所有的變數都存儲到這個哈希表中，同名變數被哈希會被同一個地方，當然它們要屬於不同作用域，而區分不同作用域就在於這張圖上面一部分，它會把同一個作用域的變數連接起來

symboltable.Symbol

這個類用來描述符號表裡的一個符號

如果從github下載源文件的話，裡面有許多是在後面程式碼生成才需要用到的，現在可以忽略

主要屬性有：

• level: 用來表明變數的層次
• duplicate：是否是一個同名變數
• args：如果該符號對應的是函數名,那麼args指向函數的輸入參數符號列表
• next: 指向下一個同層次的變數符號

public class Symbol {      String name;      String rname;      int level;      boolean duplicate;      Symbol args;      Symbol next;  }

這時候用Symbol加上之前的Specifier和Declarator就有足夠的表達力來描述一個符號，那麼就需要把這三個類聯繫起來，先增加一個TypeLink

TypeLink

TypeLink表示一個Specifier或者一個Declarator，這裡用繼承來實現可能會顯得更好看一點

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里就要加入兩個屬性

typeLinkBegin和typeLinkEnd就是用來描述變數的說明符和修飾符的整個鏈表，也就是之前說的把這些修飾符或者說明符按順序連接起來

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];

就可以這樣表示

結構體符號的定義

StructDefine這個文件還沒講過，這個文件是用來描述結構體的，因為結構體本身的複雜性，所以就需要對它進行特殊處理，但是結構體本質上還是一堆變數的組合，所以依舊可以用上面的方法描述

• tag: 結構體的名稱
• level: 結構體的嵌套層次
• Symbol：對應結構體里的變數

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;      }  }

例子

看一個結構體定義的例子

struct dejavidwh {      int array1[5];      struct dejavudwh *pointer1;  } one;

小結

所以最後只需要

private HashMap<String, ArrayList<Symbol>> symbolTable = new HashMap<>();      private HashMap<String, StructDefine> structTable = new HashMap<>();

就可以描述一個符號表

symbolTable里的key相當於變數的名字，而後面的ArrayList存放著同名變數，因為每個Symbol都有一個next指針來指向同級的其它Symbol，所以這樣的結構就相當於開頭描述的那個哈希表

這一節主要是描述了符號表的數據結構，兩個關鍵點是

1. 描述變數

   所以定義了修飾符和描述符來描述一個變數

2. 關聯變數

   定義了Symbol鏈表來串聯各個變數

另外我的github部落格：https://dejavudwh.cn/