shift/reduce conflict , reduce/reduce conflict의 정의

yacc나 bison에 -v 옵션을 붙여서 컴파일 하면 output 파일이 나오는데, 이를 열어보면
yacc 코드의 어느부분이 conflict를 발생시키는 지 알 수 있다.

name.output 의 예 :

State 93 conflicts: 1 reduce/reduce

State 94 conflicts: 4 shift/reduce

State 134 conflicts: 1 shift/reduce

현재 총 6개의 충돌이 있고, state 134에 어떤 충돌이 있는지 따라가보니

state 134

   31 SelectionStmt: IF '(' Expr ')' IFDE Stmt .

   33              | IF '(' Expr ')' IFDE Stmt . ELSE $@2 Stmt

    ELSE  shift, and go to state 137

    ELSE      [reduce using rule 31 (SelectionStmt)]

    $default  reduce using rule 31 (SelectionStmt)

위와 같이 else 토큰이 들어왔을떄 이를 31 rule을 써서 reduce 할지, state 137로 shift 할지 몰라서 충돌에러를 발생시켰다.
 

yacc 파서안에는 sementic stack 이 존재한다. 그리고 파서에서 넘어오는

각종 토큰들을 계속해서 stack 안으로 push 하는데, 이러한 동작을 shift라고 한다

그리고 cfg 문법의 우변에 있는 토큰조합들이 스택에 갖추어지는순간,

yacc는 이것을 '인식'하여 스택에서 다시 제거하게된다. 이를 reduce라고한다.

즉, E: A '+' B 에서 스택에 A와 '+'순으로 쌓여있고 B가 들어오는 순간

스택의 순서는 A '+' B가 되어 yacc가 인식하게되고 pop을 이용해

A '+' B 는 E 라는 상위 토큰으로 reduce 되어진다.

따라서 reduce/reduce conflict란, 

E : A + B 

 |  B + C 

와 같이 yacc가 어느쪽 문법으로 reduce 해야할지 모르는 상황을 말한다.

shift/reduce conflict란, 

E : A B C

|   D C

D:  A B

에서 A B C 라는 입력이 들어왔을 경우, A B 가 스택에 있는 상황에서

C를 shift 해야할지, 아니면 A B 를 D로 reduce 해야할지 yacc가 알 수

없는 상황을 말한다.

하면 할수록 재밌군.