对于已经以分割格式给出的大量输入数据，并行化解析器似乎很容易，例如单个数据库条目的大列表，或者很容易通过快速预处理步骤进行分割，例如解析大型文本中句子的语法结构。
并行解析似乎有点困难，它已经需要相当多的努力来定位给定输入中的子结构。通用编程语言代码看起来就是一个很好的例子。在像 Haskell 这样的语言中，使用布局/缩进来分隔各个定义，您可以在找到新定义的开头后检查每行的前导空格数，跳过所有行，直到找到另一个定义并传递每个定义将块跳过到另一个线程进行完整解析。
当涉及到像 C、JavaScript 等使用平衡大括号来定义范围的语言时，预处理的工作量会大得多。您需要遍历整个输入，从而计算大括号的数量，处理字符串文字内的文本等等。对于像 XML 这样的语言，情况更糟，您还需要跟踪开始/结束标记中的标记名称。
I found CYK 解析算法的并行版本 https://pdfs.semanticscholar.org/7f00/907026e8ed51f46e3226134c111baf796a85.pdf这似乎适用于所有上下文无关语法。但我很好奇确实存在哪些其他通用概念/算法可以使解析器并行化，包括上面描述的大括号计数之类的东西，它只适用于有限的语言集。这个问题不是关于具体的实现，而是关于这种实现所基于的想法。
我想你会找到 McKeeman 1982 年的论文并行LR解析 http://www.cs.dartmouth.edu/~mckeeman/references/ParallelLR82.pdf非常有趣，因为它看起来很实用并且适用于广泛的语法类别。
基本方案是标准LR解析。聪明的是，（大概很长）输入被分成大约 N 个大小相等的块（对于 N 个处理器），并且每个块都被单独解析。因为块的起点可能（必须！）位于某些产生式的中间，所以与经典的 LR 解析器不同，McKeeman 的各个解析器从所有可能的左上下文开始（需要增强 LR 状态机）来确定哪个 LR项目适用于块。 （在单个解析器确定真正适用的状态之前，不应该需要太多标记，因此这并不是非常低效）。然后所有解析器的结果被拼接在一起。
他在某种程度上回避了在令牌中间划分输入的问题。 （您可以想象一个任意大的字符串文字，其中包含看起来像代码的文本，以欺骗解析器从中间开始）。似乎发生的情况是解析器遇到错误，并放弃其解析；左边的解析器填补了空缺。人们可以想象分块器使用一点点智能来基本上避免这种情况。
他演示了一个真正的解析器，可以在其中获得加速。
确实很聪明。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
