컴파일러 교재에서 살펴보면

여러가지 LR 파서를 구현하기 위해서는 꼭 필요한 것들이 있는데

여기서 LR(0) 개념이 가장 중요하다.


실질적으로 여기서 설명하는 개념을 통해

여러가지 LR 파서의 기반을 만든다.


LR 파서는 기본적으로 핸들 이라는 개념을 사용한다.


교재를 보면 해당 rule 사이에 점을 찍는 것으로 표현한다.




핸들 의 의미는 다음과 같다.

" 현재 읽고 있는 시점(부분) "

즉 바로 다음에 나올 심볼을 읽기 바로 직전의 상태를 의미한다.


이 핸들의 개념은 매우 중요한데

LR 파서는 기본적으로 상향식 파싱을 한다.

이때 계속 어떠한 토큰을 읽어들였을 때

그 시점에서 어떤 위치 (어떤 파싱 과정을 거쳐 그 상태에 도달)

을 나타내기 때문이다.


따라서 그 상태에서 또 어떠한 심볼을 읽어 다른 상태로 가고 이때 핸들은 이동한다.

이렇게 계속 핸들이 이동하다가 결국에는 파스트리의 꼭대기의 바로 뒤를 읽게 되고

이때 성공적으로 인식되었음을 확인하며 accept 하게 된다.



여기서 DFA 개념을 또 사용하게 되는데

가능한 모든 경로에 대해서 이미 전부 결정되어 있다 (하나의 길만 존재한다)

는 것이다.

이것이 구성되는 과정은 


1. 최초 상태의 핸들은 맨앞에 존재하고 읽기 직전이다.

이때 가능한 핸들의 위치를 전부 찾아낸다 (CLOSURE 연산)


2. 그뒤 가능한 핸들의 위치에 따라 바로 다음에 갈 수 있는 모든 심볼들에 대하여

중복되지 않게 새로운 상태를 만들고 핸들을 이동한다 (GOTO 연산)


이 과정을 계속 반복하면 모든 결정가능한 경로를 다 찾아내고 

결국에는 더이상 상태가 늘어나지 않을 것이다.



쉽게 말해 무식하게 모든 경우의 수를 다 찾아내는 것이다.

다만 똑똑하게 중간에 중복되는 경우를 하나의 상태로 만들어서

상태를 이동하는 것으로 처리하는 것이다.



위 개념을 실제로 구현하기 위해서 필요한 것들은 다음과 같다.

1. 각 상태에서 존재하는 핸들들의 위치

2. CLOSURE , GOTO 연산

3. 그래프가 만들어질 때 그 사이의 간선 (어떤 심볼을 읽고 다른 상태로 이동했는가)

4. DFA를 구성하는 알고리즘



Posted by 멍충한아싸

댓글을 달아 주세요