프로그래밍 언어 대부분은 SLR 정도로도 해결되는 것 같다..

더욱이 LALR 기반으로 했으니 더 넓은 범위를 카바칠수 있다..

하지만 그래도 충돌이 발생하는데

대부분의 프로그래밍 언어가 if-else 를 지원하기 때문이다.


shift-reduce conflict 발생

if-else 구문을 간략화하여 살펴보면 충돌은 필연적이다.

그러기에 야크에서는 충돌이 발생했을 때 해결할 수 있는 방법으로



우선순위를 미리 지정한다.

대개

%left + -
%left * / 

식으로 미리 써 놓는다.

그리고 같은 우선순위에서 충돌이 날 수도 있는데

좌결합이면 reduce를 먼저 선택해야 할 수 밖에 없다.

%right  를 적으면 우결합 이다.


정리해보면

shift-reduce 충돌이 있을 때  

1. 우선순위가 높은 것을 선택한다. 
( 사칙연산에서 + 연산이 들어간 것을 reduce 하느냐  , * 심볼을 shift 하느냐 일때 * 를 선택하는 식)

2. 같은 우선순위면 좌결합이면 reduce를 선택, 우결합이면 shift 를 선택


나는 또 우선순위를 명시하기가 귀찬아서

충돌이 발생하면 리스트로 매달고

나중에 action goto table 을 생성할 때 리스트에 따라

둘중 하나를 결정하는 식으로 하였으나 

진정한 야크의 정신에서 벗어나는것 같다.. ㅠ


reduce-reduce  충돌은 LR(1) 과 LALR과 차이가 있는데

간선이 동일하면 그에 따른 CLOSURE 도 동일하게 생성이 되나

LR(1) 같은 경우는 룩어헤드가 각각 다르기 때문에 다른 상태로 친다.

하지만 LALR 같은 경우는 동일한 핸들 위치를 가지고 있으면

하나의 상태로 묶기 때문에  룩어헤드가 합집합 된다.


따라서 shift-reduce 충돌의 경우 , LR(1), 이나 LALR 이나 똑같으나

reduce-reduce 충돌의 경우 LR(1)에서 충돌이 아닌데도 LALR에서 충돌이 나타날수 있다.



하지만 reduce-reduce 충돌이 발생하는 경우는 아주 드문것 같다.


충돌 해결을 위한 루틴은 간단하니

그냥 LALR 구성하는 파일에 다 들어가 있어

코드는 다 명시한다.






대략 이렇게 선택하는 식으로 충돌을 해결한다.

같은 우선순위인 경우 좌결합이므로 reduce를 선택

그 외는 높은 우선순위 선택..

Posted by 멍충한아싸

댓글을 달아 주세요