파서는 shift/reduce 충돌을 어떻게 해결합니까?

Question

나는 텍스트 파일에서 표현의 수 (한 줄에 하나씩)를 해결하는 산술 표현을위한 문법을 ​​가지고있다. YACC를 컴파일하는 동안 메시지 2 교대가 충돌을 줄이려고합니다. 하지만 제 계산은 적절합니다. 구문 분석기가 적절한 출력을 제공하면 교대/축소 충돌을 어떻게 해결할 수 있습니까? 그리고 제 경우에는 YACC 문법에서 그것을 해결할 방법이 있습니다.

YACC 문법 내 문법 이러한 충돌을 제거하기 위해 무엇을해야 변화

Calc : Expr    {printf(" = %d\n",$1);} 
    | Calc Expr   {printf(" = %d\n",$2);} 
    | error    {yyerror("\nBad Expression\n ");} 
    ; 
Expr : Term    { $$ = $1;   } 
    | Expr '+' Term  { $$ = $1 + $3; } 
    | Expr '-' Term  { $$ = $1 - $3; } 
    ; 
Term : Fact    { $$ = $1;   } 
    | Term '*' Fact  { $$ = $1 * $3; } 
    | Term '/' Fact  { if($3==0){ 
       yyerror("Divide by Zero Encountered."); 
      break;} 
       else 
       $$ = $1/$3;  
        } 
    ; 
Fact : Prim    { $$ = $1;  } 
    | '-' Prim   { $$ = -$2;  } 
    ;  
Prim : '(' Expr ')'  { $$ = $2;  } 
    | Id     { $$ = $1;  } 
    ; 
Id :NUM     { $$ = yylval; } 
    ; 

?

Answer 1

Bison/yacc는 이동을 선택하여 shift-reduce 충돌을 해결합니다. 이것은 bison manual의 Shift-Reduce conflict 섹션에서 설명합니다.

귀하의 입력은 단지 일련의 Expr입니다. 이들 사이에 구분자없이 함께 실행하십시오.

4 - 2 

하나 개의 표현 (4-2을)이 될 수 있거나 두 식 (4, -2) 될 수있다 : 즉 것을 의미한다. 들소 생성 된 파서는 항상 이동하는 것을 선호하기 때문에, 파서는이 두 줄에 입력 한 경우에도 하나의 표현으로 구문 분석을 선택합니다 :

4 
-2 

을 사용하면 사용자가 그런 자신의 표현을 입력 할 수 있도록하려면, 분리 기호가 없으면 충돌이 생길 수도 있고 (비교적 양성이기 때문에) 또는 문법에 성문화 할 수 있지만 꽤 많은 작업이 필요합니다. 문법에 넣으려면 Expr의 두 가지 유형을 정의해야합니다. 하나는 최상위 수준에서 사용하는 것이고 단항 빼기로 시작할 수없고 다른 하나는 다른 곳에서 사용할 수 있습니다. 단항 마이너스로 시작할 수 있습니다.

정말하고 싶은 것은 뉴 라인이나 다른 종류의 표현 구분 기호를 사용하는 것입니다. 개행 문자를 파서에 전달하고 Calc을 Calc: | Calc '\n' | Calc Expr '\n'으로 변경하는 것만 큼 간단합니다.

---

나는 이것이 다른 곳에서 나타날 것이라고 확신하지만 찾을 수 없습니다. 그래서 표현식의 처음에 단항 마이너스를 사용하는 것을 허용하지 않으므로 구분 기호없이 표현식을 함께 실행할 수 있습니다. n_을 시작하는 비 단말기는 단항 마이너스로 시작할 수 없습니다 :

문법과 같은 언어를 구문 분석

input: %empty | input n_expr { /* print $2 */ } 

expr: term | expr '+' term | expr '-' term 
n_expr: n_term | n_expr '+' term | n_expr '-' term 

term: factor | term '*' factor | term '/' factor 
n_term: value | n_term '+' factor | n_term '/' factor 

factor: value | '-' factor 

value: NUM | '(' expr ')' 

하지만 시프트 감소 충돌을 생성하지 않고. 동일한 언어를 파싱하기 때문에 입력은 여전히 ​​하나의 표현식으로 파싱됩니다.

4 
(-2)