Bison 如何在没有 shift-reduce 冲突的情况下描述语法中的可选语法？

Question

我有一个用语法描述的文件。它有一个section，可以包含一种或两种内容，可以任意排列：

...
type_a_thing
type_b_thing
type_b_thing
type_a_thing
....

或者只是

...
type_a_thing
...

或

...
type_b_thing
type_b_thing
...

或任何组合，出现次数不限。 type_a_thing andtype_b_thing 都具有明确定义的结构。我设法描述了这一点，以便解析器工作，但我仍然收到 shift/reduce 错误。 我在这里上传了一个最小的例子：

https://github.com/waszil/minimal_bison_parser

这是解决这个问题的正确方法吗？我做错了吗？ 我为此尝试了很多东西，用详细标志检查了 bison 生成的 .output 文件，但我不知道，应该如何正确完成。有点类似于Flex&Bison O'Reilly书中描述的nested-list语法问题，但又不一样

感谢任何提示！

Answer 1

看看你这部分的语法：

contents:
    foobar
    | contents foobar
    ;
foobar:
    foos
    | bars
    ;
foos:
    foo
    | foos foo
    ;
bars:
    bar
    | bars bar
;

因此 contents 是 foobar 的列表，而 foobar 是 foo 的列表或 bar 的列表。这是不明确的，因为由两个连续 foo 组成的输入可以通过将两个 foo 解释为包含两个 [=15] 的单个 foobar 来解析为 contents =]s 或两个 foobars，每个包含一个 foo。

消除这种歧义的一个简单方法是放弃内部列表：

contents: foobar | contents foobar;

foobar: foo | bar;

如果您需要以不同方式处理连续的 foo，您仍然可以在 post 处理期间检测到它们。如果你确实需要在语法中处理这个问题，你可以重构语法，这样 foos 后面只能跟着 bars（而不是另一个 foos），反之亦然。