Tangle：A prototype one-pass parser for C language

緣起

本人於2023年暑期開始貢獻 Shecc ，從暑期至今都主要活躍於前端（包括 lexer 及 parser）的改進以及函式抽象化的優化（參考此處）。

然而後來開始著手處理解決 lexer 及 parser 對於 preprocessor directives 的 hack code 以及缺陷時，發現僅仰賴傳統作法的 lexer parser 對於某些具有上下文敏感性 preprocessor directive （如：#define, function-like macro）的 syntax 上會受到諸多限制。

針對此狀況，我於2024年4月開始，利用 Rust 來快速概念驗證於腦中所構思的新技術：Regional Lexical Analyzer (a.k.a. Regional Lexer)。

挑選 Rust 作為快速概念驗證的原因

本次快速概念驗證中挑選 Rust 作為實作語言的原因牽涉到諸多考量：

• 生命週期：為有效保證該實作的記憶體使用能夠不造成 dangling reference 並在合理的範圍內釋放，我們在此借助 borrow checker 以及 lifetime 機制來確保上述的需求。
• 豐富的 stdlib ：對於某些繁重且重複的操作，在快速概念驗證中可以藉由帶入 Functional Programming 的技巧（使用Iterator）來簡化邏輯。
• 簡化不必要的設計考量：雖然 Tangle 最後的實作將會被移植至 Shecc 中，但快速概念驗證的主旨即是以邏輯導向將程式實作出來。相較於 C 語言，Rust 雖然必須確保 borrow checker 的一些規則，但最終來說我們可以借助 Rust 的 RAII 來幫助我們隱含地釋放未使用的資源，進而避免 dangling reference 的問題，採用 C 則會需要明確地使用 free 含式於正確的位置上釋放資源，此差別將會大幅地影響概念驗證中的實作時長。

Regional Lexer 概述

筆者註：我在實作 Regional Lexer 的時候並無參考任何論文，若有相似的實作技巧歡迎留言！

Regional Lexer ，如字面上所述，藉由將原始碼分割並交由不同用途的特化 Lexer 進行 tokenize 的動作，達成消弭單一 Lexer 的過度特化。實作架構大致如下：

pub struct Lexer {
    aliases: Vec<Alias>,
    macros: Vec<Macros>,
    regional_lexers: VecDeque<RegionalLexer>
}

pub struct RegionalLexer {
    regional_aliases: Vec<Alias>,
    skip_newline: bool,
    skip_backslash: bool,
    // ... internal
}

pub struct Alias {
    alias: String
    replacement: String,
    // ... internal
}

pub struct Macros {
    name: String,
    parameters: Vec<Alias>,
    is_variadic: bool,
    source_span: String,
}

其中，regioanl_lexers 是一個 stack，每個 Regional Lexer 皆有各自負責的原始碼區域（區域可能是藉由 synthesize 產生而成的偽原始碼）。藉由分離某些特化的 Lexer 規格（如 skip_newline、skip_backslash），我們可以更有效的控制何種規則需要用於解析相對應的原始碼。

由於這樣的做法會有多個 Regional Lexer 需要維護，故我們需要一個 "Global" Lexer 來管理整體。而根據設計，"Global" Lexer 中始終會有一個 Regional Lexer 存在（等價於原先已經 source loader 展開過後的原始碼所使用的 Lexer）。

流程

由於 Parser 是一個單純的語法規則處理單元，所以不需要做過多調整。而透過 "Global" Lexer 的包裝，我們可以有效的抽象化一些
共用邏輯（如：lex_token）。

對於 Lexer 的邏輯，我們可以把 #define 所定義的 macro 或 alias 視為一段合成的程式碼，並當遇到對應的 aliased identifier 時，直接將 Lexer 的解析的位置重置至需要被置換的原始碼位置。由於不論是 macro 還是 alias，我們都需要在特定的位置再重置 Lexer 位置回到上一次跳轉的位置，這時候我們可以利用 Lexer::regional_lexers 其資料結構 Stack<_> 的特性：當子程式碼的位置超過合成程式碼的範圍，其會始終回傳 TokenType::TEof，也就可以斷定該層的詞法分析已結束，將該 Regional Lexer 的資源及本身釋放，並回傳前一層 Regional Lexer 所分析的 Token 結果，即達成區域詞法分析的功能。

Lexer::regional_lexers 如此設計甚至對後續實作 Nested Macro Invocation 有諸多奇效！

筆者註：由於篇幅問題，這裡不會討論 Macro 的額外特殊判斷及行為。有興趣可以到 Tangle 參考實作邏輯。

後記

雖然仍有兩個特性有待新增並驗證：

• Identifier Concatenation
• Identifier Stringify

但該概念驗模型已解決先前 Shecc 所無法達成的目標，如：

• Multiple Token Aliasing
• Nested Macro Invocation

此外，我將持續改進該概念驗證模型，由於目前所合成的程式碼可能會造成過多的字串複製，進而留下可觀的 memory footprint，因此，目前下一步需要概念驗證的是如何利用 Rust 的 std::slice（也就是 &str）來防止過多的字串複製以及確保原始碼的生命週期。

參考資源

• Shecc
• Tangle