지난 시간에는 프로그래밍 언어의 규칙을 정의하는 '설계도', 즉 형식 문법(Formal Grammar)과 그 종류를 나누는 촘스키 계층에 대해 알아보았다. 설계도가 있다는 것은 알겠는데, 그렇다면 컴파일러는 이 설계도를 가지고 우리가 실제로 지은 집(작성한 코드)이 규칙에 맞게 잘 지어졌는지 어떻게 검사하는 것일까?
오늘은 컴파일러가 문법을 기반으로 코드의 구조를 분석하고 이해하는 핵심 과정인 파싱(Parsing)과 그 결과물인 파스 트리(Parse Tree)에 대해 깊이 있게 탐구해 볼 것이다.
1. 파싱(Parsing)이란 무엇인가? 문법 검사기
파싱(Parsing) 또는 구문 분석(Syntax Analysis)은 주어진 문자열(소스 코드)이 특정 문법(Grammar)의 규칙에 따라 생성될 수 있는지를 확인하는 과정이다. 쉽게 말해, 컴파일러의 '문법 검사기' 역할을 수행하는 단계인 것이다.
입력: 어휘 분석기를 거쳐 토큰(Token)의 나열로 변환된 소스 코드
작업: 해당 토큰의 순서가 문법 규칙에 맞는지 검사
출력: 토큰들의 관계를 계층적인 구조로 나타낸 파스 트리(Parse Tree)
만약 파싱 과정에서 문법에 맞지 않는 토큰 순서를 발견하면, 컴파일러는 "Syntax Error"와 같은 오류 메시지를 출력하고 컴파일을 중단한다.
2. 코드의 뼈대를 시각화하다, 파스 트리(Parse Tree)
파스 트리(Parse Tree)는 파싱 과정을 거쳐 생성된, 코드의 문법적 구조를 시각적으로 표현한 트리이다. 지난 시간에 배운 '유도(Derivation)' 과정을 그대로 나무 형태로 옮겨놓은 것이라고 생각하면 쉽다.
예를 들어, id + id * id라는 코드를 이전에 살펴본 문법으로 파싱하면 다음과 같은 파스 트리가 생성된다.
루트 노드(Root Node): 문법의 시작 기호(Start Symbol)에서 시작한다. (예: <expr>)
내부 노드(Internal Nodes): 문법의 비단말 기호(Non-terminals)로 구성된다. (예: <expr>, <term>)
리프 노드(Leaf Nodes): 문법의 단말 기호(Terminals)로 구성되며, 실제 코드를 나타낸다. (예: id, +, *)
파스 트리는 왜 중요한가? 단순히 문법이 맞았는지 확인하는 것을 넘어, 코드의 구조적인 의미를 명확하게 보여주기 때문이다. 위 트리에서는 + 연산이 * 연산보다 상위 레벨에 있어, 컴파일러가 연산자들의 관계와 우선순위를 파악하고 다음 단계(의미 분석, 코드 생성)를 준비할 수 있게 해준다.
3. 문법의 모호성(Ambiguity), 컴파일러의 최대 난관
만약 하나의 코드에 대해 두 개 이상의 파스 트리가 만들어질 수 있다면 어떻게 될까? 이를 모호한 문법(Ambiguous Grammar)이라고 한다.
예를 들어, 다음과 같은 간단한 규칙을 생각해 볼 수 있다. <expr> → <expr> + <expr> | <expr> * <expr> | id
이 규칙으로 id + id * id를 파싱하면 아래와 같이 두 가지 해석(두 개의 파스 트리)이 모두 가능해진다.
(id + id) * id 로 해석되는 경우
id + (id * id) 로 해석되는 경우
컴파일러는 어떤 트리를 선택해야 할지 알 수 없으며, 이는 전혀 다른 결과값을 내는 심각한 문제이다. 프로그래밍 언어는 절대 모호해서는 안 되므로, 우리는 모호하지 않은(unambiguous) 문법을 사용해야만 한다.
4. 모호성 해결하기: 연산자 우선순위 부여
모호성을 해결하는 가장 일반적인 방법은 문법 자체를 수정하여 연산자 우선순위(Operator Precedence)를 명시적으로 부여하는 것이다. 지난 시간에 살펴본 Expression, Term, Factor를 사용한 문법이 바로 그 예시이다.
<expr> → <expr> + <term> | <term> (덧셈은 낮은 순위)
<term> → <term> * <factor> | <factor> (곱셈은 높은 순위)
<factor> → (<expr>) | id
이렇게 문법을 여러 레벨로 나누면, 곱셈(*)이 덧셈(+)보다 항상 파스 트리의 더 깊은 곳(먼저 계산되는 곳)에 위치하도록 강제할 수 있다. 결과적으로 id + (id * id)로 해석되는 단 하나의 파스 트리만 생성되어 모호성이 사라진다.
마무리하며
오늘은 문법이라는 설계도를 가지고 실제 코드를 검사하는 파싱과 그 결과물인 파스 트리에 대해 알아보았다. 또한, 좋은 문법의 필수 조건인 모호성 문제와 이를 해결하는 방법까지 살펴보았다.
