shift/reduce 충돌 yacc

Question

yacc에 대한 다음 코드를 참조하십시오. 생산 요소를 제거하면 '!' expr, 구문 분석 충돌이 사라집니다. 여기에 무슨 일이 일어 났습니까? 파서가 볼 때 때문에 충돌이 아마 발생과 같은

%{ 
#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; 
} 

Answer 1

그것은 나에게 보이는 '을!'이 '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"라고 쓰면, 부정은 최초 진실 또는 전체 분리에만 적용됩니까?

EDIT : 다른 말로하면 "or"또는 "expr"을 이동해야하는지 결정할 수 없습니다.

yacc에서 -v 명령 줄 옵션을 설정하면 shift/reduce 충돌에 대한 진단 정보를 비롯하여 모든 종류의 이점이있는 .output 파일이 생성됩니다. DFA의 모든 상태와 충돌이 발생한 위치가 표시되며 때로는 그 이유를 정확하게 표시합니다.

논리적으로는 "기간"과 "요인"사이에 부정을 두는 것이 트릭을 수행해야합니다.

Answer 2

factor: ! expr을 factor: ! factor으로 변경하면 충돌이 사라집니다.

단지 첫 번째 충돌을 분석하면 term이 expr으로 줄어들거나 더 복잡한 term이 될 수 있다는 점이 문제입니다. !이 없으면이 결정은 하나의 미리보기 심볼로 만 이루어질 수 있습니다.

시프트/줄이기 충돌이 반드시 오류는 아닙니다. 갈등은 당신이 원하는 것일 수있는 전환을함으로써 해결됩니다. 대부분의 실제 제품 문법에는 여러 가지 시프트/감소 충돌이 있습니다.