parsing - 单曲面解析——它是什么？

Question

我刚刚从Edward Kmett的名为“Monoids 简介”的幻灯片中偶然发现了monoidal 解析一词。幻灯片始终使用 haskell。

现在，在搜索这个词时，我只发现很少提到它，而且最多的是同一作者。所以我认为这个术语可以在这里解释。

那么，monoidal 解析是不是很有趣又新颖呢？除了我链接的幻灯片之外，它是否出现在任何地方？最重要的是它是什么？幻灯片本身似乎没有给出定义，也没有过多强调它。

Answer 1

我将从解析器通常的工作方式开始。从广义上讲，解析器按顺序获取输入标记。在某个时刻（通常在所有标记都用完之后），解析器返回输出。该模型的一个缺点是它本质上是顺序的：因为解析器按顺序对一系列标记进行操作，因此如何并行化该过程并不明显。

但是，如果我们可以访问能够将部分解析结果组合成单个结果的操作，则解析可以并行化。例如，如果我们的语言可以用上下文无关文法表示，那么我们可以分别并行地解析每个顶级定义，然后使用组合操作组装这些部分。

Monoidal 解析仅仅意味着解析器可以访问合适的组合函数。幺半群是具有零元素和二元关联运算符的结构。例如，列表形成一个幺半群，其中零是空列表，关联运算符是连接。请记住，关联性意味着(a++b)++c == a++(b++c)。碰巧这是确保我们能够以合理的方式重新组合解析结果的必要属性。重新组合子解析的确切顺序无关紧要，只要将每个子解析保存在正确的序列位置即可。

当然，对于实际编写并行解析器，也有必要适当地拆分块。如果要并行解析顶级定义，则必须能够识别该定义的开始位置。此任务通常由解析器本身执行。我记得，他的大部分幻灯片都涵盖了这个主题。在顶级定义上拆分是相当粗粒度的；理想情况下，我们的解析器将能够从任意标记开始，然后在应用 monoid 运算符时从片段中理解。

不幸的是，我不能说“monoidal parsing”是否是新的，因为我对文献不是特别熟悉。但是，我怀疑任何用于并行解析的模型或算法都涉及一个幺半群结构，即使它没有明确命名。一段时间以来，众所周知，monoids 适用于并行化问题，因此如果该技术在解析器研究人员中很常见，我不会感到惊讶。

Answer 2

试试他在这个页面上的另一个演示文稿，它是您正在阅读的那个之后的第二个。这是新的东西，我真正能做的就是解释他的幻灯片，并告诉你这是一种尝试单子解析（如 Parsec）并使用更弱的代数结构，以便有更多的空间来重构计算。这个想法是为了提高并行性。

编辑：页面上的评论表明这两次会谈是背靠背安排的，所以你看到的幻灯片上提到的可能是第二次会谈的前兆。