LR 관련 파서는 개념적으로 집합을 많이 사용한다.

터미널 집합, 논터미널 집합, DFA 상태 집합 등등등...

실제로 구현하기 위해서는

집합 관련  연산들이 정의 되어 있어야 한다.


집합의 특징을 구현하려면 문제가 많다.

1. 순서에 상관 없다.
2. 중복되지 않는다.
3. 무한개의 아이템을 지닐수 있는 집합?


솔직히 컴퓨터에서 무한개의 아이템을 지닌다는 것은 거의 불가능 하고

제약을 두어야 한다.



이를 쉽게 구현하기 위해서는 배열을 생각해 볼 수 있다.

 a  b  c  d  e  f  ...
 1  0  0  1  1  0  ...

그냥 쉽게 생각해 해당 아이템이 있으면 1, 없으면 0 인 것이다.

기존에 심볼테이블을 둘 때 스트링을 중복되지 않게 검사하면서 

유일한 값으로 인덱스를 사용하므로

이 인덱스를 바탕으로 배열을 사용하여 집합을 구현하면 되겠다.



하지만 int 형 배열로 구현하면 단지 0, 1만 나타낼 뿐인데  공간 낭비가 심하므로

비트열의 값에 따라 집합을 표현하는 방식을 선택했다.

그러면 기존 집합 크기보다 1/32  의 크기로 줄어들 것이다.

밑은 비트열을 이용해 집합을 생각하고

LR 파서에 필요한 연산들을 정의한 것이다.



ringsum 연산은

앞서 설명한 정의인


[정의]. ringsum 연산

A (+) B  = A                                (A 는 epsilon을 가지지 않는다)
A (+) B  = (A - {epsilon} ) U B      ( A는 epsilon을 가진다)

을 표현한 것이다.
Posted by 멍충한아싸

댓글을 달아 주세요