Mat*_*ath 4 compiler-construction algorithm math build-automation
为了扩大读者群，我通过一个详尽的（有些乏味的）现实生活例子重新阐述了我的原始问题。原始问题显示在下面。
Tom刚被聘为Acme Inc.（根据其前两个工作日的表现）担任初级软件工程师。他的工作是用编程语言Acme ++实现由高级软件开发人员设计的算法。公司按照goto首席执行官的独裁命令执行严格的“不”政策。如果汤姆在试用期内表现出色，他将在公司担任全职工作。
在第1天，Tom收到以下要实施的算法。
Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 4 otherwise goto Step 5
Step 4. Set x=-x
Step 5. Output x
Step 6. END
Tom认为任务非常复杂，他认为通过将其表示为流程图，可以从研究程序的抽象结构中受益。在绘制了下图第一天的流程图后，他很快意识到，他被要求计算x的绝对值，并且他可以使用简单的if-then-else语句来实现它。汤姆很高兴，他在一天结束时完成了任务。
在第2天，Tom收到以下要实施的算法。
Step 1. START
Step 2. Input x
Step 3. In case x<0 goto Step 2 otherwise goto Step 4
Step 4. Output x
Step 5. END
作为新手，汤姆再次感到最好还是以抽象的方式理解该算法，因此他绘制了以下流程图第二天的流程图。
对流程图的检查表明，Tom被要求执行一个while循环，以等待第一个非负输入。汤姆很高兴，并在一天结束时完成了任务。
基于他出色的表现，汤姆已被公司聘用。
但是，在第3天，汤姆就陷入了深渊，因为他收到了goto由公司前雇员设计的1996年跳高的1000行算法，并且没有其他人知道算法的作用，它是如何做到的，以及为什么首先要以这种方式设计它。但是，这与Tom完全无关，因为他的唯一任务是不管算法是什么都实现该算法。凭借前两天的专业知识，他在具有1997个有向边的1000个节点上绘制了流程图。汤姆非常绝望，他在stackoverflow上询问如何处理这种混乱，有经验的程序员反复建议他这样做。
goto; 和汤姆非常勤奋，考虑了这些建议，他的想法如下：
goto编程是好是坏（请参阅GOTO仍然被认为有害吗？），他担心的是他的公司始终需要遵循某些编程准则。您可以帮助Tom弄清楚如何开始实施“两线制不明显”的东西吗？特别是，显然应该按照什么顺序执行流程图各节点所描述的任务？显然，某些嵌套循环应该以什么顺序依次出现？
流程图中最小的“原子”是什么，这些原子不能进一步分解为较小的部分？也就是说，Tom何时可以自信地对stackoverflow做出回应，“我已经将算法分解成更小的部分”？是否所有内容本质上都是while循环和/或二进制分支点（第一天和第二天的任务）吗？
如何像汤姆在第一天和第二天那样自动地或多或少地自动实现这种“原子”？
汤姆（Tom）能否与首席执行官争辩说goto在某些情况下使用是必不可少的，也就是说，他们要么使用它来实现某种算法，要么完全没有其他方法可以按照公司的准则来实现（即，不使用goto） ？
流程图的哪些部分存在问题，需要进行重组，为什么？例如，三路分支可以用嵌套的两路if-then-else语句代替，也就是说，Tom可以安全地假定流程图中的每个节点的出节点数最多为2。但是，应该采取什么其他重组措施来处理由goto语句引起的所有嵌套循环呢？什么样的图形属性使重组成为必要？也许，学位高？
最初提出的算法（由软件开发团队）的流程图背后的数学（图形）理论是什么，以及该算法的重组和分解流程图（实际上是Tom所说的更多） -或更少自动实现？
假设我有一些使用二进制决策和goto语句的算法。以以下高级方式在N> = 2（有限）步中描述该算法，并且应按顺序执行（一个步骤一个接一个）：
不论什么算法
Step 1. START
Step 2. Do something. If condition in Step 2 holds goto Step X else goto Step Y.
Step 3. Do something. If condition in Step 3 holds goto Step U else goto Step V.
Step 4. Do something.
Step 5. Do something. If condition in Step 5 holds goto...
Step 6. ...
...
Step N. END
你明白了。例如，Knuth以这种与编程语言无关的高级方式在他的书中描述了算法。
现在的问题是，如何将带有goto语句的高级描述转换为带有while循环和if / else语句的实际实现？是否可以完全消除所有goto语句，并用while循环替换它们？如果是这样，一般应该怎么做？
基于算法的描述，可以构造相应的流程图，从而构造（定向）流程图。因此，换句话说，问题是“如何实现基于其流程图上无码goto语句一般？”。
有两种方法可以回答这个问题。最好且非常有希望的是，我正在寻找一种算法方法来实现算法。如果ALGORITHM WHATEVER 非常简单，则可以直观地看出应该做什么，但是在我看来，一旦经常访问某个步骤（其中有许多goto语句在其中跳跃），或者换句话说，当流程图的节点之一具有较大的度数。然后，我不太清楚while循环应该以什么特定顺序嵌套。另一方面，一个人很可能根本无法完成我通常想要的事情，而这样的回答应该得到对算法不可能的高级描述的支持，该描述清楚地表明，无论如何，一个人根本无法做到避免使用goto 跳入实际的实现。
在我看来，将实现转换为流程图的要求有几次：自动流程图工具和此处创建流程图的算法[一点指导？]。程序code2flow似乎是可视化代码的良好起点。
但是，我对另一个方向感兴趣。一个简单的搜索显示DRAKON（另请参阅https://en.wikipedia.org/wiki/DRAKON和http://drakon-editor.sourceforge.net/）可能完全在执行我要问的事情。从这个角度来看，问题是，在不使用该goto语句的额外假设下，这种自动流程图到代码程序将如何工作？
引用OP：最好，并且非常有希望，我正在寻找一种算法方法来实现任何算法
好吧，最明显的答案是用目标语言为算法的每个步骤定义一个标签，在该标签上为每个步骤编写代码，并按照算法所描述的完全插入GOTO语句。这将为您提供一个工作程序，大多数人将其称为“意大利面条代码”。
OP进行了冗长的介绍，暗示他（或者可能是Tom）宁愿以令人信服的匹配算法的方式编写goto-free版本。
好的，所以好消息是Bohm和Jocopini早就表明您可以使用sequence，if-then-else和while循环这三个基本控制流操作来实现任何计算，并且具有单项输入的好特性。 ，一次退出。因此，我们知道有一个“结构化程序”实现。
不好的消息是它们的构造性证明（从gotoful /流程图的版本构建此类程序的过程）引入了一组布尔变量和其他测试来控制循环。这些变量用于跳过循环迭代的其余部分，以强制退出循环，并告知循环调用者循环已退出。对我来说，这些额外的代码使所生成的程序在读取时有些糟糕，即使您不反对管理这些变量所需的存储和执行时间。（请参阅Wikipedia链接以获取针对goto-ful COBOL程序执行此操作的算法）。
更好的消息是，S。Rao Kosaraju证明，如果您可以摆脱任意嵌套深度的循环，则无需额外的控制变量即可构建此类程序。许多编程语言都提供了这种功能。C提供了一个脆弱的版本，其“ break N”；从N个嵌套循环中跳出的语句（当有人在现有代码中插入一个额外的循环而没有注意到break语句时，使用此著名的AT＆T崩溃的东海岸电话系统）。Ada和其他语言允许人们给循环加上标签，实际上是“ leave”以指定的标签名称离开循环。对我来说，这是一个不错的解决方案。[我更喜欢一种变体，其中有一个带有标签的开始-结束块，可以“离开”。如果您的语言没有这种标记离开的构造，在每个循环之后，写“ goto”而不是请假。
因此，我们知道可以从干净的任意流程图/有信用的程序中构建结构化程序。
为此，有一种算法可以按照Sue Graham 1975年的论文《一种快速且通常为线性的全局流分析算法》将原始流程图简化为结构化的子元素 。
该算法的本质是在可能的情况下，逐步将原始流程图逐步简化为Bohm / Jacopini原语（序列/ if-then-else / loop）构造，并减少“不可归约”构造（以流程图中的小结为例） ）看起来并不特殊。在每个步骤中，流程图的一部分都被简化为该部分的单个摘要节点。最终，此过程将任意复杂度的原始流程图简化为单个节点。此时，还原过程可以反向运行，每个摘要节点都可以扩展回原始节点。
出于OP的目的，摘要节点的扩展提供了以结构化方式编写简化子图代码的机会。重复进行直到产生原始流程图，然后使整个程序以结构化的方式编写。
[今天就这些。让我们看看我是否可以产生一个算法。关注此空间]。