수업시간에 FIRST와 FOLLOW를 구하는 법을 분명 열심히 들었는데 집에 와서 하려고 해보니 이해가 안되서 삽질하다가 정리해 보았다. FOLLOW의 경우에는 계속 헷갈렸는데 이제 제대로 이해한 듯 하다!! 미래의 내가 이해할 수 있게 최대한 쉽게 정리해보았다.
FIRST(A)란 nonterminal symbol A로부터 유도되어 첫 번째로 나타날 수 있는 terminal의 집합을 나타낸다. 말은 어렵지만 그냥 첫번째로 나올 수 있는 terminal symbol이라고 생각하면 될 것 같다.
nullable하다는 것은 nonterminal symbol이 ε를 유도할 수 있다는 것이다.
ringsum 연산이란 첫 번째 피연산자의 집합이 ε를 갖지 않으면 그 자신이 되며, ε를 포함하고 있으면 ε를 제외한 첫 번째 피연산자와 두 번째 피연산자를 합집합한 것이다.
쉽게 말하자면
A ringsum B를 했는데 A에 ε이 존재하지 않으면 값은 A가 되고, A에 ε이 존재하면 값은 A와 B를 합집합 한 것에서 ε를 뺀 것이다.
결과적으로 nullable이 아닌 심벌까지의 FIRST를 합집합 한 것이 스트링의 FIRST이다.
FOLLOW(A)란 ε-생성규칙을 갖는 문법에서 (시작 심벌로부터 유도될 수 있는 모든 문장 형태에서) A 다음에 나오는 terminal 심볼의 집합을 나타낸다.
FIRST만으로는 생성 규칙을 결정적으로 선택할 수 없다. FIRST가 여러 개라면 여러 방향으로의 확장이 가능하기 때문이다. 따라서 nonterminal A 다음에 나오는 심벌이 어느 생성 규칙으로 유도할 것인지를 결정하게된다.
$ : 입력 스트링의 끝을 표기하는 marker symbol
시작 심벌은 $를 초기값으로 갖는다.
A → αBβ 라고 할 때
β가 terminal일 경우 FOLLOW(B)에 β를 추가한다.
β가 nonterminal 일 경우 FIRST(β)에서 ε를 제외한 terminal 심벌을 FOLLOW(B)에 추가한다.
FIRST(β)에 ε이 속하는 경우 혹은 A → αB의 경우에는 FOLLOW(A) 전체를 FOLLOW(B)에 추가한다.
일련의 유도 과정을 통해 문장 형태가 나타나게 되는데, 이 문장 형태에서 nonterminal을 어떤 생성규칙을 통해 대치할 것인지를 결정적으로 선택하는 것이 LL조건이다.
임의의 생성규칙 A → α | β 에 대하여