如何解决在JFLEX/CUP中使用相同分隔符的嵌套列表的移位/减少冲突?

Question

我试图在JFLEX/CUP (JFLEX 1.8.2, CUP 0.11b)中实现一个解析器，用于包含不同类型元素的列表可以嵌套的语言(例如语句列表和包含表达式列表的语句)。我把这个问题归结为以下MWE:

杯语法:

terminal            A, B, C, COMMA;

non terminal Object list_a, list_b, item_a, item_b;
list_a             ::= list_a COMMA item_a | item_a;
item_a             ::= A | C list_b;
list_b             ::= list_b COMMA item_b | item_b;
item_b             ::= B;

终端在相应的JFlex文件中定义为"a"， "b"， "one_answers",";分别;省略空格

当我尝试编译时，我得到以下冲突:

Warning : *** Shift/Reduce conflict found in state #6
between item_a ::= C list_b (*)
and     list_b ::= list_b (*) COMMA item_b
under symbol COMMA
Resolved in favor of shifting.

通读

1. Shift/Reduce C变量语法冲突
2. 如何避免转移减少冲突在LALR语法解析嵌套列表?

很有见地，但不能解决我的问题。没有一个列表是空的，如(1)，并且由于list_b的开头总是由前面的C表示，因此item_b产品列表不可能被解析为item_a产品列表，如(2)。

这个问题似乎与list_b在生产item_a中没有跟随任何其他终端的事实有关-我没有看到避免这种情况的方法。进行以下更改

item_a             ::= A | C list_b COMMA item_a;

编译并适用于list_b生产后再生产item_a的情况，但当然这并不能涵盖所有情况，而且在语义上也不是我想要的。

我也没有看到通过分别定义COMMA的结合性优先级来解决问题的方法。通过这样做，我可以修复Shift/Reduce冲突，但是语法没有按照期望的方式运行。例如，当定义precedence left COMMA;时，我得到输入

a,a,a,a,a,c b,b,b,a,a

第19列的语法错误(即第一个"a"在最后一个" "之后。

不能改变语法或使用语义动作。

如果有人能就如何解决这个问题给我一些建议，我将不胜感激。

Answer 1

我想我已经设法解决这个问题了。

list_a             ::= item_a COMMA list_a | C list_b COMMA list_a | item_a | C list_b;
item_a             ::= A;
list_b             ::= list_b COMMA item_b | item_b;
item_b             ::= B;