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 )

같이 보기

• LR 파서
• LALR 파서