FIRST·FOLLOW 집합 계산기
문맥자유문법의 생성규칙을 넣으면 각 비단말의 FIRST·FOLLOW 집합을 정의대로 구하고 LL(1) 파싱 테이블까지 만들어 충돌 여부를 판정합니다.
「A -> X Y | eps」 꼴로 한 줄에 하나씩. start: 로 시작 기호를 지정합니다(생략 시 첫 줄 좌변). 비단말 12개까지.
LL(1) 여부
LL(1) 문법입니다
파싱 테이블의 모든 칸에 생성규칙이 하나씩만 들어가, 다음 글자 하나만 보고도 어떤 생성규칙을 쓸지 정할 수 있습니다.
생성규칙
FIRST · FOLLOW
| 비단말 | FIRST | FOLLOW |
|---|---|---|
| E | { (, id } | { $, ) } |
| Ep | { +, ε } | { $, ) } |
| T | { (, id } | { +, $, ) } |
| Tp | { *, ε } | { +, $, ) } |
| F | { (, id } | { *, +, $, ) } |
LL(1) 파싱 테이블
| 비단말 | + | * | ( | ) | id | $ |
|---|---|---|---|---|---|---|
| E | 1 | 1 | ||||
| Ep | 2 | 3 | 3 | |||
| T | 4 | 4 | ||||
| Tp | 6 | 5 | 6 | 6 | ||
| F | 7 | 8 |
칸의 숫자는 적용할 생성규칙 번호입니다. 번호가 두 개 이상 겹치면 그 칸에서 다음 글자 하나만 보고는 어떤 규칙을 쓸지 정할 수 없다는 뜻입니다.
사용 방법
- 1생성규칙을 「A -> X Y | eps」 꼴로 한 줄에 하나씩 적습니다. 여러 대안은 |로 구분합니다.
- 2「start: A」로 시작 기호를 지정합니다. 생략하면 첫 생성규칙의 좌변이 시작 기호가 됩니다.
- 3ε 생성규칙은 eps·ε·epsilon 중 아무거나 쓰거나 화살표 뒤를 비워 둡니다.
- 4FIRST·FOLLOW 표와 LL(1) 파싱 테이블을 확인하고, 칸에 규칙이 둘 이상이면 충돌 표시를 봅니다.
자주 묻는 질문
어떤 기호에서 유도를 시작했을 때 맨 앞에 나올 수 있는 단말 기호들의 모음입니다. 비단말 A → X₁X₂…Xₖ 라면 X₁의 FIRST를 먼저 넣고, X₁이 빈 문자열(ε)도 유도할 수 있으면 X₂의 FIRST까지 넘어가 살펴봅니다. 하향식 파서가 「지금 어떤 생성규칙을 적용해야 할지」를 다음 글자 하나만 보고 정할 때 이 집합을 씁니다.
어떤 비단말이 ε를 유도할 수 있을 때, 그 비단말이 사라진 자리 바로 다음에 무엇이 올 수 있는지를 알아야 하기 때문입니다. A가 ε로 사라지면 파서는 「다음 글자가 FOLLOW(A)에 있으면 A → ε를 쓴다」고 판단합니다. 시작 기호의 FOLLOW에는 입력이 끝났다는 표시 $가 항상 포함됩니다.
테이블의 한 칸(비단말, 다음 글자)에 생성규칙이 둘 이상 들어간다는 뜻입니다. 다음 글자 하나만 보고는 어느 생성규칙을 써야 할지 정할 수 없어, 이 문법은 하향식 예측 파서(LL(1) 파서)로 그대로 처리할 수 없습니다. 흔한 원인은 같은 글자로 시작하는 대안이 여럿 있는 경우(좌인수분해로 해결)와 좌재귀(우재귀로 바꿔 해결)입니다.
FIRST·FOLLOW 자체는 계산되지만 대개 충돌이 나타납니다. 예를 들어 S → S a | b는 M[S, b] 칸에 두 생성규칙이 겹쳐 LL(1)이 아니라고 나옵니다. 직접 좌재귀는 항상 하향식 예측 파서와 상성이 나쁘므로, 오른쪽으로 재귀하도록(S → b S′, S′ → a S′ | ε) 고쳐 써야 합니다.
이 계산기가 보여주는 것은 어떤 생성규칙을 적용해야 하는지에 대한 규칙표일 뿐, 실제 문자열을 파싱해 보여주지는 않습니다. 문법이 LL(1)이면 이 표만으로 예측 파서를 그대로 만들 수 있고, 어떤 입력에도 항상 유일한 생성규칙이 선택됩니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 알고리즘은 Aho·Sethi·Ullman·Lam 「컴파일러: 원리·기법·도구」(용의 책) 4판 4.4절의 정의를 그대로 구현했습니다.
- 교재 4.4.1절의 대표 예제(E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → (E) | id)로 FIRST·FOLLOW 값이 교재와 정확히 일치하는지 테스트로 대조했습니다.
- 비단말은 좌변에 한 번이라도 등장한 기호로 정하고, 그 외 기호는 모두 단말로 취급합니다. 시작 기호에 생성규칙이 없거나 화살표가 없는 줄은 에러로 표시합니다.
- 비단말 12개·단말 20개까지 다룹니다. FIRST·FOLLOW 계산은 값이 늘어나기만 하는 고정점 반복이라 좌재귀·상호재귀가 있어도 유한 횟수 안에 멈춥니다.
- 충돌 판정은 이 계산기의 파싱 테이블에 국한됩니다. 실제 파서 생성기(예: yacc·ANTLR)는 더 넓은 전망(LALR 등)을 쓰므로 여기서 충돌이 나도 다른 파싱 방식으로는 처리될 수 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.