컴파일러 프런트엔드: 렉싱과 파싱 (Frontend Compilers)

1. Overview

프론트엔드 컴파일러 - 렉싱과 파싱(Frontend Compilers: Lexing & Parsing)은 인간이 작성한 소스 코드 문자열을 **컴파일러가 이해하고 처리할 수 있는 구조화된 내부 표현(AST, Abstract Syntax Tree)**으로 변환하는 컴파일러 첫 두 단계를 다룹니다.

학습자는 소스 코드를 토큰(Token, if, 42, "hello", ==) 스트림으로 변환하는 **렉서(Lexer, Tokenizer)**의 정규 표현식 → DFA 구현 원리를 살펴봅니다. 이어서 토큰 스트림을 문법(Grammar)에 따라 파스 트리로 조립하는 **파서(Parser)**의 두 가지 주요 방식—하향식(Top-Down, LL/Recursive Descent)과 상향식(Bottom-Up, LR/LALR)—의 차이와 각각의 충돌 해결 전략을 비교합니다. 마지막으로 파스 트리를 의미 분석(Semantic Analysis)에 최적화된 AST로 단순화하고, **심볼 테이블(Symbol Table)**을 구축하는 과정까지 프론트엔드 파이프라인 전체 흐름을 정리합니다.

2. Scope & Boundaries

In-Scope

• 렉서 (Lexer / Tokenizer): 토큰 명세(정규 표현식), DFA 기반 렉싱, 렉서 제너레이터(Lex/Flex).
• 파서 (Parser): 재귀 하강 파서(Recursive Descent, LL(1)), LR 파서(LALR(1), Yacc/Bison), First/Follow 집합.
• AST 구축 (AST Construction): 파스 트리 → AST 변환, 방문자 패턴(Visitor), AST 노드 설계.
• 의미 분석 (Semantic Analysis): 심볼 테이블(Symbol Table), 타입 검사(Type Checking), 스코프(Scope) 분석.

Out-of-Scope

• 코드 최적화와 코드 생성: IR(Intermediate Representation) 최적화, LLVM IR → 어셈블리 → 05-02-02 Optimization & Code Generation 영역.
• 런타임 시스템: JIT 컴파일, GC → 05-02-03/04 영역.

Boundaries

• LL vs LR 파서: LL(1) 파서(재귀 하강)는 구현이 단순하고 오류 메시지가 직관적이며, 수작업 구현이 가능합니다. 하지만 좌재귀(Left Recursion) 문법을 처리하지 못하는 한계가 있습니다. LR(LALR(1)) 파서는 더 광범위한 문법을 처리하며 yacc/bison으로 자동 생성되지만, 충돌(Shift-Reduce, Reduce-Reduce) 디버깅이 어렵습니다.

3. Counterexample

• 렉서 없는 파서의 토큰 오해 (Lexer-less Parsing Confusion): 소스 코드 "if(x==10)" 문자열을 파서에 직접 전달하면, 파서가 i, f, ( 같은 개별 문자를 처리해야 하는데, 문법 규칙이 if_stmt → 'if' '(' expr ')' stmt처럼 토큰 단위로 정의됩니다. 렉서가 "if" → TK_IF, "==" → TK_EQ 같이 의미 단위 토큰으로 분리하는 선처리 없이는 파서가 문법을 적용할 수 없습니다. 렉서와 파서의 역할 분리가 필수입니다.
• 좌재귀 문법과 LL 파서의 무한 루프 (Left Recursion in LL Parser): 산술식 문법 E → E + T | T는 자연스러운 좌재귀(Left Recursive) 문법. 재귀 하강 파서(LL)에서 parse_E() 함수는 E를 파싱하기 위해 먼저 parse_E()를 호출 → 다시 parse_E() 호출 → 무한 루프(Left Recursion Loop). LL 파서에서는 E → T E', E' → + T E' | ε로 좌재귀를 제거(Left Recursion Elimination)해야 합니다.

4. Prerequisites

• 정규 표현식과 DFA (Basic): 렉서가 정규 표현식으로 토큰을 정의하고 DFA로 인식합니다. (04-04-02 String Matching & Automata)
• 문맥 자유 문법 (Basic): 파서가 CFG에 따라 토큰 스트림을 파스 트리로 변환합니다. (05-01-01 Grammar & Semantics)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 문자열을 의미 덩어리로 쪼개다, 렉서와 토크나이저 (Lexer & Tokenization)

• Why to Learn: 모든 프로그래밍 언어 파서, JSON/XML/YAML 파서, SQL 파서의 첫 단계가 렉서임을 이해하고, 직접 미니 렉서를 구현하여 토크나이저의 정규 표현식 → DFA 변환 과정을 익히기 위함입니다.
• What to Learn:
  • Concepts: 토큰(Token, 유형+값 쌍), 어휘 단위(Lexeme), 최장 일치 규칙(Maximal Munch), 화이트스페이스/주석 건너뜀.
  • Skills: 정규 표현식으로 토큰 패턴 정의, 파이썬 re 모듈 기반 렉서 구현.
  • Tools: Python re.compile 기반 렉서, Flex/Lex 도구.
• How to Learn:
  • 1단계: 토큰 유형 정의: NUMBER, PLUS, MINUS, STAR, LPAREN, RPAREN, ID, IF. 각 유형에 정규 표현식 패턴. 소스 "x + 42 * (y - 3)" → [ID('x'), PLUS, NUMBER(42), STAR, LPAREN, ID('y'), MINUS, NUMBER(3), RPAREN] 토큰 스트림으로 변환하는 과정을 살펴봅니다.
  • 2단계: 최장 일치(Maximal Munch): >=를 > + =가 아닌 단일 토큰 GTE로 인식하는 규칙. 패턴을 긴 것부터 먼저 시도하여 최장 매칭을 보장하는 방식을 살펴봅니다.
• Implement: 파이썬 Lexer 클래스. TOKEN_SPECS = [('NUMBER', r'\d+'), ('PLUS', r'\+'), ('MINUS', r'\-'), ('STAR', r'\*'), ...]. tokenize(source) → 토큰 리스트. "if x == 42: return x * 2" → 올바른 토큰 스트림 출력 검증.

Recommended

Core Topic 02: 문법 규칙을 함수로, 재귀 하강 파서 (Recursive Descent Parser)

• Why to Learn: GCC의 C 파서, Python 인터프리터, TypeScript 파서가 모두 재귀 하강 파서로 구현됩니다. 수작업으로 파서를 직접 구현하는 능력은 DSL(Domain Specific Language) 설계, 설정 파일 파서, 쿼리 언어 구현의 핵심 기술입니다.
• What to Learn:
  • Concepts: 재귀 하강(Recursive Descent), 예측 파싱(Predictive Parsing), FIRST 집합, FOLLOW 집합, LL(1) 조건, 좌재귀 제거.
  • Skills: 산술식/불리언 표현식/if-else 문 파서 구현.
• How to Learn:
  • 1단계: 산술식 문법 E → T E', E' → + T E' | ε, T → F T', T' → * F T' | ε, F → (E) | num. 각 비단말(Non-terminal)이 파이썬 함수 parse_E(), parse_T(), parse_F()로 1<1> 대응하는 구조를 살펴봅니다.
  • 2단계: parse_E() 내부: left = parse_T(). while current_token == PLUS: consume(PLUS); right = parse_T(); left = BinOp('+', left, right). return left. 재귀 하강으로 2+3*4 → BinOp('+', 2, BinOp('*', 3, 4)) AST를 구성하는 과정을 따라갑니다.
• Implement: 파이썬 RecursiveDescentParser. tokenize("2 + 3 * (4 - 1)") 후 parse_expr(). 결과 AST {op:'+', l:2, r:{op:'*', l:3, r:{op:'-', l:4, r:1}}}. eval_ast(ast) 함수로 11 계산 검증. "if x > 0: x = x - 1" 파싱 AST 추가 구현.

Practical

Core Topic 03: 스택으로 쌓고 환원하다, LR 파서와 LALR(1) (LR Parsing)

• Why to Learn: yacc/bison, ANTLR, Java CUP 같은 파서 제너레이터가 자동 생성하는 LR 파서의 내부 동작(Shift-Reduce)을 이해하면, shift/reduce conflict 오류를 디버깅하고, 복잡한 언어 문법을 설계할 때 모호성을 제거하는 역량을 갖출 수 있습니다.
• What to Learn:
  • Concepts: LR(k) 파서, 파싱 테이블(Action/Goto), Shift(토큰 스택 push), Reduce(스택 top 규칙 적용), Shift-Reduce/Reduce-Reduce 충돌, LALR(1) 상태 병합.
  • Skills: 간단 LR(0) 아이템 집합 구축, 충돌 해결(우선순위/결합성 선언).
  • Tools: Python PLY(Python Lex-Yacc), Bison.
• How to Learn:
  • 1단계: 입력 id + id * id LR 파싱 과정. 스택: [] id → Shift [id] → Reduce [E] → [E+] Shift → [E+id] Shift → Reduce [E+E] → Reduce [E+E*] → ... 스택 상태와 액션 테이블 조회로 파싱이 진행되는 흐름을 살펴봅니다.
  • 2단계: Shift-Reduce 충돌: if E then if E then S else S. else를 만났을 때 외부 if의 미완성 부분(Shift)과 내부 if의 완성(Reduce) 중 선택. C/Java의 else가 가장 가까운 if에 붙는 "단면 else(dangling else)" 해결 방식을 살펴봅니다.
• Implement: Python PLY 라이브러리로 산술식 LALR(1) 파서. import ply.lex as lex; import ply.yacc as yacc. 토큰 정의 + yacc 문법 규칙. "2 + 3 * 4" → 14 계산. Shift-Reduce 충돌 우선순위 선언(precedence = (('left','PLUS','MINUS'), ('left','TIMES','DIVIDE')))으로 해결.

Advanced

Core Topic 04: 파스 트리를 의미로 변환, AST와 의미 분석 (AST & Semantic Analysis)

• Why to Learn: 파서가 생성한 파스 트리는 문법 규칙의 모든 중간 단계를 포함하여 최적화/변환에 비효율적입니다. AST로 단순화하고 심볼 테이블로 변수 타입·스코프를 추적하는 의미 분석 단계가 완전한 컴파일러 프론트엔드를 완성하며, 이후 최적화 단계의 기반을 형성합니다.
• What to Learn:
  • Concepts: 파스 트리 → AST 변환(불필요한 중간 노드 제거), 심볼 테이블(Symbol Table, 이름→타입·스코프·위치), 스코프 체인(Scope Chain), 타입 검사(Type Checking, 이항 연산 타입 호환성).
  • Skills: 방문자 패턴(Visitor Pattern)으로 AST 순회, 타입 오류 메시지 생성.
• How to Learn:
  • 1단계: 파스 트리 (E (T (F 2)) + (T (F 3) * (F 4))) → AST BinOp('+', 2, BinOp('*', 3, 4)). 불필요한 E, T, F 중간 노드가 제거되어 핵심 의미 구조만 남는 AST 단순화 과정을 살펴봅니다.
  • 2단계: 심볼 테이블: int x = 10; { int y = x + 1; }. 외부 스코프 {x: int, offset=4}, 내부 스코프 {y: int, offset=8}. 내부에서 x 참조 시 스코프 체인을 타고 외부 스코프에서 탐색하는 과정을 살펴봅니다.
• Implement: 파이썬 AST 방문자 패턴. class TypeChecker(ASTVisitor). visit_BinOp(node): 좌우 타입 추론 후 호환성 검사. int + float → float(OK), int + string → TypeError(오류). 타입 오류 메시지 "Line 3: Type mismatch: cannot add int and str" 생성. 중첩 스코프 심볼 테이블 구현 + x = y + 1 (y 미정의) → NameError 탐지.

7. Terminology

8. References

Primary

• [P1] CS2023 - Programming Languages (PL) - Compiler Lexical and Syntax Analysis
• [P5] SFIA - Software Development (PROG) - Compiler Frontend

Secondary

• [Compilers: Principles, Techniques, and Tools (Dragon Book)] Aho, Lam, Sethi, Ullman - Lexical Analysis and Parsing
• [Engineering a Compiler] Keith Cooper, Linda Torczon - Front End Overview

Industry

• [Clang Frontend Documentation] - Clang AST and Lexer
• [Babel Handbook] - JavaScript Parser and AST Traversal

9. Final Checklist

Primary

• 정규 표현식(Regex)을 이용한 유한 상태 기계(FSM)가 소스 코드를 토큰으로 분할하는 원리를 설명할 수 있는가?
• 파서(Parser)가 토큰 스트림을 입력받아 재귀적 하향 파싱(Recursive Descent)을 통해 AST를 조립하는 과정을 묘사할 수 있는가?

Secondary

• Parse Tree (CST)와 AST(Abstract Syntax Tree)의 차이를 비교하고, 컴파일러가 왜 CST를 압축하여 AST를 사용하는지 논증할 수 있는가?
• 구문 에러(Syntax Error)와 의미 에러(Semantic Error)의 발생 시점이 어떻게 다르며, 심볼 테이블(Symbol Table)이 의미 검증에 어떻게 쓰이는지 설명할 수 있는가?

Industry

• LL(1) 파서와 LR 파서의 차이를 설명하고, 실무에서 수작업(Hand-written) 파서가 파서 제너레이터(Yacc/Bison)보다 선호되는 이유(오류 메시지 처리)를 분석할 수 있는가?
• 프론트엔드 파이프라인에서 생성된 AST가 정적 분석기(Linter)나 코드 포매터(Prettier)에서 어떻게 활용되는지 아키텍처 관점으로 설계할 수 있는가?