編譯器構造/編寫可重用語法的秘訣

所以你需要編寫一個語法。但你需要處理多個重要的實際問題

• 你需要你的解析器能夠從你的語言中使用。
• 你可能還想從其他語言中重用它。
• 你使用的語言可能有一個非常不成熟的解析器生成器，很難用於任何複雜的事情
  • 它可能完全缺乏除錯工具。
  • 它可能返回非常奇怪的錯誤訊息，即使你的語法看起來正常。
  • 即使所有內容都編譯得很好，生成的解析器也可能在執行時崩潰。
• 方便的解析器生成器生成的解析器可能非常慢。

所以我們來看看如何解決這些問題。解決這些問題的總體思路很簡單

• 一步一步地做所有事情；
• 使用正確的工具。

1. 建立足夠多的簡單的你要解析的語言樣本。

2. 看一看。問問自己你的語法必須是什麼樣的最小語法類。是否可以建立上下文無關語法？如果不是，是否可以將你的語法簡化為上下文無關語法，在解析樹構建完成後解決非上下文無關問題？

3. 選擇你要的目標語言。在我的例子中是 Python。

4. 為它找到解析器生成器。對於每個生成器，獲取以下已知資訊

• 它可以生成的語法類；
• 它是分詞器/無詞法器還是帶詞法器的；
• 它是否支援模組化語法，每個子部分可以分別開發和測試；
• 除錯和視覺化工具的可用性
  • 如果解析器帶詞法器，應該可以解析前列印詞法單元；
  • 跟蹤器；
  • 樹視覺化器；
• 預建立語法的庫的可用性；
• 良好的文件和示例的可用性；
• 它是否被編譯成目標語言結構直接進行解析，還是被編譯成一個由執行時解釋的資料結構？
• 即使它被轉換成程式碼，程式碼可能仍然使用一些執行時。使用的執行時的效率和依賴性是什麼？
• 解析器生成器支援哪些其他程式語言？

5. 在網際網路上搜索預建立語法。可能已經存在該語法，你只需要將其適應你的解析器生成器。

6. 選擇你的初始解析器生成器。現在你需要在高層次上編寫你的語法，並使其工作。我的意思是，你現在的主要目標是建立一個能夠正確解析字串的語法，而不是與生成器作鬥爭。

• 它應該是GLR。你可以降低類並最佳化後續部分。它可以讓你免於解決衝突。
• 它應該是無詞法器的。它可以讓你免於為每個詞法單元定義不同的字元類。
• 它必須有工具允許你跟蹤它的執行。
• 它必須返回一個解析樹，而不是使用語義動作構建它。語義動作是特定於語言的，它們的語法通常是特定於解析器的。在一些解析器生成器中，它們允許使用自己的程式碼進行消歧，但這並不是通用的，並且 API 使用高度依賴於解析器生成器。
• 它必須能夠視覺化解析樹。
• 它必須支援命名詞法單元和跳過不相關的詞法單元。

我使用了 GLR 模式下的 parglare。parglare 有一個除錯工具，允許我看到轉換圖及其中的路徑，以及可能的路徑以及錯誤發生的位置。

7. 選擇其他解析器生成器。標準相同，但它們可能屬於另一個類。你的最終目標是讓你的語法與所有這些生成器相容，並將生成的解析樹包裝在一個抽象層中，以便你的手寫程式碼只處理抽象層。將解析器生成器更改為相同或更高類通常很簡單：只需確定一個語法DSL 語法特徵到另一個語法 DSL 語法特徵的對映。

降級語法類可能需要更改解析器生成器和語法。保持所有不同生成器的語法同步非常重要，以便具有相同的結構。你的目標是為一個解析器生成器編寫一個語法，使其能夠自動轉換為其他解析器生成器。保持同步可能意味著更高類甚至相同類的語法將變得不必要地更難看：不同的解析器生成器具有不同的語法糖，因此你必須使用公共子集。它變得有點難看並不重要。你可以在解析樹解析完成後對其進行後處理，以使它更方便以後使用。重要的是，當你降級解析器時，你會提高

• 效能
• 錯誤訊息的可解釋性
• 增加可以使用你的語法的解析器生成器集合（可以在PEG 和LR(1) 解析器生成器中使用 LL(1) 語法，但不能在LL(1) 解析器生成器中使用LR(1) 語法，也不能在LR(1) 解析器生成器中使用GLR）。
  • 你增加了在進一步開發語法時可以使用除錯工具的集合；
  • 你的語法變得有用，因為更多人可以在他們語言中可用的解析器生成器中重用它；
  • 你將語法限制為所有解析器生成器通用的功能，因此更容易移植。

幸運的是，我已經開發了一個名為UniGrammar 的工具。它具有以下功能

• 基於 YAML 的自己的格式（實際上，任何可以序列化任何可以序列化為 JSON 的物件的格式都可以使用），因此不需要語法進行解析和序列化；
• 它為其他 DSL 生成語法；
• 它還生成包裝器（目前只在 python 中），將特定於解析器的解析樹轉換為我們自己的格式中的解析樹，這些解析樹旨在針對由同一 UniGrammar 語法生成的不同的解析器解析相同的文字時相同；
• 它提供統一的 CLI 來使用支援的解析器的任何子集測試語法；
• 它提供了一個庫，可以使將第三方工具插入 UniGrammar 變得更容易；
• 它具有模組化架構，可以輕鬆地新增對解析器生成器的支援；
• 它有所謂的模板。這些是高階構造，轉換成為低階語法塊。例如，你可以指定你有一個專案列表，每個專案都使用一些（非）終結符指定，它們之間使用另一個（非）終結符指定分隔符，該工具將為其生成所需的規則，以及一個包裝器，允許你將結果作為真正的 python 列表獲取，因此你的程式碼不需要特殊對待第一個專案。

本文的其餘部分側重於使用該工具。

8. 編寫一個高層次的GLR 語法。

• 解決生成器發出的所有錯誤和警告。
• 除錯它。使用跟蹤和解析樹視覺化。
  • 無論如何使它在最簡單的例子上工作。
  • 然後使它在所有示例上工作。
  • 然後使它返回你想要的解析樹，幷包含所有示例。

9. 最佳化語法使其看起來乾淨。將詞法單元與產生式分離。除錯並測試它。

9. 使語法退化

• 如果分詞器使用正則表示式，則用詞法單元和產生式替換正則表示式。大多數生成器不支援正則表示式作為詞法單元。這可能會降低效能（正則表示式在原生代碼中執行，但解析器在 python 中執行），但這裡通用性更有價值；
• 將組分離為單獨的詞法單元/產生式。理由：一些生成器沒有它們；
• 將字元類與由它們組成的詞法單元分離。理由：對於某些生成器（更準確地說，是 LL(1) 生成器），詞法單元不能包含與其他詞法單元中迭代的相同字元，否則它們無法進行消歧。因此，所有詞法單元必須被劃分為不同的字元類。曾經是一個詞法單元現在將成為產生式中的多個詞法單元。例如（在 parglare 語法中）

terminals
Something: /[^0-9]+/;
Name : /[a-zA-Z_0-9-]+/;

必須轉換為

somethingSegment: NonDigitNonAlphaNum | Alpha;
nameSegment: Digit | Alpha;
name: nameSegment+;
something: somethingSegment+;

terminals
Alpha: /[a-zA-Z_-]/;
NonDigitNonAlphaNum: /[^0-9a-zA-Z_-]/;
Digit: /[0-9]/;

這將有利於轉換為 LL。UniGrammar 必須生成 LL 語法，它在自己的語法中強制執行這種結構。（注意：這並不意味著你只能在 UniGrammar 中指定 LL 語法）。

• 將被捕獲的內容分離到自己的產生式中。理由：一些解析器生成器沒有捕獲。因此，我們必須實現一個自己的代理：我們只是儲存必須捕獲的特定於解析器的 AST 節點名稱的對映，並在後處理步驟中從它們中恢復捕獲組。

在每一步後測試語法。

10. 將語法檔案提交到儲存庫。

11. 將語法從特定於解析器生成器的 DSL 轉換為 UniGrammar DSL。將語法編譯到你的解析器生成器。將生成的文

13. 使用 UniGrammar test ... 測試你的語法。

12. 將語法降級為LR(1)（我使用了 LR 模式下的同一個 parglare），解決所有編譯問題並再次除錯和改進它。

12. 將語法移植到PEG。我使用了waxeye。它沒有任何除錯工具，但它是一個直譯器，而且非常簡單，我不得不將一些跟蹤程式碼嵌入到它的 python 執行時中。除錯，同步，修復程式碼測試。

13. 將語法降級為LL(*)。我使用了ANTLR，它有一個除錯工具，允許我檢視詞法單元型別和匹配跟蹤並檢查解析樹。

確保所有後端按預期工作，並修復它們和語法，直到所有內容都工作。

16. 將語法降級為LL(1)。這可能需要在編譯時以相同方式進一步解決檢測到的衝突（在編譯時存在的某些衝突在LL(*)中並非衝突）。我使用了 -CoCoPy 的分支 - w:CoCo/R 的變體。它有非常奇怪的錯誤訊息，幾乎沒有除錯工具。我能夠使這種語法在 CoCo/R 上工作的唯一原因是它與其他解析器生成器相似，因此將這種語法改編到它們會導致將這種語法改編到 CoCo/R。

17. 最佳化、重構、清理、測試所有內容。

18. 新增到語法庫中，以便其他人可以使用它。