0

我正在尝试解决一些 yacc 问题。在遇到冲突后，我的几次尝试都是徒劳的：减少/减少错误。举个例子，我正在尝试解决“接受更多 0 而不是 1 的字符串”，我编写了以下代码来显示减少/减少冲突（我在这里只给出规则部分）：

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

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

谢谢你，

4

1 回答 1

1

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

详细的输出文件（bison -v rrconf.yyield 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)

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

不过，您还有另一个问题——高级算法设计问题。输入 101后跟 110满足零多于一的要求，但不会被此语法识别。

于 2013-09-15T18:40:17.763 回答