INTRODUCTION

이러한 임의의 문법이 하나의 언어를 정의하는 과정을 살펴보는 방법에는 몇 가지가 있으나 대표적으로, 생성하고자 하는 식에 있어서 그것의 왼쪽 비단말들을 오른쪽의 문자열로 대체시키는 규칙으로 취급하는 유도(Derivation) 관계를 보는 것이 있다. parse tree는 이러한 derivation 과정에서 대치가 어떤 순서로 이루어지는가를 그림으로 보여 준다. 하지만 어떤 문장에 대해서 하나 이상의 parse tree를 만들어내는 문법에 생길 수 있는데 이를 우리는 모호하다(ambiguous)고 한다. 다시 말해서 모호한 문법은 같은 문장에 대해서 하나 이상의 맨 왼쪽이나 오른쪽 유도를 생성해 내는 것이다.
parsing이란 어떤 토큰열이 그 문법(grammer)에 의해서 생성될 수 있는지를 검사하는 과정으로, 크게 하향식 파싱(top down parsing)과 상향식 파싱(bottom up parsing)으로 구분할 수 있다. 하향식 파싱(top down parsing)은 입력 문자열에 대해서 맨 왼쪽 유도를 찾는 과정이라고 볼 수 있다. 다시 말해서 입력 문자열에 대해서 루트에서 시작해서 왼쪽 우선순으로 트리의 노드들을 만들어가는 과정이라고 볼 수 있다. 다른 하나인 상향식 파싱(bottom up parsing)은…(생략)