野牛转移 - 减少冲突

Question

带有冲突的精简版语法:

body: variable_list function_list;
variable_list:
  variable_list variable | /* empty */
;
variable:
  TYPE identifiers ';'
;
identifiers:
  identifiers ',' IDENTIFIER | IDENTIFIER
;
function_list:
  function_list function | /* empty */
;
function:
  TYPE IDENTIFIER '(' argument_list ')' function_body
;

问题是变量和函数都以TYPE和IDENTIFIER开头,例如

int some_var;
int foo() { return 0; }

变量总是在这种语言的函数之前声明,但是当尝试解析时,它总是给出

解析错误:语法错误,意外'(',期待','或';'[在foo之后]

如何使variable_list变得不那么贪婪,或者让解析器意识到如果下一个标记是'('而不是';'或','它显然是一个函数,而不是一个变量声明？

冲突的野牛调试输出是

state 17

3 body: variable_list . function_list
27 variable_list: variable_list . variable

T_INT    shift, and go to state 27
T_BOOL   shift, and go to state 28
T_STR    shift, and go to state 29
T_VOID   shift, and go to state 30
T_TUPLE  shift, and go to state 31

T_INT     [reduce using rule 39 (function_list)]
T_BOOL    [reduce using rule 39 (function_list)]
T_STR     [reduce using rule 39 (function_list)]
T_VOID    [reduce using rule 39 (function_list)]
T_TUPLE   [reduce using rule 39 (function_list)]
$default  reduce using rule 39 (function_list)

variable       go to state 32
simpletype     go to state 33
type           go to state 34
function_list  go to state 35

我已经尝试了各种%prec语句,以使它更喜欢reduce(虽然我不确定在这种情况下会有什么不同),但是没有成功使用bison使用reduce来解决这个问题,而且我也试过了洗牌规则制定像non_empty_var_list这样的新规则并将主体拆分为function_list | non_empty_var_list function_list并没有任何尝试可以解决这个问题.我是新手,我已经没有解决这个问题的想法了,所以我完全感到困惑.

Answer 1

问题在于变量和函数都以TYPE和IDENTIFIER开头

不完全是.问题是function_list是左递归的,可能是空的.

当您variable在前瞻中使用TYPE 到达分号时,解析器可以根据第一个variable_list生成将变量缩减为variable_list.现在接下来可能是function_list,并且允许function_list为空.因此它可以对function_list进行空缩减,这是开始解析函数所必需的.在看到'('这是第三个下一个标记之前,它不知道不会这样做.这太遥远了.

这是一个简单的解决方案:

function_list: function function_list
             | /* EMPTY */
             ;

另一个解决方案是使function_list非可选:

body: variable_list function_list
    | variable_list
    ;

function_list: function_list function
             | function
             ;

如果你这样做,野牛可以移动TYPE标记,而不必决定它是变量或函数定义的开始.