하향식 파싱

하향식 파싱의 주요 장점은 구현의 용이성과 직관성에 있다. 이 방식은 주어진 문법의 최상위 시작 기호에서 출발하여 점차 하위 구성 요소로 내려가며 파싱 트리를 구축하는데, 이 과정이 사람이 문장의 구조를 이해하는 방식과 유사하여 개념을 이해하고 파서를 설계하기가 비교적 쉽다. 특히 재귀 하강 파서는 각 문법 규칙을 하나의 재귀 함수로 직접 매핑하여 구현할 수 있어, 수동으로 파서를 작성해야 하는 경우에 매우 적합한 모델을 제공한다.

또한, LL 파서와 같은 일부 하향식 파싱 알고리즘은 입력을 한 번만 훑는(one-pass) 방식으로 동작하며, 백트래킹이 필요 없는 경우에는 분석 과정이 매우 효율적일 수 있다. 이는 파싱 테이블을 미리 구축하여 다음에 적용할 규칙을 예측하는 예측 파서의 동작 원리와도 연결된다. 이러한 특성 덕분에 하향식 파싱은 컴파일러 구축 교육이나 프로토타이핑, 그리고 구문 강조 또는 간단한 도메인 특화 언어 처리와 같은 응용 분야에서 널리 활용된다.

하향식 파싱은 좌측 재귀 문법을 처리하는 데 취약하다는 근본적인 단점을 가진다. 좌측 재귀는 문법 규칙이 자신을 다시 참조하는 형태로, 하향식 파서가 같은 규칙을 무한히 적용하려 하여 스택 오버플로나 무한 루프에 빠질 수 있다. 이를 해결하려면 문법을 변환해야 하는데, 이 과정이 번거롭고 변환된 문법이 원래 구조를 반영하지 못할 수 있다.

또한, 일부 하향식 파서는 결정적이지 않은 문법을 처리할 때 백트래킹을 필요로 한다. 이는 파싱 과정에서 잘못된 규칙을 선택했을 때 이전 상태로 돌아가 다른 규칙을 시도하는 방식으로, 입력 문자열을 여러 번 재검사하게 만들어 성능을 저하시킬 수 있다. 특히 복잡한 문법에서는 이러한 비효율성이 두드러진다.

하향식 접근법은 일반적으로 상향식 파싱에 비해 문법의 제약이 더 많다. 예를 들어, LL 파서는 LL(k) 문법과 같이 미리 정해진 개수(k)의 토큰만을 미리 보는 문법에만 적용 가능하다. 이는 상대적으로 표현력이 제한적일 수 있음을 의미한다. 또한, 구문 분석 트리를 구축하는 과정에서 하위 구조에 대한 정보가 부족할 수 있어, 특정 구문 오류를 일찍 감지하기 어려울 수 있다.

재귀 하강 파서는 하향식 파싱의 가장 대표적이고 직접적인 구현 방식이다. 이 방법은 문맥 자유 문법의 각 비단말 기호에 대해 하나의 재귀 함수를 정의하여, 그 함수가 해당 비단말 기호로부터 유도될 수 있는 문자열을 처리하도록 설계한다. 파싱 과정은 최상위 시작 기호에 해당하는 함수를 호출하는 것으로 시작되며, 이 함수는 필요에 따라 다른 비단말 기호에 대한 함수를 재귀적으로 호출하면서 입력 토큰을 좌측에서 우측으로 소비해 나간다.

이 방식의 주요 특징은 소스 코드와 문법 규칙 간의 직접적인 대응 관계에 있다. 각 문법 규칙이 하나의 함수로 매핑되기 때문에, 파서의 논리 구조를 이해하고 디버깅하기가 비교적 용이하다. 또한, 백트래킹을 사용하는 일반적인 재귀 하강 파서 외에도, 예측 분석을 통해 다음 입력 토큰을 미리 살펴보고 사용할 규칙을 결정하는 예측적 재귀 하강 파서로 구현될 수 있다. 후자의 경우 LL(1) 문법과 같이 충분히 예측 가능한 문법에서 매우 효율적으로 동작한다.

재귀 하강 파서는 구현이 직관적이고 구조가 명확하여 교육 목적이나 소규모 언어 처리 도구를 개발할 때 널리 사용된다. 그러나 이 방법은 문법에 좌측 재귀가 존재할 경우 함수 호출이 무한 루프에 빠질 수 있어, 문법을 변환하거나 별도의 메커니즘을 도입해야 하는 제약이 있다. 또한, 모든 가능한 유도를 탐색하는 백트래킹 방식은 시간 복잡도 측면에서 비효율을 초래할 수 있다는 단점도 있다.

LL 파서는 하향식 파싱의 주요 알고리즘 중 하나로, 입력 문자열을 좌측에서 우측으로 읽어가며 좌측 유도 방식으로 파싱 트리를 구축한다. LL은 'Left-to-right, Leftmost derivation'의 약자로, 이 과정을 명확히 나타낸다. 이 방식은 재귀 하강 파서의 일반적인 형태로 볼 수 있으며, 예측 파서와도 밀접한 관련이 있다. LL 파서는 주어진 문맥 자유 문법에 대해 미리 구축된 파싱 테이블을 사용하여 결정론적으로 동작한다.

LL 파서는 일반적으로 LL(k)로 분류되며, 여기서 k는 결정을 내리기 위해 미리 살펴보는 토큰의 개수를 의미한다. 가장 일반적인 형태는 LL(1) 파서로, 다음 토큰 하나만을 미리 보아도 파싱이 가능한 문법을 사용한다. LL(1) 파서는 FIRST 집합과 FOLLOW 집합을 계산하여 파싱 테이블을 구성하며, 이를 통해 구문 분석기가 효율적으로 동작할 수 있다.

이 파서의 주요 장점은 구현이 직관적이고, 재귀 하강 파싱과의 호환성이 높아 수동으로 파서를 작성하기에 적합하다는 점이다. 또한 결정론적 방식으로 동작하기 때문에 백트래킹이 필요 없어 파싱 속도가 비교적 빠르다. 그러나 LL 파서는 좌측 재귀를 포함하는 문법을 직접 처리할 수 없다는 근본적인 단점을 지닌다. 또한 모든 문맥 자유 언어를 표현할 수 없어, 사용 가능한 문법이 제한적이라는 한계가 있다.

LL 파싱 기법은 간단한 프로그래밍 언어의 컴파일러나 구문 분석 도구를 구현하는 데 널리 사용되어 왔다. ANTLR과 같은 파서 생성기는 LL 파싱의 변형을 사용하여 강력한 파싱 능력을 제공한다.

예측 파서는 하향식 파싱의 한 유형으로, 파싱 테이블을 사용하여 다음에 적용할 문법 규칙을 미리 결정하는 방식으로 동작한다. 이는 백트래킹을 필요로 하지 않아 효율적이며, 주로 LL 파서와 연관되어 사용된다. 예측 파서는 입력 문자열을 좌측에서 우측으로 읽으며(좌측 유도), 주어진 문맥 자유 문법에 따라 파싱 트리의 최상위 노드에서 시작하여 하위 노드로 확장해 나간다.

예측 파서의 핵심은 미리 구축된 파싱 테이블이다. 이 테이블은 현재 논터미널 기호와 입력 스트림의 다음 터미널 기호(lookahead 토큰)를 조합하여 적용해야 할 유일한 생성 규칙을 지시한다. 이 덕분에 파서는 결정론적으로 동작하며, 여러 규칙 중에서 선택하기 위해 시행착오를 겪지 않는다. 예측 파서는 LL(1) 파서가 대표적이며, 여기서 숫자 '1'은 결정을 내리기 위해 미리 보는(lookahead) 토큰의 개수를 의미한다.

예측 파서는 컴파일러의 프론트엔드나 구문 분석기를 구현할 때 널리 사용되며, 그 직관성과 효율성 덕분에 많은 프로그래밍 언어의 구문 분석에 채택된다. 그러나 이 방식은 문법이 LL(1) 조건을 만족해야만 파싱 테이블을 충돌 없이 구성할 수 있다는 제약이 있다. 문법에 모호성이나 좌측 인자가 존재하는 경우, 문법을 변환하거나 더 많은 lookahead를 사용하는 LL(k) 파서를 고려해야 한다.

상향식 파싱은 하향식 파싱과 대비되는 구문 분석 기법으로, 파싱 트리를 구축하는 방향이 다르다. 하향식 파싱이 최상위 시작 기호에서 시작해 입력 토큰을 맞춰나가는 방식이라면, 상향식 파싱은 입력 토큰(말단 노드)에서 시작해 점차 규칙을 적용하여 비단말 기호로 축소해 나가며, 최종적으로 시작 기호로 도달하는 방식을 취한다. 즉, 트리를 잎(하위)에서 뿌리(상위) 방향으로 구성한다. 이 방식은 LR 파서나 LALR 파서와 같은 자동 파서 생성기에서 널리 사용되는 기반이 된다.

상향식 파싱의 대표적인 알고리즘은 LR 파싱으로, 입력 문자열을 좌측에서 우측으로 스캔하며 가장 우측 파생을 사용하는 방식이다. 이 과정은 스택을 활용하여 진행되며, 파서는 스택의 내용과 남은 입력을 보고 이동 또는 축약이라는 두 가지 기본 동작을 결정한다. 이동은 입력 토큰을 스택에 쌓는 것이고, 축약은 스택 상단의 일련의 심볼들이 어떤 문법 규칙의 우변과 일치할 때, 그 규칙의 좌변 비단말 기호로 바꾸는 것이다. 이러한 과정을 반복하여 스택에 최종적으로 시작 기호만 남게 되면 파싱이 성공한 것으로 본다.

하향식 파싱과 비교했을 때, 상향식 파싱은 일반적으로 더 넓은 범위의 문맥 자유 문법을 처리할 수 있다는 장점이 있다. 특히 하향식 파서가 처리하기 어려운 좌측 재귀 문법을 자연스럽게 처리할 수 있다. 또한, 백트래킹이 필요 없는 결정적 파싱이 가능하여 효율적이다. 반면, 파싱 테이블의 크기가 커질 수 있고, 파싱 과정이 하향식에 비해 덜 직관적이어서 수동 구현보다는 도구를 통한 자동 생성에 더 적합한 경향이 있다. 두 기법은 각각의 장단점에 따라 컴파일러 설계나 자연어 처리 등 다양한 분야에서 선택적으로 활용된다.