如何删除reduce/reduce冲突

Question

我试图解决几个yacc错误，在得到冲突后，我的几次尝试都是徒劳的: reduce/reduce problems.And。举个例子，我正在试着解决"string FOr更多的0而不是1“，我写了下面的代码，它显示了reduce/reduce冲突(我在这里只给出了规则部分)：

    s   :   s1 ';'   {printf("valid");exit(0);}
        ;
    s1  :   '0' '1' '0' s   
        |   '0' '0' '1' s
        |   '1' '0' '0' s
        |   '0' s
        | 
        ;

谁能告诉我在这里我做错了什么，如果你在未来建议我如何从这个错误中恢复，我将不胜感激。

谢谢,

Answer 1

您使用的是右递归而不是左递归。通常，左递归在Bison和Yacc语法中是首选的。在s1规则中使用s而不是s1也有点奇怪。

详细的输出文件(bison -v rrconf.y生成rrconf.output)如下所示：

State 20 conflicts: 1 reduce/reduce
State 21 conflicts: 1 reduce/reduce

Grammar

    0 $accept: s $end

    1 s: s1 ';'

    2 s1: '0' '1' '0' s
    3   | '0' '0' '1' s
    4   | '1' '0' '0' s
    5   | '0' s
    6   | /* empty */

...

state 20

    2 s1: '0' '1' '0' s .
    5   | '0' s .

    ';'       reduce using rule 2 (s1)
    ';'       [reduce using rule 5 (s1)]
    $default  reduce using rule 2 (s1)


state 21

    4 s1: '1' '0' '0' s .
    5   | '0' s .

    ';'       reduce using rule 4 (s1)
    ';'       [reduce using rule 5 (s1)]
    $default  reduce using rule 4 (s1)

可以很容易地将语法更改为使用左递归：

%%
s   :   s1 ';'   {printf("valid");exit(0);}
    ;
s1  : s1 '0' '1' '0'
    | s1 '0' '0' '1'
    | s1 '1' '0' '0'
    | s1 '0'
    | 
    ;
%%

它给你留下了两个shift/reduce冲突(比reduce/reduce冲突要轻得多)：

State 5 conflicts: 2 shift/reduce

Grammar

    0 $accept: s $end

    1 s: s1 ';'

    2 s1: s1 '0' '1' '0'
    3   | s1 '0' '0' '1'
    4   | s1 '1' '0' '0'
    5   | s1 '0'
    6   | /* empty */

...


state 5

    2 s1: s1 '0' . '1' '0'
    3   | s1 '0' . '0' '1'
    5   | s1 '0' .

    '0'  shift, and go to state 7
    '1'  shift, and go to state 8

    '0'       [reduce using rule 5 (s1)]
    '1'       [reduce using rule 5 (s1)]
    $default  reduce using rule 5 (s1)

这对你来说是否足够，我不确定。

不过，您还有另一个问题--高级算法设计问题。输入10个1，然后输入11个0符合0大于1的要求，但此语法无法识别。