Forth中的有限状态机（1994）

# Forth 中的有限状态机 Source: https://www.forth.org/literature/noble.html **J\.V\. Noble** 核物理与粒子物理研究所 弗吉尼亚大学 夏洛茨维尔，弗吉尼亚州 22901 ### 摘要 > 本笔记提供了在 Forth 中构造确定性和非确定性有限状态自动机的方法。“最佳”方法能在定义与自动机状态表之间建立一一对应关系。该方法的一个重要特点是无需（慢速的）嵌套 IF 子句。 ### 引言 某些编程问题即使使用结构化代码也很难用过程式方法解决，但使用抽象有限状态机（FSM）[1] 却很简单。例如，编译器必须区分表示浮点数的文本字符串和可能以相似顺序包含相似字符的代数表达式。或者，机器控制器必须对以随机顺序出现的预定输入选择响应。这类问题之所以有趣，是因为一个响应不定输入的程序比单纯的顺序程序更接近“思维机器”。因此，表示浮点数的字符串由一组规则定义；它既没有确定的长度，符号也不是按确定顺序出现。更糟的是，同一个数字可能允许多种形式——用户友好性要求格式具有一定灵活性。虽然可以通过逻辑表达式（即拼接足够多的 IF、ELSE 和 THEN）来实现通用模式识别，但生成的代码通常难以阅读、调试或修改。更糟的是，无论代码布局多么“漂亮”，这种方法都毫无结构性可言：缩进只能做到这种程度。而且，主要由逻辑表达式组成的程序可能很慢，因为许多处理器在分支时会清空流水线[2]。嵌套 IF 方法的这些缺陷，从大量用于克服它们的商业工具中可见一斑：Stirling Castle 的 Logic Gem（转换并简化逻辑表达式）、Matrix Software 的 Matrix Layout（将 FSM 的表格表示转换为 BASIC、Modula-2、Pascal 或 C 等语言），以及 AYECO, Inc. 的 COMPEDITOR（执行类似的转换）。[这些 CASE 工具至少在 1993 年时仍可从 The Programmer's Shop 和其他面向开发者的软件折扣商处获得。] Forth 是一种特别结构化的语言，它鼓励以自然、可读的方式生成 FSM。本笔记描述了几种高级 Forth 实现。本刊先前已讨论过有限状态机[3]、[4]。本文方法对先前方法有所改进。 ### 一个简单示例 考虑从键盘接受数字输入的任务。一个不友好的程序会让用户输入整个数字，然后才告知他在第一位数字后键入了两个小数点。相反，友好的程序会拒绝识别或显示非法字符。它而是等待合法字符或回车（表示输入结束）。它允许回溯，允许删除错误输入。为了保持示例简短，我们的数字输入例程允许带符号的十进制数，但不带 10 的幂指数（用 FORTRAN 术语说就是定点数）。小数点、数字和开头负号是合法的，但其他 ASCII 字符（包括空格）都不会被识别。以下是一些合法数字的示例：`` 0.123, .123, 1.23, -1.23, 123, etc. `` 从这些示例中我们推导出规则： - 0-9、- 和 . 以外的字符是非法的。 - 数字 0-9 是合法的。 - 第一个字符可以是 -、0-9 或小数点。 - 在第一个字符之后，- 是非法的。 - 在第一个小数点之后，小数点是非法的。 传统的程序化方法可能看起来像这样： `` VARIABLE PREVIOUS.MINUS? \ history semaphores VARIABLE PREVIOUS.DP? : DIGIT? ( c -- f) ASCII 0 ASCII 9 WITHIN ; \ tests : DP? ( c -- f) ASCII . = ; : MINUS? ( c -- f) ASCII - = ; : FIRST.MINUS? MINUS? PREVIOUS.MINUS? @ NOT AND ; : FIRST.DP? DP? PREVIOUS.DP? @ NOT AND ; : LEGAL? ( c -- f) \ horrible example DUP DIGIT? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE DUP FIRST.MINUS? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE FIRST.DP? IF TRUE DUP PREVIOUS.DP? ! ELSE FALSE THEN THEN THEN ; `` 完成工作的词是（向 Uderzo 和 Goscinny——Asterix 的创作者——致歉）： `` : Getafix FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? ! \ initialize history semaphores BEGIN KEY DUP CR WHILE LEGAL? IF DUP ECHO APPEND THEN REPEAT ; `` 为什么这个例子——其类似物几乎以每种语言频繁出现在已发表代码中——如此糟糕？每个合法性依赖于时间的字符都需要一个历史信号量。因此，即使通过部分因子分解和逻辑运算得到了简化，也很难通过检查来判断词 `LEGAL?` 的逻辑实际上是不正确的。 ### Forth 有限状态机 FSM 方法用单个状态变量取代真假历史信号量。规则可以体现在一个状态表中，该表以具体动作和状态转换的形式表达对每种可能输入的响应，如下面的图 1 所示。 `` Input: OTHER? DIGIT? MINUS? DP? State Does Trans Does Trans Does Trans Does Trans 0 X -> 0 E -> 1 E -> 1 E -> 2 1 X -> 1 E -> 1 X -> 1 E -> 2 2 X -> 2 E -> 2 X -> 2 X -> 2 `` > 图 1 归纳固定小数点数的规则的状态表。E 表示“回显”（到 CRT），X 表示“什么都不做”。 在状态表中， - “其他”字符的非法性通过一致的动作 X 和没有状态转换来表达。 - 第一个字符的特殊地位通过以下事实表达：所有可接受字符都会导致从初始状态 (0) 发生的转换： - 开头的 - 号或数字导致状态 1，在状态 1 中不接受 - 号。 - 小数点总是使系统进入状态 2，在状态 2 中小数点不被接受。 虽然某些 FSM 可以用 `BEGIN...WHILE...REPEAT` 或 `BEGIN...UNTIL` 循环来综合，键盘输入并不太适合这种方法。我们现在探讨图 1 状态表的三种 Forth FSM 实现。 ### 暴力 FSM “暴力”FSM 使用 Eaker 的 CASE 语句，要么使用其原始形式 [5]，要么使用 HS/FORTH [6] 中的简化结构。HS/FORTH 提供定义词 `CASE:` `;CASE`，其子词执行其定义中的若干词之一，如 `` CASE: CHOICE WORD0 WORD1 WORD2 WORD3 ... WORDn ;CASE 3 CHOICE ( executes WORD3 ) ok `` HS/FORTH 的 `CASE: ... ;CASE` 相对于直接执行这些词本身几乎不产生运行时速度损失。那么，我们如何使用 `CASE: ... ;CASE` 实现 FSM？首先我们需要一个状态变量（初始化为 0），它可以取值 0、1 和 2。为了测试输入字符是数字、负号、小数点还是“其他”，我们定义 [注：ANSI 标准 [7] 将 `ASCII` 重命名为 `CHAR`，将 `UNDER` 重命名为 `TUCK`；此外 `DDUP` 是 HS/FORTH 特有的，为了 ANSI 兼容应替换为 `2DUP`。这里使用的 `WITHIN` 在 a <= n <= b 时返回 TRUE，这与 ANS 规范不同。这些说明在此处及下文均适用，除非另有说明。] `` VARIABLE mystate mystate 0! : WITHIN ( n a b -- f) DDUP MIN -ROT MAX ROT UNDER MIN -ROT MAX = ; : DIGIT? ( c -- f ) ASCII 0 ASCII 9 WITHIN ; : DP? ( c -- f ) ASCII . = ; : MINUS? ( c -- f ) ASCII - = ; `` 现在，为了使用 `CASE:` `;CASE`，我们定义 3 个词来处理每个状态中的测试： `` : (0) ( char -- ) DUP DIGIT? OVER MINUS? OR IF EMIT 1 mystate ! ELSE DUP DP? IF EMIT 2 mystate ! ELSE DROP THEN THEN ; : (1) ( char -- ) DUP DIGIT? IF EMIT 1 mystate ! ELSE DUP MINUS? IF 1 mystate ! ELSE DUP DP? IF EMIT 2 mystate ! ELSE DROP THEN THEN THEN ; : (2) ( char -- ) DUP DIGIT? IF EMIT ELSE DROP THEN ; `` 最后，我们定义使用上述词的词： `` CASE: (0) (1) (2) ;CASE : Getafix 0 mystate ! \ initialize state BEGIN KEY DUP 13 \ not CR ? WHILE mystate @ <Fixed.Pt#> \ execute FSM REPEAT ; `` ### 更好的 FSM 虽然上文 P3.1 中概述的方法（本质上是 Berrian [8] 最近描述的方法）既能工作，又比 P2 的二元逻辑树产生清晰得多的代码，但它仍然可以改进。词 (0)、(1) 和 (2) 没有被充分因子化（它们包含对输入字符执行的测试）。它们还包含 `IF...ELSE...THEN` 分支（为了速度和结构，我们希望避免这些分支）。最后，每个 FSM 都必须由大量附属定义手工打造。 我们想把图 1 中的状态表翻译成程序。前面的尝试太间接了——每个状态由自己的词表示，而这个词做了太多事情。也许我们可以通过更直接的翻译来实现所需的简洁性。在 Forth 中，这种翻译最自然地通过定义词完成。假设我们将状态表视为一个矩阵，其单元格包含动作规范（地址或执行令牌），其列表示输入类别，其行是状态。如果我们将输入类别转换为列号，则类别和状态变量的当前值（行索引）确定唯一的单元格地址，其内容可以被取出并执行。将输入翻译成列号将测试因子化为一个对每个字符执行一次的词。这个词应避免浪费时间的分支指令，因此所有关于执行表中哪个单元格的决定都将被计算出来，而不是被判定。 对于我们的测试示例，初步定义是 `` VARIABLE mystate 0 mystate ! : WITHIN ( n a b -- f) DDUP MIN -ROT MAX ROT TUCK MIN -ROT MAX = ; : DIGIT? ( n -- f ) ASCII 0 ASCII 9 WITHIN ; : DP? ASCII . = ; : MINUS? ASCII - = ; `` 输入翻译由以下代码完成： `` : cat->col# ( n -- n') DUP DIGIT? 1 AND \ digit -> 1 OVER MINUS? 2 AND + \ - -> 2 SWAP DP? 3 AND + \ dp -> 3 ; \ other -> 0 `` 现在我们必须规划状态表编译器。通常，我们为表中的每个单元格定义一个动作词，它执行所需的动作和状态改变。在编译时，定义词将编译一个由这些动作词的执行地址（ANSI Forth 术语中的执行令牌 [9]）组成的数组。在运行时，子词根据用户提供的列号和 `mystate` 的当前值计算适当矩阵单元格的地址，从其矩阵单元格取出执行地址，并 `EXECUTE` 适当的动作。由于一个表可以有任意多列，因此必须在编译时提供列数。这些要求导致以下定义： `` : TUCK COMPILE UNDER ; \ ANS compatibility : WIDE ; \ NOOP for clarity : CELLS COMPILE 2* ; \ ANS compatibility : CELL+ COMPILE 2+ ; \ ANS compatibility : PERFORM COMPILE @ COMPILE EXECUTE ; \ alias : FSM: ( width -- ) CREATE , ] DOES> ( n adr -- ) TUCK @ mystate @ * + CELLS CELL+ + ( adr') PERFORM ; `` 这里 `CREATE` 在字典中创建一个新的头，`,` 将栈顶数字存入参数字段的第一格，而 `]` 切换到编译模式。运行时代码计算包含所需动作向量的单元格地址，取出该向量并执行该动作。[注：这种简单而优雅的实现仅适用于间接线程化 Forth。附录中提供了 ANS 标准的替代方案。] 现在我们将这个强大的新词应用于我们的示例问题。