yacc shift/reduce 与空规则冲突

Question

test.y

%%
TOP :
    OPTIONS
  ;

OPTIONS :
    OPTION
  | OPTIONS OPTION
  ;

OPTION :
   /*no option is possible*/
  | 'C'
  ;
%%

yacc -v test.y

y.output包含以下内容

   0  $accept : TOP $end

   1  TOP : OPTIONS

   2  OPTIONS : OPTION
   3          | OPTIONS OPTION

   4  OPTION :
   5         | 'C'

0: shift/reduce conflict (shift 1, reduce 4) on 'C'
state 0
    $accept : . TOP $end  (0)
    OPTION : .  (4)

    'C'  shift 1
    $end  reduce 4

    TOP  goto 2
    OPTIONS  goto 3
    OPTION  goto 4


state 1
    OPTION : 'C' .  (5)

    .  reduce 5


state 2
    $accept : TOP . $end  (0)

    $end  accept


3: reduce/reduce conflict (reduce 1, reduce 4) on $end
3: shift/reduce conflict (shift 1, reduce 4) on 'C'
state 3
    TOP : OPTIONS .  (1)
    OPTIONS : OPTIONS . OPTION  (3)
    OPTION : .  (4)

    'C'  shift 1
    $end  reduce 1

    OPTION  goto 5


state 4
    OPTIONS : OPTION .  (2)

    .  reduce 2


state 5
    OPTIONS : OPTIONS OPTION .  (3)

    .  reduce 3


State 0 contains 1 shift/reduce conflict.
State 3 contains 1 shift/reduce conflict, 1 reduce/reduce conflict.


3 terminals, 4 nonterminals
6 grammar rules, 6 states

为什么会有 shift/reduce 和 reduce/reduce 冲突。

我已经阅读了 http://dinosaur.compilertools.net/yacc/ 的 "How the Parser Works" 部分中的 yacc 解析器如何工作，但我不明白 yacc 如何处理空规则。似乎它正试图在任何地方使用空规则。

问题1. yacc如何处理状态机和上面link中描述的"look ahead token"的空规则

问题 2. 如何摆脱冲突并仍然保持语法的 "logic"？

感谢您事先的帮助。

Answer 1

当然是在尝试使用空规则"everywhere"。它正在按照您的指示去做。

你说的是非终结符OPTIONS代表任意正数的OPTION个非终结符，一个OPTION个非终结符可以是一个C或者空。

由于 OPTION 可以为空，因此在空输入中可以有任意多个。两个空的 OPTION 看起来和 153 个空的 OPTION 完全一样。更重要的是，两个 C 标记之间可以有任意数量的空 OPTIONs。

所以你的语法有歧义，bison 报告解析冲突。

如果您想将 OPTIONS 定义为任意数量的 OPTION，包括零个 OPTION，那么只需说：

options: %empty
       | options option
option : 'C'

yacc shift/reduce 与空规则冲突

yacc shift/reduce conflict with empty rules

yacc

bison