FIRST는 해당 rule 에서 가장 첫번째로 나올 수 있는 터미널 심볼을 말한다.
그래서 해당 rule의 첫번째가 터미널 이면 바로 그놈이 된다.
A -> 'a' B .... ;
위와 같은 경우 A의 FIRST 는 { a } 인 것이다.
해당 rule의 첫번째가 논터미널인 경우는 이렇게 한다.
A -> B C ;
B -> 'a' | 'b' ;
1번 rule 즉 A 의 FIRST는 여기서 'a' , 'b' 가 되는데
첫번째 심볼이 논터미널 B 이므로 B의 생성규칙에 가서 또 FIRST를 구하면 되는 것이다.
이는 딱봐도 재귀적으로 추적하면 알아낼 수 있다
또 B 가 첫번째 rule에 논터미널을 가지면 계속 재귀적으로 추적해 나가면 되는 것이다.
약간 복잡한 경우 해당 논터미널이 epsilon을 포함하고 있는 경우도 있다. 이때는 다음과 같이 한다.
A -> B C ;
B -> 'a'
| ;
C -> 'b' A ;
B는 epsilon을 가지고 있다.
그래서 A의 FIRST를 구하려고 할때 B의 FIRST 뿐만 아니라 C의 FIRST도 구해야 한다.
그러므로 위와 같은 경우 A 의 FIRST는 { a, b} 가 된다.
즉 rule의 첫번째 심볼이 epsilon을 포함하면 그 다음의 FIRST를 구하여 기존것에 epsilon을 제거한 것과 union 하고
그 다음놈도 epsilon을 가지면 또 그 다음놈의 FIRST를 구하고 ... 하면서
rule의 끝까지 진행하면서 FIRST를 계속 구하게 되는 것이다.
개념적이고 직관적으로는 이렇게 하므로
딱 재귀로 구현하면 될 것 같지만.......
실제 구현할 시에는 재귀적으로 추적하면 안된다.
이유는 다음과 같은 경우도 있을 수가 있다.
위 예는 전부 LL을 가정했으나 목표는 LALR 즉 LR 문법이다.
LR의 경우 다음도 허용이 된다.
A -> A B;
즉 첫번째로 나오는 심볼이 자기 자신인 경우이다.
대표적인 예로는 사칙연산같은 것이다.
E -> E '+' T | T ;
...
..
위와 같은 경우 재귀적으로 추적하면 무한호출에 빠지게 된다.
그래서 MAP 같은 것을 두고 첫번째 심볼이 자기자신이면 우선 건너뛰는 방법도 생각해 볼 수 있는데
이 경우는 구하는 순서에 문제가 생겨서 어처구니 없게도
구하는 순서에 따라 FIRST가 바뀌는 경우가 생길 수도 있다.
따라서 이를 해결하기 위해 알고리즘은 재귀적으로 구성하지 않고 다음과 같이 한다.
[정의]. ringsum 연산
A (+) B = A (A 는 epsilon을 가지지 않는다)
A (+) B = (A - {epsilon} ) U B ( A는 epsilon을 가진다)
[알고리즘]
step1.
모든 rule에 대해 첫번째 심볼이 터미널일 경우를 우선 전부 구한다. (epsilon도 포함)
step2
남은 생성규칙들은 전부 논터미널로 시작하므로 ringsum 연산을 사용하여
모든 논터미널의 FIRST가 변하지 않을 때까지 반복한다.
즉 재귀적으로 (하향식) 구하는 것이 아니라
상향식으로 먼저 터미널부터 구한뒤 바뀌지 않을 때까지 계속 반복하는 것이다.
'프로젝트 > 어설픈 야크 ,2010' 카테고리의 다른 글
| 4. 어설픈 야크 만들기 (4) FIRST 구현 (0) | 2011.01.12 |
|---|---|
| 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 |
댓글을 달아 주세요
저여쭤보고싶은게있는데요 컴파일러공부하다가요
2013.12.08 17:58 [ ADDR : EDIT/ DEL : REPLY ]메일주소좀 호기가르켜주실수있으세요???