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) 파서 방식으로 파싱하는 과정은 다음과 같다. 우선 해당 문법에 대한 파싱 테이블을 다음과 같이 준비한다.
   (    )   a     + $ S    2         -         1           -       - F   -          -         3           -       -

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

 단계  동작 설명  동작 후 스택  동작 후 입력 문자열 1  초기 상태  S $  ( a + a ) 2  입력 문자열에서 (를 읽고, 스택의 가장 위에 있는 문자 S를 확인한다. 파싱 테이블에 의하여 규칙 2를 적용한다.  ( S + F ) $  ( a + a ) 3  입력 문자열에서 (를 읽고, 스택의 가장 위에 있는 문자 (를 확인한다. 두 문자가 같으므로 삭제한다.  S + F ) $  a + a ) 4  입력 문자열에서 a를 읽고, 스택의 가장 위에 있는 문자 S를 확인한다. 파싱 테이블에 의하여 규칙 1을 적용한다.  F + F ) $  a + a ) 5  입력 문자열에서 a를 읽고, 스택의 가장 위에 있는 문자 F를 확인한다. 파싱 테이블에 의하여 규칙 3을 적용한다.  a + F ) $  a + a ) 6  입력 문자열에서 a를 읽고, 스택의 가장 위에 있는 문자 a를 확인한다. 두 문자가 같으므로 삭제한다.  + F ) $  + a ) 7  입력 문자열에서 +를 읽고, 스택의 가장 위에 있는 문자 +를 확인한다. 두 문자가 같으므로 삭제한다.  F ) $  a ) 8  입력 문자열에서 a를 읽고, 스택의 가장 위에 있는 문자 F를 확인한다. 파싱 테이블에 의하여 규칙 3을 적용한다.  a ) $  a ) 9  입력 문자열에서 a를 읽고, 스택의 가장 위에 있는 문자 a를 확인한다. 두 문자가 같으므로 삭제한다.  ) $  ) 10  입력 문자열에서 )를 읽고, 스택의 가장 위에 있는 문자 )를 확인한다. 두 문자가 같으므로 삭제한다.  $  11  입력 문자열과 스택 모두 빈 것을 확인하고 작동을 종료한다.  $ 

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

 같이 보기 
 LR 파서
 LALR 파서

분류:파싱 알고리즘