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

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

쉽게 풀면

사람이 문장을 읽을 때도 먼저 단어를 하나하나 인식한 다음, 그 단어들이 문법에 맞게 배열되어 있는지를 파악합니다. 컴파일러도 똑같은 과정을 거칩니다. 어휘 분석(lexical analysis) 단계에서는 "if", "(", "x", ">", "0", ")" 처럼 소스 코드의 글자들을 의미 있는 최소 단위인 토큰으로 잘라냅니다. 그다음 구문 분석(syntax analysis, 파싱) 단계에서는 이 토큰들이 해당 프로그래밍 언어의 문법 규칙에 맞게 나열되어 있는지 검사하고, 그 결과로 코드의 구조를 나무 모양으로 표현한 자료구조를 만들어냅니다. 오타나 괄호 짝이 안 맞는 코드를 실행하면 "문법 오류(syntax error)"가 뜨는 것이 바로 이 구문 분석 단계에서 걸러지기 때문입니다.

왜 중요한가

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

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

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

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

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

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

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

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

조금 더 깊게 보면

구문 분석은 크게 하향식(top-down)과 상향식(bottom-up) 방식으로 나뉘며, 각각 LL 파서, LR 파서와 같은 대표적인 알고리즘 계열로 구현됩니다. 이 두 단계를 거쳐 만들어지는 구조가 바로 추상 구문 트리이며, 이후의 의미 분석(semantic analysis)이나 코드 생성 단계는 이 트리를 입력으로 삼아 진행됩니다. 최근에는 문법 오류에 강건한 오류 복구(error recovery) 기법이나, 불완전한 코드도 처리할 수 있는 파서 설계도 함께 논의되는 경우가 많습니다.

주의할 점

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