bison - 检查字符串是否为 0^n 1^n 形式

Question

我有一个 Yacc 程序来检查一个数字是否是 0^n 1^n 的形式。

%start S
%%
    S:'0' S '1' {printf("Success\n");}|;
%%

（所有标记都在 lex 文件中定义）

我得到的输出如下

0011
Success
Success
syntax error

1100
syntax error

我理解为什么成功打印两次，但是第一个输出中的语法错误是什么？

此外，bisonLALR(1) 解析器生成器是如何完成这项任务的？

Answer 1

问题是您的语法只匹配无限字符串——您的语法描述的语言中没有有限字符串。

您需要添加一个带有有限字符串的“基本情况”，以便它可以接受该字符串或由它构建的字符串。最明显的情况是空字符串（对于 n = 0）：

S : /* empty */
  | '0' S '1'
  ;

Answer 2

语法错误是因为你的语法不能识别空字符串，所以一旦所有的'1' S '0'产生式都减少了，就没有进展了。

Bison 拒绝接受这种语法，但很容易解决：

%start S
%%
S: '1' S '0'
 | ;
%%

单看语法，应该就明白如何用one-token lookahead解析字符串了。其实文法就是LL(1)；您只需要1遇到的 s 的堆栈（或计数器）。如果这还不够充分，请启用 bison 的跟踪功能并观察解析发生的情况。