YACC和上下文无关文法

Question

我无法为以下问题派生yacc程序。

对于具有的相等数目的字符串和b的是如下

S上的语法 - >一个S B S | b S a S | epsilon

我想知道是否有可能为它制作YACC程序。在编写代码的同时，我意识到如果输入不具有相同的a和b。我应该在YACC打印一些表明字符串无效的消息？

Answer 1

yacc为LALR(1)语法实现解析器;语法（和，我相信，语言）不是LALR(1)。 （这与我下面的第一点有关。）

如果您使用bison（很可能），那么您可以使用%glr选项生成GLR语法，在这种情况下，该语法的天真音译将起作用。但是，你会遇到两个问题：

1. 最有效字符串有多个解析和野牛的GLR分析器坚持认为，最终的结果不会含糊。我不知道是否有一个简单的解决这个使用%dprec，但其可能的。

2. 你不能告诉，直到你到达字符串结尾的字符串不符合语法，因为任何字符串是一个有效的字符串的前缀。 （你只需要添加少数符号足以实现平等。）