[컴파일러] - 구문 분석 (Syntax Analysis) I

1. 개요

컴파일러에서는 구문 분석을 수행하는 모듈을 파서 (parser)라고 한다. 파서는 어휘 분석기에서 생성한 토큰 스트림이 생성 가능한 것인지를 판별하고, 토큰 스트림으로부터 파스 트리 (parse tree)를 생성한다.

파서의 일반적인 유형으로는 보편적 (universal), 하향식 (top-down), 상향식 (bottom-up)이 있다. 보편적 파싱 방법은 어떠한 문법도 파싱할 수 있지만, 파싱 과정이 매우 비효율적이기 때문에 상용 컴파일러에는 적용될 수 없다. 따라서, 컴파일러에서는 하향식과 상향식 파서가 이용되며, 주로 상향식 파서가 많이 이용된다.

2. 문맥 자유 문법 (Context-free grammar, CFG)

우리가 영어 문장에서 문법적 오류를 검출하기 위해서는 영어 문법을 이해하고 있어야 하는 것이 당연하듯이 파서 또한 프로그래밍 언어 정의에 이용된 문법을 이해하고 있어야 한다. 현재까지 개발된 있는 대부분의 프로그래밍 언어는 문맥 자유 문법을 기반으로 정의되어 있다. 문맥 자유 문법은 촘스키 위계 (Chomsky hierarchy)의 type-2에 해당하는 문법이다.

[그림 1] 촘스키 위계 (Chomsky hierarchy)

문맥 자유 문법 $G$는 $G = (V, T, P, S)$의 순서쌍으로 정의되며, 각 원소의 의미는 아래와 같다.

• $V$: nonterminal의 유한집합으로써 nonterminal은 언어에 대한 계층적 구조를 부여하는 역할을 한다.
• $T$: terminal의 유한집합으로써 terminal은 더 이상 다른 terminal이나 nonterminal로 유도가 불가능하다. $V$와 $T$는 서로소이다.
• $P$: 생성규칙 (production)의 유한집합. 문법의 생성규칙은 nonterminal과 terminal들의 조합되어 문자열을 생성할 수 있는 방법을 명시한다.
• $S$: 문법에서는 한 개의 nonterminal을 시작 기호 (start symbol)로 갖는다. $S$는 해당 문법의 시작 기호를 나타내며, 문법은 항상 시작 기호로부터 시작된다.

문맥 자유 문법의 정의에서 생성규칙은 다음과 같이 정의된다. 아래의 생성규칙을 이해하기 위해서는 언어 도메인에서의 연산에 대한 이해가 필요하다. 언어 도메인에서의 연산은 이 글에 간략하게 설명되어 있다.

문맥 자유 문법에서 생성규칙의 가장 큰 특징은 생성규칙의 좌변에는 항상 1개의 nonterminal만 올 수 있다는 것이다. 하나의 nonterminal만 고려하여 문자열을 생성하기 때문에 문맥에 자유롭다는 의미에서 문맥 자유 문법이라고 한다.

문맥 자유 문법을 이용한 예제 문법으로는 아래와 같은 문법이 있을 수 있다.

3. 유도 (Derivation)

구문 분석에서 유도라는 것은 문법의 생성규칙에 따라 특정한 문자열을 도출해나가는 과정이다. 예를 들어, 아래와 같은 문법이 있을 때

문자열 -(id + id)를 유도하는 과정은 아래와 같다. 유도는 생성과 다르게 직선이 두 개 있는 화살표로 표현한다.

위의 유도에서는 항상 가장 왼쪽에 위치한 nonterminal을 생성규칙에 따라 변환하였는데, 이를 최좌돤 유도 (leftmost derivation)이라 한다. 반대로 다음과 같이 항상 가장 오른쪽에 위치한 nonterminal을 변환하는 방식은 최우단 유도 (rightmost derivation)이라 한다.

4. 파스 트리 (Parse tree)

파서의 주 목적은 소스 코드라는 문자열에서 파스 트리를 생성하는 것이다. 파스 트리를 생성하는 것은 문법의 생성규칙과 유도를 통해 서술될 수 있다. 아래의 [그림 2]는 예제 문법으로부터 문자열 -(id + id)에 대한 파스 트리를 생성한 것이다.

[그림 2] 문자열 -(id + id)에 대한 파스 트리 (parse tree)

지금까지 유도와 파스 트리에서 나타나는 것은 시작 기호로부터 특정 문자열을 도출해나가는 과정이다. 그러나 컴파일러의 역할을 잘 생각해보면 이와 반대로 특정 문자열이 프로그래밍 언어의 문법적 정의에 의해 도출될 수 있는지를 검사하는 것이 컴파일러의 주요한 기능이다.

유도 및 파스 트리와 소스 코드의 문법적 오류 검출간의 관계는 다음 글에서 상향식 파서 (top-down parser)와 하향식 파서 (bottom-up parser)에 대해 소개하면서 자세하게 설명할 것이다.

5. 모호성 (ambiguity)

어떤 문자열에 대해 두 개 이상의 서로 다른 파스 트리를 생성하는 문법을 "모호하다"라고 한다. 즉, 모호한 문법은 동일한 문자열에 대해서 2개 이상의 최좌단 유도나 2개 이상의 최우단 유도를 생성하는 문법이다. 예를 들어, 아래와 같은 문법이 있는 경우,

문자열  id + id * id이 입력된다고 가정하면, 해당 문법은 동일한 문자열에 대해 아래의 [그림 3]과 같은 두 개의 서로 다른 파스 트리를 생성한다.

[그림 3] 동일 문자열에 대한 두 개의 서로 다른 파스 트리 (parse tree)

따라서, 위의 문법은 모호하다.

대부분의 파서에서 문법은 모호하지 않은 것이 바람직하다. 문법이 모호할 경우에는 파서가 어떠한 생성규칙을 선택할지를 유일하게 결정할 수 없기 때문이다. 문법을 정의할 때는 모호한 문법이 되지 않도록 하는 것이 중요하며, 좌재귀 제거와 좌인수분해 등 문법의 모호성을 제거하기 위한 다양한 방법들이 있다.