LL 파서

LL 파서(LL parser)는 문맥 자유 문법의 일부를 파싱할 수 있는 하향식 파서이다. LL 파서는 입력 문자열의 왼쪽(Left)에서부터 파싱을 시작하여, 좌측유도(Leftmost derivation) 방식으로 동작한다. LL 파서로 파싱이 가능한 문법은 LL 문법이라고 부른다.

만약 LL 파서가 lookahead에 최대 k개의 토큰(token)을 사용한다면, 그 파서는 LL(k) 파서라고 부른다. LL(k) 파서로 파싱이 가능한 문법은 LL(k) 문법이라고 부른다.

파서의 구조 

LL 파서는 보통 다음과 같은 구조로 이루어져 있다.
 입력 버퍼: 파싱할 문자열을 저장한다.
 스택: 파싱 중인 토큰을 저장하는 데에 사용한다.
 파싱 테이블: 각 토큰에 대해, 어떤 파싱 규칙을 사용해야 하는지를 정리해놓은 표로, 파싱 문법에 따라 결정된다.

스택의 초기 상태에는 가장 위쪽에 시작 문자 S가 들어있고, 그 밑에 스택의 바닥을 표시하는 특수 문자 $가 들어있다. LL 파서에서는 스택에 들어있는 토큰들에 대해, 파싱 테이블을 이용하여 토큰을 다른 토큰들로 바꾸거나, 혹은 파싱이 완료된 문자를 출력 스트림에 출력한다.

예제 

다음과 같은 문법에 대해서:
 S → F
 S → ( S + F )
 F → a

( a + a )라는 문자열을 LL(1) 파서 방식으로 파싱하는 과정은 다음과 같다. 우선 해당 문법에 대한 파싱 테이블을 다음과 같이 준비한다.

스택의 초기 상태는 다음과 같다. (왼쪽이 가장 위, 오른쪽이 가장 아래의 상황)
 S $
이제 스택의 가장 위에 있는 토큰을 확인하고 해당 토큰을 다른 토큰으로 교체하는 작업을 반복한다.

파싱 과정에서 사용한 규칙은 순서대로 2, 1, 3, 3이다. 즉, ( a + a )는 다음과 같이 파싱된다.
 S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

같이 보기 
 LR 파서
 LALR 파서

파싱 알고리즘