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가 변하지 않을 때까지 반복한다.


즉 재귀적으로 (하향식) 구하는 것이 아니라

상향식으로 먼저 터미널부터 구한뒤 바뀌지 않을 때까지 계속 반복하는 것이다.
Posted by 멍충한아싸

댓글을 달아 주세요

  1. 김다솔

    저여쭤보고싶은게있는데요 컴파일러공부하다가요
    메일주소좀 호기가르켜주실수있으세요???

    2013.12.08 17:58 [ ADDR : EDIT/ DEL : REPLY ]