LL 파서

정의

LL 파서는 컴퓨터 과학에서 문법 분석기(parser) 의 한 종류로, 입력 문자열을 Left‑to‑right 방식으로 읽으면서 Leftmost(가장 왼쪽) 파생을 생성하는 위‑아래(top‑down) 파싱 기법이다. 일반적으로 “LL(k) 파서”라는 형태로 표현되며, 여기서 ‘k’는 파싱 과정에서 미리 보는 심볼(look‑ahead)의 최대 개수를 의미한다. ‘LL(*)’와 같이 가변적인 look‑ahead를 허용하는 확장 형태도 존재한다.

구조 및 동작 원리

1. 입력 토큰 스트림: 토크나이저(lexer)가 만든 토큰 시퀀스를 왼쪽부터 순차적으로 읽는다.
2. 파싱 테이블: 비터미널에 대한 *예측 집합(predictive set)*을 미리 계산하여, 현재 토큰과 비터미널 조합에 따라 어느 생산 규칙을 적용할지 결정한다.
3. 재귀 하강(recursive‑descent) 또는 표 기반(table‑driven) 구현 방식이 일반적이며, 전자는 각 비터미널을 함수로 구현하고, 후자는 스택과 파싱 테이블을 이용한다.
4. 파생 단계: 현재 비터미널에 대해 선택된 규칙을 적용하고, 오른쪽에 있는 심볼들을 차례대로 스택에 푸시한다. 스택의 최상위 심볼이 터미널이면 입력 토큰과 일치하는지 검사하고, 일치하면 토큰을 소비한다.

LL(k)와 LL(*)

• LL(1): 가장 널리 사용되는 형태로, 한 개의 look‑ahead 토큰만으로 다음 규칙을 결정한다. 문법이 LL(1) 조건(즉, 각 비터미널마다 FIRST와 FOLLOW 집합이 겹치지 않아야 함)을 만족해야 한다.
• LL(k) (k>1): 두 개 이상의 토큰을 미리 보아 결정한다. 파싱 테이블이 커지고 구현이 복잡해지지만, 더 많은 문법을 처리할 수 있다.
• LL(*): 정적 k값에 제한을 두지 않고, 필요에 따라 임의 길이의 토큰 시퀀스를 검사한다. ANTLR4 같은 현대 파서 생성기가 채택하고 있다.

장점

• 구현이 간단하고, 재귀 하강 방식은 사람이 이해하기 쉬워 교육용으로도 자주 사용된다.
• 오류 회복(error recovery)이 비교적 직관적이며, 구문 오류 위치를 빠르게 찾을 수 있다.
• 예측 파싱(predictive parsing)으로 백트래킹이 필요 없는 효율적인 파싱이 가능하다(특히 LL(1)).

한계

• 좌측 재귀(left‑recursion)를 포함하는 문법을 직접 처리할 수 없으며, 변환이 필요하다.
• 복잡한 문법(예: C++와 같이 전역적인 문맥 의존성이 큰 언어)은 LL 파서로 표현하기 어려워 LALR, GLR 등 다른 파싱 기법이 선호된다.
• LL(k)에서는 k가 커질수록 파싱 테이블이 급격히 커져 메모리 사용량이 증가한다.

주요 구현 및 도구

관련 파싱 기법

• LR 파서(LR(k), LALR, SLR) – 입력을 왼쪽에서 읽고 오른쪽most 파생을 생성하는 아래‑위(bottom‑up) 방식.
• GLR 파서 – Generalized LR, 복수의 파싱 경로를 동시에 탐색해 모호한 문법도 처리 가능.
• PEG (Parsing Expression Grammar) – 입력을 순차적으로 매칭하는 방식으로, 백트래킹을 허용하지만 LL과는 다른 이론적 기초를 갖는다.

역사

• 1970년대 초에 Aho, Sethi, Ullman이 제안한 LL(1) 파서가 최초의 형식화된 위‑아래 파싱 방법으로 소개되었다.
• 이후 LL(k) 개념이 확대되었으며, 1990년대에 LL(*)와 같은 가변 look‑ahead 전략이 연구되었다.
• 2000년대 초 ANTLR(ANother Tool for Language Recognition)의 등장으로 LL 파서 구현이 실무에 널리 퍼졌으며, 현재는 대부분의 DSL(도메인 특화 언어)와 프로그래밍 언어 프론트엔드에서 사용된다.

참고문헌

1. Aho, A. V., Sethi, R., & Ullman, J. D. (1986). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison‑Wesley. – LL 파싱 기본 이론.
2. Parr, T. (2013). The Definitive ANTLR 4 Reference. Pragmatic Bookshelf. – LL(*) 파서 구현.
3. Grune, D., & Jacobs, C. J. H. (2008). Parsing Techniques – A Practical Guide. Springer. – 다양한 파싱 알고리즘 비교.

LL 파서는 위‑아래 파싱 기술 중 하나로, 문법이 LL(k) 조건을 만족한다면 간결하고 빠른 구문 분석을 제공한다. 다만 복잡한 언어 구조를 다루기 위해서는 다른 파싱 기법과의 적절한 조합이 필요하다.