sora

前言#

詞法分析器 tokenzier 的構建步驟就不贅述了，可以參照 repo 裡的 tokenizer，也可以自己寫一個其他類型的，保證 tokenzier 返回的 token 和 parser 裡的 token（這裡是Symbol類的實例）能銜接起來即可。

這個項目基於龍書 [1] 實現，Parser 中的相當一部分細節都可以在龍書中找到對應部分，可以作為例子輔助理解龍書。

這個項目使用 Python 語言。為什麼？Python 語言的自由度能夠使人最大限度地專注於程序邏輯的實現，而非語法的細枝末節，非常適合實踐想法，而且可以借助類型註解實現靜態檢查。後續如果對性能有要求也可以此為藍本構建 C++ 版本的程序。

最後感謝課程老師出了這麼難的實驗題目，不然還真不會想到去做這麼一件事，更不會如痴如醉地投入一個星期左右的精力。

路線#

準備#

開發環境是 Windows 11 + Jetbrains Pycharm + Python 3.9

• 其中用到的較新版本 Python 特性有:
  • Python 3.6 以來內置類型dict的插入變為有序，用來清晰地打印項集族
  • Python 3.7 以來支持的from __future__ import annotations用法，用來類型註解，放寬了類先後定義的順序，可以把後面定義的類在前面作為類型註解
• 編程習慣：
  • 把常量儘量放在一個統一的文件中，如 constants.py，儘量避免魔法數字和魔法字符串
  • 多使用類型註解，方便理清變量的類型，靜態排錯
  • 在類中定義debug_mode開關打印調試信息
  • 做單元測試
    • 參考代碼中的單測在tester.py
• 如何從外部主程序 main.py 進行調試？
  • 在外部主程序實現一個create_cfg方法，在裡面定義和修改上下文無關文法
  • 準備好測試的程序文本，如 test.c
    • 示例 CFG 文法可參考 test.c 中的c_generators
  • 定義好 Tokenizer 實例，讀入所有 token
  • 定義好 Parser 實例，打開調試模式，初始化格局
  • 可以用 Tester 實例封裝測試過程
  • 觀察和分析輸出，不斷調整實現
    • 為了方便查看，可以重定向輸出到文件

對符號、產生式、項、項集等建模#

對符號、產生式、項、項集等的建模位於 grammar.py 文件中。

• 文法符號 -> Symbol類
  • 成員變量
    • sType: token 的類型
      • 按終結符號和非終結符號兩類劃分
    • name: token 的類型
      • 按數值常量、標識符等劃分
      • 如標識符對應的name是constants
    • content: token 的字符串表示
      • 如：int a; 中 a 是標識符類型，屬性name為 "constants"，屬性content為 "a"
  • 成員函數
    • __str__：轉換為字符串表示，方便打印
    • __hash__和__eq__：方便使用集合類型
    • fromStr: 從str類型轉換到Symbol類型，需要外部指定終結符號集
  • 空符號怎麼表示？
    • 在constants.py中定義常量，用ε表示
    • 定義成Symbol類型或str均可
• 產生式 -> Generator類
  • 成員變量
    • start：產生式左部的非終結符號
    • end: 產生式右部的文法符號串
  • 成員函數
    • __str__：轉換為字符串表示，方便打印調試
  • ComposedGenerator是幹什麼的？
    • 手動定義 CFG 文法時，寫字符串比定義Symbol要方便得多，所以用ComposedGenerator做了一層轉換
    • 另外，同一個產生式左部可能對應多個產生式右部，如A -> a | b，體現為ComposedGenerator中的成員end類型註解為list[list[str]]，是為 "Composed"
      • 例子：A -> a | b
        • 定義成ComposedGenerator是{start: 'A', end: [['a'], ['b']]}
        • 轉換成Generator可得到兩個Generator類型的實例
          • {start: 'A', end: ['a']}
          • {start: 'A', end: ['b']}
• LR (1) 項 -> Item類
  • 成員變量
    • start: 產生式左部非終結符號
    • end: 產生式右部文法符號串
    • point: 產生式體內的點，表示讀入到的位置
    • lf_symbols: 向前看的符號，LR (1) 只看一個
  • 成員函數
    • __hash__和__eq__：區分實例，方便使用集合類型
    • __str__：轉換為字符串表示，方便打印
      • 這裡特判了產生式為空的情況
• LR (1) 項集 -> ItemSet 類
  • 成員變量
    • _items：所有的項
  • 成員函數
    • add：將項加入項集，重複的自動忽略
    • union：和其他ItemSet類型合併
    • toList: 轉換成列表
      • 方便後續用數字索引 LR 自動機的狀態
    • __hash__和__eq__：區分實例，方便使用集合類型
    • __iter__: 返回內部迭代器，用於for遍歷
    • __len__: 返回大小
      • 需要繼承Sized
  • 為什麼要為項集建模？直接用set(Item)不行嗎？
    • 很好，一開始我也是這樣想的
    • 問題主要出在求 LR (1) 規範項集族的時候
      • 需要判斷沒有新增的項集時，第一反應是在set(Item)外面再套一層，set(set(Item))
      • 但是set(Item)上沒有偏序和等價的默認定義，是一個複合類型
        • "複合類型" 可參考編程原本 [2] 第十二章
      • 所以需要為項集手動定義偏序和等價
    • 加上打印調試等需求，所以需要為項集建模
• 上下文無關文法 (CFG) -> GrammarCFG類
  • start_mark: 開始符號的字面量
  • end_mark: 終結符
    • 一般是棧底的 '$'
  • end_symbols: 終結符號的集合
  • generators: 產生式集合
    • 從中可得出非終結符號的集合

實現求 FIRST 集和 FOLLOW 集#

從這一步開始實現 Parser，對應的參考實現在parser.py，對應的龍書參考頁碼在代碼有詳盡的註釋。

• 參考代碼中相關函數
  • get_first
  • get_chain_first（對文法符號串求 first）
  • get_follow
  • _get_follow_once
  • _get_follow_all
• 參考代碼中相關成員變量
  • self._map_follow
  • self._map_first
• 為什麼要先從求 first 集和 follow 集開始？
  • 求 first 集和 follow 集是後續算法的基礎
  • 而且你已經建模好了語法，只要按照龍書上的流程實現就可以了，只涉及文法符號和產生式
  • 從簡單的操作開始不斷調試迭代，可以慢慢找到編程的狀態
• 應該怎麼求？
  • 求 first 集沒有什麼坑，函數的調用過程是一個樹形結構
    • 比如：對於A -> B 和 B -> b
      • 求first(A)調用求first(B)
      • 求first(B)得到{b}
  • 但是求 follow 集，函數的調用過程有環
    • 比如：對於A -> aB 和 B -> bA | b
      • 根據求 follow 集的第三條規則
      • 求 follow (A)，發現 follow (A) 都在 follow (B) 中
      • 求 follow (B)，發現 follow (B) 都在 follow (A) 中
    • 參考實現中的解決方法比較簡單粗暴
      • 預先計算所有非終結符號的 follow 集，用dict保存在全局變量self._map_follow
      • 不斷掃描所有非終結符號的 follow 集，直到沒有新的終結符號加入為止
        • 判斷方法比如 union 兩個非終結符號的 follow 集，檢查len是否有變化等等
    • 可以試著尋找更好的實現

實現求 CLOSURE 和 GOTO#

有了求 first 集和 follow 集的工具，下一步可以從 LR (1) 項涉及到的算法開始著手了。對應的參考實現在parser.py，對應的龍書參考頁碼在代碼有詳盡的註釋。

• 參考代碼中相關函數
  • get_closure
  • get_goto
• 書上沒說到的部分？
  • 按照依賴順序，先實現 closure，後實現 goto
  • closure 集
    • 需要注意去重
    • 一次遍歷中另外存儲新加入的項，下次只遍歷新加入的項
    • 需要注意把新加入的項最後一塊加進去，防止迭代器失效
    • 參考代碼中我的實現很差勁，現在發現只是碰巧能跑，可能當時喝醉了，建議不要作為參考
  • goto 集是沒有什麼坑的
    • 後面一個符號是 X，移動點，加進去就可以
    • 最後求 closure 閉包返回

實現求 LR (1) 項集#

從增廣文法的第一條產生式求閉包開始，有了 goto，就可以求 LR (1) 項集了。不斷求 goto，直到沒有新的項集加入為止。對應的參考實現在parser.py，對應的龍書參考頁碼在代碼有詳盡的註釋。

• 可以採用和求 follow 集類似的方法判斷 “沒有新的項集加入”
• 參考代碼中相關函數
  • get_lr1_items
• 順利完成這一步後，通過把求 goto 的過程打印出來，把每個項集看作一個狀態，你會發現實際上你已經完成了 LR (1) 項集的自動機，到這一步已經成功一半了

實現 LR (1) 的分析表#

• 參考代碼中相關函數
  • get_lr
• 需要
  • 建模一個動作，作為填入分析表的內容
    • 成員必須包含
      • 執行的動作類型
      • 執行動作必需的信息
        • 比如：
          • 用哪個產生式規約
          • 下一步到哪個狀態
  • 建模一個 LR (1) 分析表，往裡面一個一個填
    • 對應LRSheet
    • 一維是狀態的下標，一維是符號
  • 規範 LR (1) 項集族，作為所有狀態
• 可以像參考代碼一樣按照規則一條條填動作，也可以合到一塊填動作
• 如果填寫過程中一個格子填了兩遍？
  • 實現有錯誤
  • 文法不是 LR (1) 文法
• 其他
  • 參考代碼中，空產生式的規約是通過出錯後向棧頂試著放一個空符號實現的

實現 LR (1) 的格局#

• 建模格局
  • 假設全部輸入已知
  • 這裡沒有嚴格按照 158 頁 [1] 定義
  • 除了棧中的輸入和餘下的輸入，還有棧中的狀態下標，方便調試和觀察自底向上的處理過程
  • 參考代碼中把執行一步動作也放到了格局裡，方便打印狀態
• 到這一步基本就完成了

加入簡單的 SDD 語法制導分析#

這裡的 SDD 僅限於 S 屬性的 SDD，以遞歸子程序的方式定義在create_cfg()體內，且僅在 action 為產生式規約操作時觸發。可以試試自行修改到在產生式中間、在 action 為移入操作時觸發。

• 可以參考以下步驟加入 SDD：
  • 擴展 Symbol 等建模，使其可攜帶各種語義屬性
  • 實現簡單的類型聲明
  • 實現簡單的表達式求值
  • 實現簡單的類型檢查規則
  • 實現控制流的 SDD
• 注意
  • Python 內部對於對象是淺拷貝，所以在forward執行語義動作前需要進行一層深拷貝，防止覆蓋其他Symbol實例的 SDD
• 如何擴展？
  • 約定好遞歸子程序的格式，比如
    • 參數列表都是(input_symbols: list[grammar.Symbol], reduction_symbol: grammar.Symbol, st: parser.SymbolTable)
    • 定義好屬性的名稱在constants.py
      • 正好體現了統一定義常量的好處
      • 不需要多次手打字面量，容易打錯字母，出意想不到的 bug
  • 每定義一個產生式，綁定一個函數作為遞歸子程序
  • 在Item類中也加入這個參數
  • 在 Parser 類各種方法創建新的Item實例時把綁定的函數也一塊傳遞進去
  • 在forward執行一步規約動作時執行語義動作
  • 具體可查看參考代碼中的 Git 差異

存在的問題#

• 在一開始建模時沒有充分考慮Symbol等價的問題
  • 比如: a 和 b 在產生式中都是identifier ，所以對它們進行比較會得到相等的結果
  • 最終採用了只比較在產生式中的表示，不會比較字符串內容
• 為什麼有sType和name兩個分開？既然都是表示 token 類型，合併起來不好嗎？
  • 當初設計這兩個分開主要是和接口銜接的問題
  • 詞法分析器 tokenizer 部分的類型沒有按照終結符號與非終結符號劃分，而是細分為五類
  • 最後在外部定義 CFG 文法時又按終結符號和非終結符號劃分了一遍，處理的確實不好，應該在 tokenizer 就劃分好
• Parser 內部的一些函數是公開的
  • 為了方便單測，但不夠 neat
• if-else沒有處理好，用了特判懸空 else 處理
  • 其實可以用語法定義解決，詳見龍書 134 頁
• 沒有實現真正的恐慌模式，只是丟棄到需要的 token 出現為止
• 沒有考慮實現的效率問題
  • 比如求 follow 集和求 LR (1) 規範項集族時，判斷沒有新的項或項集加入的操作是非常簡單粗暴的
• SDD、三地址碼的實現不規範
• constants.py和外部create_cfg耦合度高
• ItemSet沒有充分考慮修改後求 hash 的問題
• 求閉包中用來去重的實現不好
  • 比如不用cur_items去重而是用f_list去重
  • f_list把向前看的符號和產生式右部混在一塊，有潛在的 bug

參考資料#

• [1] 編譯原理 第 2 版（Compilers: Principles, Techniques and Tools, Second Edition），（美）Alfred, V.A. 等著；趙建華等譯，—— 北京：機械工業出版社，2009.1
• [2] 編程原本（Elements of Programming），（美）Stepanov, A.，（美）McJones, P. 著；裘宗燕譯.—— 北京：機械工業出版社，2011.12