x86汇编（GCC）实现DFA程序问题：输入始终被拒绝

先确认DFA核心逻辑是否正确 #

首先明确目标DFA的状态定义和转移规则：

• 状态用两位二进制标识：第一位对应0的数量奇偶（0=偶数，1=奇数），第二位对应1的数量奇偶（0=偶数，1=奇数）
• 共4个状态：
  • S00（数值0）：初始状态+接受状态（0和1数量均为偶数）
  • S01（数值1）：0数量偶、1数量奇
  • S10（数值2）：0数量奇、1数量偶
  • S11（数值3）：0数量奇、1数量奇
• 转移规则：
  • 输入'0'：翻转0的奇偶位（第一位），比如S00→S10、S01→S11
  • 输入'1'：翻转1的奇偶位（第二位），比如S00→S01、S10→S11

如果你的DFA设计和上述逻辑不符，先修正状态转移的核心逻辑。

汇编代码常见错误点排查 #

1. 初始状态设置错误 #

检查状态寄存器的初始值：

• 若用寄存器（比如%bl）存储状态，初始值必须设为0（对应S00）。如果误设为1/2/3，后续无论输入如何都难以回到接受状态。
• 错误示例：mov $1, %bl（初始状态设为S01）

2. 字符判断逻辑错误 #

• 必须准确匹配'0'（ASCII 0x30）和'1'（ASCII 0x31）的ASCII码，判断条件写反或用错值会直接打乱转移逻辑：
  • 错误示例：把判断'0'的条件写成cmp $0x31, %al，会将'1'当成'0'处理
• 若程序要求只处理纯二进制串，遇到非0/1字符应直接拒绝，避免干扰状态计算。

3. 状态转移操作错误 #

状态转移的位翻转操作必须和你的状态定义严格对应：

• 假设用寄存器低两位存储状态，若0的奇偶位是高位（第二位），输入'0'时需执行xor $0x02, %bl；若0的奇偶位是低位（第一位），则执行xor $0x01, %bl
• 输入'1'时同理，翻转对应位即可。如果搞反了两位的对应关系，所有转移都会出错。
• 错误示例：输入'0'时翻转1的奇偶位，输入'1'时翻转0的奇偶位

4. 接受状态判断错误 #

循环结束（读取到字符串结束符'\0'）后，必须检查状态是否等于0（S00）：

• 错误示例：cmp $3, %bl后跳转至接受分支，会导致所有输入都被判定为拒绝

5. 输入读取逻辑错误 #

检查字符串遍历逻辑：

• 是否正确读取每个字符，有没有提前终止循环（比如误把空格当成结束符）
• 是否在读取字符后先判断是否为'\0'，避免处理内存垃圾值导致状态混乱

正确核心逻辑参考片段（GCC x86汇编） #

# 输入字符串地址存于%esi，状态存于%bl（初始为0）
start_loop:
    mov (%esi), %al          ; 读取当前字符
    test %al, %al            ; 判断是否到字符串末尾
    jz check_accept          ; 结束则检查状态

    cmp $0x30, %al           ; 判断是否为'0'
    je handle_zero
    cmp $0x31, %al           ; 判断是否为'1'
    je handle_one
    jmp reject_input         ; 非二进制字符直接拒绝

handle_zero:
    xor $0x02, %bl           ; 翻转0的奇偶位（对应S00→S10）
    jmp next_char

handle_one:
    xor $0x01, %bl           ; 翻转1的奇偶位（对应S00→S01）
    jmp next_char

next_char:
    inc %esi                 ; 指针移至下一个字符
    jmp start_loop

check_accept:
    cmp $0, %bl              ; 检查是否处于接受状态S00
    je accept_input
    jmp reject_input

accept_input:
    # 输出接受信息的代码
    ret

reject_input:
    # 输出拒绝信息的代码
    ret

将你的代码和上述逻辑对比，即可快速定位错误点。

内容的提问来源于stack exchange，提问作者Erique