컴파일러 관련 책을 보면

FIRST는 LL 파트 부분에 나온다.

하지만 LR 계열에서도  FIRST는 반드시 구해야 하는데

이는 가장 심플한 SLR 조차 

reduce 를 적용하기 위해서 

각 논터미널에 대한 FOLLOW 를 구해야 된다.

이때 필요한 것이 FIRST 이기 때문이다. 


LR(1) 과 LALR 같은 경우와 SLR 의 차이점은

SLR의 경우 reduce 가 필요한 경우 해당 논터미널에 모든 FOLLOW에 대해(grammar 전체에 대한) 

reduce rule 을 적용시킨다.

LR(1) 의 경우는 이와는 다르게 LookAhead 심볼들의 집합을 구하는데

LR set 을 구할때 일종의 DFA 집합을 형성한다. 이때 각 원소(상태) 에 따라서 

핸들이 성공적으로 파싱되었을 때 그 이후에 나올 놈들까지 계산하는 것이다.


말이 어려운데 쉽게 말하면

SLR은 그냥 단순무식하게 뒤에 나올 모든 심볼에 대해 reduce rule 을 적용시키고

LR(1)의 경우 각 상태에 따라 뒤에 나올 수 있는 심볼들에 대해서만 reduce rule 을 적용시키는 것이다.

LALR은 이 LR(1)에서 거의 공통적인 상태들을 한데 묶는 것이다.


여기서 가장 강력한 놈은 역시나 LR(1)이란 것을 알 수 있으나 

강력하다 해서 좋은건 아니고 이것은 테이블이 너무 커진다.


어쩃건 목표는 LALR인데 이는 테이블의 크기는 SLR과 똑같으나 파워는 더 강력하기 때문이다.

LA (LookAhead) 를 구하기 위해서는 FOLLOW 가 필요하며

이 FOLLOW를 구하기 위해서는 FIRST가 필요하므로 

반드시 각 논 터미널에 대한 FIRST를 구하는 작업은 선행되어야 한다.


Posted by 멍충한아싸

댓글을 달아 주세요