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）并使用较弱的代数结构，以便重构计算的范围更大。这个想法是改善并行性。

编辑：网页上的评论意味着两次会谈是背对背排定的，所以也许您在幻灯片上提到的内容是第二次演讲的前奏。