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까지는 적합한 문구라고 ..

2021.08.05