c++ - 混合多个lex/yacc组合

Question

我有一个lex / yacc项目，可以很好地完成一件事。我还有另一个lex yacc，可以很好地完成另一件事。这些yacc的主要部分指定了输入和输出文件，在回叫中，我将结果放入输出文件中。如何将第一个lex yacc的输出提供给另一个lex yacc的输入。我不想生成中间文件并将输出文件推入并输入到第二个程序。那一部分我想改变。问题是做1件事完全可以完成的lex，yacc的数量巨大并且正在增加（当前为100），因此我正在寻找可以重用的通用策略。
我正在寻找一种通用解决方案，其中所有lex / yacc对都构成我可以使用的单个项目的一部分。有什么建议吗？

Answer 1

如果我正确地理解了这个问题，那么它与解析工具无关（但请参阅下面的注释），因为它是一个更普遍的问题的实例-链接多对多转换器-这是Producer-Consumer problem的实例。

简而言之，问题在于被链接的变压器不是一对一的，因此您不能简单地为第一个变压器提供一些输入，收集其相应的输出，然后将其输入第二个。相反，您必须提供某种形式的控制流反转，在这种方式中，使用者和生产者都可以在其他进程正在执行时挂起它们的执行（保留他们自己的调用堆栈）。 coroutines可以轻松实现此模型，但是C++ does not (yet) have such things可以轻松实现。在其他语言（如Go）中，可以通过channels解决此问题，但这些问题（尚未）仍不是native to C++。

这正是标准外壳程序“管道”运算符（|）解决的问题，该运算符是在pipe系统调用和多个进程的后台实现的。 （链接的联机帮助页中有一个示例。）

我希望在所有这些链接之间都能找到一些满足您需求的方法。



经过反思，并使此答案对于后代可能更有用，值得注意的是，该问题实际上与标准解析器生成器工具的限制有关。

本质上，yacc / bison和（f）lex协同工作以生成一个工具，该工具从某个源中逐块读取输入，并在适当时调用用户定义的动作（令牌生成器动作和归约动作的组合）。因此，您可以将控制流查看为：

     --> tool -->
          /\
         /  \
        /    \
       /      \
/-->read     perform<-\
|   chunk     action  |
|     |          |    |
|____/           \____|

工具内部的控制流程是封闭的，因此我们不能简单地中止执行以等待输入或提供部分“输出”（即事后处理）。

但是，为了将两个或多个这些工具耦合在一起，我们需要能够做到这一点。第二个进程的输入需要来自第一个进程的输出，但是第二个进程需要调用（某些东西）以获取其输入，而确定第一个进程要调用（某些东西）以处理其输出。

因此，标准解决方案如答案的第一部分所述：通过在单独的进程/线程/纤维/协程/等中运行这两个工具，将这两个工具与控制流分离。通过管道/队列/通道/等进行通信。中间对象，即管道/队列/通道，具有有趣的特征，即可以“调用”两端，从而允许我们反转控制流。

但是，如果这些工具不是用call + call而是用call + return（调用某些东西来获取输入，但是返回每个输出片段）或调用+ call（用每个输入块调用，则整个问题都可以避免）。调用某些东西来处理每个输出块）。在任何一种情况下，我们都可以将两个或多个工具链接在一起。例如，在第二种情况下（称为+ call），我们将有：

/-->input---->tool1
|____/          |
              /-->|
             /    |---->tool2
             |___/        |    
                        /-->|
                       /    |---->output
                       |___/

这通常称为“推送”模型，因为我们将连续的输入块“推送”到系统中，这最终（通过回调）提供了连续的输出操作。还有一个“拉”模型，上面称为“调用+返回”，在该模型中，每次需要输出时便调用系统，并且在需要更多输入来满足请求时调用输入提供者：

/-->call<----tool2
|____/         |
              /-->|
             /    |<----tool1
             |___/        |    
                        /-->|
                       /    |<----input
                       |___/

（请注意，在推模型中，我们调用工具1，以推入下一个输入，而在拉模型中，我们调用工具2，以获取下一个结果。）

查找实现push模型的解析器很简单。 Lemon解析器一直以这种方式工作，而bison拥有推送API已有相当一段时间了。但这还不够好，除非我们除了（f）lex构建的扫描器以外还提供某种机制来提供令牌流，因为我们要推送的是“大量输入”，而不是一系列令牌。

此外，找到实现拉模型的扫描仪很简单。 （F）lex一直这样做；每次拥有新令牌时都会返回。

但是要将两者粘合在一起形成推或拉复合材料，我们需要它们同时推或拉。

这应该不难。 （f）lex和yacc / bison都不产生递归函数，因此连续调用之间的保存状态应该简单明了。 （F）lex扫描仪已经做到了这一点，但有一项警告（如下所述），使它们能够以拉动模式工作。 Bison的推入API会这样做，以便以推入模式进行操作。

但...

Bison声称具有“推” API和“推” API。但是根据上述模型，它并不是真正的“拉动” API，因为它不会从每个动作中返回（就像（f）lex扫描仪通常所做的那样）。生成允许从操作返回的代码意味着在调用该操作之前需要保存状态，因为C不允许拦截 return语句，而据我所知，bison不允许这样做。做到这一点。 （但是添加起来可能并不困难。）

另一方面，（f）lex扫描器具有几乎所有必要的状态基础结构，但有一个小问题：状态的最重要部分（即要模拟的状态机的实际状态）没有保存。结果是您只能从令牌的开头运行状态机。由于输入块不落在令牌边界上，因此，为了处理新的输入块，扫描器必须从重新扫描当前部分扫描的令牌开始。如果输入块很小，这将变得非常低效。如果提供了推入接口，则期望可以用连续的字符来调用它（以模拟交互模式），这将自动导致令牌长度的扫描时间是平方的。

实际上，这种情况实际上是在每次柔韧性扫描仪需要重新填充其缓冲区时（内部）发生的，因此，较小的缓冲区大小（或较大的令牌大小）会造成非常糟糕的性能。幸运的是，在典型的语言处理器中，这两种情况都不是正确的：令牌很小，缓冲区很大，并且很少进行重新扫描。

保存状态机的状态实际上并不困难。不这样做是为了在内部扫描循环中保存一个寄存器而作的明智选择，因为flex的原始硬件目标是缺少寄存器的机器。对于许多现代体系结构，这将不是必需的，并且消除缓冲区重新填充上的重新扫描实际上并不困难。因此，使用推入接口来生成flex版本并不难，但是据我所知，这还没有完成。