在CUP中移位/減少衝突

我正在嘗試爲JFlex和Cup編寫javascript-ish語言的解析器，但是我遇到了致命移位/減少問題以及減少/減少問題的一些問題。在CUP中移位/減少衝突

我已經徹底搜索並發現了大量的例子，但我無法將這些推斷到我的語法。我迄今爲止的理解是，這些問題是因爲解析器無法確定它應該採用哪種方式，因爲它無法區分。

我的語法如下：以INPUT開頭;

INPUT::= PROGRAM; 

PROGRAM::= FUNCTION NEWLINE PROGRAM 
| NEWLINE PROGRAM; 

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der; 

    OPTIONAL ::= 
    | TYPE; 


    TYPE::= integer 
    | boolean 

    ARG ::= 
    | TYPE id MORE_ARGS; 

    MORE_ARGS ::= 
    | colon TYPE id MORE_ARGS; 


    NEWLINE ::= salto NEWLINE 
    | ; 

    BODY ::= ;

我得到一些衝突，但這些2僅僅是個例子：

Warning : *** Shift/Reduce conflict found in state #5 
between NEWLINE ::= (*) 
and  NEWLINE ::= (*) salto NEWLINE 
under symbol salto 
Resolved in favor of shifting. 

Warning : *** Shift/Reduce conflict found in state #0 
between NEWLINE ::= (*) 
and  FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
under symbol function 
Resolved in favor of shifting.

PS：語法要複雜得多，但我想，如果我看到這些移位/減少的問題已解決，我將能夠解決其餘問題。

感謝您的回答。

來源

2017-06-04 inidar

PROGRAM是無用的（in the technical sense）。也就是說，它不能產生任何句子，因爲在

PROGRAM::= FUNCTION NEWLINE PROGRAM 
     | NEWLINE PROGRAM;

這兩個產品的PROGRAM是遞歸的。爲了使非終端有用，它需要能夠最終生成一些終端串，爲此它必須至少有一個非遞歸生產;否則，遞歸永遠不能終止。我很驚訝銀聯沒有提到你。或者它可以，而且你選擇忽略警告。

這是一個問題 - 無用的非終端真的無法匹配任何東西，所以它們最終會導致解析錯誤 - 但這不是您報告的解析衝突。衝突來自同一生產的另一個特點，這與你不能以0分割的事實有關。

關於什麼都不是，沒有任何數量的東西仍然沒有。所以，如果你有很多不知道的東西，並且有人過來問你究竟有多少個沒有，你會有一些問題，因爲要從「0 *很多」中獲得「充足」，你必須計算「0/0」，這不是一個明確定義的值。（如果你有足夠多的兩個人，並且有人問你有多少個，那麼這不會是一個問題：假設大量的二者達到40，你可以很容易地計算出40/2 = 20，這可以解決問題因爲20 * 2 = 40。）

所以在這裏我們沒有算術，我們有一串符號。不幸的是，沒有符號的字符串真的是看不見的，就像所有那些千年數字都是0，直到一些阿拉伯數學家發現不能寫任何東西的價值。

如果這是所有在我身邊的就是，你有

PROGRAM::= ... something ... 
     | NEWLINE PROGRAM;

但NEWLINE被允許生產什麼。

NEWLINE ::= salto NEWLINE 
     | ;

因此，PROGRAM的第二次遞歸生產可能不會添加任何內容。而且它可能不會增加很多次，因爲生產是遞歸的。但是解析器需要具有確定性：它需要確切地知道存在多少個nothings，這樣它就可以將每個nothing減少到非終端，然後減少一個新的非終端PROGRAM。它真的不知道要添加多少空格。

總之，可選的記號和重複的記號是不明確的。如果您要在您的語言中插入任何內容，則需要確保有固定數量的nothings，因爲這是解析器可以毫不含糊地解析虛無的唯一方法。

現在，由於該特定遞歸的唯一一點（據我所知）是允許空的換行符終止的語句（因爲換行符而可見，但什麼都不做）。你能做到這一點通過改變遞歸避免什麼：

PROGRAM ::= ... 
     | salto PROGRAM;

雖然它不相關的當前的問題，我覺得有必要提一提，銀聯是一個LALR解析器生成和所有的東西你可能已經在互聯網上了解或閱讀了關於遞歸下降解析器不能處理左遞歸不適用。（我刪除了關於解析技術的教學方式，所以您必須嘗試從我留下的提示中恢復它。）自下而上的解析器生成器，如CUP和yacc/bison 愛左遞歸。當然，他們也可以處理右遞歸，但是很不情願，因爲除了左遞歸之外，他們需要浪費每個遞歸的堆棧空間。所以沒有必要扭曲你的語法來對付這個缺陷。只是自然寫語法而快樂。（所以你很少，如果需要代表什麼「的其他」非終端）。

PD：沒什麼大量是從1934年歌劇Porgy and Bess一個特定的文化參考一首歌。

來源

2017-06-04 05:29:31 rici

@ rici非常感謝。終於有了你的幫助 – inidar

在CUP中移位/減少衝突

回答

相關問題