드디어 대망의 LA 집합을 구한다.

이것을 구하게 되면

해당 LR 상태에 대해 이후 나올 심볼을 알 수 있으므로

그 심볼이 나오면 reduce를 적용시켜서 스택을 줄여나갈 수 있다.

우선 알고리즘은 다음과 같다.

1. 헤드가 $tart 이면 ( start symbol) 이면 이후 나올 룩어헤드 심볼은 {$ (맨끝)} 이다.

2. reduce 대상 핸들을 가지고 있는 룰에 대해 헤드가 start symbol 이 아니라면 먼저 기원(pred 함수를 사용)을 구한다

3. 그 핸들이 위치한 룰의 기원을 가지고 있는 상태에 가서 해당 룰의 헤드 심볼 이후에 나올수 있는 FIRST 집합을 구한다.

4. 만일 FIRST 집합에 epsilon 이 포함될수도 있으므로 헤드 심볼 이후 나오는 모든 심볼에 대해 위 알고리즘을 
다시 적용한 것과 Ring sum 한다..


처음엔 굉장히 이해하기 어려웠는데 머릿속에 그려보면서 이해하게 되면

과정은 확실히 이해가 될 것이다. 하지만 이를 코드로 표현하는 것이 문제인데

나 같은 경우는 다음과 같이 하였다.


기본적으로 3중 포문인데 또 그 안에서 재귀 호출 하므로

그야말로 엄청 비효율 적이다. 개선 시킬 여지가 있을 것 같지만

지금은 알고리즘을 표현하는데도 급급하므로 우선 넘어간다.
Posted by 멍충한아싸

댓글을 달아 주세요