試圖找到移位/減少語法

衝突

我有以下的語法（Yacc中），這是一個簡單的C編譯器的開始，我是從一個簡單的if聲明開始：試圖找到移位/減少語法

S : E 
    ; 

E : COND_NO_ELSE 
    ; 

COND_NO_ELSE : IF BOOL_EXP BLOCK 
; 

BLOCK : LC EXP RC 

BOOL_EXP : LP EXP BOOL_OP EXP RP 
    ; 

BOOL_OP : LT_OP 
    | GT_OP 
    | LE_OP 
    | GE_OP 
    | EQ_OP 
    | NE_OP 
    ; 

MATH_OP : PLUS_OP 
    ; 

EXP : IDENTIFIER 
    | EXP MATH_OP EXP 
    ;

這裏有對於相關的規則詞法分析器掃描儀：

"="  { yylval.string = strdup(yytext); return ASSIGN;} 
"+"  { yylval.string = strdup(yytext); return PLUS_OP;} 
"-"  { yylval.string = strdup(yytext); return MINUS_OP;} 
"*"  { yylval.string = strdup(yytext); return MULTIPLY_OP;} 
"/"  { yylval.string = strdup(yytext); return DIV_OP;} 
"%"  { yylval.string = strdup(yytext); return MOD_OP;} 

"<"  { yylval.string = strdup(yytext); return LT_OP;} 
">"  { yylval.string = strdup(yytext); return GT_OP; } 
"<="  { yylval.string = strdup(yytext); return LE_OP; } 
">="  { yylval.string = strdup(yytext); return GE_OP; } 
"=="  { yylval.string = strdup(yytext); return EQ_OP; } 
"!="  { yylval.string = strdup(yytext); return NE_OP; } 
"("  { yylval.string = strdup(yytext); return LP; } 
")"  { yylval.string = strdup(yytext); return RP; } 
"{"  { yylval.string = strdup(yytext); return LC; } 
"}"  { yylval.string = strdup(yytext); return RC; } 
if { return IF; }

我知道，衝突開始時，我加入MATH_OP（我把所有的數學運營商比，得到了5個衝突，不是刪除所有，但PLUS_OP並獲得1個移位/減少衝突）。

我使用的-v標誌輸出文件的建議here，並檢查this的問題，但它並不像我的語法太多...

我怎樣才能找到衝突？

來源

2016-12-16 argamanza

你的語法包括生產：

EXP : EXP MATH_OP EXP

這本質上是不明確的。假設你有兩個運營商：

1 + 2 * 3

顯然，上面是EXP MATH_OP EXP（因爲沒有其他選擇），但就是

[EXP: 1 + 2] [MATH_OP *] [EXP: 3]

還是

[EXP: 1] [MATH_OP +] [EXP: 2 * 3]

這兩個解析顯然有不同的語義，語法允許兩者。

即使你有一個單一的操作符，也存在一個模棱兩可的問題（事實上，相同的模糊性），儘管它發生在通常的定義+評估將是相同的。（這將是與單一運營商不同 -，這使得不確定性略微清晰。）

有用於算術表達式創建YACC /野牛語法兩個正常策略：

明確指示如何解析表達式。（Example from Wikipedia）。
使用優先聲明隱式限制解析。（Example from bison manual。）

第一個策略是字典但更靈活;如果您想了解LR解析是如何工作的，那可能會更好，因爲它是明確的。第二種策略更加緊湊並且可以更容易閱讀（因爲許多隨便的讀者比上下文無關的語法更能理解操作符的優先級列表），但理解它是如何工作的更詳細的工作。

在任何情況下，您都不能將所有運算符合併到單個非終端，如MATH_OP，因爲具有不同優先級的運算符在語法上是不同的。

您還可以在本網站找到許多相關的問題和解答。

順便說一句，這是非常有用的很少傳遞一個純粹的語法令牌的字符串值，就像+解析器。解析器不需要該值，因爲它已經知道該令牌類型，所以strdup()是不必要的開銷，並且相應的free()混亂了語法操作（同樣，它不明顯放在哪裏）。如果您認爲您需要字符串來跟蹤語法操作，請查看bison's debug facilities，它們比在整個解析器中散佈printfs更容易使用，更可靠。如果你根本沒有爲操作符使用語義值，那麼你顯然不需要去複製一個字符串然後釋放或泄漏內存的麻煩。

來源

2016-12-16 17:33:18 rici

試圖找到移位/減少語法

回答

相關問題