從0實作JVM語言之語意分析-Semantic

原始碼github, 如果這個系列文章對您有幫助, 希望獲得您的一個star

本節相關語意分析package地址

致親愛的讀者:

    個人的文字組織和寫文章的功除錯實一般, 寫的也比較趕時間, 所以系列文章的文字可能比較粗糙,
難免有詞不達意或者寫的很迷惑抽象的地方 

    如果您看了有疑問或者覺得我寫的實在亂七八糟, 這個很抱歉, 確實是我的問題, 您如果有不懂的地方
的地方或者發現我的錯誤(文字錯誤, 邏輯錯誤或者知識點錯誤都有可能), 可以直接留言, 我看到都會回復您!

系列食用方法建議

    由于時間原因, 目前測驗并不完善, 所以推薦如下方式根據您的目的進行閱讀

    如果您是學習用, 建議您先將整個專案clone到本地, 然后把感興趣的章節洗掉, 自己重寫對照著重寫
    書寫完每一步測驗一下能否正常運行(在指定的路徑去讀取原始碼測驗能否編譯成功并在命令列執行

    java Application(類名)

嘗試能否輸出期望結果, 我沒有研究Junit對編譯器輸出class檔案進行測驗, 所以目前可能需要您手動測驗)

    按照以上步驟, 等您將所有模塊重寫一遍, 大概也對這個系列的脈絡有深刻理解了! 如果您重頭開始重寫, 
往往可能由于出現某些低級錯誤導致長時間debug才找得到錯誤, 所以對于初學者, 推薦采用自己補寫替換模塊的
方式

    對于希望貢獻代碼的朋友或者對Cva感興趣的朋友, 歡迎貢獻您的原始碼與見解, 或者對于該系列一些錯誤/
bug愿意提出指正的朋友, 您可以留言或者在github發issue, 我看到后一定及時處理!

語意分析器作業基于語法分析器輸出的抽象語法樹, 通過對該語法樹的分析做進一步的檢查,
回答我們, 也回答代碼生成器最后一個問題:源程式是否符合語意規則. 如果確實存在問題,
那么這段代碼即使翻譯成機器碼(在這里是我們后面要生成的JVM匯編指令), 也不可能執行成功,
必然收到JVM的拒絕執行(讀者可以自己嘗試瞎寫命令然后用jasmin匯編成位元組碼, 看報錯反應, 哈哈),
或者造成一些意想不到的問題, 因此語意分析有問題勢必造成后面的錯誤, 所以語意分析旨在搜集
代碼出現的邏輯錯誤(多數是型別檢查的型別問題), 并指出, 以讓接下來的步驟能正常進行

在這個階段要給出盡可能準確的報錯資訊, 供用戶參考并修改源代碼.
語意分析中最重要的作業便是型別檢查, 此外還會有一些其他的檢查, 例如變數在使用前是否宣告等.

語意分析實作

符號表

語意分析的正常進行少不了符號表的參與. 所謂符號, 程式中的變數、方法、欄位、類都是符號.
符號表存盤了程式中的符號的相關資訊, 這些資訊包括型別、作用域、訪問控制資訊等等, 而且符號表必須非常高效,
因為程式中符號的規模會非常大. 我們的符號表都是采用HashMap, JVM針對HashMap的優化可謂是比較極致,
我們的JDK8后引入了紅黑樹, 對于Map, HotSpot會傾向于將其編譯成本地代碼, 在一些情況下,
其運行效率甚至超過一般的手寫分支判斷

我們的哈希表以符號名字為鍵, 以符號的相關資訊為值, 建立映射.
并按照樹形結構, 組織各個作用域的符號及資訊, 建立全域符號表.

全域符號表的大致結構如下：

// TODO: 樹形圖

+ ClassMap
  + ClassBinding
    + BaseClass
    + FieldMap
      + Field
      + ...
    + MethodMap
      + Method
      + ...
  + ...

+ MethodVariableMap

+ ClassMap

  全域符號表的入口, 直接維護了類名和類的相關資訊的

+ ClassBinding

  存盤了類的相關資訊, 包括父類, 欄位表, 方法表. 其中欄位表和方法表是以名為鍵的映射. 

+ Field

  存盤了欄位的宣告型別

+ Method

  存盤了方法的相關資訊, 包括宣告的回傳型別, 引數的個數及各自型別. 

+ MethodVariableMap

  引數和本地變數表, 是名字和型別的映射. 當分析某個方法的時候, 對于該方法的引數和本地變數的訪問是相當頻繁的,
 因此將他們單獨存盤到某個位置, 分析完畢即銷毀, 優化空間的占用. 

分析思路

本質上說, 所謂“分析”僅僅是語法樹的遍歷而已, 只是附帶上了附加條件, 要求某子樹符合某個要求. 此外我們應當注意到,
型別的宣告、欄位的宣告和方法的宣告, 并沒有任何值得語意分析的地方, 真正值得我們去分析和檢查的是陳述句和運算式,
查看它們是否合法. 因此, 分析程序可簡要分成兩步.

1. 資訊收集和索引

   對當前語法樹的前幾層進行遍歷, 掃描并存盤類資訊, 各自的欄位和方法相關資訊, 構建全域隨時可用的“全域符號表”,
   該程序僅在語意分析實際進行之前進行一次.

2. 語意分析和檢查

   收集要分析的方法的引數和變數資訊, 然后順序遍歷方法的每一條陳述句和運算式. 如果找到錯誤, 那么就輸出一條資訊,
   提示用戶在某位置發現何種型別的錯誤, 并盡可能進行恢復, 繼續檢查下文, 在一趟分析中給出盡可能多的錯誤資訊.

對于每個方法, 都執行一遍步驟2, 直到所有的方法都分析過. 如果未發現任何錯誤, 那么進入下一階段, 如果發現問題,
那么在給出所有資訊后, 退出編譯程序.

分析程序

型別檢查

型別檢查是語意分析的重點所在, 如果此處的檢查沒有通過, 那么這個程式必定存在問題, 必定不能運行.
下面通過幾個例子來展示型別檢查的作業細節.

運算式

對于運算式而言, 型別檢查主要分為以下幾類

• 運算子

  對于單目運算子邏輯非 !主要檢測其運算元是否是前端boolean
  (只有前端用戶才會看到boolean, 在編譯器后端boolean會被處理為int),
  對于雙目運算子如+ - * /型別檢查的步驟是:

  先確認兩側/單側的運算式型別, 然后確認兩側運算式型別是否匹配,
  最后確認當前的運算子能否對該型別進行操作全部沒有問題的話, 才認為該運算式通過了檢查,
  并確認該運算式的值型別(在代碼中運算式的結果值直接取雙目運算子的左邊)
  (在這里, 我們前面的toEnum()方法就派上了用場)

  錯誤語法例子如:

  • 10 + true

    顯然 + 兩側型別不匹配, 型別檢查的給出的資訊是,

    Cva日后將遵循JVM規范, 基本運算可以是范圍小于 int 的整形, 做運算時都強轉為 int
    如 byte char short 型別轉為運算元都視為 int, 編譯器不報錯

    Error: Line 1 Add Expr ression: the type of left is @int, but the type of right is @boolean

  • true < false

    兩側型別是一致的, 但很顯然, 這個比較沒有任何意義, 因此這個運算式也是個錯誤

    Error: Line 1 only numeric can be compared.

  • !200

    只有布林值才能取邏輯非, 因此這個運算式顯然也是非法的

    Error: Line 1 the Expr r cannot calculate to a boolean.

• 方法呼叫

  Cva目前僅支持實體方法呼叫, 暫不支持靜態方法、方法多載等.

  對于方法呼叫運算式, 型別檢查主要關注形參及實參.
  首先確認形參和實引數量是相等的, 然后確認引數的型別是一一對應的.
  通過檢查后, 運算式的值型別被設定成為該方法的回傳值型別.

  假定本類中有有方法 int compute(int a, int b), 對它的兩種錯誤呼叫如下

  • this.compute(10)

    顯然, 這并不能通過第一步: 對于引數個數的檢查

    Error: Line 1 the count of arguments is not match.

  • this.compute(10, false)

    顯然, 第二個引數的型別不是匹配的

    Error: Line 32 the parameter 2 needs a int, but got a boolean

  • println(Expr expr)

    應當注意到, 在本程式中我們認為write(控制臺寫操作, println, echo, printf)是一個陳述句,
    (內置方法關鍵字)而不是函式呼叫運算式. 這樣做的目的是為了簡化該編譯器開發,
    但其本質依舊是函式呼叫, 因此對于它的型別檢查等同函式呼叫. 寫操作應檢查引數是否為string 或者基本型別,
    因此Expr expr最終應當能求得一個string 或者 整形(目前, 以后完善boolean和浮點數情形

• 回傳運算式

  這里是確認方法宣告處的回傳型別和實際的回傳型別是匹配的. 首先檢查 return 關鍵字后緊跟的運算式是否有意義,
  然后再確認這個有意義的運算式是否符合回傳型別. 考慮這樣的一個源程式：

  boolean doSomething()
  {
      // Some VarDecls
      // Some Statements
      return 666;
  }
  

  很明顯, 實際回傳型別和宣告的回傳型別不一致, 我們應當給出相應的錯誤提示
  此外, 在Cva中, void回傳型別的方法, 我們允許不顯式return, 也可以在方法結束時 使用return; 陳述句

  Error: Line 3 the return Expr ression's type is not match the method "DoSomething" declared.

• 識別符號 / 字面量 / this / new cvaIdentifierExpr r()

  這里是討論剩余的幾類特殊的運算式, 變數/欄位參考, 字面量, this關鍵字, 實體化物件運算式.

  • 識別符號

    查找識別符號大致分為兩步, 首先在引數串列/本地變數表查找該識別符號, 若查找失敗, 再去類/基類欄位宣告串列中嘗試查找.
    若最終查找失敗, 則報一個錯.

    Error: Line 1 you should declare "x" before use it.

  • 字面量 / this

    這個種類主要包括常量(數字整形字面量, true ,false), this關鍵字. 應當特別注意this關鍵字,
    它指代當前類的實體, 它的型別自然是該關鍵字所處的類的型別.

  • new cvaIdentifierExpr r()

    應當注意到本程式不支持建構式, 因此每個類只有一個形式上的無參構造器. 除主類外,
    對于其他普通類的宣告順序不做要求. 如果嘗試實體化一個不存在的類, 也會報告錯誤.

    `Error: Line 1 cannot find the declaration of class "XXX".`
    

陳述句

有了前面運算式級的型別檢查作為基礎, 做陳述句的型別檢查就很方便快捷了.

• write

  上文(writeExpr )已給出解釋

• if / while / for

  對于這種型別的陳述句, 只需要檢查是否符合對應的規則即可. 例如條件判斷處必須是個布爾型別的運算式

• {StatementList}

  這種型別的運算式, 按順序輪流進行檢查即可

• cvaIdentifierExpr r = Expr r;

  賦值陳述句, 只要等號兩側的型別是互相匹配的, 那就允許賦值.

特別注意

應當注意到, 我們之前提到的一直是“型別匹配”, 而不是“型別相等”. 隱含的, 我們允許合法的型別隱式轉換.

其他檢查

在本程式里, 我們還做了另外兩個對于識別符號的檢查：變數/欄位識別符號(CvaIdentifierExpr expr),
類名識別符號(也是identifier). 由于這兩類識別符號存在于不同的符號表里面, 因此本程式可以宣告類似
SomeThing SomeThing; 這樣型別和名稱一樣的變數/欄位,這種宣告是合法的, 在使用時具體的意義取決于這個符號所在位置的語意.

錯誤恢復

前面已經提到, 在這個階段, 我們要在一遍掃描中給出盡可能多的資訊, 因此我們需要實作錯誤恢復功能. 出現的具體錯誤和恢復思想如下

• 使用了未宣告的變數

  一旦發現某處使用了未使用的變數, 那么會立即給出資訊提示此處發現一個未宣告變數, 但是分析還是要繼續, 于是原地定義該變數是
  一個 unkonwn 型別, 使用該型別, 進行接下來的分析.

• 運算子型運算式

  例如 true + 10, !200這種型別的錯誤, 我們優先考慮運算子的語意, 例如在我們的程式中, 加減乘必定得出一個整數,
  比較運算必定得出布爾型別的值. 我們假定該運算子被正確使用并得出結果, 然后進行下面的分析.

• 方法呼叫

  方法呼叫出現了問題, 例如引數不全、引數型別不匹配, 我們給出應當提示用戶的資訊之后, 假定方法正常呼叫, 按照該有的回傳值進行下面的分析.

標籤：其他

上一篇：C語言學習：在編程中的一些低級錯誤

下一篇：ThinkPHP5權限管理