bison - 歧义语法的 Yacc 规则

Question

我正在尝试编写一个 yacc 语法来识别以下模式：

AAAA  -> Multiple As
BBBB  -> Multiple Bs
AAAABB -> 2 As followed by (AABB)
AAABBBBB  -> (AAABBB) followed by 2Bs

一般来说，我想将相等的连续 As 和 B 块组合在一起，优先于仅 As 或 B 的运行。一个简单的语法显示了一堆冲突。

我需要一种方法来优先处理这种生产。

T -> | AB | ATB

超过

U -> | AU

（其中 T 和 U 是 yacc 产生式，A 和 B 是令牌）

这是怎么做到的？

Answer 1

In general, yacc cannot deal with ambiguous grammars. If you give it an ambiguous grammar (or any non-LALR(1) grammar), it will parse a subset of the language of that grammar, which may or may not be what you want.

With bison, you can use %glr-parser to create a glr parser that can parse an ambiguous grammar. However, you need to add %dprec and %merge directives to the appropriate spots in the grammar to resolve ambiguities, or you'll end up with a runtime error.

However, the language you've described isn't particularly ambiguous. In fact, its fairly trivially LALR(1), so can be easily handled by yacc:

%token A B
%%
input: multiA | multiB | twoA | twoB ;
multiA: A | A A | A A A | A A A moreAs ;
moreAs: A | moreAs A ;
multiB: B | multiB B ;
twoA: A A A A B B ;
twoB: A A A B B B B B ;