LL 파서(LL parser)는 컴퓨터 과학, 특히 컴파일러 설계 분야에서 사용되는 하향식(top-down) 파서의 한 종류이다. 문맥 자유 문법(context-free grammar)의 일부를 파싱할 수 있으며, 입력 문자열의 왼쪽(Left)에서부터 파싱을 시작하여 좌측유도(Leftmost derivation) 방식으로 동작한다. LL 파서로 파싱이 가능한 문법을 LL 문법이라고 부른다.
명칭의 의미
"LL"이라는 명칭은 두 가지 특성을 나타낸다. 첫 번째 L은 입력 문자열을 왼쪽에서 오른쪽으로(Left to right) 스캔한다는 의미이고, 두 번째 L은 좌측유도(Leftmost derivation)를 수행한다는 의미이다. 파서가 lookahead(미리 내다보기)에 최대 k개의 토큰을 사용한다면 그 파서를 LL(k) 파서라고 부르며, LL(k) 파서로 파싱 가능한 문법을 LL(k) 문법이라고 부른다. 가장 널리 사용되는 형태는 한 개의 토큰만을 내다보는 LL(1) 파서이다.
구조와 동작 원리
LL 파서는 일반적으로 다음과 같은 구성 요소로 이루어진다.
- 입력 버퍼: 파싱할 문자열을 저장한다.
- 스택: 파싱 중인 토큰을 저장하는 데 사용한다.
- 파싱 테이블: 각 토큰에 대해 어떤 파싱 규칙을 사용해야 하는지를 정리한 표로, 파싱 문법에 따라 결정된다.
스택의 초기 상태에는 가장 위쪽에 시작 문자 S가 들어 있고, 그 아래에 스택의 바닥을 표시하는 특수 문자 $가 들어 있다. LL 파서는 스택에 있는 토큰에 대해 파싱 테이블을 이용하여 토큰을 다른 토큰들로 교체하거나, 파싱이 완료된 문자를 출력 스트림에 출력하는 방식으로 동작한다. 스택의 최상단이 비단말(non-terminal) 기호인 경우 파싱 테이블을 참조하여 해당 규칙을 적용하고, 최상단이 단말(terminal) 기호인 경우 입력 스트림의 기호와 비교하여 일치하면 둘 다 제거한다. 입력과 스택이 모두 $에 도달하면 파싱이 성공적으로 완료된 것으로 간주한다.
LL(1) 파싱 테이블의 구성
LL(1) 파싱 테이블을 구성하기 위해서는 FIRST 집합과 FOLLOW 집합을 계산해야 한다. FIRST 집합은 특정 문자열로부터 유도될 수 있는 문자열의 첫 번째 위치에 나타날 수 있는 단말 기호들의 집합이며, FOLLOW 집합은 특정 비단말 기호 뒤에 나타날 수 있는 단말 기호들의 집합이다. 파싱 테이블의 각 셀에는 해당 비단말과 입력 기호 조합에 적용할 문법 규칙이 최대 하나만 존재해야 하며, 모든 셀에 규칙이 하나 이하로 존재할 때 그 문법을 LL(1) 문법이라고 부른다.
LL(1) 충돌과 해결
LL(1) 문법이 되기 위해서는 두 가지 유형의 충돌이 발생하지 않아야 한다. FIRST/FIRST 충돌은 동일한 비단말에 대한 서로 다른 두 규칙의 FIRST 집합이 교집합을 가질 때 발생하며, FIRST/FOLLOW 충돌은 어떤 규칙의 FIRST 집합과 FOLLOW 집합이 겹칠 때 발생한다. 이러한 충돌은 좌인수분해(left factoring), 치환(substitution), 좌재귀 제거(left recursion removal) 등의 기법을 통해 해결할 수 있다. 특히 좌재귀(left recursion)는 LL 파서에서 FIRST/FIRST 충돌을 유발하는 대표적인 원인으로 알려져 있다.
특징과 한계
LL 파서는 문법 규칙과 lookahead 정보를 바탕으로 결정적으로 동작할 수 있어 백트래킹 없이 파싱이 가능하다는 장점이 있다. 또한 재귀 하강 파서(recursive descent parser)로 구현하기 쉬워 많은 프로그래밍 언어가 LL(1) 문법에 맞게 설계되기도 한다. 그러나 LL 파서는 모든 문맥 자유 언어를 인식할 수는 없다. LL(k) 언어의 집합은 LL(k+1) 언어의 집합에 포함되며, 모든 k에 대해 LL(k) 파서로 인식할 수 없는 문맥 자유 언어가 존재한다. LL(1) 언어는 LR(1) 언어의 진부분집합으로 알려져 있다.
LL(k) 문법은 1969년 Richard E. Stearns와 P. M. Lewis에 의해 소개된 것으로 알려져 있다. LL 파서는 테이블 기반 방식과 재귀 하강 방식으로 구현될 수 있으며, ANTLR과 같은 파서 생성기에서도 LL 계열의 파싱 전략이 사용된다.
