bison - Bison如何在没有移位减少冲突的情况下描述语法中的可选语法？

Question

我有一个用语法描述的文件。它有一个部分可以包含一种或两种内容，并且可以按任意顺序排列：

...
type_a_thing
type_b_thing
type_b_thing
type_a_thing
....

要不就

...
type_a_thing
...

或者

...
type_b_thing
type_b_thing
...

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

https://github.com/waszil/minimal_bison_parser

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

感谢您的任何提示！

标签： bisonflex-lexershift-reduce-conflictambiguous-grammar

Answer 1

看看你语法的这一部分：

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

scontents的列表也是如此，要么是 s 的列表，要么是s 的列表。这是模棱两可的，因为由两个连续的 s 组成的输入可以通过将两个 s 解释为包含两个s的单个s 或每个包含一个 s的两个 s来解析为 a 。foobarfoobarfoobarfoocontentsfoofoobarfoofoobarfoo

摆脱这种歧义的一种简单方法是放弃内部列表：

contents: foobar | contents foobar;

foobar: foo | bar;

如果您需要foo以不同方式处理连续的 s，您仍然可以在后处理期间检测到它们。如果您绝对需要在语法中处理这个问题，您可以重组语法，以便 afoos后面只能跟 a bars（而不是 another foos），反之亦然。