Top-down and bottom-up parsing

parsing을 하기 위해서는, 주어진 문장이 어떻게 출발 심볼로부터 생성되었나를 알아야 한다. 이를 위한 방법은 두 가지가 있다.

하강(top-down) : 출발 심볼로부터 시작하여 트리 구조의 종단에서의 심볼들이 parsing되는 문장의 요소들과 같게 될 때까지 순방향(forward)으로 문법에서 주어진 생성 규칙들을 적용하는 방법.

상승(bottom-up) : parsing되고자 하는 문장으로부터 시작하여, 문법에서 주어진 생성 규칙들을 역방향(backward)으로 계속 적용시켜 종단 노드가 주어진 문장의 단어로 구성되고 루트 노드(root node)가 출발 심볼인 트리를 얻게하는 방법.

이 두가지 방식 중 어느 것을 선택할 것인가는, 주어진 업무에 비추어 선택하여야 한다. 때로는 이 두 가지 방식을 결합한 하강 여과를 지닌 상승 parsing(bottom-up parsing with top-down filtering)을 사용하는 수도 있는데, 이 경우에는 parsing은 상승으로 하나(즉, 생성규칙을 역방향으로 적용시킴), 미리 준비된 표를 이용하여 가능성이 없는 것은(즉, S로 갈 수 없는 것) 중도에 제거된다. 앞서 주어진 몇 개의 예에서 알 수 있듯이, 문장을 이해하는 과정은 여러 가능한 해석이 놓여진 공간에서 특별히 문장에서 주어진 여러 제한을 만족하는 한 가지 해석을 찾는, 일종의 탐색에 해당하는 것이다. 다른 탐색과 마찬가지로, 이 경우에도 모든 가능한 경로를 검토할 것인지, 아니면 가장 가능성있는 경로를 검토하여 이의 결과를 답으로 할 것인지를 결정하여야 한다.
  예로써, 문장을 이해하는 프로그램이 입력문장의 단어를 한 번에 한 개씩, 왼쪽부터 오른쪽으로 처리한다고 가정하자. 입력 중 다음의 문장까지를 처리하였다고 하자.

Have the students who missed the exam

이때에 이 프로그램이 따를 수 있는 다음의 두 가지 경로가 가능하다.

• Have가 다음과 같이 명령문의 본동사로 해석되는 경우
  Have the students who missed the exam take it today.
• Have가 다음과 같이 의문문의 조동사로 사용되는 경우
  Have the students who missed the exam taken it today?

이와 같은 문장을 처리하는데는 다음의 네 가지 방법이 있다.

(1) 모든 경로 추적 - 가능한 모든 경로를 고려하여 각각의 경로에 대항 잠정적인 결과를 내었다가 이를 요구할 것으로 기대되는 입력이 나타나지 않으면 이를 제외시킨다. 위의 예에서 have를 조동사로 설정했다가 taken같은 과거분사가 나오지 않으면 조동사로 설정한 것을 제외시킨다. 이 방식은 모든 경로를 고려하므로 비효율적이다.
(2) 백트래킹(backtracking)을 사용하는 최적경로 추적 - 한번에 한 경로만 선택하되, 어떤 경로를 따랐을 때 해석이 실패할 경우 다른 선택을 하기 위한 필요 정보를 매 선택점마다 기억해 놓고, 선택한 경로가 문장을 완전히 해석하지 못하였을 경우에는 저장한 정보를 사용한다. 이 예에서는 만일 have를 조동사로 해석할 것을 우선 선택하였으나, 문장이 끝날 때까지 본동사가 나타나지 않으면, 프로그램은 이러한 선택이 실패임을 깨달아 먼저으 선택점으로 백트랙(backtrack)하여 다른 경로를 선택한다. 이 방법의 단점은 각 선택점에서 상태 정보를 저장하는데 많은 시간고 공간이 소요되고, 같은 문장 요소들이 여러번 분석될 수도 있는 것이다. 우리의 예에서 만일 have에 대한 선택이 잘못되었다면 이의 잘못은 'the student who missed the exam'의 부분이 읽힐 때까지 인식되지 못할 것이다. 일단 잘못되었다는 것을 알게되면, 간단한 백트래킹을 사용하는 경우에는 have 이후의 모든 해석을 취소하고, have에 대한 두 번째 선택을 한뒤, have 뒤의 모든 해석을 다시하게 될 것이다.
(3) 패치 업(path-up)을 이용한 최적경로 추적 - 이 방법에서는 한 번에 한 경로만을 추적하여 해석을 시도하지만, 일단 이 경로의 선택이 잘못되었음이 밝혀지면, 이미 해석된 문장요소들을 다시 배열시킨다. 예로써 앞에서 주어진 보기를 살펴 보자. 만일 have를 조동사로 선택하여 해석을 시도하였다면 다음에 뒤따르는 명사구 'the student who missed the exam'을 해석하고, 이를 문장의 주어로써 기록하여 놓을 것이다. 만일 이 뒤에 taken이 나타난다면, 이 선택경로는 계속될 것이다. 그러나 만일 take가 다음에 나타났다면, 프로그램은 have가 주동사임을 알게되고, 문장의 주어는 you(명령문이므로)임을 알게되며, 이미 해석된 'the student who missed the exam'은 문장의 주어는 아니나, 이의 해석을 또다시 하지는 않고, 단지 문장에서의 이 명사구의 역할을 재조정한다. 이 방법은 앞서의 다른 두 방법보다는 효율적이기는 하지만, 이를 위하여서는 문법에서의 법칙간의 상호 관계가 분명히 명시되어 문장요소들이 한 곳에서 다른 곳으로 이동할 수 있어야 한다.
(4) 대기 및 관찰(wait-and-see) - 이 방법에서는 한 경로만 따라가지만, 문장의 각 요소를 만나게 되면 그 기능을 결정하지 않고, 후에 충분한 정보가 얻어져서 정확한 결정이 가능할 때가지 보류한다. 이 방법을 우리의 예에 적용시켜 보자. 이 문장에서 have를 만났을 때, 이는 동사로써 그 기능은 아직 알려져 있지 않은 것으로 기록된다. 뒤따르는 명사구는 해석되어 단순히 명사구로써 기록된다. 다음 단어를 만났을 때, 이제까지 만난 모든 요소들을 어떻게 구성시켜야 할 것인지를 결정할 수 있게 된다. 여러 파서(parser)가 이러한 방법을 사용하였는데 그 중 특히 PARSIFAL [Mar 79] [Mar 80]이 이 방법을 집중적으로 사용하는 예가 되겠다. 이러한 방식은 상당히 효율적이기는 하지만, 만일 대기하는 정보가 많게 되면 해결이 곤란하게 된다. 그러나 이러한 경우에 대해서는 인간도 같은 어려움을 겪는 것이 보통이다. 예로써,

The horse raced past the barn fell down.

이 경우, 말(horse)이 넘어진 것(fell down)인지 아니면 헛간(barn)이 무너진 것(fell down)인지 애매하다.

  이렇듯 어떤 경로를 따를 것인지 결정하는 문제와 어떻게 백트랙을 처리할 것이냐는 모든 탐색 과정에 있어서 생기는 공통적인 문제이지만, 이들이 언어 이해에 있어서 더욱 복잡하게 되는 것은, 언어에는 선천적으로 애매한 문장들이 존재하기 때문이다. 예로써 "They are flying plane."은 예를 상기해 보면 된다. 만일 한 가지 해석이 아닌 가능한 모든 경우의 해석이 필요하다면, 모든 경로를 따라하거나(이는 상당히 비효율적인데, 이유는 이들 대부분이 문장의 끝을 만나기 전에 제거되기 때문이다) 아니면 강제적으로 백트래킹을 시킨다(이 역시 중복된 연산을 하므로 비효율적이 된다). 많은 실용적인 경우에는 하나의 가능한 해석을 찾는 것으로 만족하게 된다. 이 해석이 후에 의미의 불합리나 혹은 실용적인 이유에서 거부된다면, 다른 해석을 찾는 새로운 작업이 수행될 것이다.