c – 解开Knuth结：如何重组意大利面条代码？

找到一个更好的论文,讨论如何生成结构化代码,同时保留原始控制流程图：

https://stackoverflow.com/a/36661381/120163597/1-s2.0-S01676423https://stackoverflow.com/a/36661381/120163597-main.pdf?_tid=1b75bd8c-1401-11e6-ae94-00000aab0f02&acdnat=1462590747_485d767d608ea2714e654707609910dc” rel=”nofollow noreferrer”>W.D Maurer,“Generalized structured programs and loop trees”,Science of Computer ProgrAMMing,2007

我遵循这个程序(在纸上,希望我做的对,在上午2:40看起来不错).他的基本技巧是找到强连接的区域(代码中的循环);这些将成为循环;他然后通过删除边缘来打破这个循环;这最终成为一个循环反向链接(当他完成时恢复).重复该过程,直到找不到更多的循环;剩下的是本质上是具有识别循环的结构化程序.这样做是很棘手的;你真的需要一个自动化程序.你的代码虽然很小,但仍然很糟糕： – }

我在一个地方骗了Maurer坚持认为,前进goto是可以的,甚至进入循环的中间.如果你买的话,那么你可以保存CFG.如果没有,你必须处理循环有两个或多个入口点的情况;你的算法有这样一个循环.我通过对循环进行编码来解决问题,并编写一个循环尾部片段等价物,其行为就像跳转到中间的第一个迭代,循环本身后面.

我的符号有点滑稽：大多数语言没有“块{…}”结构. [我编码的(见生物)].认为这是一个“执行一个迭代”循环： – }我假设块/循环有循环退出并循环继续.如果你没有这些,你可以用足够数量的{{}}和exiT_Block @ N来模拟它们.

编辑接受后：在光明的一天,我没有做到正确,我省略了while循环@ 3.我修补了对块构造的需求现在消失了,因为我可以退出while循环@ 3来实现相同的影响.实际上,代码读得好一点.

即使不需要数字标签,也可以放置数字标签,方便参考.

//Algorithm X;
1:
initialize();
2:
while (true) {
   enter_level(k);
   3: 
   while (true) {
      set(a[k],q);
      if (test() == ok) {
         if (k != n) exit_while@3;
         visit();
         decrease(k); // Replicate logic at 6 to avoid jumping into middle of 5 loop
         if (k==0) return;
         set(p,u_k);
      }
      5:
      while (true) {
         increasev2(a[k]);
         if (q != 0) conTinue_while@3;
         6:
         decrease(k);
         if (k==0) return;
         set(p,u_k);
      } // while(true)@5
  } // while(true)@3
  4:
  increase(k);
} // while(true)@2

与我迄今为止看到的大多数其他答案不同,它的运行速度与原始速度相同(没有额外的标志或标志检查).

@ hatchet的答案很有趣; a)同样快,b)他用相同的技术选择了两个入口循环,但他选择了“其他条目”作为循环顶点.他在标签2中做了类似于“enter_level(k)”的操作.

有趣的是,所有这些结构似乎都不能帮助这个代码的可读性.令人惊奇的是“结构化计划”的整体.也许精心设计的意大利面条不是那么糟糕： – }