[컴파일러] Top-down 파싱 | 예측구문분석기 - 파싱테이블 구성하는 방법 | (Predictive, LL parser)
Intro : LL(1) 파서 구현방법
ⓐ Recursive descent parser (재귀적 하강 구문분석기)
- 직관적, 쉽다
- 문법이 바뀔 때마다 parser 전체를 바꿔야 한다.
ⓑ Predictive parser (예측 구문분석기, LL(1) 구문분석)
- 파싱테이블을 이용한다
- 문법이 바뀌어도 parser를 바꾸는게 아니라 파싱테이블만 바꾸면 된다.
- recall) LL : Left to Right 스캐닝 & Left 유도
- recall) LL(1) : lookahead가 1이라는 거다. 2, 3만 되어도 파싱테이블이 엄청 커져서 컴파일러에 부적합하여 대부분 1로 한다. 이 글에서 LL이라고 하면 LL(1)을 칭하겠다.
.
.
Predictive parser에서 구문분석할 때 '파싱 테이블'을 이용한다.
파싱 테이블을 만들어두면 이 테이블을 보고 기계적으로 파싱해나갈 수 있다.
LL(1)이기 때문에 기계적으로 입력문자 하나씩 보면 된다.
이 글은 파싱 테이블은 어떻게 구성되는지, 어떻게 만드는지에 대한 글이다.
파싱 테이블을 구성하는 알고리즘을 먼저 보이자면 이렇다.
for each A →α ∈ 생성규칙
if : α is not nullable & terminal a ∈ FIRST(α)
then : M[A, a] = A→α
if : α is nullable
then : for b ∈ FOLLOW(A), M[A, b] = A→α
아래서 예제와 함께 익숙해져보자.
Predictive parser의 구성
Predictive parser는 크게 3가지로 구성된다.
ㄴ stack
ㄴ input buffer
ㄴ parsing table
파싱 테이블
문법 G에 대한 파싱테이블을 만들어보면, G가 LL문법인지 아닌지를 알 수 있다.
테이블의 모든 칸에 2개이상의 생성규칙이 들어가 있지 않으면 LL문법이다.
▼ predictive 파싱 테이블 구성 방법
for each A →α ∈ 생성규칙
if : α is not nullable & terminal a ∈ FIRST(α)
then : M[A, a] = A→α
if : α is nullable
then : for b ∈ FOLLOW(A), M[A, b] = A→α
(와닿지 않으면 몇번 직접 해보면 된다. 금방 한다.)
● input string이 LL문법일 경우 파싱 테이블 예제
- 다음 문법에 대한 파싱 테이블 구하기
| 1. E -> TE' | 2. E' -> +TE' |
| 3. E' -> ε | 4. T -> FT' |
| 5. T' -> *FT' | 6. T' -> ε |
| 7. F -> (E) | 8. F -> id |
-- FIRST
First(E) = First(T) = First(F) = { id, ( }
First(T') = { *, ε }
First(E') = { +, ε }
-- FOLLOW
Follow(E) = Follow(E') = { ), $ }
Follow(T) = Follow(T') = { +, ), $ }
Follow(F) = { +, *, ), $ }
- 파싱 테이블을 작성한다.
행 : Non-terminal
열 : terminal
파싱 테이블 : non-terminal x terminal = 적용될 생성규칙 번호
| id | + | * | ( | ) | $ | |
| E | 1 | 1 | ||||
| E' | 2 | 3 | 3 | |||
| T | 4 | 4 | ||||
| T' | 6 | 5 | 6 | 6 | ||
| F | 8 | 7 |
아래 생성규칙 넘버를 잘 채워넣는다.
| 1. E -> TE' | 2. E' -> +TE' |
| 3. E' -> ε | 4. T -> FT' |
| 5. T' -> *FT' | 6. T' -> ε |
| 7. F -> (E) | 8. F -> id |
<풀이과정>
* FIRST를 먼저 보자.
lhs가 E인 규칙1을 보면 FIRST(E)에 id, ( 가 포함된다. 따라서 M[E, id] = M[E, ( ] = 규칙1
lhs가 E'인 규칙2, 3을 보면 FIRST(E')에 +, ε이 포함된다.
따라서 M[E', +]=규칙2 다.
그런데 규칙3을 보면 E'가 nullable이므로, 규칙3은 FOLLOW(E')를 보고 넣어야 한다.
lhs가 T인 규칙4를 보면 FIRST(T)에 id, ( 가 포함된다. 따라서 M[T, id] = M[T, ( ] = 규칙4
lhs가 T'인 규칙5, 6을 보면 FIRST(T')에 *, ε가 포함된다.
따라서 M[T', *]=규칙5 다.
그런데 규칙6을 보면 T'가 nullable이므로, 규칙6은 FOLLOW(T')를 보고 넣어야 한다.
lhs가 F인 규칙 8을 보면 FIRST(F)에 ( 와 id가 포함된다. 따라서 M[F, ( ]=규칙7 그리고 M[F, id]=규칙8이다.
* null이었던 것에 대해 FOLLOW를 보자.
규칙3에서 E'가 nullable이었다. FOLLOW(E')={ ), $}다.
따라서 M[E', ) ] = M[E', $] = 규칙3
규칙6에서 T'가 nullable이었다. FOLLOW(T')={ +, ), $ }다.
따라서 M[T', +] = M[T', ) ] = M[T', $] = 규칙6
끝나따!
ㅡㅡㅡㅡㅡㅡㅡㅡㅡ
▼ 같은 내용
∨ FIRST
First(E) = First(T) = First(F) = { id, ( }
- Non-terminal E에서 terminal {id}, { ( }가 유도되려면 생성규칙 1번 적용
- Non-terminal T에서 terminal {id}, { ( }가 유도되려면 생성규칙 6번 적용
- Non-terminal F에서 terminal {id}가 유도되려면 8번이, { ( }가 유도되려면 7번 적용
First(T') = { *, ε }
- Non-terminal T'에서 terminal { * }가 유도되려면 생성규칙 5번 적용
First(E') = { +, ε }
- Non-terminal E'에서 terminal { + }가 유도되려면 생성규칙 2번 적용
∨ FOLLOW를 보고 마저 채워보자. FOLLOW는 nullable일때 본다는 것을 주의하자.
Follow(E) = Follow(E') = { ), $ }
- Non-terminal E'에서 terminal { ) }, { $ }가 유도되려면 생성규칙 3번 적용
- E에서 ), $ 유도하는 건 왜 안따지지? 앗 E -> TE'에서 TE'가 not nullable이라서!
Follow(T) = Follow(T') = { +, ), $ }
- Non-terminal T'에서 terminal { + }, { ) }, { $ }가 유도되려면 생성규칙 6번 적용
- T에서 +, ), $ 유도하는 건 왜 안따지지? 아아 얘도 T -> FT'에서 FT'가 not nullable이라서!!
Follow(F) = { +, *, ), $ }
- Non-terminal F도 볼 필요 없다. not nullable이라서!!!
가만보면 파싱테이블의 모든 Non-terminal X terminal 한 칸에 두개 이상의 생성규칙은 들어가지 않는다.
=> 그러면 LL문법이다!
● input string이 LL문법이 아닐 경우 파싱 테이블 예제
- 다음 문법에 대한 파싱 테이블 구하기
1. S -> iCtSS'
2. S -> a
3. S' -> eS
4. S' -> ε
5. C -> b
-- FIRST
First(S) = {i, a}
First(S') = {e, ε}
First(C) = {b}
-- FOLLOW
참고) 1, 3번 규칙을 보니까 Follow(S) == Follow(S')다.
Follow(S) = (First(S') - {ε}) ∪ Follow(S) = { e, $ }
Follow(S') = { e, $ }
Follow(C) = { t }
- 파싱 테이블을 작성한다.
만들어진 파싱 테이블을 보면, 규칙 2개 이상이 들어간 칸이 존재한다.
그러므로 input string은 LL문법이 아니다.
즉, 결정적인 선택이 불가하다
| a | b | e | i | t | $ | |
| S | 2 | 1 | ||||
| S' | 3, 4 | 4 | ||||
| C | 5 |
1. S -> iCtSS'
2. S -> a
3. S' -> eS
4. S' -> ε
5. C -> b
<풀이과정>
* 일단 FIRST 먼저 보기
lhs가 S인 규칙 1,2를 보면 FIRST(S)에 i와 a가 포함된다. 그럼 M[S, i]=규칙1, M[S, a]=규칙2 넣으면 되겠다
lhs가 S'인 규칙 3,4를 보면 FIRST(S')에 e와 ε가 있다. nullable이 아닌 경우인 M[S', e]=규칙3 넣자.
반면 규칙 4를 보면 S'가 nullable하다는 것을 알 수 있다.
그럼 FOLLOW(S')를 봐주면 되겠다.
lhs가 C인 규칙 5를 보면 FIRST(C)에 b가 포함된다. M[C, b]=규칙5 넣자.
* FIRST에서 nullable인 경우에 대해 FOLLOW를 보기
"규칙 4"에서 S'가 nullable임을 봤다. 그럼 FOLLOW(S')를 봐야 한다.
FOLLOW(S')={ e, $ }다.
그럼 M[S', e]와 M[S', $]에다가 "규칙 4를" 넣어주면 된다. 규칙4를!!
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
-- FIRST
First(S) = {i, a}
First(S') = {e, ε}
First(C) = {b}
-- FOLLOW
Follow(S) = (First(S') - {ε}) ∪ Follow(S) = { e, $ }
Follow(S') = { e, $ }
Follow(C) = { t }
오 근데 이런 파싱테이블을 파서가 어떻게 사용해서 구문분석한다는 건지
한번 쓱 보면 더 좋겠다 >.<
- 파서는 다음 액션을 반복하며 구문분석한다.
recall. 아까 perspective parser는 스택과 입력버퍼를 둔다고 했다.
- pop : 스택에서 pop 또는 입력버퍼에서 pop
- expand : 스택 탑이 Non-terminal이면 알맞은 생성규칙을 적용하여 pop & expand해간다.
스택에 있는 Non-terminal을 생성규칙이 유도하는 걸로 바꿔치기하는 것이다.
그리고 구문분석이 끝나는 경우는 이러하다.
- accept : 입력 스트링이 올바름을 인식하여 구문분석 성공하거나
- error : 구문분석에 실패하거나 : 스택탑이 Non-terminal인데 유도불가한경우 (즉 적용할 규칙 존재 X)
- 예제
입력 스트링 : aabccd
생성규칙
1. S -> aS
2. S -> bA
3. A -> d
4. A -> ccA
| stack | input string | parsing action | parse | |
| 1 | $S | aabccd$ | expand 1 | 1 |
| 2 | $S |
pop & advance | 1 | |
| 3 | $S | abccd$ | expand 1 | 11 |
| 4 | $S |
pop & advance | 11 | |
| 5 | $S | bccd$ | expand 2 | 112 |
| 6 | $A |
pop & advance | 112 | |
| 7 | $A | ccd$ | expand 4 | 1124 |
| 8 | $Ac |
pop & advance | 1124 | |
| 9 | $A |
pop & advance | 1124 | |
| 10 | $A | d$ | expand 3 | 11243 |
| 11 | $ |
pop & advance | 11243 | |
| 12 | $ | $ | accept | 11243 |
Let ) 파싱 테이블 M이 다 마련되어 있다!
주의 ) 스택에 넣을 때 순서 유의! 먼저 봐야 할 문자를 당연히 위로 가게끔
맨 처음 스택에는 시작심볼 넣고 시작!
과정1: 파싱 테이블에서 M[S, a]를 찾아 규칙1을 적용 : expand 1
과정2: expand되었다! 엇 문자 a가 일치한다. 일치하는 문자열 a를 pop한다. 그리고 포인터를 다음 문자열로 옮긴다.
즉 pop & advance
과정3: 파싱 테이블에서 M[S, a]를 찾아 규칙 1을 적용 : expand 1
과정4: pop & advance
과정5: 파싱 테이블에서 M[S, b]를 찾아 규칙 2를 적용 : expand 2
과정6: pop & advance
과정7: 파싱 테이블에서 M[A, c]를 찾아 규칙 4를 적용 : expand 4
과정8: pop & advance
과정9: pop & advance
과정10: 파싱 테이블에서 M[A, d]를 찾아 규칙 3을 적용 : expand 3
과정11: pop & advance
과정12: accept : 스택도 입력도 다 제거하고 $만 남았다. 구문분석 성공!
- 또다른 예제
문자열 (a,a)에 대해 파싱해보기!!
| stack | input string | parsing action | parse | |
| 1 | $S | (a,a)$ | ||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | ||||
| 7 | ||||
| 8 | ||||
| 9 | ||||
| 10 | ||||
| 11 | ||||
| 12 |
이렇게..
Predictive Parser를 공부하면서
FIRST와 FOLLOW를 사용하여
파싱테이블을 직접 만들어보고
input string이 LL문법인지 아닌지까지 확인해보았다.