15A: 程序终止的测定

练习15A、15B和15C不分先后学习顺序。

在这一课中，你将完成一个长而复杂的问题，我们已经把它分解成了几个部分，所以可以分部完成。本课还将介绍str.split()，它是一个有用的分割字符串的方法：删除所有的空格，然后返还一个字符串中所有单词的序列，并且原始字符串不会被修改。

示例
str.split()的例子

你可以调用split()并加上特殊的参数来做更复杂的分割，但目前我们不需要这么做。如果感兴趣的话，可以查看一下Python文档.

现在我们需要完成第一步。旧的编程语言 BASIC 因其带有编号的代码行和goto语句而出名。对于这个练习，你将创建一个带有下面这些功能的BASIC简单版。具体来说，程序的输入将由下面格式中的几行组成

«label» goto «target»

«label»和«target»都是正整数。label（标签）就像是这一行的名字或者地址；所有的标签都是唯一的。target（目标）会告诉你需要移动到的下一行代码的标签是什么。程序的最后一行是«label» END，表明一旦运行到这一行，程序就应该停止。下面是一个BASIC程序的示例：

5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END
当这个BASIC程序运行时，我们在第一行（标签5）处开始。标签5这行代码的目标是30，所以下一步我们前往标签为30的这一行。然后30这一行告诉我们去标签为40的代码行。最后这行代码告诉我们程序结束。所以，程序就终止了。

另一方面，一个BASIC程序也可以循环。这里是一个例子：

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END
该程序在第10行开始，但它会永远在21和37行之间循环。

你的任务 是要编写一个Python程序, 它可以读入一个BASIC程序作为输入。如果程序终止，你的程序应该打印success。如果程序进入一个无限循环，程序应该打印infinite loop。假设每个目标都有有效的标签，所有的标签都是独一无二的。所以不必检查。
有几种不同的方法可以做到这一点。但在这一课中，我们选择一个简单的方法，并把它分解成3个子任务（课程15C中有一个比较大的问题，你需要自己设计子任务）。

子任务1: 读取程序

想要读取BASIC程序，我们需要不停地调用input()。但是，当我们达到最后一行BASIC代码(带有END的那一行)的时候，我们要停止调用input()来避免EOFError。

编程练习: 读取程序
编写一个没有实参的函数 getBASIC()，使它能够做下列这些: 使用while循环来持续阅读输入的每一行；当它结束时，返回一个字符串列表形式的整体程序。(提示: 关于 列表 和 结束)

子任务2: Go to it!

一旦读取了这个程序，我们就需要能够在程序中跳跃到另一行。要做到这一点，你需要完成以下子程序。

编程练习: Go to it!
定义一个函数findLine(prog, target) 来完成下面这些内容。假设prog 是一个含有BASIC程序的字符串列表，与getBASIC()生成的类型一样; 假设 target 是一个包含一个代码行标签的字符串，它会是一个GOTO语句的target（目标）。这个函数应该返还索引i (一个 0 到 len(prog)-1之间的整数)使得prog[i] 成为标签等于 target的这一行。提示 
输入/输出 示例: 如果你调用

findLine(['10 GOTO 20','20 END'], '10')
那么输出应该是 0，因为列表中项目0是标签为10的这一行代码。

子任务3: 智能模拟

在前两个练习中，我们完成了输入程序和搜寻任务。这将有助于主程序的编写并使
其更加简练。然而，仍然有一个主要的问题要解决：如何才能真正解决最初的问题？最简单的方法是模拟BASIC程序的运行：

  • 让 prog 作为BASIC程序 (一个字符串列表)
  • 开始名为location的计数变量；因为我们是从程序的第一行开始，所以设定初始值为0
  • 正确时,
    • 如果prog[location]是结束行，返还"success"并终止。
    • 让 T 作为在prog[location]中指出的目标字符串
    • 让findLine(prog, T)作为location的新值

但是还有一个主要问题没有解决：无法检测无限循环，如果BASIC程序有一个无限循环，那么Python程序也将永远循环。而我们想要的是：在这种情况下，该程序打印“无限循环”。我们把这个问题留给你解决，但是会给你一个提示。

编程练习: Smart Simulation
编写一个函数 execute(prog) 来完成下列这些事。和前面一样，假设 prog 是一个含有BASIC程序的字符串列表。然后取决于程序是否终止或循环，程序应该返还 "success" 或者 "infinite loop"。重要信息: 假设这个函数findLine(prog, target) 的定义在子任务2中已经定义好了，不需要重新编写。 提示

整合

要测试你的代码，复制并粘贴你以前的答案到下面的模板中。

编程练习: BASIC模拟器
把你的BASIC模拟器“组装”好。

如果你使用的编程语言再稍微复杂一点，那么你是不可能写出一个关于这个语言的终止检查程序的。这是计算机科学中最早的一个重要定理，这个定理在19世纪30年代被艾伦-图灵证明，现在人们将这个结果称为"这个停机问题是不可判定的。"