Total
0. 구문분석
•
구문분석은 주어진 문장이 문법규칙에 올바른지 아닌지를 검사하는 것.
•
방식
◦
top-down
◦
bottom-up
•
일반적으로는 비교적 문법의 제약이 없는 bottom-up 방식이 주로 사용됨
1. Top-Down 구문분석
•
시작 기호 → 문장
•
2. Bottom-Up 구문분석
•
핸들(handle)
◦
Bottom-up 구문분석에서 reduce 되는 부분
•
reduce
◦
유도과정을 거꾸로 적용한 것
◦
즉, S ⇒ αAw ⇒ αβw의 유도과정이 존재할 때, 문장형태 αβw에서 β를 A로 대체하는 것
•
예시
3. Shift-Reduce 구문분석
•
그림
•
예시
◦
구문분석행동은 파싱표에 의해 결정
4. FIRST
4.1. 정의
•
첫번째 나오는 터미널 기호
•
A ⇒ ε이면 A는 nullable 하다.
•
문자열 α로부터 유도되어, 첫 번째로 나타날 수 있는 터미널기호들의 집합
•
문법 규칙에 따라 유도
4.2. FIRST(X) 계산방법
•
계산방법
4.3. FIRST 예시
•
예시
•
ring sum 예시
5. FOLLOW
5.1.정의
•
A 뒤에 나오는 터미널 기호들
•
즉, 어떤 문장형태에 있어서, 논터미널 A 다음에 나타나는 터미널 기호들의 집합이다. 여기에서 $기호는 입력 문자열의 끝을 나타내는 기호
5.2. FOLLOW(A) 계산방법
•
계산방법
5.3. FOLLOW의 예
•
예시
6. 종합 예제
•
FIRST
•
FOLLOW
