一元化解析--这是什么？

Question

我刚刚偶然发现了一个词，这个词来自幻灯片，由爱德华·克米特命名为“Monoids的介绍”(Introduction)。幻灯片始终使用haskell。

现在，当我搜索这个词时，除了很少提到它，而且从同一个作者那里找到最多的，什么也没有发现。所以我想这个词可以在这里解释。

那么，单面分析是什么有趣和新的东西吗？除了我链接到的幻灯片之外，它是否出现在任何地方？最重要的是它是什么？幻灯片本身似乎没有给出一个定义，也没有突出它那么多。

Answer 1

我将从解析器通常的工作方式开始。一般说来，解析器按顺序接收输入令牌。在某个时候(通常在所有令牌用完之后)，解析器将返回输出。这个模型的一个缺点是它本身是顺序的:因为解析器按照顺序对一系列令牌进行操作，所以如何并行处理并不明显。

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

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

当然，对于实际编写并行解析器来说，也需要适当地分割块。如果您希望并行地解析顶级定义，则必须能够识别该定义从何处开始。此任务通常由解析器本身执行。我记得，他的幻灯片很大一部分涉及到了这个主题。在顶层定义上的分裂是相当粗粒度的；理想情况下，我们的解析器可以从任意令牌开始，然后在应用单面运算符时理解这些片段。

不幸的是，我不能说“一元论解析”是否是新的，因为我对文献并不特别熟悉。但是，我怀疑任何用于并行解析的模型或算法都涉及一个单面结构，即使它没有显式命名。一段时间以来，人们都知道单行词适合并行化问题，所以如果解析器的研究人员普遍使用这种技术，我就不会感到惊讶了。

Answer 2

试试他在此页的另一个演示文稿，这是你正在读的第二个报告。这是一种新的东西，我真正能做的就是翻译他的幻灯片，告诉你这是一种尝试，采用一元解析(如Parsec)，并使用较弱的代数结构，以便有更多的空间来重构计算。这样做是为了提高并行性。

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