FIRST·FOLLOW 계산기 (LL(1) 파싱 테이블)
문법의 nullable, FIRST, FOLLOW 집합과 LL(1) 파싱 테이블을 계산하고, 충돌과 좌재귀를 찾아 알려 주며 예측 파싱 과정을 단계별로 보여 줍니다.
시작 기호: E (첫 번째 규칙의 왼쪽). $는 입력의 끝을 나타냅니다.
| 비단말 기호 | 공집합 유도 가능 | FIRST | FOLLOW |
|---|---|---|---|
| E | 아니요 | { (, id } | { ), $ } |
| E' | 예 | { +, ε } | { ), $ } |
| T | 아니요 | { (, id } | { +, ), $ } |
| T' | 예 | { *, ε } | { +, ), $ } |
| F | 아니요 | { (, id } | { +, *, ), $ } |
| + | * | ( | ) | id | $ | |
|---|---|---|---|---|---|---|
| E | E → T E' | E → T E' | ||||
| E' | E' → + T E' | E' → ε | E' → ε | |||
| T | T → F T' | T → F T' | ||||
| T' | T' → ε | T' → * F T' | T' → ε | T' → ε | ||
| F | F → ( E ) | F → id |
| 스택 | 입력 | 동작 |
|---|---|---|
| E $ | id + id * id $ | E → T E' |
| T E' $ | id + id * id $ | T → F T' |
| F T' E' $ | id + id * id $ | F → id |
| id T' E' $ | id + id * id $ | 일치: id |
| T' E' $ | + id * id $ | T' → ε |
| E' $ | + id * id $ | E' → + T E' |
| + T E' $ | + id * id $ | 일치: + |
| T E' $ | id * id $ | T → F T' |
| F T' E' $ | id * id $ | F → id |
| id T' E' $ | id * id $ | 일치: id |
| T' E' $ | * id $ | T' → * F T' |
| * F T' E' $ | * id $ | 일치: * |
| F T' E' $ | id $ | F → id |
| id T' E' $ | id $ | 일치: id |
| T' E' $ | $ | T' → ε |
| E' $ | $ | E' → ε |
| $ | $ | 수락 |
하향식(LL(1)) 파서를 만들 때는 먼저 모든 비단말 기호에 대해 공문자열을 유도할 수 있는지, FIRST 집합, FOLLOW 집합 세 가지를 구해야 합니다. 여기서 예측 파싱 테이블이 나오고, 한 칸에 규칙이 둘 이상 들어가면 충돌이라 LL(1)에 맞지 않는 문법입니다. 이 계산기는 이 모두를 구하고, 충돌을 나열하고, 좌재귀를 제거하며, 입력에 대한 예측 파싱 과정을 추적해 줍니다.
사용 방법
- 문법을 E -> T E'처럼 한 줄에 규칙 하나씩 입력하고, 대안은 |로 구분합니다.
- 공문자열은 ε(또는 eps)로 쓰며, 첫 번째 규칙의 왼쪽이 시작 기호입니다.
- 원하면 파싱할 입력 문자열을 입력합니다.
- 집합, LL(1) 테이블, 충돌, 파싱 과정을 확인합니다.
계산식
FIRST(αβ) = FIRST(α) ∪ (α ⇒* ε이면 FIRST(β)) · A → αBβ: FIRST(β) − {ε} ⊆ FOLLOW(B), β ⇒* ε이면 FOLLOW(A) ⊆ FOLLOW(B)
집합은 더 이상 변하지 않을 때까지 이 규칙을 반복해서 구하며, 시작 기호의 FOLLOW에는 $를 넣습니다. 규칙 A → α는 FIRST(α)의 모든 단말 기호 a에 대해 테이블 칸 M[A, a]에 들어가고, α가 공문자열이 될 수 있으면 FOLLOW(A)의 모든 기호에 대해서도 들어갑니다. 좌재귀는 공문자열을 유도할 수 있는 접두 부분을 거치는 경우(간접 좌재귀)까지 찾으며, Aho, Lam, Sethi, Ullman의 표준 알고리즘에 따라 프라임 기호를 추가해 제거합니다.
예시
입력란의 수식 문법에서 FIRST(E) = FIRST(T) = FIRST(F) = { (, id }, FIRST(E') = { +, ε }, FIRST(T') = { *, ε }이고, FOLLOW(E) = FOLLOW(E') = { ), $ }, FOLLOW(T) = FOLLOW(T') = { +, ), $ }, FOLLOW(F) = { +, *, ), $ }입니다. 어느 칸에도 규칙이 둘 들어가지 않으므로 이 문법은 LL(1)이고 "id + id * id"는 수락됩니다. 좌재귀 버전인 E -> E + T | T는 바로 이 문법으로 고쳐 쓰입니다.
자주 묻는 질문
ε는 FIRST에는 있는데 FOLLOW에는 왜 없나요?
A가 공문자열을 유도할 수 있으면 FIRST(A)에 ε가 들어갑니다. FOLLOW(A)는 A 바로 뒤에 올 수 있는 단말 기호와 입력 끝을 나타내는 $를 모은 것이며, ε는 무엇의 뒤에도 올 수 있는 기호가 아닙니다.
한 글자보다 긴 기호는 어떻게 쓰나요?
모든 기호를 공백으로 구분하세요. 예: E -> E + T | id. 한 글자 모드에서는 대문자('나 숫자를 붙일 수 있음)가 비단말 기호이고 나머지 문자는 모두 단말 기호입니다.
충돌은 무슨 뜻인가요?
같은 비단말 기호의 두 규칙이 같은 선행 토큰으로 시작해서 예측 파서가 고를 수 없다는 뜻입니다. 좌인수분해, 좌재귀 제거, 언어 자체의 수정으로 보통 해결되지만, 댕글링 else처럼 LL(1)이 아닌 언어도 있습니다.
출처
최종 업데이트:
이 입력값이 담긴 페이지 주소: https://kakao.mobile/ko/tools/context-free-grammar-tool/
인용·퍼가기
kakaoCalc. (2026, November 8). FIRST·FOLLOW 계산기 (LL(1) 파싱 테이블). https://kakao.mobile/ko/tools/context-free-grammar-tool/
“FIRST·FOLLOW 계산기 (LL(1) 파싱 테이블).” kakaoCalc, 8 Nov. 2026, kakao.mobile/ko/tools/context-free-grammar-tool/.