我想将 CFG 渲染为高级代码。通常这很容易；遍历树，依次渲染每个基本块，用 goto 将它们粘合在一起。
不幸的是，这些天 goto 已经过时了，大多数现代语言都不支持它们。所以我需要一些方法来将我的基本块粘合在一起，只使用语言中存在的那些控制流语句：for, while, do... while, if,break和continue. （我不愿意考虑使用变量构建状态机。）
看起来虽然有算法可以做到这一点，但它们并非在所有情况下都有效。也就是说，仅使用上述有限的一组控制流结构，就可以构建一个不能被扁平化为结构化代码的 CFG。
这对我来说似乎很直观，但我无法证明它（我发现的算法的文档没有更详细）。而且我还没有找到一个不能像这样展平的CFG的例子。
我想明确地知道这是否可能。
选项（a）：有没有人有一个如上所述不能展平的 CFG 示例？（这会告诉我这是不可能的。）
选项 (b)：是否有人证明 CFG可以如上所述被展平？（这会告诉我这是可能的。）做它的算法也是非常可取的，因为我必须让它工作......
尽管很久以前就有人问过这个问题，但这实际上似乎是可能的。Mozilla 在将 LLVM 编译为 JS（或现在的 WebAssembly）时遇到了类似的问题。JS 和 WebAssembly 只允许结构化控制流，而 LLVM 允许任意控制流。
他们为此写了一篇论文，也用于WebAssembly：
这个想法以2011年的Relooper算法为蓝本。有证据表明，任何控制流都可以结构化的方式表示，只使用 JavaScript 中可用的控制流构造，并使用像 Tilt 语义中提到的标签这样的辅助变量，没有任何代码重复（其他方法拆分节点，并且有糟糕的最坏代码大小情况）。relooper 也已在 Emscripten 中实现，在过去的 4 年中，我们获得了大量的实践经验，表明它在实践中取得了良好的效果，通常很少使用辅助变量。
我想我有结果了。
答案似乎是：不可能。这是来自ACM 通讯，第 9 卷，第 366 至 371 页，在 1966 年的一篇名为“流程图、图灵机和只有两条形成规则的语言”的论文中，作者是 Giuseppe Jacopini。CiteSeer 链接。（有趣的是，我发现引用了 Knuth 的开创性文章（从我的角度来看，这非常烦人）Go To Statement Considered Harmful。）
令人失望的是，他们没有证据，说他们找不到。
好消息是，该论文确实描述了一种将任意 CFG 转换为 CFG 的策略，该策略仅使用有限的控制流机制以有效的方式，使用尽可能少的状态。这篇论文很难写，但看起来很有希望。
通常，您不能通过遍历树来展平 CFG。如果您有 k 个前瞻标记，这将适用于 LL(k) 语法。然而，对于更复杂的文法，如 LR(k) 文法，需要更复杂的技术。例如，参见http://en.wikipedia.org/wiki/LR_parser。
一般来说，没有已知的算法可以解析任何 CFG，尽管大多数有用的 CFG 可以写成 LR(k) 语法。更多的研究对此进行了改进，并且可以解析大量的 CFG。我不认为这个问题是无法确定的（虽然我不确定），所以这当然有可能总是可以完成 - 但我认为这是一个研究问题，而不是可以回答是/否的问题你在这里。
我还应该补充一点，今天所有有价值的语言都是图灵完备的，这意味着你可以用 GOTO 做的任何事情都可以用 if/while/for/... 类型构造来完成。新语言不是限制，需要帮助的是理论构建块。
但在实践中，您将无法解析任何您想要的 CFG。但这并不意味着我们不知道将来会如何...