# Tangle:A prototype one-pass parser for C language ## 緣起 本人於2023年暑期開始貢獻 Shecc ,從暑期至今都主要活躍於前端(包括 lexer 及 parser)的改進以及函式抽象化的優化(參考[此處](https://github.com/sysprog21/shecc/issues/84))。 然而後來開始著手處理解決 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`](https://doc.rust-lang.org/std/iter/trait.Iterator.html))來簡化邏輯。 - 簡化不必要的設計考量:雖然 Tangle 最後的實作將會被移植至 Shecc 中,但快速概念驗證的主旨即是以邏輯導向將程式實作出來。相較於 C 語言,Rust 雖然必須確保 borrow checker 的一些規則,但最終來說我們可以借助 Rust 的 RAII 來幫助我們隱含地釋放未使用的資源,進而避免 dangling reference 的問題,採用 C 則會需要明確地使用 free 含式於正確的位置上釋放資源,此差別將會大幅地影響概念驗證中的實作時長。 ## Regional Lexer 概述 :::info 筆者註:我在實作 Regional Lexer 的時候並無參考任何論文,若有相似的實作技巧歡迎留言! ::: Regional Lexer ,如字面上所述,藉由將原始碼分割並交由不同用途的特化 Lexer 進行 tokenize 的動作,達成消弭單一 Lexer 的過度特化。實作架構大致如下: ```rust 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](https://github.com/sysprog21/shecc/blob/master/src/parser.c#L2920) 展開過後的原始碼所使用的 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 有諸多奇效! :::info 筆者註:由於篇幅問題,這裡不會討論 Macro 的額外特殊判斷及行為。有興趣可以到 [Tangle] 參考實作邏輯。 ::: ## 後記 雖然仍有兩個特性有待新增並驗證: - Identifier Concatenation - Identifier Stringify 但該概念驗模型已解決先前 Shecc 所無法達成的目標,如: - Multiple Token Aliasing - Nested Macro Invocation 此外,我將持續改進該概念驗證模型,由於目前所合成的程式碼可能會造成過多的字串複製,進而留下可觀的 memory footprint,因此,目前下一步需要概念驗證的是如何利用 Rust 的 `std::slice`(也就是 `&str`)來防止過多的字串複製以及確保原始碼的生命週期。 ## 參考資源 - [Shecc] - [Tangle] [Shecc]: https://github.com/sysprog21/shecc [Tangle]: https://github.com/ChAoSUnItY/tangle
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up