파서

어휘 분석기는 파서의 첫 번째 단계를 담당하는 구성 요소로, 소스 코드나 입력 문자열을 읽어 의미 있는 최소 단위인 토큰으로 분해하는 과정을 수행한다. 이 과정을 어휘 분석 또는 스캐닝이라고 부른다. 어휘 분석기는 연속된 문자들로 이루어진 원시 입력을 스캔하며, 공백 문자나 주석과 같은 불필요한 요소를 제거하고, 언어의 키워드, 식별자, 리터럴, 연산자 등을 인식하여 토큰 스트림을 생성한다. 이렇게 생성된 토큰 스트림은 이후 구문 분석기로 전달되어 문법적 구조를 분석하는 데 사용된다.

어휘 분석기의 핵심 작업은 정규 표현식으로 정의된 패턴을 사용하여 입력을 토큰화하는 것이다. 예를 들어, 프로그래밍 언어에서 정수 리터럴은 연속된 숫자로, 식별자는 문자로 시작하는 문자와 숫자의 조합으로 패턴이 정의된다. 어휘 분석기는 이러한 패턴을 바탕으로 입력을 스캔하며, 가장 긴 일치 규칙을 적용해 토큰을 결정한다. 이 과정은 유한 상태 기계를 통해 효율적으로 구현되는 경우가 많다.

컴파일러나 인터프리터와 같은 언어 처리 시스템에서 어휘 분석기는 구문 분석기와 분리되어 설계된다. 이는 모듈성을 높이고 유지보수를 용이하게 한다. 어휘 분석기를 생성하는 도구로는 Lex나 Flex와 같은 파서 생성기가 널리 사용되며, 이러한 도구들은 정규 표현식으로 작성된 규칙 명세를 입력받아 해당 언어로 된 어휘 분석기 소스 코드를 자동으로 생성해준다.

구문 분석기는 어휘 분석기가 생성한 토큰의 일련을 입력으로 받아, 주어진 형식 문법에 따라 그 구조를 분석하는 컴퓨터 프로그램 또는 소프트웨어 컴포넌트이다. 이 과정에서 토큰들의 배열이 문법에 맞는지 검증하고, 그 결과를 파스 트리나 추상 구문 트리와 같은 계층적 자료 구조로 변환한다. 구문 분석기는 컴파일러나 인터프리터의 핵심 구성 요소로서, 프로그래밍 언어의 소스 코드를 이해 가능한 구조로 분해하는 역할을 한다.

구문 분석 방식에 따라 크게 하향식 구문 분석과 상향식 구문 분석으로 분류된다. 하향식 파서는 최상위 문법 규칙에서 시작하여 점차 하위 규칙으로 내려가며 입력을 분석하는 반면, 상향식 파서는 입력 토큰을 점차 축약하여 최상위 문법 규칙을 도출해낸다. 또한, 구문 분석기를 구현하는 방식에 따라 직접 코드를 작성하는 수동 파서와 문법 규칙을 기술하면 자동으로 파서 코드를 생성해주는 파서 생성기를 이용하는 방식으로 나눌 수 있다.

구문 분석기의 응용 분야는 매우 다양하다. 전통적으로는 C나 자바 같은 프로그래밍 언어를 처리하는 컴파일러 설계의 핵심이다. 또한, HTML이나 XML 같은 마크업 언어, JSON이나 YAML 같은 데이터 직렬화 형식을 읽고 쓰는 라이브러리, 그리고 자연어 처리 시스템에서 문장의 구문 구조를 분석하는 데에도 필수적으로 사용된다.

하향식 파서는 구문 분석을 수행하는 방식 중 하나로, 구문 트리의 루트 노드에서 시작하여 아래쪽으로, 즉 말단 노드 방향으로 분석을 진행하는 방식을 말한다. 이 방식은 주어진 문법을 바탕으로 입력 문자열을 생성해 나가는 과정을 시뮬레이션한다고 볼 수 있다. 하향식 파서는 일반적으로 재귀 하강 파서의 형태로 구현되며, 프로그래밍 언어의 문법 규칙이 재귀적으로 정의된 경우에 적합하다.

하향식 파서의 대표적인 알고리즘으로는 LL 파서가 있다. LL 파서는 입력을 왼쪽에서 오른쪽으로 읽으며, 가장 왼쪽 유도를 생성하는 방식으로 동작한다. 이 알고리즘은 예측 분석 테이블을 사용하여 어떤 생성 규칙을 적용해야 할지 결정하며, LL(1)과 같이 미리 볼 토큰의 개수에 따라 여러 종류로 분류된다. 이러한 파서는 C 언어나 Pascal과 같은 많은 전통적인 프로그래밍 언어의 구문 분석에 사용되어 왔다.

하향식 파서의 주요 장점은 구현이 비교적 직관적이고 이해하기 쉽다는 점이다. 문법 규칙이 프로그래밍 언어의 함수 구조에 직접적으로 매핑될 수 있어 수동으로 파서를 작성하기에 용이하다. 그러나 단점으로는 좌재귀 문법을 직접 처리할 수 없어 문법을 변형해야 하며, 백트래킹이 발생할 경우 성능이 저하될 수 있다는 점이 있다. 이러한 한계를 극복하기 위해 LL(*) 파서나 ANTLR과 같은 고급 파서 생성기가 개발되었다.

하향식 파싱 기법은 컴파일러의 프론트엔드나 인터프리터뿐만 아니라, SQL 파서, 마크업 언어 파서, 구성 관리 도구의 설정 파일 분석 등 다양한 소프트웨어 도구의 핵심 구성 요소로 널리 응용되고 있다.

상향식 파서는 입력 문자열의 가장 작은 단위인 단말 기호부터 시작하여 점차 큰 구문 단위를 구성해 나가며, 최종적으로 문법의 시작 기호에 도달하는 방식으로 동작하는 구문 분석기이다. 이 방식은 파스 트리의 리프 노드에서부터 루트 노드로 올라가며 트리를 구성한다는 점에서 '상향식'이라는 이름이 붙었다. 이 접근법은 주어진 문맥 자유 문법에 대해 좌파스를 생성하며, 하향식 파서와 비교했을 때 일반적으로 더 넓은 범위의 문법을 처리할 수 있다는 장점을 가진다.

상향식 파싱의 핵심 동작 원리는 감축이다. 파서는 입력된 토큰 시퀀스를 차례대로 읽어들이면서, 읽힌 토큰들이 문법의 어떤 생성 규칙의 우변과 일치하면, 그 일치 부분을 해당 규칙의 좌변 비단말 기호로 교체한다. 이 감축 과정을 스택 기반으로 구현하는 것이 일반적이며, 파서는 스택과 남은 입력 버퍼를 유지하면서 스택의 최상단 부분이 어떤 생성 규칙에 맞아떨어질 때마다 감축을 수행한다. 이 과정은 스택에 시작 기호만 남고 입력 버퍼가 빌 때까지, 또는 파싱 에러가 발생할 때까지 반복된다.

상향식 파서의 가장 대표적인 알고리즘 계열은 LR 파서이다. LR 파서는 입력을 왼쪽에서 오른쪽으로 스캔하며, 가장 오른쪽 유도를 사용한다는 특징을 가진다. LR 파서 계열에는 LR(0), SLR, LALR, LR(1) 등이 있으며, 이들은 사용하는 파싱 테이블의 구성 방식과 복잡도, 그리고 처리 가능한 문법의 범위에서 차이를 보인다. 이 외에도 간단하지만 제한적인 연산자 우선순위 파서나, 더 일반적인 CYK 알고리즘 등도 상향식 파싱에 속한다.

상향식 파서, 특히 LALR 파서는 파서 생성기인 Yacc나 그 현대적 변종들(Bison, ANTLR의 특정 타깃 등)을 통해 자동 생성되는 경우가 많다. 이들은 프로그래머가 문법 규칙을 정의하면 해당 문법에 맞는 파싱 코드를 생성해주어, 컴파일러나 인터프리터를 구현하는 데 널리 사용된다. 상향식 파싱은 문법의 모호성을 잘 처리할 수 있으며, 실용적인 프로그래밍 언어의 대부분을 파싱하는 데 적합한 방법으로 평가받는다.

파서는 컴파일러의 핵심 구성 요소로, 소스 코드의 문법적 구조를 분석하는 역할을 한다. 컴파일러의 전통적인 구조에서 파서는 어휘 분석기가 생성한 토큰 스트림을 입력받아, 해당 프로그래밍 언어의 문법에 맞는 구문 트리나 추상 구문 트리를 생성한다. 이 과정에서 문법 오류를 검출하고 보고하는 것도 파서의 중요한 임무이다.

컴파일러 설계에서 파서의 성능과 효율성은 전체 컴파일 과정의 속도와 안정성에 직접적인 영향을 미친다. 따라서 LL 파서나 LR 파서와 같은 효율적인 구문 분석 알고리즘이 개발되어 왔으며, Yacc나 ANTLR 같은 파서 생성기 도구를 사용하여 문법 규칙으로부터 파서를 자동 생성하는 방식이 널리 사용된다. 파서가 생성한 구문 트리는 이후 의미 분석 및 코드 생성 단계의 기초 자료로 활용된다.

파서는 인터프리터의 핵심 구성 요소로 작동한다. 인터프리터는 소스 코드를 한 줄씩 읽어 즉시 실행하는 프로그램인데, 이 과정에서 소스 코드의 문법적 구조를 이해하기 위해 파서가 필요하다. 인터프리터의 파서는 일반적으로 토큰 시퀀스를 분석하여 추상 구문 트리나 다른 중간 표현을 생성하며, 이 구조를 바탕으로 실행 엔진이 명령을 해석하고 수행한다. 이는 컴파일러가 전체 소스 코드를 한 번에 분석하여 기계어로 변환하는 방식과는 차이가 있다.

인터프리터에 사용되는 파서는 주로 하향식 구문 분석 방식을 따르는 경우가 많다. 특히 LL 파서나 재귀 하강 파서와 같은 알고리즘이 널리 사용되는데, 이는 소스 코드를 실시간으로 분석하고 실행해야 하는 인터프리터의 특성에 적합하기 때문이다. 파이썬, 루비, 자바스크립트와 같은 대표적인 스크립트 언어의 인터프리터는 이러한 파싱 기술을 기반으로 구현되어 있다.

파서는 프로그래밍 언어의 소스 코드 분석 외에도 다양한 형태의 데이터를 처리하는 데 널리 사용된다. 특히 구조화된 텍스트 데이터 형식을 읽고 해석하는 과정에서 핵심적인 역할을 한다.

마크업 언어인 HTML이나 XML 문서를 처리할 때 파서는 태그와 요소의 계층 구조를 분석하여 문서 객체 모델(DOM) 트리를 생성한다. 이는 웹 브라우저가 웹 페이지를 렌더링하거나, 데이터 추출 도구가 특정 정보를 찾는 기반이 된다. 또한 JSON과 YAML과 같은 데이터 직렬화 형식의 파일을 읽어 메모리 내의 자료 구조로 변환하는 작업에도 파서가 필수적으로 사용된다. 이러한 형식들은 설정 파일이나 API 응답 데이터 교환에 흔히 쓰인다.

자연어 처리(NLP) 분야에서도 파서의 개념이 적용된다. 자연어 문장의 구문 분석을 통해 단어들 사이의 문법적 관계(예: 주어, 목적어, 술어)를 파악하고 구문 트리를 구성한다. 이는 기계 번역, 감정 분석, 질의 응답 시스템 등 고급 언어 이해 작업의 중요한 전처리 단계가 된다.

데이터 처리용 파서는 주로 정규 표현식, 유한 상태 기계, 또는 문맥 자유 문법에 기반한 구문 분석 알고리즘을 구현하여 데이터 스트림을 효율적으로 읽고, 구조를 검증하며, 필요한 정보를 추출한다. 이는 데이터베이스 질의어 처리, 로그 파일 분석, 스프레드시트 파일 형식 변환 등 광범위한 데이터 관리 작업을 지원한다.

LL 파서는 하향식 구문 분석 방식을 사용하는 구문 분석기의 한 종류이다. 이 이름은 입력을 왼쪽(Left)에서 오른쪽으로 읽어가며, 좌측 유도(Leftmost derivation) 방식으로 구문 트리를 생성한다는 특징에서 유래한다. LL 파서는 일반적으로 재귀 하강 파서의 형태로 구현되며, 문맥 자유 문법 중 LL(k) 문법에 속하는 언어를 처리할 수 있다. 여기서 k는 구문 분석 결정을 내리기 위해 미리 살펴보는 토큰의 개수를 의미한다.

LL 파서의 핵심 작동 원리는 주어진 비단말 기호와 현재 입력 토큰, 그리고 미리 계산된 파싱 테이블을 기반으로 적용할 생성 규칙을 결정하는 것이다. 파서는 시작 기호에서 출발하여, 스택의 최상단 기호와 입력 토큰을 보고 파싱 테이블을 참조한다. 테이블은 어떤 생성 규칙을 적용해야 하는지, 아니면 오류인지를 지시하며, 이를 따라 파서는 좌측 유도 방식으로 구문 트리를 완성해 나간다.

LL 파서는 그 직관적이고 명확한 구조 덕분에 수동으로 구현하기 비교적 쉬운 편에 속한다. 이는 많은 교육용 컴파일러 및 간단한 프로그래밍 언어의 프로토타입 구현에 널리 사용된다. 또한 ANTLR와 같은 유명한 파서 생성기도 LL 파싱 기술을 기반으로 하고 있다. 그러나 LL 파서가 처리할 수 있는 문법의 범위는 상대적으로 제한적이며, 좌재귀 문법을 직접 처리하지 못하는 등의 한계를 가진다.

LR 파서는 상향식 구문 분석 방식을 사용하는 구문 분석기의 한 종류이다. 이는 입력 문자열을 가장 왼쪽에서부터 오른쪽으로 읽어가며, 주어진 문맥 자유 문법에 맞는 파스 트리를 오른쪽에서부터 역으로 구축하는 방식으로 동작한다. LR 파서는 LL 파서와 달리 더 넓은 범위의 문법을 처리할 수 있으며, 컴파일러와 인터프리터의 핵심 구성 요소로 널리 사용된다.

LR 파서의 핵심은 구문 분석 과정에서의 상태와 결정을 미리 계산하여 구문 분석 테이블에 저장하는 데 있다. 이 테이블은 유한 상태 기계와 유사하게 동작하며, 파서는 현재 상태와 입력 토큰을 보고 테이블을 참조하여 다음 동작을 결정한다. 주요 동작으로는 시프트, 리듀스, 접수, 오류가 있다. 이러한 결정론적 방식 덕분에 LR 파서는 매우 효율적이며 강력한 구문 분석 능력을 가진다.

LR 파서는 그 생성 방식과 처리 능력에 따라 여러 하위 계열로 분류된다. 가장 기본적인 형태는 LR(0) 파서이며, 여기에 lookahead 토큰을 하나 사용하는 SLR 파서와 LALR 파서, 그리고 일반적인 LR(1) 파서가 있다. 이 중에서 LALR 파서는 실용적인 처리 능력과 테이블 크기의 효율성 사이에서 좋은 균형을 이루어, Yacc나 Bison과 같은 대표적인 파서 생성기들이 주로 이 방식을 채택하고 있다.

LR 파싱 알고리즘은 프로그래밍 언어의 정확한 구문을 정의하고 처리하는 데 필수적이다. 이는 복잡한 문법을 가진 언어의 컴파일러를 구현하거나, JSON, XML과 같은 구조화된 데이터 형식을 안정적으로 해석하는 도구의 기반이 된다.