[기술] 컴파일러[프론트엔드] 한 걸음씩 - 세번째

인사

이번 포스팅에서는 이전에 다뤘던 프론트엔드의 Lexical Analysis에 이어,
**Syntax Analysis(구문 분석)**에 대해 제가 공부한 내용을 공유드리겠습니다.

Frontend - Syntax Analysis 요약

Syntax Analysis(구문 분석)는 Lexical Analysis를 통해 생성된 **토큰 스트림(Token Stream)**을 기반으로
**AST(Abstract Syntax Tree)**를 생성하는 과정입니다.

우선, 토큰 스트림을 바탕으로 **Chomsky의 Type-2 문법(CFG, Context-Free Grammar)**을 정의하고,
이를 통해 FIRST와 FOLLOW 집합을 계산하여 Parsing Table을 구성합니다.
이 Parsing Table과 토큰 스트림을 함께 사용하여 **파서 트리(CST, Concrete Syntax Tree)**를 구성하게 됩니다.

CST가 완성되면 이를 후위 순회(post-order traversal)하며,
불필요한 비단말 기호(non-terminal), ε(εpsilon) 등을 제거하여
더 간결하고 의미 중심적인 AST로 변환합니다.

이 과정에서 등장하는 변수, 함수 등의 식별자 정보를 **심볼 테이블(Symbol Table)**에 저장해 나가게 됩니다.

자세한 소개에 앞서서 심볼테이블에 대해서 말씀드리면 컴파일하는 과정에서 문자가 어떠한지를 조사한 후 알려주는 테이블을 뜻합니다. 이 심볼테이블은 후에 소개해드릴 Semantic Analysis 단계나 Intermediate Code Generation 단계에서 사용되어집니다.

심볼 테이블이란?

심볼 테이블은 컴파일 과정에서 식별자의 정보를 관리하는 자료구조로,
주로 다음 단계인 Semantic Analysis 또는 Intermediate Code Generation 과정에서 사용됩니다.

이 테이블에는 변수나 함수 등의 이름(name), 타입(type), 스코프(scope) 등
컴파일에 필요한 메타정보가 저장되며,
정확한 의미 분석과 코드 생성을 가능하게 해줍니다.

이름	타입	스코프	값 or 위치
x	int	global	10 or offset

CFGs (Context-Free Grammars)

CFGs는 Chomsky의 Formal Grammar 이론을 바탕으로,
토큰 스트림을 문법적으로 구조화하기 위해 사용됩니다.

컴파일러의 Syntax Analysis 단계에서는 Chomsky 위계(Chomsky Hierarchy) 중
**Type-2 문법인 문맥 자유 문법(Context-Free Grammar)**을 사용합니다.
이 문법은 다음과 같은 형태의 규칙을 따릅니다:

A → α

여기서 A는 하나의 **비단말 기호(Non-terminal)**이고,
α는 **단말 기호(Terminal)**와 비단말 기호들의 조합입니다.

예시: 수식 1 + 2 * 3

다음과 같은 수식을 CFG로 표현해보면 다음과 같습니다:

N = { <EXPR>, <COUNT>, <DATA> }

T = { "+", "*", "NONE", NUMBER }

P = {

<DATA> → "NONE" | NUMBER

}

S = <EXPR>

이와 같은 방식으로 CFG를 구성하면, 토큰 스트림을 문법적으로 해석하고 파서 트리(CST)를 생성하는 데 사용할 수 있습니다.

Chomsky 이론 이란

Chomsky 이론은 언어의 문장 구조를 수학적이고 계층적으로 표현하기 위한 체계입니다.

이 위계를 통해 문법을 네 가지 수준(Type 0~3)으로 나누며,
**컴파일러 분야에서는 주로 Type-2인 문맥 자유 문법(CFG)**이 사용됩니다.

유형	이름	특징	예
Type 0	무제한 문법	가장 일반적	튜링 기계
Type 1	문맥 민감 문법	A → αBβ → αγβ (B → γ)	일부 자연어
Type 2	문맥 자유 문법	A → α	프로그래밍 언어
Type 3	정규 문법	A → aB 또는 A → a	정규 표현식

FIRST, FOLLOW, PARSING TABLE

**CFGs(문맥 자유 문법)**를 기반으로 FIRST 함수와 FOLLOW 함수를 정의하고, 이를 바탕으로 Parsing Table을 생성합니다. 이 과정은 LL(1) 파서와 같은 **예측 파싱(Predictive Parsing)**의 핵심입니다.

다음은 간단한 CFG 예시입니다.
(소문자는 단말 기호, 대문자는 비단말 기호를 의미합니다)

S → d A B c

A → a | ε

B → b

**FIRST(X)**는 어떤 비단말 기호 X가 파생할 수 있는 첫 번째 단말 기호 집합입니다.

FIRST(S) = { d }

FIRST(A) = { a, ε }

FIRST(B) = { b }

**FOLLOW(X)**는 비단말 기호 X 다음에 올 수 있는 단말 기호 집합입니다.
또한, 시작 기호 S에 대해서는 항상 **$ (입력의 끝)**이 포함됩니다.

FOLLOW(S) = { $ }

FOLLOW(A) = FIRST(B) ∪ { c } = { b, c }

FOLLOW(B) = { c }

여기서 구한 FIRST 함수와 FOLLOW 함수는 PARSING TABLE을 제작하는데 사용이 됩니다.

	a	b	d	c	$
S			S - dABc
A	A -> a	A -> ε		A -> ε
B		B -> b

CST(파서 트리)

토큰 스트림과 Parsing Table을 이용해 **CST(Concrete Syntax Tree)**를 생성합니다.
파서 트리를 만드는 방법은 다양하지만, 크게 **탑다운 파서(Top-Down Parser)**와 **바텀업 파서(Bottom-Up Parser)**로 나눌 수 있습니다.

탑다운 파서 중에서도 백트래킹 여부에 따라 또 나뉘는데,
이번에 소개드릴 방식은 백트래킹이 없는 Predictive Parser 중 하나인 LL(1) 파서입니다.

LL에 뜻은 L(첫 번째): 입력을 왼쪽부터 오른쪽으로 읽는다 (Left-to-right) L(두 번째): 좌측 유도(Leftmost derivation)를 사용한다 여기서 1: 한 번에 하나의 토큰을 본다 (Lookahead = 1)입니다.

LL(1) 파서의 동작 방식

   1. 스택을 사용하며 초기 상태는 [$, <시작 비단말>] 입니다.
2. 스택의 가장 위(top)에 있는 기호를 꺼냅니다.
3.이 기호와 현재 토큰 스트림의 토큰을 비교하여,
   4. Parsing Table을 참조해 해당되는 생성 규칙을 찾습니다.
   5. 해당 규칙의 우변 기호들을 스택에 역순으로 push합니다.
   6. 이 과정을 반복하다가 **스택의 top이 $**이고 **입력 토큰도 $**이면 종료합니다.
   7. 이 과정을 통해 **구문 규칙에 맞는 파서 트리(CST)**를 구성할 수 있습니다.

예를 들어서 1 + 2 * 3 이 있다고 처봅시다. 이거에 대한 CFG에 NTPS는

N = { <EXPR>, <COUNT>, <DATA> }

T = { "+", "*", "NONE", NUMBER }

P = {

<DATA> → "NONE" | NUMBER

}

S = <EXPR>

이렇게 되고 이를 이용해서 PARSING TABLE을 만들면 아래와 같이 됩니다.

	NONE	NUMBER	+	*	$
EXPR	EXPR → COUNT	EXPR → COUNT
COUNT	COUNT → DATA	COUNT → DATA
DATA	DATA → "NONE"	DATA → NUMBER

주어진 토큰 스트림은 다음과 같습니다:

[

{ "name": 1, "type": "CONSTANT" },

{ "name": "+", "type": "KEYWORD" },

{ "name": 2, "type": "CONSTANT" },

{ "name": "*", "type": "KEYWORD" },

{ "name": 3, "type": "CONSTANT" }

]

LL(1) 파서의 초기 스택 상태는 ["$", <START>]입니다.
파서는 <START>를 꺼내어 <EXPR>로 확장하고, <EXPR>를 다시 스택에 넣습니다.

이후 <EXPR>를 꺼내 현재 토큰 스트림의 첫 번째 값인 1을 확인합니다.
파싱 테이블을 참조하면, <EXPR>는 <COUNT>로 확장되고
<COUNT>는 <DATA>로, <DATA>는 NUMBER로 확장됩니다.

토큰 1은 실제 단말 기호 NUMBER와 일치하므로
스택에서 제거되고 CST에 해당 노드로 기록됩니다.

이때 스택의 변화는 다음과 같이 진행됩니다:

[ $, COUNT, +, EXPR ]

→ [ $, COUNT, +, COUNT ]

→ [ $, COUNT, +, DATA ]

→ [ $, COUNT, +, NUMBER ]

NUMBER는 단말 기호이므로 토큰 스트림의 값 1과 매칭되어
파서 트리에 단말 노드로 추가됩니다.

이러한 과정을 반복적으로 수행하면 전체 CST(Concrete Syntax Tree)가 완성되며,
토큰 스트림의 모든 요소가 문법에 따라 구조화되어 표현됩니다.

<START>

<EXPR>

/ | \

| |

| |

| |

NUMBER NUMBER

AST (Abstract Syntax tree)

AST는 **CST(Concrete Syntax Tree)**를 기반으로 후위 순회(Post-order Traversal)를 통해 생성됩니다.
이 과정의 핵심 목적은 구조적으로는 필요하지만 의미적으로는 중요하지 않은 요소들,
예를 들어 ε, <EXPR>, <TERM> 같은 중간 비단말 기호를 제거하고,
실제로 의미를 갖는 연산자나 값들만 남기는 것입니다.

이때 AST를 구성할 때 중요한 역할을 하는 것이 바로 **RHS(Right-Hand Side)**입니다.
CST는 생성 규칙의 RHS를 그대로 따르기 때문에,
우리는 RHS의 구조를 분석하여 의미 있는 요소만 걸러내 AST를 구성하게 됩니다.

RHS(Right-Hand Side)란

**RHS(Right-Hand Side)**는 **문맥 자유 문법(CFG)**에서 생성 규칙의 오른쪽 항을 의미합니다.
예를 들어 다음과 같은 규칙이 있다고 가정해 봅시다:

이 경우 <EXPR> + <TERM>과 <TERM>이 RHS입니다.
이 규칙에서 **의미 있는 연산자 +**는 AST에 남기고,
<EXPR>나 <TERM>처럼 단순한 구조 표현 역할만 하는 비단말 기호는 제거하게 됩니다.

만약 바로 위의 CST를 AST로 바꾼다면 다음과 같습니다.

/ \

1 *

/ \

2 3

오류

우리가 코딩을 하다 보면 **Syntax Error(구문 오류)**를 자주 마주하게 됩니다.

이는 문법적으로 코드 구조가 잘못되었을 때 발생하는 오류로,
Syntax Analysis(구문 분석) 단계에서 컴파일러가 이를 감지하게 됩니다.

예를 들어 다음과 같은 코드가 있다고 가정해봅시다:

const if = 10;

SyntaxError: Unexpected token 'if'

if는 자바스크립트에서 **예약어(keyword)**이기 때문에
변수 이름으로 사용할 수 없으며,
CFGs(Context-Free Grammars)를 기반으로 분석할 때
이와 같은 토큰의 배치와 의미 구조가 문법 규칙에 위배됨을 감지하여 오류를 발생시킵니다.

또 다른 예를 보겠습니다:

if a === 1 {
  console.log("a는 숫자 1입니다.");
}

SyntaxError: Unexpected identifier 'a'

if 문은 문법적으로 반드시 괄호로 조건식을 감싸야 합니다.
즉, CFGs에서는 다음과 같은 규칙이 설계되어 있을 것입니다:

<IF_STMT> → if ( <EXPR> ) { <BLOCK> }

이러한 CFG의 구조에 맞지 않는 코드 흐름이 들어오면,
Syntax Analysis 단계에서 **"기대하지 않은 토큰"**이라는 메시지와 함께 오류가 발생하는 것입니다.

예고

다음 포스팅에서는 **Semantic Analysis(의미 분석)**에 대해 소개드릴 예정입니다.
Semantic Analysis는 앞서 생성한 **AST(Abstract Syntax Tree)**를 기반으로,
코드의 흐름상 의미적인 오류가 있는지를 검증하는 과정입니다.
Syntax Analysis 단계에서 잡지 못한 오류들을 이 단계에서 탐지하게 됩니다.

긴 글 읽어주셔서 감사드리며,
항상 하시는 일에 좋은 결과 있으시길 바랍니다. 화이팅!