BNF语法检查器对特定输入误判为yes的问题排查求助

问题根源 #

输入0 1 0 ; 0被错误判定为合法，核心原因有两个：

1. B函数的提前终止逻辑错误：当匹配到;时，代码直接打印yes并执行后续的exit(1)，程序直接终止，完全跳过了main函数中检查是否有剩余未匹配token的关键逻辑——输入末尾的0根本没被检查到。
2. B函数末尾的强制exit：无论B的推导是否成功（除了触发error的情况），函数最后都会执行exit(1)，导致整个解析流程无法正常回到调用链，main函数的后续检查永远不会执行。

修复思路 #

不需要添加else if语句，而是修正解析函数的终止逻辑：

• 移除B函数末尾的exit(1)，让函数在推导完成后正常返回，确保解析流程能回到main函数，执行剩余token检查。
• 移除B函数中匹配;时的printf("yes")，合法输入的判定统一在main函数完成所有检查后执行，避免提前输出错误结果。
• 确保所有错误路径通过error函数统一处理，不要额外添加exit逻辑。

修复后的代码 #

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void A(), B();

// input token
char tok[10];

// return the next token from standard input as a string,
// or return NULL if there is no more input
char *lexan() {
  int n;
  n = scanf("%s", tok);
  if (n == EOF) {
    return NULL;
  }
  return tok;
}

// print an error message and exit
void error(char* msg) {
  printf("%s\n", msg);
  exit(1);
}

// return if the standard input follows the syntax for A,
// else print an error message and exit
void A() {
  char *lookahead;

  lookahead = lexan();

  if (lookahead == NULL) {
    error("no");
  }
  else if (strcmp(lookahead, "0") == 0) {
    B();
  }
  else {
    error("no");
  }
}

// return if the standard input follows the syntax for B,
// else print an error message and exit
void B() {
  char *lookahead;

  lookahead = lexan();

  if (lookahead == NULL) {
    error("no");
  }
  else if (strcmp(lookahead, "1") == 0) {
    A();
  }
  else if (strcmp(lookahead, "2") == 0) {
    B();
  }
  else if (strcmp(lookahead, ";") == 0) {
    // 匹配到;，B推导完成，直接返回
    return;
  }
  else {
    error("no");
  }
}

int main() {
  A();
  // 检查是否有剩余未匹配的token
  if (lexan() != NULL) {
    error("no");
  }
  printf("yes\n");
  return 0;
}

验证说明 #

修复后，输入0 1 0 ; 0的解析流程：

1. A匹配0，调用B；
2. B匹配1，调用A；
3. A匹配0，调用B；
4. B匹配;，返回上一层A，再返回上一层B，最终回到main函数；
5. main函数调用lexan()，读取到剩余的0，触发error输出no，符合预期。

内容的提问来源于stack exchange，提问作者Agent Programmer 001