野牛移减少冲突

一个精简与冲突语法的版本：野牛移减少冲突

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和标识符开始，如

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

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

parse error: syntax error, unexpected '(', expecting ',' or ';' [after 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报表，使其更喜欢减少（虽然我不知道的区别是在这种情况下的），用没有成功使野牛使用减少来解决这个问题，并且我也尝试了对制定新规则（比如non_empty_var_list并将正文拆分为function_list | non_empty_var_list function_list并且没有任何尝试可以解决此问题。我对此很陌生，但我已经没有了解如何解决这个问题的想法，所以我完全被困惑了。

来源

2012-10-29 mcu17818

the problem is in that variables and functions both start with TYPE and IDENTIFIER

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

当您到达用分界符中的TYPE终止variable的分号时，解析器可以根据第一个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令牌

来源

2012-10-29 03:51:45 rici

啊，我试过嘛王变量列表右递归，但不是函数列表。这确实解决了它，虽然我更喜欢它是递归的，所以我从来没有遇到堆栈空间问题。我通过指定一个glr解析器来找到另一个解决方案，这也解决了我的问题。假设我无法使函数列表不可选，只能是非空的，否则解决方案比其他解决方案更好，假设我不能使函数列表非选择性地执行 – mcu17818

@ mcu17818：按照第二种选择中的rici建议，不会使'function_list'不可选，只是非空。它仍然允许一个没有'function_list'的'body'，只需要额外的'body'规则。 –

哦，我现在明白了。谢谢。我会去做 – mcu17818

野牛移减少冲突

回答

相关问题