将CFG展平为结构化代码

Question

我想将CFG展示给高级代码。通常这很容易;走树，依次渲染每个基本块，然后用gotos将它们粘在一起。

不幸的是，goto的都是过时的这些日子里，和最现代化的语言不支持他们。因此，我需要一些方法来使用语言中存在的那些控制流程语句将我的基本块粘合在一起：for,while,do ... while, if,break和continue。 （我不愿意考虑使用变量来构建一个状态机）。

看来虽然有算法可以做到这一点，但他们会在每种情况下都会使用而不是。也就是说，可以仅使用上述有限的控制流结构来构造不能平滑到结构化代码的CFG。

这似乎直观明显，我，但我不能证明这一点（和我发现没有进入更详细的算法文档）。而我一直无法找到一个不能像这样变平的CFG的例子。

我想知道，如果这是可能的话。

方案（a）：没有任何人有如上所述不能被扁平化CFG的实例？ （这会告诉我这是不可能的。）

选项（b）：是否有人证明CFGs 可以如上所述变平？ （这会告诉我，它是可能）。一个算法做到这一点也是非常可取的，因为我将不得不使它工作...

Answer 1

我想我有一个结果。

答案似乎是：这是不可能的。这是从1996年由Giuseppe Jacopini所着的名为“Flow Diagrams，Turing Machines and Languages with only Two Formation Rules”的论文中的ACM的第9卷第366至371页的通信。 CiteSeer link.（其中，有趣的是，我发现从Knuth的精液（和，从我的角度来看，令人难以置信的烦人） goto语句是有害的引用。）

令人失望的是，他们没有证据，说他们无法找到一个。

好消息是，本文确实描述了一种策略，即只使用有限的控制流机制以尽可能少的状态将任意CFG转换为CFG。这篇论文很难，但看起来很有希望。

Answer 2

一般来说，你不能只是变平通过走树的CFG。如果您有k个预读令牌，这将适用于LL（k）语法。但是，对于更复杂的语法，比如LR（k）语法，需要更复杂的技术。例如参见http://en.wikipedia.org/wiki/LR_parser。

一般来说，没有已知的算法解析ANY CFG，尽管是可以写为一个LR（k）文法有用最CFGS。更多的研究对此进行了改进，并且可以分析大量的CFG。我不认为这个问题是不可判定的（尽管我不确定），所以这当然可以做到这一点 - 但我认为这是一个研究问题，而不是回答是/否你在这里。

我还要补充一点，今天的一切都是值得的语言是图灵完备的，这意味着什么，你可以做GOTO语句可以用，如果做/而/为/ ...型结构。新语言不是限制，它是需要帮助的理论基石。

实际上，你将无法解析任何你想要的CFG。但是，这并不意味着我们不会知道未来如何...

Answer 3

虽然这个问题很久以前就被问过了，但实际上这似乎是可能的。编译LLVM到JS（或现在的WebAssembly）时，Mozilla有类似的问题。 JS和WebAssembly仅允许结构化控制流程，而LLVM允许任意控制流程。

They'v写这里面也用于WebAssembly纸：

这个想法是从2011的Relooper算法建模。有证据表明，任何控制流都可以用结构化的方式表示，仅使用JavaScript中可用的控制流构造，并使用像Tilt语义中提到的标签这样的辅助变量，而不用任何代码重复（其他方法分离节点，并且具有不好的最坏情况码尺寸情况）。 emscripten也实现了relooper，在过去的4年中，我们已经获得了大量的实践经验，表明它在实践中给出了很好的结果，通常很少使用helper变量。