compiler-errors - YACC和上下文无关文法

Question

对于以下问题，我无法导出yacc程序。

具有相同数量的a和b的字符串的语法如下

S-> a S b S | b S a S | ε

我想知道是否有可能为此编写YACC程序。同样在编写代码时，我意识到如果输入不等于a和b怎么办。我应该在YACC的哪里打印一些消息，指示字符串无效？

Answer 1

yacc实现LALR(1)语法的解析器；语法(我相信语言)不是LALR(1)。 (这与我在下面的第一点有关。)

如果使用bison(可能的话)，则可以使用%glr选项生成GLR语法，在这种情况下，可以对语法进行简单的音译。但是，您将遇到两个问题:

大多数有效的字符串都有多个解析，而bison的GLR解析器坚持认为最终结果不会是模棱两可的。我不知道是否有使用%dprec的简单解决方案，但是有可能。

在到达字符串结尾之前，您不能说出一个字符串与语法不匹配，因为任何字符串都是有效字符串的前缀。 (您只需添加足够的少数符号即可实现相等。)