移位/減少衝突yacc

請參閱yacc的以下代碼。如果我刪除了生產係數：'！' expr，解析衝突消失。這裏發生了什麼？移位/減少衝突yacc

%{ 
#include <stdio.h> 
#include <ctype.h> 

%} 


%token TRUE 
%token FALSE 


%% 
line : line expr '\n' { printf("%d\n", $2); } 
    | line '\n' 
| 
; 
expr : expr "or" term { printf("expr : expr or term\n"); $$ = $1 | $3; } 
| term  { printf("expr : term\n");  } 
; 
term : term "and" factor { printf("term : term and factor\n"); $$ = $1 & $3; } 
| factor  { printf("term : factor\n"); } 
; 
factor : '(' expr ')' { printf("factor : (expr)\n"); $$ = $2; } 
| '!' expr { printf("factor : !expr\n"); $$ = !$2; } 
| TRUE  { printf("factor : TRUE\n"); } 
| FALSE  { printf("factor : FALSE\n"); } 
; 
%% 

#include "lex.yy.c" 

int main(int argc, char** argv) 
{ 
while (yyparse() == 0) { 
    } 

    return 0; 
}

來源

2009-11-14 Rohit Banga

它看起來對我來說，衝突可能出現，因爲當解析器看到一個「！」，它的運行與你重寫爲「expr的」問題。忽略其他生產的「因素」，具體看看這兩個作品：「！」

expr : expr "or" term { printf("expr : expr or term\n"); $$ = $1 | $3; } 
     | term   { printf("expr : term\n"); } 
     ; 

factor : '!' expr  { printf("factor : !expr\n"); $$ = !$2; }

由於expr是遞歸的，當分析器看到了，它知道否定適用於以下EXPR，但如果你寫「！TRUE OR TRUE」，這個否定只適用於第一個真，還是全部的析取？

編輯：換句話說，它不能決定是否需要移動「或」或減少「表達式」。

在yacc中設置-v命令行選項將生成一個.output文件，其中包含所有類型的好東西，包括shift/reduce衝突的診斷信息。它會向您展示DFA的所有狀態以及發生衝突的位置，並且有時會向您顯示原因。

將邏輯上的「術語」和「因素」之間的否定放在他們自己的生產中，應該能夠做到。

來源

2009-11-14 18:54:37

如果將factor: ! expr更改爲factor: ! factor，衝突將消失。

只分析第一個衝突，問題是term可以減少到expr或成爲更復雜的term。如果沒有!，這個決定只能用一個符號向前看。

請注意，shift/reduce衝突不一定是錯誤。衝突通過轉變來解決，這可能就是你想要的。大多數實際生產語法都包含一些轉換/減少衝突。

來源

2009-11-14 19:11:06 DigitalRoss

移位/減少衝突yacc

回答

相關問題