closure 연산에서 가장 중요한 개념은 

커널 아이템과 논커널 아이템이 무엇인지 아는것이 중요하다.


1. 커널 아이템

초기항목이다.
즉 $tart -> S  (문법 트리에서 최상위노드)
핸들이 맨앞에 있지 않는 것들이다..

2. 핸들이 생성규칙의 맨앞에 있는 것들..


이것이 어떤 의미가 있는가 하면

핸들이 논터미널을 읽기 직전이라면

해당 논터미널의 생성규칙들의 맨앞을 읽기전과 마찬가지이다.

또 그 생성규칙 맨앞도 또 논터미널이면

그 논터미널의 생성규칙들의 맨앞을 읽기전과 마찬가지이다.

즉 초기 넘어온 커널항목 들로부터  계산하여 

파생될 수 있는 모든 생성규칙의 핸들들(맨앞에)인 비커널 항목들을 찾아내는 것이다.


이것을 찾아내는 알고리즘은 다음과 같다.

closure 연산

1. 자기자신을 집합에 추가한다.
2. 만일 논터미널이면 그 논터미널의 생성규칙들을 전부 찾아 
맨앞에 대해 다시 closure 연산한다.


이를 C로 실제로 구현하기 위해서

집합개념을 다음과 같이 표현한다.

int lr0[LR_NUM][RULE_NUM];
int lr0_pos;

LR 집합은 DFA 연산하기 전에는 몇개나 될지 알 수 없다.

따라서 기존 rule의 개수보다 충분히 큰 크기로 잡았다 
(LR_NUM에 정의되고 크기는 룰크기의 4배... 하지만 4배보다 훨씬더 늘어날 가능성이 있다.)

RULE_NUM 은 룰의 개수인데

특이한 점은 해당 룰에서 핸들의 위치를 알아내야 하면 3차원 배열을 써야할텐데 

2차원 배열로 가능한 이유는 rule의 크기를 32로 제한했기 때문이다.

웬만한 프로그래밍 언어의 문법을 작성할 때 하나의 생성규칙의 최대크기가

32를 넘기기는 매우 힘들것이다.


알고리즘을 실제 코드로 구현하면 다음과 같다. 
 

sub_closure 는 개념적인 알고리즘을 충실히 구현한 것이고

lr_closure 는 인풋이 lr 집합일때 (커널만 있을때) 그 해당 lr 아이템에 대해서

CLOSURE를 계산하게 된다.




GOTO 연산은 어떠한 lr 아이템 (상태) 에서 어떤 심볼값에 대해

핸들이 이동하고 나서 만들어지는 새로운 lr 아이템에 CLOSURE 연산을 수행한 것이다.

이를 실제로 구현하면 어떤 심볼값으로 핸들이 이동될수 있는지 전부 찾아 기록하고

CLOSURE 연산을 수행하면 된다.

코드는 다음과 같다. 


Posted by 멍충한아싸

댓글을 달아 주세요