Monoidal解析 - 它是什麼？

Question

我只是偶然發現monoidal解析從slide名爲「簡介猿」Edward Kmett。幻燈片始終使用haskell。

現在，當搜索該術語時，我發現只有少數幾個提及它，並且來自同一作者。所以我認爲這個詞可以在這裏解釋。

那麼，是monoidal解析東西是有趣的和新的？它出現在除了我鏈接的幻燈片之外的任何地方嗎？最重要的是它是什麼？幻燈片本身似乎沒有給出定義，也沒有突出顯示。

Answer 1

我將從解析器的工作原理入手。廣義上講，解析器按順序獲取輸入令牌。在某個點（通常在所有令牌耗盡之後），解析器返回輸出。這種模式的一個缺點是，它本質上是連續的：因爲解析器按順序操作一系列令牌，所以並行處理並不明顯。

但是，如果我們有權訪問能夠將部分解析結果合併爲單個結果的操作，則解析可以並行化。例如，如果我們的語言可以用上下文無關的語法表示，那麼我們可以分別並行地解析每個頂層定義，然後使用組合操作來組裝這些部分。

Monoidal解析僅僅意味着解析器可以訪問合適的組合函數。幺半羣是具有零元素和二元關聯算子的結構。例如，列表形成一個monoid，其中零是空列表，而關聯運算符是連接。請記住，關聯性意味着(a++b)++c == a++(b++c)。碰巧這是確保我們能夠以合理的方式重新組合解析結果的必要屬性。子分析重組的順序並不重要，只要每個子分析保存在正確的序列位置即可。

當然，爲了實際編寫並行解析器，還需要適當地分割塊。如果您想要並行解析頂級定義，則必須能夠識別定義開始的位置。這個任務通常由解析器本身執行。我記得，他的幻燈片的很大一部分都涉及這個話題。在頂層定義上進行拆分相當粗糙;理想情況下，我們的解析器將能夠從任意任意的標記開始，然後在應用monoid操作符後再從其中取出。

不幸的是，我不能說，「monoidal解析」是新的，因爲我不是特別熟悉文獻。不過，我懷疑任何用於並行解析的模型或算法都涉及一個monoid結構，即使它沒有明確命名。衆所周知，monoids適用於並行化問題，因此如果這種技術在解析器研究人員中很常見，我不會感到驚訝。

Answer 2

請嘗試他的其他演示文稿this page，這是您閱讀之後的第二個演示文稿。這是一件新鮮事，我真正能做的就是解釋他的幻燈片，並告訴你這是嘗試採用單調解析（如Parsec）並使用較弱的代數結構，以便重構計算的範圍更大。這個想法是改善並行性。

編輯：網頁上的評論意味着兩次會談是背對背排定的，所以也許您在幻燈片上提到的內容是第二次演講的前奏。