2.1.2 파싱

다음 단계는 파싱(parsing, 구문 분석)이다. 구문에 문법(grammar), 즉 작은 부품들을 모아 더 큰 표현식과 문장을 구성하는 능력이다. 영어 수업 시간에 문장(sentence)을 도식화한 경험이 있는 독자라면 이미 (영어에 수천, 수만 개의 ‘키워드’가 있고 다의성(多義性)이 차고 넘친다는 점을 제외하면) 파서가 하는 일을 손수 해본 셈이다. 사람의 언어에 비하면 프로그래밍 언어는 훨씬 간단하다.

파서는 플랫(flat)한² 일련의 토큰을 받아 문법 특유의 중첩된 성질을 반영하는 트리 구조로 만든다. 이 트리는 소스 언어의 원시 구문 구조에 얼마나 가까운지에 따라 파스 트리(parse tree) 또는 추상 구문 트리(AST, Abstract Syntax Tree)라는 상이한 두 가지 이름으로 불린다. 보통 해커들은 구문 트리(syntax tree)나 AST, 아니면 그냥 트리(tree)라고 부른다.

파싱은 CS에서 유구한 역사를 자랑하는 분야로서 인공 지능(AI, Artificial Intelligence) 커뮤니티와 밀접하게 연관되어 있다. 오늘날 프로그래밍 언어의 파싱 기법은 원래 대부분 인간과 대화가 가능한 컴퓨터를 연구했던 AI 과학자들이 인간의 언어를 파싱하려고 고안한 것들이다.

인간의 언어는 엄격히 정해진 문법만 처리 가능한 파서에게 너무 지저분했지만, 이보다 훨씬 단순한 프로그래밍 언어의 인공 문법에는 완벽하게 잘 맞았다. 아, 그러나 흠 많은 우리 인간은 이리도 단순한 문법조차 잘못 사용하는 경우가 허다해서 파서는 구문 에러(syntax error)를 리포트하는 임무까지 수행한다.