轉換減少衝突

我在理解轉換/減少關於語法的轉換/減少的問題時遇到了問題，我知道它沒有含糊之處。這種情況是if類型之一，但它不是'懸而未決'的問題，因爲我有強制性的END子句分隔代碼塊。轉換減少衝突

這裏是GPPG語法（它是一種野牛一樣編譯器編譯...這不是一個回聲）：

%output=program.cs 

%start program 

%token FOR 
%token END 
%token THINGS 
%token WHILE 
%token SET 
%token IF 
%token ELSEIF 
%token ELSE 
%% 

program : statements 
     ; 

statements : /*empty */ 
      | statements stmt 
      ; 

stmt : flow 
    | THINGS 
    ; 

flow : '#' IF '(' ')' statements else 
    ; 

else : '#' END 
    | '#' ELSE statements '#' END 
    | elseifs 
    ; 

elseifs : elseifs '#' ELSEIF statements else 
     | '#' ELSEIF statements else 
     ;

這裏是衝突輸出：

// Parser Conflict Information for grammar file "program.y" 

Shift/Reduce conflict on symbol "'#'", parser will shift 
Reduce 10: else -> elseifs 
Shift "'#'": State-22 -> State-23 
    Items for From-state State 22 
    10 else: elseifs . 
    -lookahead: '#', THINGS, EOF 
    11 elseifs: elseifs . '#' ELSEIF statements else 
    Items for Next-state State 23 
    11 elseifs: elseifs '#' . ELSEIF statements else 

// End conflict information for parser

我已經切換了一切，我確實知道如何解決它，但該解決方案涉及放棄'elseif'上的左遞歸以獲得正確的遞歸。

香港專業教育學院已通過所有scarse文檔我有一個關於這個問題（我張貼在最後的一些鏈接），並在互聯網上發現至今還沒有找到一個很好的解決方案。我知道ANTLR，我現在不想考慮它。請將您的解決方案限制爲Yacc/Bison解析器。

我會感激優雅的解決方案，我設法做到這一點，通過排除/ *空* /規則和重複所有需要一個空列表，但在更大的語法我在工作它只是結束了像'sparghetti語法症候羣' 。

這裏有一些鏈接：

http://nitsan.org/~maratb/cs164/bison.html

http://compilers.iecc.com/comparch/article/98-01-079

GPPG, the parser I'm using

Bison manual

來源

2008-10-12 Caerbanog

您的修訂ELSEIF規則沒有標記符的條件 - 它應該名義上加'（'和'）'。

更嚴重的是，你現在有

elsebody : else 
     | elseifs else 
     ;

和

elseifs : /* Nothing */ 
     | elseifs ...something... 
     ;

的 '無'，不需要的規則;它被隱含地由沒有'別名'的'別人'照顧。

我會非常傾向於使用規則「opt_elseifs」，「opt_else」和「結束」：

flow : '#' IF '(' ')' statements opt_elseifs opt_else end 
    ; 

opt_elseifs : /* Nothing */ 
      | opt_elseifs '#' ELSIF '(' ')' statements 
      ; 

opt_else : /* Nothing */ 
     | '#' ELSE statements 
     ; 

end : '#' END 
    ;

我不通過解析器生成器上運行這一點，但我覺得這是比較容易理解。

來源

2008-10-12 23:39:21

是的。我也期待它的工作，你說的最容易理解是對的。但是我確實在解析器上運行了它，並且不幸地給出了4個轉換/減少衝突。通過gppg運行並親自查看。我不明白（得到我的'龍'編譯器手冊回） – Caerbanog 2008-10-12 23:58:19

我認爲這個問題是elseifs子句。

elseifs : elseifs '#' ELSEIF statements else 
     | '#' ELSEIF statements else 
     ;

我覺得不需要的第一個版本，因爲else子句指回elseifs反正：

else : '#' END 
    | '#' ELSE statements '#' END 
    | elseifs 
    ;

如果你改變elseifs？：

elseifs : '#' ELSEIF statements else 
     ;

來源

2008-10-12 22:10:20

你說得對。排隊解決衝突。我將原來的語法簡化爲這個小問題，試圖找出問題並最終引入錯誤。我想我必須重做我原來更復雜的語法，並將其用於解決此問題。 – Caerbanog 2008-10-12 22:17:23

Darn：剛注意到它爲什麼起作用。它再次是正確的遞歸。我之後的解決方案應該在elseifs上留下遞歸，因爲它們可能是一個很長的流。 – Caerbanog 2008-10-12 22:20:20

我會發生什麼還在原地開關的事情角落找尋，和我原來的問題了，因爲elseifs一些錯誤序列有一個其他 allways在最後這是錯誤的。這裏是另一個走的問題，這個時候，我得到兩個轉變/減少衝突：

flow : '#' IF '(' ')' statements elsebody 
    ; 

elsebody : else 
     | elseifs else 
     ; 

else : '#' ELSE statements '#' END 
    | '#' END 
    ; 

elseifs : /* empty */ 
     | elseifs '#' ELSEIF statements 
     ;

此刻的衝突是：

// Parser Conflict Information for grammar file "program.y" 

Shift/Reduce conflict on symbol "'#'", parser will shift 
Reduce 12: elseifs -> /* empty */ 
Shift "'#'": State-10 -> State-13 
    Items for From-state State 10 
    7 flow: '#' IF '(' ')' statements . elsebody 
    4 statements: statements . stmt 
    Items for Next-state State 13 
    10 else: '#' . ELSE statements '#' END 
    11 else: '#' . END 
    7 flow: '#' . IF '(' ')' statements elsebody 

Shift/Reduce conflict on symbol "'#'", parser will shift 
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements 
Shift "'#'": State-24 -> State-6 
    Items for From-state State 24 
    13 elseifs: elseifs '#' ELSEIF statements . 
    -lookahead: '#' 
    4 statements: statements . stmt 
    Items for Next-state State 6 
    7 flow: '#' . IF '(' ')' statements elsebody 

// End conflict information for parser

空規則只是加重GPPG我是affraid。但他們似乎很自然地使用我一直在嘗試他們。

我已經知道權利遞歸解決問題，因爲1800信息說過。但是我正在尋找與的解決方案在elseifs條款左遞歸。

來源

2008-10-12 22:42:20 Caerbanog

elsebody : elseifs else 
     | elseifs 
     ; 

elseifs : /* empty */ 
     | elseifs '#' ELSEIF statements 
     ; 

else : '#' ELSE statements '#' END 
    ;

我認爲這應該留下遞歸併始終終止。

來源

2008-10-12 23:43:57

上面Jonathan的答案似乎是最好的，但由於它不適合你，我有幾個建議你可以嘗試一下，這將有助於你調試錯誤。

首先，你有沒有考慮過使用散列/尖角符號作爲令牌本身的一部分（即#END，#IF等）？這樣他們就可以被詞法分析器取出，這意味着它們不必被包含在解析器中。

其次，我會敦促你重寫規則而不重複任何令牌流。（不要重複自己的原則的一部分。）所以規則「'＃'ELSEIF語句其他」應該只存在於該文件中的一個位置（不是上面的兩個）。

最後，我建議您查看IF/ELSEIF/ELSE標記的優先級和關聯性。我知道你應該能夠編寫一個不需要這個的解析器，但它可能是你在這種情況下需要的東西。

來源

2008-10-13 00:40:04 Daemin

好的 - 這裏是if語句的語法（不是最小的）。我將它從我有的一些代碼中挖出來（稱爲adhoc，基於Kernighan & Plauger的「UNIX編程環境」）。這個大綱語法與Yacc編譯時沒有衝突。

%token NUMBER IF ELSE 
%token ELIF END 
%token THEN 
%start program 

%% 

program 
    : stmtlist 
    ; 

stmtlist 
    : /* Nothing */ 
    | stmtlist stmt 
    ; 

stmt 
    : ifstmt 
    ; 

ifstmt 
    : ifcond endif 
    | ifcond else begin 
    | ifcond eliflist begin 
    ; 

ifcond 
    : ifstart cond then stmtlist 
    ; 

ifstart 
    : IF 
    ; 

cond 
    : '(' expr ')' 
    ; 

then 
    : /* Nothing */ 
    | THEN 
    ; 

endif 
    : END IF begin 
    ; 

else 
    : ELSE stmtlist END IF 
    ; 

eliflist 
    : elifblock 
    | elifcond eliflist begin   /* RIGHT RECURSION */ 
    ; 

elifblock 
    : elifcond else begin 
    | elifcond endif 
    ; 

elifcond 
    : elif cond then stmtlist end 
    ; 

elif 
    : ELIF 
    ; 

begin 
    : /* Nothing */ 
    ; 

end 
    : /* Nothing */ 
    ; 

expr 
    : NUMBER 
    ; 

%%

我使用的「NUMBER」作爲虛設元件，而不是東西，我使用ELIF代替ELSEIF。它包含THEN，但這是可選的。 '開始'和'結束'操作用於獲取生成程序中的程序計數器 - 因此應該可以從中刪除而不影響它。

有一個原因，我認爲我需要使用正確的遞歸，而不是正常的左遞歸 - 但我認爲這是與我使用的代碼生成策略，而不是其他任何事情。評論中的問號在原文中;我記得對此並不滿意。整個計劃確實奏效 - 這個項目在過去十年左右一直處於支撐之下（嗯......我在2004年底和2005年初做了一些工作;在此之前，它是在1992年和1993年）。

我沒有花時間瞭解爲什麼這個編譯無衝突，我之前概述的沒有。我希望它有幫助。

來源

2008-10-13 04:10:25

轉換減少衝突

回答

相關問題