어휘 분석과 구문 분석 (Lexical & Syntax Analysis)

한 줄 정의: 컴파일러가 소스 코드를 이해하는 첫 두 단계로, 문자열을 의미 있는 단어 단위(토큰)로 쪼개는 어휘 분석과 그 토큰들이 문법에 맞게 배열되었는지 확인하는 구문 분석을 말합니다.

쉽게 풀면

사람이 문장을 읽을 때도 먼저 단어를 하나하나 인식한 다음, 그 단어들이 문법에 맞게 배열되어 있는지를 파악합니다. 컴파일러도 똑같은 과정을 거칩니다.

어휘 분석(lexical analysis) 단계에서는 "if", "(", "x", ">", "0", ")" 처럼 소스 코드의 글자들을 의미 있는 최소 단위인 토큰으로 잘라냅니다.

그다음 구문 분석(syntax analysis, 파싱) 단계에서는 이 토큰들이 해당 프로그래밍 언어의 문법 규칙에 맞게 나열되어 있는지 검사하고, 그 결과로 코드의 구조를 나무 모양으로 표현한 자료구조를 만들어냅니다.

오타나 괄호 짝이 안 맞는 코드를 실행하면 "문법 오류(syntax error)"가 뜨는 것이 바로 이 구문 분석 단계에서 걸러지기 때문입니다.

왜 중요한가

어휘 분석과 구문 분석은 컴파일러·인터프리터 설계뿐 아니라 정적 분석, 코드 자동 리팩토링, 프로그램 이해를 위한 머신러닝 연구 등 소스 코드를 구조화된 형태로 다뤄야 하는 대부분의 소프트웨어공학 연구에서 전처리 단계로 쓰입니다. 코드를 텍스트가 아니라 구조를 가진 데이터로 취급할 수 있게 해주기 때문에, 새로운 프로그래밍 도구나 언어를 제안하는 논문의 방법론에서 빠지지 않고 언급됩니다.

어떤 절차인가

컴파일러의 앞부분(프런트엔드)은 두 단계로 소스 코드를 구조화합니다.

어휘 분석: 글자 흐름을 토큰으로 자릅니다. 토큰의 패턴은 정규표현식(유한 오토마타)으로 정의하는 것이 일반적입니다. 공백과 주석은 이때 버려집니다.
구문 분석: 토큰열이 문맥자유문법(CFG)에 맞는지 확인하고 구조를 만듭니다. 하향식(LL 계열, 재귀 하향 파서 등)과 상향식(LR 계열) 방식이 있습니다(Knuth, 1965; Aho et al., 2006).

구문 분석의 결과물은 파스 트리 또는 추상 구문 트리이며, 이후 의미 분석과 코드 생성이 이 트리를 입력으로 삼습니다. 문법 오류는 이 단계에서 걸러집니다.

언제 쓰고 무엇을 얻나

간단한 예를 코드로 처리해 봅니다. 소스 if (x > 0) y = 1;을 어휘 분석하면 다음 열 개의 토큰이 나옵니다(코드로 처리한 결과).

KEYWORD(if) · PUNCT(() · IDENT(x) · OP(>) · NUMBER(0) · PUNCT()) · IDENT(y) · OP(=) · NUMBER(1) · PUNCT(;)

구문 분석의 예로 문법 expr → term { + term }, term → factor { * factor }를 재귀 하향으로 구현해 1 + 2 * 3을 처리하면 괄호식 트리 (+ 1 (* 2 3)), 곧 곱셈이 덧셈보다 먼저 묶이는 구조가 나옵니다. 연산자 우선순위가 문법 규칙의 계층으로 표현된다는 점이 핵심입니다.

이 두 단계는 컴파일러뿐 아니라 정적 분석 도구, 코드 변환·리팩터링, 코드 표절·유사도 비교, 프로그램 이해를 위한 기계학습 연구에서 코드를 구조화된 데이터로 만드는 전처리로 쓰입니다.

논문에는 이렇게 적는다

어떤 언어의 어떤 문법(버전)을 대상으로 했는지, 어휘·구문 분석기를 직접 구현했는지 생성기(lex/yacc 계열, ANTLR 등)를 썼는지 적습니다.
파서 방식(LL, LR, 재귀 하향 등)과 문법의 모호성 처리 방법을 밝힙니다.
불완전하거나 틀린 코드에 대한 오류 복구 방식을 적습니다. 도구형 연구에서는 이 점이 실용성에 큰 영향을 줍니다.
평가에는 분석 성공률, 처리 속도, 오류 메시지의 품질을 씁니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

"제안한 도구는 소스 코드에 대해 어휘 분석과 구문 분석(lexical and syntax analysis)을 수행한 뒤, 생성된 구문 트리를 기반으로 코드 스멜을 탐지한다."

이 문장은 "코드를 먼저 토큰 단위로 쪼개고 문법 구조를 분석한 결과물을 이용해, 코드에 잠재된 문제를 자동으로 찾아낸다"는 뜻입니다.

"본 연구에서는 여러 프로그래밍 언어의 소스 코드를 언어별 어휘 분석기와 구문 분석기로 처리하여 공통된 중간 표현으로 변환한 뒤, 이를 코드 유사도 비교에 활용하였다."

다중 언어 코드 분석이나 표절 탐지 연구에서 서로 다른 언어의 코드를 공통 구조로 정규화할 때 사용된다.

"학습용 프로그래밍 언어를 위해 자체 어휘 분석기와 구문 분석기를 구현하고, 발생하는 오류 메시지를 초보 학습자가 이해하기 쉬운 형태로 재구성하였다."

컴퓨터교육 분야에서 학습자용 언어나 도구를 설계하며 컴파일러 프론트엔드를 직접 구현하는 연구에서 인용된다.

조금 더 깊게 보면

구문 분석은 크게 하향식(top-down)과 상향식(bottom-up) 방식으로 나뉘며, 각각 LL 파서, LR 파서와 같은 대표적인 알고리즘 계열로 구현됩니다.

이 두 단계를 거쳐 만들어지는 구조가 바로 추상 구문 트리이며, 이후의 의미 분석(semantic analysis)이나 코드 생성 단계는 이 트리를 입력으로 삼아 진행됩니다.

최근에는 문법 오류에 강건한 오류 복구(error recovery) 기법이나, 불완전한 코드도 처리할 수 있는 파서 설계도 함께 논의되는 경우가 많습니다.

주의할 점

구문 분석의 결과물로 만들어지는 나무 모양의 자료구조는 추상 구문 트리이며, 어휘 분석과 구문 분석 자체는 그 결과물을 만들어내는 "과정"을 가리키는 말입니다. 이 둘을 같은 것으로 혼동하지 않도록 주의해야 합니다.

헷갈리기 쉬운 용어

컴파일 과정의 용어는 ‘과정’과 ‘결과물’을 나눠야 합니다.

용어	성격	역할
어휘 분석	과정	소스 코드를 토큰으로 분리
구문 분석	과정	토큰열의 문법 검사와 구조 생성
추상 구문 트리	결과물(자료구조)	구문 분석이 만든 코드 구조
재귀 하향 파서	구문 분석 구현 방식의 하나	문법 규칙마다 함수를 두는 방식
컴파일러와 인터프리터	번역·실행 프로그램	어휘·구문 분석은 이들의 앞단

참고 문헌

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley.
Knuth, D. E. (1965). On the translation of languages from left to right. Information and Control, 8(6), 607–639.
Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.