野牛转移 - 减少冲突-Java 学习之路

带有冲突的精简版语法：

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并没有任何尝试可以解决这个问题 . 我是新手，我已经没有解决这个问题的想法了，所以我完全感到困惑 .

1 回答

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

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

当您到达分号时，在前瞻中使用TYPE终止 variable ，解析器可以根据第一个variable_list生成将变量缩减为variable_list . 现在接下来可能是function_list，并且允许function_list为空 . 因此它可以对function_list进行空缩减，这是开始解析函数所必需的 . 它可以't know not to do that until it looks at the '（' which is the third next token. That'太遥远而无法相关 .

这是一个简单的解决方案：
```
function_list: function function_list
             | /* EMPTY */
             ;
```
另一个解决方案是使function_list非可选：
```
body: variable_list function_list
    | variable_list
    ;

function_list: function_list function
             | function
             ;
```
如果你这样做，野牛可以移动TYPE标记，而不必决定它是变量或函数定义的开始 .
回复于 2024-04-29T16:30:01+08:00

野牛转移 - 减少冲突

1 回答

相关问题