18 - Top Down Parsing (1)

저번에 알아봤던 탑다운 파싱에 대해 자세히 알아보자

 

탑다운 형식에서 만들어진 파싱 트리는 스타팅 노드에서 밑으로 내려가는데,

어휘가 서술 가능할 경우 그냥 내려가면 끝이지만, 불가능하게 노드가 끝날 경우

되는 경우를 찾기 위하여 다시 윗 노드로 올라가야 하는데 이를 백트래킹이라고 한다.

 

이 백트래킹은 중복되고 시간이 오래걸리기 때문에 최소화 하는 방법을 알아야 한다.

 

 

S -> aAd
S -> aB
A -> b
A -> c
B -> ccd

이와 같은 식이 주어졌다고 했을 때,

input : accd가 올바른 구문인지 검증을 top-down 방식으로 진행해보자

 

1. S -> aAd    pointer : (a)ccd

aAd에서, 포인터인 a가 적절한지 검사한다.

일단 첫 a가 동일하므로 a까지는 적합한 문구라고 판단하고 넘어간다.

 

2. A -> b    pointer : a(c)cd

A 가 b로 결론내려졌으면, abd가 되어 c와 동일하지 않다. 그러므로 다음

 

3. A -> c    pointer : a(c)cd

A 가 c로 결론내려졌다. acd가 되었고 a(c)cd중 c가 같으므로 적합하다.

 

4. A->c    pointer : ac(c)d

적합하다고 생각해서 포인터를 넘겼다. 근데 acd의 d와 accd의 c는 서로 다르다.

이제 다른걸 알아볼 수 있는 논터미널이 존재하지 않는다.

S -> aAd는 애초부터 불가능한 경로였던것이다.

그래서 아예 다른 방법부터 다시 돌아가서 시작한다.(백트래킹)

 

5. S -> aB     pointer : (a)ccd

다시 시작했는데, 아직 a까진 같아서 다시 넘어간다. B가 있으므로 B에 대한 조건으로 넘어간다.

 

6. B -> ccd    pointer : a(c)cd

B가 ccd여서 input인 accd와 완전히 같아졌다.

pointer는 적합하다고 판정하면서 계속 뒤로 갈것이며, 완전히 일치하기 때문에 적합으로 끝이 나게 된다.