野牛移減少衝突

一個精簡與衝突語法的版本：野牛移減少衝突

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

野牛移減少衝突

回答

相關問題