如何将流程图转化为实现？
How to transform a flow chart into an implementation?
编辑：简介
为了接触更广泛的读者群，我通过一个详尽（且有些乏味）的现实生活中的例子重新表述了我最初的问题。原始问题如下（远）所示。
Tom 刚刚被 Acme Inc. 聘为初级软件工程师（取决于他在头两个工作日的表现）。他的工作是用编程语言 Acme++ 实现高级软件开发人员设计的算法。根据 CEO 的独家命令，公司遵循严格的 "no 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 觉得这项任务非常复杂，他认为通过将其表示为流程图来研究程序的抽象结构会对他有所帮助。在画出下图后 Flow chart of day one 他很快意识到，他被要求计算 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，新手，又觉得还是抽象的理解算法比较好，于是画了下面的流程图Flow chart of day two.
检查流程图后发现，Tom 被要求实现一个等待第一个非负输入的 while 循环。汤姆很高兴，并在一天结束时完成了他的任务。
基于他出色的表现，汤姆被公司录用了。
然而，在第 3 天，Tom 被扔进了深渊，因为他收到了一个 1000 行的算法，有 1996 次 goto 跳转，由公司的一名前雇员设计，没有其他人留在那里谁会知道算法做什么，它是如何做的，以及为什么首先要以这种方式设计它。然而，这与 Tom 完全无关，因为他唯一的任务就是实现算法，而不管算法是什么。凭借前两天的专业知识，他在具有 1997 个有向边的 1000 个节点上绘制了流程图。 Tom 非常绝望，他在 Whosebug 上询问如何处理这样的烂摊子，有经验的程序员反复建议他
- 将程序分解成更小的部分；和
- 他确信在某些情况下使用
goto 实际上是可以的；
- 他被告知 "restructure" 程序。
汤姆非常勤奋，考虑了这些建议，他的想法如下：
- 他意识到，如果流图的连通分量恰好有一个入度和恰好一个出度，那么就可以认为是一个可以独立开发的"sub-algorithm"，所以他可以以这种方式分解他的任务。然而，他不知道如何首先找到这些组件，也不知道是否有其他智能方法可以进一步分解问题。
- Tom 并不真正关心使用
goto 是好还是坏的编程习惯（参见 GOTO still considered harmful?），他关心的是他的公司有某些编程指南他需要始终遵循的内容。
- Tom 确实可以接触算法，因为他可以自行决定替换某些导致等效算法的指令。然而，Tom 不知道程序的哪一部分需要重组，更重要的是，他不明白为什么需要重组。汤姆紧张地盯着他的 1000 顶点图，一开始并不知道如何开始实施它。
关于这个（已编辑）post的问题如下：
你能帮助 Tom 弄清楚如何开始实施不是 "two-line-dead-obvious" 的东西吗？特别是，是否清楚应该以什么顺序执行流程图节点描述的任务？是否清楚某些嵌套循环应该以什么顺序依次出现？
流程图中最小的 "atoms" 不能进一步分解成更小的部分是什么？也就是Tom什么时候才能自信的回复那个"I have broken up my algorithm into smaller parts already"的Whosebug？是不是一切本质上都是while循环and/or二元分支点（第一天和第二天的任务）？
如何自动实现这样的 "atom"，或多或少与 Tom 在第一天和第二天所做的相同？
Tom 能否与 CEO 争辩说在某些情况下使用 goto 是必不可少的，也就是说，他们要么用它来实现某种算法，要么根据公司的规定绝对没有其他方法可以实现它准则（即不使用 goto）？
流程图的哪些部分存在问题并需要重组，为什么？例如，一个三向分支可以被一个嵌套的双向 if-then-else 语句代替，也就是说，Tom 可以安全地假设他的流程图上的每个节点的出度至多为 2。但是还应该进行哪些其他重组来处理由 goto 语句引起的所有嵌套循环？什么图-属性 使重组成为必要？也许，高学历？
最初提出的算法流程图背后的数学（图）理论是什么（软件开发组），以及算法的重组和分解流程图（ s) 哪一个（比如汤姆）实际上或多或少自动实现了？
原始问题
假设我有一些使用二元决策和 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 循环替换它们？如果是这样，一般应该如何做 ?
根据算法的描述，可以构建相应的流程图，从而构建（有向）流程图。所以问题换句话说就是"How to implement a code based on its flow chart without goto statements in general?".
有两种方法可以回答这个问题。最好，并且非常希望，我正在寻找一种算法方法来实现 ALGORITHM WHATEVER。如果 ALGORITHM WHATEVER 非常 简单，那么直觉上应该做什么很清楚，但在我看来，一旦频繁访问步骤，事情就会变得相当复杂（有很多 goto 语句跳转那里），或者换句话说，当流图的节点之一具有大入度时。然后我不太明白应该以什么特定顺序嵌套 while 循环。另一方面，很可能一个人根本不能做我想做的事情，这样的答案应该得到 ALGORITHM IMPOSSIBLE 的高级描述的支持，它清楚地表明无论如何，一个人根本不能避免在实际实现中使用 goto 跳转。
在我看来，将实施转化为流程图被问了好几次：Automatic flowchart tool and here Algorithm to create flow chart [A little guidance??]. The program code2flow 似乎是可视化代码的一个很好的起点。
不过，这里我感兴趣的是另一个方向。一个简单的搜索显示 DRAKON (see also https://en.wikipedia.org/wiki/DRAKON and http://drakon-editor.sourceforge.net/) 可能正是我所询问的。从这个角度来看，问题是，在不使用 goto 语句的额外假设下，这样一个自动流程图到代码的程序如何工作？
如果我们将 ALGORITHM WHATEVER 中的每个 "Do something" 语句视为返回 TRUE 或 FALSE 的函数，您可以执行如下操作（伪代码）：
Let N be an int
curr_state be an int
T[1..N] be an array of ints
F[1..N] be an array of ints
Func[1..N] be an array of functions returning booleans
1. curr_state := 1
2. while curr_state != N+1 do /* end state */
3. if (Func[curr_state] == TRUE) then
4. curr_state := T[curr_state]
5. else
6. curr_state := F[curr_state]
7. fi
8. od
有人可能会问，"But what if the functions take arguments or need to modify some shared state?"原则上，函数参数和共享状态都可以存储在全局变量中（在您的算法范围内）。实际上，您可能会做一些稍微不同的事情。
嵌入式软件社区一直在使用此类工具并取得了不同程度的成功。我不再开发那种软件了，但是 10 年前有 Rational Rose RT（我想 IBM 已经买断了它们）、MATLAB Simulink、MATLAB Real-time Workshop 等等。他们会采用各种类型的图形输入（无论是 class 图、状态图还是流程图）并生成 C++ 代码。
您描述示例的方式不完全确定您是在描述状态转换原子仅取决于观察到的状态（这是流程图的工作方式）的有限状态机，还是您'更多地描述了一个专家系统，其中过渡项不仅关心观察到的状态，还关心在到达该状态之前发生了什么过渡。
如果您描述的是前者，那么您需要做的就是注意您的转到标签本身就是状态。流程图中的每个决策块都成为一个状态转换函数，它作用于某些信息域并在完成时设置一个新状态。新状态可能是 "END" 或其他。信息域通常在所有状态转换函数之间共享（即共享内存）。软件实现通常是命令设计模式 (GoF) 的一些变体。
如果您描述的是后者，请查看 Rete 算法。 Rete 算法是一种优化的通用算法，用于实现任何专家系统的规则手册。
引用 OP：最好，并且非常希望，我正在寻找一种算法方法来实现 ALGORITHM WHATEVER
嗯，显而易见的答案是用目标语言为算法的每个步骤定义一个标签，在该标签处为每个步骤编写代码，并完全按照 ALGORITHM WHATEVER 描述插入 GOTO 语句。这将为您提供一个大多数会调用 "spaghetti code".
的工作程序
OP 有一个长篇大论的介绍，表明他（或者可能是汤姆）更愿意以一种令人信服地匹配任何算法的方式编写无转到版本。
好吧，好消息是 Bohm and Jocopini 很久以前表明您可以仅使用 sequence、[= 的三个基本控制流操作来实现任何计算36=]if-then-else 和 while 循环 ，具有单进单出的优点 属性。所以我们知道有一个 "structured program" 实现。
不太好的消息是他们的建设性证明（从 gotoful/flowchart 版本构建此类程序的过程）引入了一组布尔变量和额外的测试来控制循环。这些变量用于跳过循环迭代的剩余部分，强制退出循环，并告诉循环调用者循环已退出。这个额外的
对我来说，代码会使生成的程序更难阅读，即使您不反对管理这些变量所需的存储和执行时间。 （有关针对 goto-ful COBOL 程序执行此操作的算法，请参阅维基百科 link）。
更好的消息是，S. Rao Kosaraju 证明了如果可以跳出任意嵌套深度的循环，则可以在没有额外控制变量的情况下构建此类程序。许多编程语言都提供这样的功能； C 提供了一个脆弱的版本，它的 "break N;" 语句打破了 N 个嵌套循环 [当有人在现有代码中插入一个额外的循环并且没有注意到 break 语句时，使用这个著名的崩溃的东海岸 AT&T 电话系统] . Ada 和其他语言允许标记循环，本质上 "leave " 以指定的标签名称离开循环。对我来说，这是一个很好的解决方案。 [我更喜欢一种变体，其中一个变体有一个标记的开始结束块，可以是 "leave"d。
如果您的语言没有这样的带标签的 leave 结构，但您愿意以风格认可的方式（而不是临时方式）使用 GOTO 语句，您可以通过放置一个标签 after[= 来模拟 leave 语句39=] 每个循环并写 "goto " 而不是离开。
因此，我们知道可以从任意 flowchart/gotoful 干净的程序构建结构化程序。
按照 Sue Graham 1975 年的论文，将原始流程图简化为结构化子元素的算法可以做到这一点，
A fast and usually linear algorithm for global flow analysis.
该算法的本质是在可能的情况下逐步将原始流程图缩减为Bohm/Jacopini原语（sequence/if-then-else/loop）构造，并减少"non-reducible"构造（想想一个小结在流程图中）看起来不像这些以特殊方式。在每个步骤中，流程图的一部分都被缩减为该部分的单个摘要节点。最终，这个过程将任意复杂的原始流程图简化为单个节点。此时，归约过程可以运行逆向进行，将每个汇总节点展开回原来的。
对于 OP 的目的，摘要节点的扩展是一个以结构化方式为减少的子图编写代码的机会。如此反复，直到产生原始流程图，然后整个程序就写成了结构化的。
[今天就到这里。让我们看看我是否可以产生一个算法。观看这个 space]。
编辑：简介
为了接触更广泛的读者群，我通过一个详尽（且有些乏味）的现实生活中的例子重新表述了我最初的问题。原始问题如下（远）所示。
Tom 刚刚被 Acme Inc. 聘为初级软件工程师（取决于他在头两个工作日的表现）。他的工作是用编程语言 Acme++ 实现高级软件开发人员设计的算法。根据 CEO 的独家命令，公司遵循严格的 "no 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 觉得这项任务非常复杂，他认为通过将其表示为流程图来研究程序的抽象结构会对他有所帮助。在画出下图后 Flow chart of day one 他很快意识到，他被要求计算 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，新手，又觉得还是抽象的理解算法比较好，于是画了下面的流程图Flow chart of day two.
检查流程图后发现，Tom 被要求实现一个等待第一个非负输入的 while 循环。汤姆很高兴，并在一天结束时完成了他的任务。
基于他出色的表现，汤姆被公司录用了。
然而，在第 3 天，Tom 被扔进了深渊，因为他收到了一个 1000 行的算法，有 1996 次 goto 跳转，由公司的一名前雇员设计，没有其他人留在那里谁会知道算法做什么，它是如何做的，以及为什么首先要以这种方式设计它。然而，这与 Tom 完全无关，因为他唯一的任务就是实现算法，而不管算法是什么。凭借前两天的专业知识，他在具有 1997 个有向边的 1000 个节点上绘制了流程图。 Tom 非常绝望，他在 Whosebug 上询问如何处理这样的烂摊子，有经验的程序员反复建议他
- 将程序分解成更小的部分；和
- 他确信在某些情况下使用
goto实际上是可以的； - 他被告知 "restructure" 程序。
汤姆非常勤奋，考虑了这些建议，他的想法如下：
- 他意识到，如果流图的连通分量恰好有一个入度和恰好一个出度，那么就可以认为是一个可以独立开发的"sub-algorithm"，所以他可以以这种方式分解他的任务。然而，他不知道如何首先找到这些组件，也不知道是否有其他智能方法可以进一步分解问题。
- Tom 并不真正关心使用
goto是好还是坏的编程习惯（参见 GOTO still considered harmful?），他关心的是他的公司有某些编程指南他需要始终遵循的内容。 - Tom 确实可以接触算法，因为他可以自行决定替换某些导致等效算法的指令。然而，Tom 不知道程序的哪一部分需要重组，更重要的是，他不明白为什么需要重组。汤姆紧张地盯着他的 1000 顶点图，一开始并不知道如何开始实施它。
关于这个（已编辑）post的问题如下：
你能帮助 Tom 弄清楚如何开始实施不是 "two-line-dead-obvious" 的东西吗？特别是，是否清楚应该以什么顺序执行流程图节点描述的任务？是否清楚某些嵌套循环应该以什么顺序依次出现？
流程图中最小的 "atoms" 不能进一步分解成更小的部分是什么？也就是Tom什么时候才能自信的回复那个"I have broken up my algorithm into smaller parts already"的Whosebug？是不是一切本质上都是while循环and/or二元分支点（第一天和第二天的任务）？
如何自动实现这样的 "atom"，或多或少与 Tom 在第一天和第二天所做的相同？
Tom 能否与 CEO 争辩说在某些情况下使用 goto 是必不可少的，也就是说，他们要么用它来实现某种算法，要么根据公司的规定绝对没有其他方法可以实现它准则（即不使用 goto）？
流程图的哪些部分存在问题并需要重组，为什么？例如，一个三向分支可以被一个嵌套的双向 if-then-else 语句代替，也就是说，Tom 可以安全地假设他的流程图上的每个节点的出度至多为 2。但是还应该进行哪些其他重组来处理由 goto 语句引起的所有嵌套循环？什么图-属性 使重组成为必要？也许，高学历？
最初提出的算法流程图背后的数学（图）理论是什么（软件开发组），以及算法的重组和分解流程图（ s) 哪一个（比如汤姆）实际上或多或少自动实现了？
原始问题
假设我有一些使用二元决策和 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 循环替换它们？如果是这样，一般应该如何做 ?
根据算法的描述，可以构建相应的流程图，从而构建（有向）流程图。所以问题换句话说就是"How to implement a code based on its flow chart without goto statements in general?".
有两种方法可以回答这个问题。最好，并且非常希望，我正在寻找一种算法方法来实现 ALGORITHM WHATEVER。如果 ALGORITHM WHATEVER 非常 简单，那么直觉上应该做什么很清楚，但在我看来，一旦频繁访问步骤，事情就会变得相当复杂（有很多 goto 语句跳转那里），或者换句话说，当流图的节点之一具有大入度时。然后我不太明白应该以什么特定顺序嵌套 while 循环。另一方面，很可能一个人根本不能做我想做的事情，这样的答案应该得到 ALGORITHM IMPOSSIBLE 的高级描述的支持，它清楚地表明无论如何，一个人根本不能避免在实际实现中使用 goto 跳转。
在我看来，将实施转化为流程图被问了好几次：Automatic flowchart tool and here Algorithm to create flow chart [A little guidance??]. The program code2flow 似乎是可视化代码的一个很好的起点。
不过，这里我感兴趣的是另一个方向。一个简单的搜索显示 DRAKON (see also https://en.wikipedia.org/wiki/DRAKON and http://drakon-editor.sourceforge.net/) 可能正是我所询问的。从这个角度来看，问题是，在不使用 goto 语句的额外假设下，这样一个自动流程图到代码的程序如何工作？
如果我们将 ALGORITHM WHATEVER 中的每个 "Do something" 语句视为返回 TRUE 或 FALSE 的函数，您可以执行如下操作（伪代码）：
Let N be an int
curr_state be an int
T[1..N] be an array of ints
F[1..N] be an array of ints
Func[1..N] be an array of functions returning booleans
1. curr_state := 1
2. while curr_state != N+1 do /* end state */
3. if (Func[curr_state] == TRUE) then
4. curr_state := T[curr_state]
5. else
6. curr_state := F[curr_state]
7. fi
8. od
有人可能会问，"But what if the functions take arguments or need to modify some shared state?"原则上，函数参数和共享状态都可以存储在全局变量中（在您的算法范围内）。实际上，您可能会做一些稍微不同的事情。
嵌入式软件社区一直在使用此类工具并取得了不同程度的成功。我不再开发那种软件了，但是 10 年前有 Rational Rose RT（我想 IBM 已经买断了它们）、MATLAB Simulink、MATLAB Real-time Workshop 等等。他们会采用各种类型的图形输入（无论是 class 图、状态图还是流程图）并生成 C++ 代码。
您描述示例的方式不完全确定您是在描述状态转换原子仅取决于观察到的状态（这是流程图的工作方式）的有限状态机，还是您'更多地描述了一个专家系统，其中过渡项不仅关心观察到的状态，还关心在到达该状态之前发生了什么过渡。
如果您描述的是前者，那么您需要做的就是注意您的转到标签本身就是状态。流程图中的每个决策块都成为一个状态转换函数，它作用于某些信息域并在完成时设置一个新状态。新状态可能是 "END" 或其他。信息域通常在所有状态转换函数之间共享（即共享内存）。软件实现通常是命令设计模式 (GoF) 的一些变体。
如果您描述的是后者，请查看 Rete 算法。 Rete 算法是一种优化的通用算法，用于实现任何专家系统的规则手册。
引用 OP：最好，并且非常希望，我正在寻找一种算法方法来实现 ALGORITHM WHATEVER
嗯，显而易见的答案是用目标语言为算法的每个步骤定义一个标签，在该标签处为每个步骤编写代码，并完全按照 ALGORITHM WHATEVER 描述插入 GOTO 语句。这将为您提供一个大多数会调用 "spaghetti code".
的工作程序OP 有一个长篇大论的介绍，表明他（或者可能是汤姆）更愿意以一种令人信服地匹配任何算法的方式编写无转到版本。
好吧，好消息是 Bohm and Jocopini 很久以前表明您可以仅使用 sequence、[= 的三个基本控制流操作来实现任何计算36=]if-then-else 和 while 循环 ，具有单进单出的优点 属性。所以我们知道有一个 "structured program" 实现。
不太好的消息是他们的建设性证明（从 gotoful/flowchart 版本构建此类程序的过程）引入了一组布尔变量和额外的测试来控制循环。这些变量用于跳过循环迭代的剩余部分，强制退出循环，并告诉循环调用者循环已退出。这个额外的 对我来说，代码会使生成的程序更难阅读，即使您不反对管理这些变量所需的存储和执行时间。 （有关针对 goto-ful COBOL 程序执行此操作的算法，请参阅维基百科 link）。
更好的消息是，S. Rao Kosaraju 证明了如果可以跳出任意嵌套深度的循环，则可以在没有额外控制变量的情况下构建此类程序。许多编程语言都提供这样的功能； C 提供了一个脆弱的版本，它的 "break N;" 语句打破了 N 个嵌套循环 [当有人在现有代码中插入一个额外的循环并且没有注意到 break 语句时，使用这个著名的崩溃的东海岸 AT&T 电话系统] . Ada 和其他语言允许标记循环，本质上 "leave " 以指定的标签名称离开循环。对我来说，这是一个很好的解决方案。 [我更喜欢一种变体，其中一个变体有一个标记的开始结束块，可以是 "leave"d。 如果您的语言没有这样的带标签的 leave 结构，但您愿意以风格认可的方式（而不是临时方式）使用 GOTO 语句，您可以通过放置一个标签 after[= 来模拟 leave 语句39=] 每个循环并写 "goto " 而不是离开。
因此，我们知道可以从任意 flowchart/gotoful 干净的程序构建结构化程序。
按照 Sue Graham 1975 年的论文，将原始流程图简化为结构化子元素的算法可以做到这一点， A fast and usually linear algorithm for global flow analysis.
该算法的本质是在可能的情况下逐步将原始流程图缩减为Bohm/Jacopini原语（sequence/if-then-else/loop）构造，并减少"non-reducible"构造（想想一个小结在流程图中）看起来不像这些以特殊方式。在每个步骤中，流程图的一部分都被缩减为该部分的单个摘要节点。最终，这个过程将任意复杂的原始流程图简化为单个节点。此时，归约过程可以运行逆向进行，将每个汇总节点展开回原来的。
对于 OP 的目的，摘要节点的扩展是一个以结构化方式为减少的子图编写代码的机会。如此反复，直到产生原始流程图，然后整个程序就写成了结构化的。
[今天就到这里。让我们看看我是否可以产生一个算法。观看这个 space]。