상향식 파싱
1. 개요
1. 개요
상향식 파싱은 구문 분석의 한 방법으로, 입력 문자열의 가장 작은 구성 요소인 단말 기호부터 시작하여 점차 큰 단위인 비단말 기호로 결합해 최종 파스 트리를 구성하는 방식이다. 이 방식은 좌측 유도 과정의 역순으로 동작하며, 컴파일러의 구문 분석 단계에서 널리 사용된다.
주요 알고리즘으로는 LR 파서, SLR 파서, LALR 파서 등이 있다. 이들은 하향식 파싱에 비해 문법에 대한 제약이 적어 더 넓은 범위의 문맥 자유 문법을 처리할 수 있는 장점이 있다. 이러한 특징 덕분에 Yacc나 Bison과 같은 파서 생성기에서 주로 상향식 파싱 기법을 채택한다.
상향식 파싱은 컴파일러 외에도 자연어 처리나 구조적 데이터 처리 등 다양한 분야에서 응용된다. 그러나 파싱 테이블을 구성하는 과정이 복잡하고, 실제 구현이 하향식 파싱에 비해 더 어려울 수 있다는 단점도 있다.
2. 상향식 파싱의 원리
2. 상향식 파싱의 원리
상향식 파싱은 구문 분석에서 널리 사용되는 접근법이다. 이 방식은 입력 문자열을 가장 작은 단위인 단말 기호부터 시작하여, 문법 규칙을 적용해 점차 더 큰 단위의 비단말 기호로 결합해 나간다. 이 과정은 최종적으로 문법의 시작 기호에 도달하고, 완전한 파스 트리를 구성하는 것으로 끝난다. 이는 하향식 파싱이 시작 기호에서 출발해 단말 기호를 향해 나아가는 것과 정반대의 방향성을 가진다.
구체적으로, 상향식 파서는 입력 문자열의 왼쪽 끝부터 읽어가며 토큰들을 스택에 쌓는다. 스택의 상단 부분이 문법의 어떤 생성 규칙의 우변과 일치하면, 그 부분을 해당 규칙의 좌변 비단말 기호로 교체하는 환원 작업을 수행한다. 이 환원 과정을 반복하여 스택에 시작 기호만 남게 되면 파싱이 성공한 것이다. 이 전체 과정은 좌측 유도 과정의 역순으로 진행된다고 설명할 수 있다.
상향식 파싱의 핵심은 언제 환원을 수행할지 결정하는 것이다. 이를 위해 파서는 현재의 입력 토큰과 스택 상태를 보고 파싱 테이블을 참조하여 다음 동작(이동 또는 환원)을 결정한다. LR 파서 계열의 알고리즘은 이러한 결정을 체계적으로 내리기 위한 강력한 방법을 제공한다. 이 방식은 문맥 자유 문법에 대한 제약이 상대적으로 적어 많은 프로그래밍 언어의 구문을 처리하는 데 적합하다.
이러한 원리 덕분에 상향식 파싱은 컴파일러의 구문 분석기 구현에 매우 중요한 역할을 한다. 또한, 자연어 처리나 구조적 데이터를 처리하는 다양한 응용 분야에서도 그 원리가 활용된다.
3. 주요 알고리즘
3. 주요 알고리즘
3.1. LR 파서
3.1. LR 파서
LR 파서는 상향식 파싱을 구현하는 가장 일반적이고 강력한 파서의 한 종류이다. 이는 입력 문자열을 왼쪽에서 오른쪽으로 읽으며, 가장 우측의 유도 과정을 역으로 추적하는 방식으로 동작한다. LR 파서의 이름은 Left-to-right scan과 Rightmost derivation을 역순으로 수행하는 특징에서 유래한다. 이 파서는 문맥 자유 문법의 광범위한 부분 집합을 처리할 수 있어, 컴파일러의 구문 분석 단계에서 널리 사용된다.
LR 파서의 핵심 구성 요소는 파싱 테이블과 스택이다. 파싱 테이블은 유한 상태 기계의 상태 전이와 파싱 액션을 결정하는 규칙으로 구성되며, 스택은 현재의 파싱 상태와 기호를 저장한다. 파서는 현재 상태와 다음 입력 기호를 보고 파싱 테이블을 참조하여 시프트, 리듀스, 승인, 에러 중 하나의 액션을 수행한다. 시프트는 입력 기호를 스택에 넣고 상태를 전이하며, 리듀스는 문법 규칙에 따라 스택 상단의 기호들을 하나의 비단말 기호로 치환한다.
LR 파서는 사용하는 파싱 테이블 생성 방법에 따라 여러 종류로 나뉜다. 가장 기본적인 형태는 LR(0) 파서이며, 여기에 LOOKAHEAD 심볼을 1개 사용하여 충돌을 해결한 것이 SLR 파서이다. 더욱 정교하게 LR(1) 아이템을 사용하여 테이블을 생성하면 LR(1) 파서가 되며, 이의 상태를 합병하여 크기를 줄인 실용적인 변종이 LALR 파서이다. LALR 파서는 대부분의 프로그래밍 언어 문법을 처리할 수 있으며, Yacc나 Bison과 같은 파서 생성기에서 표준으로 채택되고 있다.
3.2. SLR 파서
3.2. SLR 파서
SLR 파서는 상향식 파싱을 수행하는 파서의 한 종류로, LR 파서의 가장 간단한 형태이다. SLR은 Simple LR의 약자로, LR 파서의 기본 원리를 따르면서도 구문 분석 테이블을 구성하는 방법이 단순화된 특징을 가진다. 이 파서는 컴파일러의 구문 분석 단계에서 널리 사용되는 알고리즘 중 하나이다.
SLR 파서의 핵심은 LR(0) 항목 집합을 기반으로 구문 분석 테이블을 생성하는 데 있다. 이 과정에서 FOLLOW 집합 정보를 활용하여 환원 동작을 결정함으로써 LR(0) 파서보다 더 넓은 범위의 문맥 자유 문법을 처리할 수 있다. 그러나 이 FOLLOW 집합을 사용하는 방식이 비교적 단순하기 때문에 LALR 파서나 표준 LR 파서에 비해 허용하는 문법의 범위는 제한적이다.
SLR 파서의 동작은 일반적인 LR 파싱 알고리즘을 따른다. 파서는 상태 전이 테이블과 동작 테이블을 참조하며, 입력 버퍼에서 기호를 읽어 스택에 쌓는다. 스택의 상단 상태와 현재 입력 기호를 보고 테이블을 조회하여 시프트, 환원, 수용, 오류 중 하나의 동작을 수행한다. 이때 환원 동작을 결정할 때 해당 생성 규칙 좌측 비단말 기호의 FOLLOW 집합을 확인한다.
SLR 파서는 구현이 상대적으로 간단하면서도 하향식 파싱 방식인 LL 파서보다 훨씬 더 많은 종류의 문법을 처리할 수 있다는 장점이 있다. 이로 인해 초기 컴파일러 생성기인 Yacc와 그 후계자들에서도 기본적인 파싱 방법론으로 채택되곤 했다. 그러나 모호성이 없고 충돌이 발생하지 않는 문법에 대해서만 정상적으로 동작하며, 보다 복잡한 문법을 처리하기 위해서는 LALR이나 표준 LR 파서와 같은 더 발전된 알고리즘이 필요하다.
3.3. LALR 파서
3.3. LALR 파서
LALR 파서는 상향식 파싱에서 널리 사용되는 LR 파서의 한 종류로, Look-Ahead LR 파서의 약자이다. 이는 SLR 파서의 단순함과 정식 LR 파서의 강력함 사이의 균형을 잡은 효율적인 파싱 알고리즘으로 평가받는다. LALR 파서의 핵심 아이디어는 LR 파서가 생성하는 많은 수의 상태를, Lookahead 심볼 집합만을 기준으로 합쳐서 상태 수를 줄이는 데 있다. 이 과정을 통해 파싱 테이블의 크기를 크게 감소시킬 수 있으며, 이는 실제 컴파일러 구현에서 메모리 효율성과 실용성을 높이는 데 결정적인 역할을 한다.
LALR 파서의 구동 원리는 기본적인 LR 파서와 동일하다. 파서는 스택과 입력 버퍼를 사용하며, Shift와 Reduce라는 두 가지 기본 동작을 조합하여 입력 문자열을 분석한다. LALR 파서의 독특한 점은 파싱 테이블을 구성할 때, LR(1) 아이템의 상태 중 핵심(core)이 동일하고 Lookahead 심볼만 다른 상태들을 하나로 병합한다는 것이다. 이 병합 과정은 LR(0) 아이템의 상태 수준에서는 SLR 파서와 동일한 수의 상태를 가지게 하지만, 각 상태에 첨부된 Lookahead 정보는 더 정교하여 SLR 파서보다 더 넓은 범위의 문법을 처리할 수 있게 해준다.
LALR 파서는 실용적인 측면에서 큰 장점을 지닌다. 대표적인 컴파일러 생성기인 Yacc나 그 현대적 후계자인 Bison이 바로 LALR 파싱 테이블을 생성하는 도구이다. 이는 LALR 파서가 대부분의 프로그래밍 언어 문법을 처리하는 데 충분한 능력을 가지면서도, 파싱 테이블의 크기가 상대적으로 작아 구현 및 관리가 용이하기 때문이다. 따라서 C 언어, 파스칼, 자바와 같은 많은 프로그래밍 언어의 구문 분석기에 채택되어 왔다.
그러나 LALR 파서에도 한계는 존재한다. 상태 병합 과정에서 때때로 Reduce-Reduce 충돌이나 Shift-Reduce 충돌이 발생할 수 있으며, 이는 원본 LR(1) 문법에서는 충돌이 없었더라도 발생할 수 있다. 이로 인해 모든 문맥 자유 문법을 처리할 수는 없다. 또한, 파싱 테이블 생성 알고리즘이 SLR 파서보다 복잡하여, 파서 생성기 도구에 의존하는 경우가 많다. 그럼에도 불구하고 효율성과 표현력의 균형으로 인해, 상향식 파싱을 기반으로 한 실제 소프트웨어 도구에서 가장 보편적으로 사용되는 파서 유형이다.
4. 하향식 파싱과의 비교
4. 하향식 파싱과의 비교
상향식 파싱은 구문 분석의 두 주요 접근법 중 하나로, 하향식 파싱과 근본적으로 다른 방향성을 가진다. 하향식 파싱이 최상위 비단말 기호에서 시작해 단말 기호를 향해 파싱 트리를 확장해 나가는 반면, 상향식 파싱은 입력된 단말 기호들을 읽어가며 점차 큰 규칙으로 축약하여 최종적으로 시작 기호를 도출한다. 이는 좌측 유도 과정의 역순으로 진행된다고 볼 수 있다.
두 방식의 가장 큰 차이는 파싱의 시작점과 방향에 있다. 하향식 파서는 주로 재귀 하향 파서나 LL 파서를 사용하며, 예측 기반으로 동작하여 주어진 문법에서 어떤 규칙을 적용할지 미리 결정한다. 반면 상향식 파서는 LR 파서 계열이 대표적이며, 이동-감축 방식을 통해 입력을 스택에 쌓아가며 문법 규칙의 우변을 발견하면 그에 대응하는 좌변의 비단말 기호로 감축한다. 이 과정은 하향식 파싱보다 일반적으로 더 강력하여 더 넓은 범위의 문맥 자유 문법을 처리할 수 있다.
실용적인 측면에서, 상향식 파서는 하향식 파서에 비해 구현이 더 복잡하고 이해하기 어려울 수 있다. 그러나 그 대가로 LR 파서나 LALR 파서와 같은 알고리즘은 구문 분석기 생성기를 통해 자동 생성하기에 매우 적합하며, 생성된 파서의 효율성과 신뢰성이 높다. 이는 컴파일러와 같은 도구를 구축할 때 큰 장점으로 작용한다. 반면, 하향식 파서는 직관적인 구조 덕분에 수동으로 구현하거나 디버깅하기가 상대적으로 용이하다.
5. 장단점
5. 장단점
상향식 파싱은 구문 분석에서 널리 사용되는 방식으로, 하향식 파싱과 비교하여 뚜렷한 장점과 단점을 지닌다.
주요 장점은 문법에 대한 제약이 상대적으로 적다는 점이다. 하향식 파싱은 재귀 하향 파서를 사용할 경우 좌재귀 문법을 처리하기 어려운 반면, 상향식 파싱은 LR 파서와 같은 알고리즘을 통해 좌재귀를 포함한 더 넓은 범위의 문맥 자유 문법을 처리할 수 있다. 이는 프로그래밍 언어의 복잡한 구문을 정의하는 데 유연성을 제공한다. 또한, 파싱 과정에서 입력 문자열을 처음부터 끝까지 한 번만 스캔하며 구문 트리를 구성하기 때문에 일반적으로 효율적이며, 구문 오류를 조기에 발견할 수 있다는 장점도 있다.
반면, 단점으로는 구현의 복잡성이 높다는 점이 꼽힌다. LR 파서나 LALR 파서와 같은 대표적인 상향식 파서를 구현하려면 복잡한 파싱 테이블을 생성해야 하며, 이 과정은 수동으로 수행하기 어렵고 주로 파서 생성기에 의존한다. 또한, 생성된 구문 트리의 구조가 하향식 파싱에 비해 직관적이지 않을 수 있으며, 파싱 과정 자체를 추적하고 디버깅하기가 더 어려울 수 있다.
요약하면, 상향식 파싱은 강력하고 효율적인 구문 분석이 가능하여 컴파일러 제작에 널리 채용되지만, 그 구현과 이해에는 더 높은 진입 장벽이 존재한다.
6. 응용 분야
6. 응용 분야
상향식 파싱은 주로 컴파일러의 구문 분석 단계에서 핵심적으로 활용된다. 프로그래밍 언어로 작성된 소스 코드는 어휘 분석을 통해 토큰 시퀀스로 변환된 후, 상향식 파서에 의해 구문 트리로 구조화된다. 이 과정에서 LR 파서나 그 변형인 LALR 파서가 널리 사용되며, C나 자바와 같은 많은 현대 프로그래밍 언어의 컴파일러 구현에 채택되어 문법의 정확성을 검증한다.
자연어 처리 분야에서도 상향식 접근법이 적용된다. 문장을 구성하는 개별 단어(형태소)로부터 시작해 구나 절 등의 더 큰 문법적 단위를 점진적으로 결합하여 구문 분석을 수행한다. 이를 통해 문장의 구조적 의미를 추출하거나 기계 번역, 질의 응답 시스템 등의 기초 자료로 활용한다.
또한, XML이나 JSON과 같은 구조적 데이터를 처리하는 파서를 구현할 때 상향식 방식을 사용할 수 있다. 데이터의 기본 요소(태그, 키-값 쌍)부터 분석을 시작해 최종적인 문서 객체 모델 트리를 구성하는 데 적합하다. 이는 웹 스크래핑, 데이터 직렬화, 설정 파일 처리 등 다양한 소프트웨어 개발 영역에서 응용된다.
