컴파일러구성 - [제7장] 구문분석 개요
bottom-up 구문분석 shift-reduce 구문분석, FIRST 와 FOLLOW
컴파일러 용어정리
FOLLOW(A) ＝ {a ∈ VT ∪ {$} | S ‗⇒ αAaβ, α, β ∈ V＊}
즉, 어떤 문장형태에 있어서, 논터미널 A 다음에 나타나는 터미널 기호들의 집합이다. 여기에서 $기호는 입력 문자열의 끝을 나타내는 기호
요점정리
- 구문분석 방법은 크게 Top-down 방법과 Bottom-up 방법의 두 종류로 나누어 볼 수 있다. Top-down방법은 시작기호로부터 시작하여 정의된 문법의 규칙(rule)들을 적용하여 유도에 의한 주어진 문자열을 찾아가는 방법이고, 반대로 Bottom-up 방법은 입력된 문자열에서 감축(reduce)에 의해 시작기호를 찾아가는 방법이다.
- Bottom-up 구문분석의 방법으로 스택과 입력 버퍼 등을 사용하는 Shift-reduce 구문분석이 있다. shift와 reduce를 사용하여 진행하는데 시작기호가 나오면 올바른 문장으로 accept 된 것이다.
- Shift-reduce 구문분석에서 shift 는 입력기호를 스택에 넣어주는 것이고 reduce 는 스택에 있는 입력기호를 가져와서 문법에 맞게 reduce 해주는 것을 의미한다.
- Shift-reduce 구문분석에서 문법에 맞게 reduce 해주는 기호가 가장 중요한데 그 것을 e핸들(handle) 이라고 한다.
- FOLLOW(A) 는 어떤 문장형태에 있어서, 논터미널 A 다음에 나타나는 터미널 기호들의 집합이다. FIRST(A)는 A로부터 유도되어 첫 번째로 나타날 수 있는 터미널기호들의 집합이다.
연습문제
다음 설명 중 잘못 설명된 것은?- 정답 :
- ③
- 해설: Shift-reduce 구문분석은 Bottom-up 구문분석 방법이다.
다음은 주어진 문법을 보고 id*id+id를 우단 유도하고 핸들을 표시한 것이다. 다음 중 핸들을 잘못 표시한 단계가 있는가?- 1) E → E * E
2) E → E + E
3) E → id
우단유도 과정 (핸들)
1. E → E * E (E * E)
2. E → E * E + E (E + E)
3. E → E * E + id (id)
4. E → E * id + id (id)
5. E → id * id + id (id)
- 정답 :
- ④
- 모두 올바르다.
- 1) E → E * E
계속해서 shift-reduce 구문분석 하는 과정이다.
빈칸 ‘가’에 알맞은 것은?단 계
스 택
입 력
구문분석 행동
0 $
id*id+id $
shift ( 가 )
1 $id
*id+id $
reduce ( 나 )
2 $E
*id+id $
shift *
3 $E*
id+id $
shift id
4 $E*id
+id $
reduce E → id
5 $E*E
+id $
shift +
6 $E*E+
id $
shift id
7 $E*E+id
$
reduce E → id
8 $E*E+E
$
reduce( 다 )
9 $E*E
$
reduce( 라 )
10 $E
$
accept
- 정답 :
- ①
- 왜냐하면 id가 핸들이므로
계속해서 shift-reduce 구문분석 하는 과정이다.
빈칸 ‘나’에 알맞은 것은?단 계
스 택
입 력
구문분석 행동
0 $
id*id+id $
shift ( 가 )
1 $id
*id+id $
reduce ( 나 )
2 $E
*id+id $
shift *
3 $E*
id+id $
shift id
4 $E*id
+id $
reduce E → id
5 $E*E
+id $
shift +
6 $E*E+
id $
shift id
7 $E*E+id
$
reduce E → id
8 $E*E+E
$
reduce( 다 )
9 $E*E
$
reduce( 라 )
10 $E
$
accept
- 정답 :
- ②
- E → id, 왜냐하면 id가 핸들이므로
계속해서 shift-reduce 구문분석 하는 과정이다.
빈칸 ‘다’에 알맞은 것은?단 계
스 택
입 력
구문분석 행동
0 $
id*id+id $
shift ( 가 )
1 $id
*id+id $
reduce ( 나 )
2 $E
*id+id $
shift *
3 $E*
id+id $
shift id
4 $E*id
+id $
reduce E → id
5 $E*E
+id $
shift +
6 $E*E+
id $
shift id
7 $E*E+id
$
reduce E → id
8 $E*E+E
$
reduce( 다 )
9 $E*E
$
reduce( 라 )
10 $E
$
accept
- 정답 :
- ④
- E → E＋E 왜냐하면 E＋E 가 핸들이므로
계속해서 shift-reduce 구문분석 하는 과정이다.
빈칸 ‘라’에 알맞은 것은?단 계
스 택
입 력
구문분석 행동
0 $
id*id+id $
shift ( 가 )
1 $id
*id+id $
reduce ( 나 )
2 $E
*id+id $
shift *
3 $E*
id+id $
shift id
4 $E*id
+id $
reduce E → id
5 $E*E
+id $
shift +
6 $E*E+
id $
shift id
7 $E*E+id
$
reduce E → id
8 $E*E+E
$
reduce( 다 )
9 $E*E
$
reduce( 라 )
10 $E
$
accept
- 정답 :
- ③
- E → E＊E , 왜냐하면 E*E 가 핸들이므로
다음 문법을 보고 First(E)를 구하면?- 연습문제 설명
- 1) E → E ＋ T
2) E → T
3) T → T ＊ F
4) T → F
5) F → (E)
6) F → id
- 정답 :
- ③
다음 문법을 보고 Follow(E)를 구하면?- 연습문제 설명
- 1) E → E ＋ T
2) E → T
3) T → T ＊ F
4) T → F
5) F → (E)
6) F → id
- 정답 :
- ②
- 출발기호니까 당연히 뒤에 ‘ $ ’ 가 있다.
1) 번 규칙은 E →E ＋ T 이므로 ‘ + ’ 가 있다.
5) 번 규칙 F →(E) 에서는 ‘ ) ’ 가 있다.
따라서 FOLLOW(E) = { $, +, ) }
'컴퓨터과학[3-2] > 컴파일러' 카테고리의 다른 글
| 컴파일러구성 - [제9강] LR 구문분석 (0) | 2016.07.18 |
|---|---|
| 컴파일러구성 - [제8강] 순위관계에 의한 구문분석 (0) | 2016.07.12 |
| 컴파일러구성 - [제6장] Context-free 문법의 효율화 (0) | 2016.07.12 |
| 컴파일러구성 - [제5장] 어휘분석기와 LEX (0) | 2016.07.12 |
| 컴파일러구성 - [제4장]정규문법,정규표현과 결정적 유한오토마타[DFA] 의 동치관계 (0) | 2016.07.10 |
댓글