將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變量。