LL 파서

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

파서의 구조[편집]

LL 파서는 보통 다음과 같은 구조로 이루어져 있다.

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

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

예제[편집]

다음과 같은 문법에 대해서:

  1. S → F
  2. S → ( S + F )
  3. 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 )

같이 보기[편집]