如何修改YACC程序以接受以'01'开头、以'10'结尾的字符串？

原始YACC程序 #

%{
int yylex(void);
#include <stdio.h>
#include <stdlib.h>
int yyerror(char* s);
%}

%token ZERO ONE NL

%%

st : ZERO s ZERO NL { printf("Sequence Accepted\n");}
;

s : ONE r
;

r: r ONE
 |
;

%%
int main()
{
    printf("Enter Sequence of Zeros and Ones :\n");
    yyparse();
    return 0;
}

int yyerror(char *s)
{
    printf("Sequence Rejected\n");
}

需求说明 #

需要修改上述程序，使其接受以'01'开头且以'10'结尾的0、1字符串（合法串最短为4位，比如0110，更长的如01010、011110等也需被接受）。

你的尝试问题分析 #

你给出的修改版本存在语法错误与逻辑冗余：

%%
st : ZERO ONE s ONE ZERO NL{printf("Sequence Accepted\n");}
;

s : s ZERO
s ONE 
ZERO
ONE
;
%%

• 语法错误：非终结符s的多个产生式之间缺少竖线|分隔，YACC无法识别规则结构；
• 逻辑冗余：s ZERO和s ONE已能递归生成任意长度的0/1序列，单独的ZERO和ONE属于多余规则，还会引发匹配歧义。

正确修改方案 #

修改核心规则部分即可，其他代码（词法声明、主函数、错误处理）保持不变：

%%
st : ZERO ONE mid ONE ZERO NL { printf("Sequence Accepted\n"); }
;

// mid 匹配开头与结尾之间任意长度（含0）的0/1组合
mid : mid ZERO
    | mid ONE
    | /* 空串，对应中间无字符的情况，如合法最短串"0110" */
;
%%

修改说明 #

1. 起始规则st直接固定开头为ZERO ONE、结尾为ONE ZERO，严格满足开头结尾的要求；
2. 新增非终结符mid，用于匹配开头结尾之间的任意0/1序列（包括空串，保证最短合法串0110能被识别）。

测试验证 #

• 合法输入：0110、01010、011110 → 输出Sequence Accepted
• 非法输入：010（长度不足）、0010（开头不符）、0111（结尾不符）→ 输出Sequence Rejected

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