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

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

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

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