有限状态机（FSM）与汇编语言[附带实例]

有限状态机（FSM）是一个根据输入改变状态的机器或程序。用图表示 FSM 相当简明， 下图中的矩形（或圆形）称为节点，节点之间带箭头的线段称为边（或弧）。


上图给出了一个简单的例子。每个节点代表一个程序状态，每个边代表从一个状态到另一个状态的转换。一个节点被指定为初始状态，在图中用一个输入箭头指出。其余的状态可以用数字或字母来标示。一个或多个状态可以指定为终止状态，用粗框矩形表示。终止状态表示程序无出错的结束状态。

FSM 是一种被称为有向图的更一般结构的特例。有向图就是一组节点，它们用具有特定方向的边进行连接。

验证输入字符串

读取输入流的程序往往要通过执行一定量的错误检查来验证它们的输入。比如，编程语言编译器可以用 FSM 来扫描程序，将文字和符号转换为记号（通常是指关键字、算法运算符和标识符）。

用 FSM 来验证输入字符串时，常常是按字符进行读取。每一个字符都用图中的一条边（转换）来表示。FSM 有两种方法检测非法输入序列：

• 下一个输入字符没有对应到当前状态的任何一个转换。
• 输入已经终止，但是当前状态是非终止状态。

字符串示例现在根据下面两条原则来验证一个输入字符串：

• 该字符串必须以字母“x”开始，以字母“z”结束。
• 第一个和最后一个字符之间可以有零个或多个字母，但其范围必须是 {a,....,y}。

下图的 FSM 显示了上述语法。每一个转换都是由特定类型的输入来标识。比如，仅当从输入流中读取字母 x 时，才能完成状态 A 到状态 B 的转换。输入任何非“z”的字母，都会使得状态 B 转换为其自身。而仅当从输入流中读取字母 z 时，才会发生状态 B 到状态 C 的转换。


如果输入流已经结束，而程序只出现了状态 A 和状态 B，那么就生成出错条件，因为只有状态 C 才能标记终止状态。下述输入字符串能被该 FSM 认可：

xaabcdefgz
xz
xyyqqrrstuvz

验证有符号整数

下图表示的是 FSM 解析一个有符号整数。输入包括一个可选的前置符号，其后跟一串数字。图中没有对数字个数进行限制。


有限状态机很容易转换为汇编代码。图中的每个状态（A、B、C…）代表了一段有标号的程序。每个标号执行的操作如下：

1) 调用输入程序读入下一个输入字符。

2)    如果是终止状态，则检查用户是否按下 Enter 键来结束输入。

3)    一个或多个比较指令检查从状态发岀的所有可能的转换。每个比较指令后面跟一个条件跳转指令。

比如，在状态 A，如下代码读取下一个输入字符并检查到状态 B 的可能的转换：

StateA:
        Cal1 Getnext                          ;读取下一个字符，并送入 AL
        cmp    al, '+'                        ;前置+ ?
        je    StateB                          ;到状态 b
        cmp    al, '-'                        ;前置 - ?
        je    StateB                          ;到状态 B
        call    IsDigit                       ;如果 AL 包含数字，则 ZF = 1
        jz    StateC                          ;到状态 C
        call    DisplayErrorMsg               ;发现非法输入
        jmp Quit

下面来更详细地检查这段代码。首先，代码调用 Getnext，从控制台输入读取下一个字符，送入 AL 寄存器。接着检查前置 + 或 -，先将 AL 的值与符号“+”进行比较，如果匹配，就发生到标号 StateB 的跳转：

StateA:
        call Getnext                         ;读取下一个字符，并送入 al
        cmp al, ' + '                        ;前置 + ?
        je StateB                            ;到状态 B

现在，再次查看上图，发现只有输入 + 或 - 时，才发生状态 A 到状态 B 的转换。所以，代码还需检查减号：

cmp al, '-'                                  ;前置 - ？
je StateB                                    ;到状态 B

如果无法发生到状态 B 的转换，就可以检查 AL 寄存器中是否为数字，这可以导致到状态 C 的转换。调用 IsDigit 子程序，当 AL 包含数字时，零标志位置 1：

call IsDigit                                 ;如果AL包含数字，贝U ZF=1
jz StateC                                    ;到状态 C

最后，状态 A 没有其他可能的转换。如果发现 AL 中的字符既不是前置符号，又不是数字，程序就会调用 DisplayErrorMsg （在控制台上显示一条错误消息）子程序，并跳转到标号 Quit 处：

call DisplayErrorMsg                         ;发现非法输入
jmp Quit

标号 Quit 标识程序的出口，位于主程序的结尾：

Quit:
    call Crlf
    exit
main ENDP

完整的有限状态机程序

如下程序实现上图所示的有符号整数 FSM：

; 有限状态机              (Finite.asm)
INCLUDE Irvine32.inc

ENTER_KEY = 13
.data
InvalidInputMsg BYTE "Invalid input",13,10,0

.code
main PROC
    call Clrscr

StateA:
    call    Getnext               ; 读取下一个字符，并送入AL
    cmp    al,'+'                 ; 前置+ ?
    je    StateB                  ; 到状态 B
    cmp    al,'-'                 ; 前置 - ?
    je    StateB                  ; 到状态 B
    call    IsDigit               ; 如果 AL 包含数字 ，则 ZF = 1
    jz    StateC                  ; 到状态 C
    call    DisplayErrorMsg       ; 发现非法输入
    jmp    Quit

StateB:
    call    Getnext               ; 读取下一个字符，并送入AL
    call    IsDigit               ; 如果AL包含数字，则 ZF = 1
    jz    StateC
    call    DisplayErrorMsg       ; 发现非法输入
    jmp    Quit

StateC:
    call    Getnext               ; 读取下一个字符，并送入AL
    call    IsDigit               ; 如果AL包含数字，则 ZF = 1
    jz    StateC
    cmp    al,ENTER_KEY           ; 按下Enter键?
    je    Quit                    ; 是：Quit
    call    DisplayErrorMsg       ; 否: 发现非法输入
    jmp    Quit

Quit:
    call    Crlf
    exit
main ENDP

;-----------------------------------------------
Getnext PROC
;
; 从标准输入读取一个字符
; 接收: 无
; 返回: 字符保存在AL中
;-----------------------------------------------
     call ReadChar            ; 从键盘输入
     call WriteChar           ; 显示在屏幕上
     ret
Getnext ENDP

;-----------------------------------------------
DisplayErrorMsg PROC
;
; 显示一个错误消息以表示
; 输入流中包含非法输入
; 接收: 无.
; 返回: 无
;-----------------------------------------------
     push  edx
     mov      edx,OFFSET InvalidInputMsg
     call  WriteString
     pop      edx
     ret
DisplayErrorMsg ENDP
END main

IsDigit子程序

有限状态机示例程序调用 IsDigit 子程序，该子程序属于本教程的链接库。现在来看看 IsDigit 的源程序，程序把 AL 寄存器作为输入，其返回值设置零标志位：

;----------------------------------------------------
IsDigit PROC
;
;确定 AL 中的字符是否为有效的十进制数字。
;接收：AL= 字符
;返回：若 AL 为有效的十进制字符，ZF=1;否则，ZF=0
;---------------------------------------------------
        cmp    al,'0'
        jb    ID1                                 ;跳转发生，ZF=0
        cmp    al, '9'
        ja    ID1                                 ;跳转发生，ZF = 0
        test    ax, 0                             ;设置 ZF=1
ID1: ret
IsDigit ENDP

在查看 IsDigit 的代码之前，先回顾十进制数字的十六进制 ASCII 码，如下表所示。由于这些值是连续的，因此，只需要检查第一个和最后一个值：

字符	'0'	'1'	'2'	'3'	'4'	'5'	'6'	'7'	'8'	'9'
ASCII 码（十六进制）	30	31	32	33	34	35	36	37	38	39

IsDigit 子程序中，开始的两条指令将 AL 寄存器中字符的值与数字 0 的 ASCII 码进行比较。如果字符的 ASCII 码小于 0 的 ASCII 码，程序跳转到标号 ID1：

cmp al, '0'
jb ID1                       ;跳转发生，ZF=0

但是有人可能会问了，如果 JB 将控制传递给标号 ID1，那么，怎么知道零标志位的状态呢？答案就在 CMP 指令的执行方式里——它执行一个隐含的减法操作，从 AL 寄存器的字符中减去 0 的 ASCII 码（30h）。如果 AL 中的值较小，那么进位标志位置 1，零标志位清除（你可能想用调试器来单步执行这段代码来验证这个事实）。JB 指令的目的是，当 CF=1 且 ZF=0 时，将控制传递给一个标号。

接下来，IsDigit 子程序代码把 AL 与数字 9 的 ASCII 码进行比较。如果 AL 的值较大，代码跳转到同一个标号：

cmp al, '9'
ja ID1                ;跳转发生，ZF=0

如果 AL 中字符的 ASCII 码大于数字 9 的 ASCII 码（39h），清除进位标志位和零标志位。这也正好是使得 JA 指令将控制传递到目的标号的标志位组合。

如果没有跳转发生（JA 或 JE），又假设 AL 中的字符确实是一个数字，则插入一条指令确保将零标志位置 1。将 0 与任何数值进行 test 操作，就意味着执行一次隐含的与全 0 的 AND 运算。其结果必然为 0：

test ax, 0          ; 置 ZF=1

前面 IsDigit 中的 JA 和 JB 指令跳转到了 TEST 指令后面的标号。所以，如果发生跳转，零标志位将清零。下面再次给出完整的过程：

Isdigit PROC
    cmp al,'0'
    jb ID1             ;若跳转发生，则 ZF=0
    cmp al,'9'
    ja ID1             ;若跳转发生，则 ZF=0
    test ax,0          ;置 zf=1
ID1: ret
Isdigit ENDP

在实时或高性能应用中，程序员常常利用硬件特性的优势，来对其代码进行充分优化。IsDigit 过程就是这种方法的例子，它利用 JB、JA 和 TEST 对标志的设置，实际上返回的是一个布尔结果。