컴파일러 관련 책을 보면
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를 구하는 작업은 선행되어야 한다.
'프로젝트 > 어설픈 야크 ,2010' 카테고리의 다른 글
| 4. 어설픈 야크 만들기 (3) 집합 관련 표현 (0) | 2011.01.12 |
|---|---|
| 4. 어설픈 야크 만들기 (2) FIRST 구하기 개념 (1) | 2011.01.12 |
| 4. 어설픈 야크 만들기 (1) FIRST 구하기 필요성 (0) | 2011.01.12 |
| 3. 어설픈 야크 만들기 (파싱) (2) | 2011.01.06 |
| 2. 어설픈 야크 만들기 (스캐너 작성) (0) | 2011.01.06 |
| 1. 어설픈 야크 만들기 (2) | 2011.01.06 |
댓글을 달아 주세요