LL 파서

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 파서의 구조
3. 파싱 절차
- 3.1. 기본 동작
4. 예제
5. 파싱 테이블 생성
6. LL(k) 파서
7. 비고
참조

1. 개요

LL 파서는 왼쪽에서 오른쪽으로 입력을 스캔하며, 좌측 유도를 생성하는 하향식 파싱 기법이다. LL 파서는 입력 버퍼, 스택, 파싱 테이블로 구성되며, 스택의 최상단 기호와 입력 버퍼의 현재 기호에 따라 파싱 규칙을 결정한다. LL 파싱은 First Set과 Follow Set을 사용하여 파싱 테이블을 생성하며, FIRST/FIRST 충돌 및 FIRST/FOLLOW 충돌과 같은 충돌을 해결해야 한다. LL(k) 파서는 k개의 토큰을 미리 보고 파싱을 수행하며, LL 파서는 모든 문맥 자유 문법을 처리할 수 있는 것은 아니다.

더 읽어볼만한 페이지

파싱 알고리즘 - 하향식 구문 분석
하향식 구문 분석은 컴파일러나 인터프리터가 소스 코드를 변환할 때 입력 전체가 문법의 최상위 규칙에 일치한다고 가정하고 좌단 기호부터 매칭하며, LL 파서는 생성 규칙을 적용하여 구문 분석을 수행하고 좌측 재귀는 변환 또는 그래프 구조 스택으로 처리한다.
파싱 알고리즘 - 재귀 하향 파서
재귀 하향 파서는 백트래킹 없이 LL(k) 문법 클래스에서 선형 시간에 동작하며 각 비종단 기호에 대한 프로시저를 가지는 예측 파서이다.

LL 파서
파싱 기술
유형	상향식 파싱, 하향식 파싱
LL 파서
종류	하향식 파서
입력 방향	왼쪽에서 오른쪽
파생 순서	최좌단 파생
룩어헤드	k개의 토큰
LL 문법
파싱 테이블	파싱 테이블 생성 가능
충돌	충돌이 없는 문법
관련 주제
관련 항목	LR 파서, 재귀 하강 파서

2. 파서의 구조

LL 파서는 일반적으로 다음과 같은 구조를 가진다.^[1]

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

파서는 스택의 맨 위에 있는 기호와 입력 버퍼의 현재 기호를 보고 적용할 규칙을 결정한다. 구문 분석기는 처음에 스택에 시작 기호 'S'와 스택 바닥을 나타내는 특수 기호 '$'를 가지고 시작한다. 즉, 스택은 `[ S, $ ]` 형태로 초기화된다. 파서는 스택의 내용과 입력 버퍼의 내용을 비교하면서 파싱 테이블을 참조하여 스택의 내용을 변경해 나간다.^[1]

파싱 과정은 다음과 같이 요약할 수 있다.^[1]

1. 스택 맨 위가 비단말 기호이면, 파싱 테이블에서 해당 비단말 기호와 입력 스트림의 기호를 기반으로 적용할 규칙을 찾는다. 규칙 번호는 출력 스트림에 기록된다.

2. 스택 맨 위가 단말 기호이면, 입력 스트림의 기호와 비교하여 일치하면 둘 다 제거한다.

3. 스택 맨 위가 '$'이고 입력 스트림에도 '$'가 있으면 파싱이 성공적으로 완료된 것이다.

이러한 단계는 파서가 입력을 완전히 파싱하거나 오류를 보고할 때까지 반복된다.

2. 1. 입력 버퍼

LL 파서는 입력 버퍼에 파싱할 문자열을 저장한다.

2. 2. 스택

LL 파서는 파싱 중인 토큰을 저장하기 위해 스택을 사용한다. 스택의 초기 상태는 시작 문자 S가 가장 위에 있고, 그 아래에 스택의 바닥을 나타내는 특수 문자 $가 있는 형태이다.^[1]

LL 파서의 스택은 다음과 같이 작동한다.^[1]

스택 맨 위의 기호가 비단말 기호( $X \in N$ )인 경우, 파싱 테이블을 참조하여 규칙 $X \to \alpha$ 를 찾고, 스택 맨 위의 $X$ 를 $\alpha$ 로 바꾼다.
스택 맨 위의 기호가 단말 기호( $X \in \Sigma$ )인 경우, $\epsilon$ (또는 일부 표기법에서는 $\lambda$ )으로 바꾸어 스택에서 제거(pop)한다. 이때 입력 기호 $x$ 를 읽고, $x \neq X$ 이면 입력을 거부한다.
스택에서 제거된 마지막 기호가 입력 종료(EOI) 기호인 $이면 파싱이 성공적으로 완료된 것이고, 빈 스택을 통해 수용한다.

파싱 테이블은 스택 상단 기호(

X

)와 룩어헤드 버퍼 내용(

|w| \le k

)을 기반으로 규칙 번호(

X \to \alpha

또는

\epsilon

)를 제공한다. 파서가 유효한 전이를 수행할 수 없는 경우 입력은 거부된다(빈 셀).^[1]

다음은 예제 문법과 입력에 대한 파싱 테이블과 스택 변화 과정을 나타낸 표이다.^[1]
예제 문법:1. S → F

2. S → ( S + F )

3. F → a
입력: ( a + a )
파싱 테이블:

	(	)	a	+	$
S	2		1
F			3

파싱 과정:

파싱 과정
단계	스택	입력	규칙	출력
1	[ S, $ ]	( a + a ) $	2	2
2	[ (, S, +, F, ), $ ]	( a + a ) $
3	[ S, +, F, ), $ ]	a + a ) $	1	1
4	[ F, +, F, ), $ ]	a + a ) $	3	3
5	[ a, +, F, ), $ ]	a + a ) $
6	[ +, F, ), $ ]	+ a ) $
7	[ F, ), $ ]	a ) $	3	3
8	[ a, ), $ ]	a ) $
9	[ ), $ ]	) $
10	[ $ ]	$

파싱이 완료되면, 파서는 입력 문자열을 수락하고, 규칙 번호 목록 [ 2, 1, 3, 3 ]을 출력한다. 이는 입력 문자열의 가장 왼쪽 유도(leftmost derivation)에 해당한다.^[1]

2. 3. 파싱 테이블

LL 파서는 파싱 테이블을 이용하여 파싱을 수행한다. 파싱 테이블은 각 토큰에 대해 어떤 파싱 규칙을 적용해야 하는지를 나타내는 표로, 파싱 문법에 따라 결정된다.

스택의 초기 상태는 시작 기호(Start Symbol) 'S'와 스택의 바닥을 나타내는 특수 문자 '$'로 구성된다. 즉, 스택에는 `[ S, $ ]` 와 같이 저장된다. LL 파서는 파싱 테이블을 이용하여 스택에 있는 토큰들을 다른 토큰들로 대체하거나, 파싱이 완료된 문자를 출력 스트림에 출력하는 방식으로 동작한다.

파싱 테이블은 다음과 같이 구성된다.

행: 스택 상단 기호 $X$
열: $|w| \le k$ 룩어헤드 버퍼 내용 (미리보기 버퍼 내용)
셀: $X \to \alpha$ 또는 $\epsilon$ 에 대한 규칙 번호

파서가 유효한 전이를 수행할 수 없는 경우, 즉 파싱 테이블에서 적절한 규칙을 찾을 수 없는 경우에는 입력이 거부된다.
예제:다음 LL(1) 문법을 고려해 보자.

1. S → F

2. S → ( S + F )

3. F → a

입력 `( a + a )`를 파싱하기 위한 파싱 테이블은 다음과 같다.

	(	)	a	+	$
S	2		1
F			3

위 테이블에서, 예를 들어 스택 상단이 'S'이고 입력 기호가 '('인 경우, 규칙 2번(S → ( S + F ))을 적용해야 함을 알 수 있다.

3. 파싱 절차

LL 파서는 입력 문자열과 스택의 상태를 기반으로 파싱 테이블을 참조하여 다음 동작을 결정한다. LL( $k$ ) 파서는 $k$ 개의 입력 기호를 미리 볼 수 있는 결정적 푸시다운 오토마타이다.

스택 알파벳은 $\Gamma = N \cup \Sigma$ 이며, 여기서:

$N$ 은 비단말 기호 집합
$\Sigma$ 는 입력 종료(EOI) 기호 $\$$ 를 포함하는 단말(입력) 기호 집합

파서 스택은 처음에 시작 기호가 EOI 위에 있는 형태(

[\ S\ \$\ ]

)로 구성된다. 파서는 스택 상단의 기호

X

를 반복적으로 다음으로 대체한다.

$X \in N$ 이고 규칙 $X \to \alpha$ 가 있는 경우, $\alpha$ 로 대체한다.
$X \in \Sigma$ 인 경우 $\epsilon$ 로 대체, 즉 $X$ 를 스택에서 팝(pop)한다. 입력 기호 $x$ 가 읽히고, $x \neq X$ 이면 입력을 거부한다.

스택에서 제거된 마지막 기호가 EOI이면 파싱이 성공적으로 완료된다.

파싱 테이블은 다음을 제공한다.

행: 스택 상단 기호 $X$
열: $|w| \le k$ 룩어헤드 버퍼 내용
셀: $X \to \alpha$ 또는 $\epsilon$ 에 대한 규칙 번호

파서가 유효한 전이를 수행할 수 없으면 입력이 거부된다 (빈 셀).

LL 파서는 다음과 같은 세 가지 유형의 단계를 수행한다.

스택의 맨 위가 비단말 기호인 경우, 파싱 테이블에서 규칙을 찾아 적용하고 규칙 번호를 출력한다. 해당 규칙이 없으면 오류를 보고한다.
스택의 맨 위가 단말 기호인 경우, 입력 스트림의 기호와 비교하여 일치하면 둘 다 제거한다. 일치하지 않으면 오류를 보고한다.
스택의 맨 위가 '''$'''이고 입력 스트림에도 '''$'''가 있으면 파싱 성공을 보고하고, 그렇지 않으면 오류를 보고한다.

이러한 단계는 파서가 중지될 때까지 반복되며, 입력 문자열의 최좌 유도를 출력하거나 오류를 보고한다.

3. 1. 기본 동작

LL(1) 파서는 다음의 작은 LL(1) 문법을 기반으로 동작한다.

# S → F

# S → ( S + F )

# F → a

그리고 입력 문자열 '''( a + a )'''를 파싱하는 과정을 예시로 설명한다.

LL(1) 파싱 테이블은 비단말 기호(nonterminal symbol)를 행으로, 단말 기호(terminal symbol)와 입력 스트림의 끝을 나타내는 특수 기호 '''$'''를 열로 갖는다. 각 셀은 문법 규칙을 가리킨다.

	(	)	a	+	$
S	2		1
F			3

파서는 입력 스트림에서 읽은 기호와 스택의 최상단 기호를 비교한다. 일치하면 둘 다 제거하고, 일치하지 않으면 파싱 테이블을 참조하여 규칙을 적용한다.
파싱 단계:1. 입력 기호 '''('''와 스택 상단 기호 'S'를 읽는다. 테이블에서 규칙 2를 적용하여 스택에 '(', S, '+', F, ')'를 푸시하고, 규칙 번호 2를 출력한다. 스택: [ '''(''', S, '''+''', F, ''')''', '''$''' ]

2. 입력 스트림과 스택에서 '''('''를 제거한다. 스택: [ S, '''+''', F, ''')''', '''$''' ]

3. 입력 스트림의 ''''a''''와 스택 상단 'S'를 보고 규칙 1을 적용, 규칙 번호 1을 출력한다. 스택: [ F, '''+''', F, ''')''', '''$''' ]

4. 입력 스트림의 ''''a''''와 스택 상단 'F'를 보고 규칙 3을 적용, 규칙 번호 3을 출력한다. 스택: [ '''a''', '''+''', F, ''')''', '''$''' ]

5. 입력 스트림과 스택에서 '''a'''를 제거한다.

6. 입력 스트림과 스택에서 '''+'''를 제거한다. 스택: [ F, ''')''', '''$''' ]

7. 다음 세 단계에서 스택의 ''''F''''를 ''''a''''로 대체하고(규칙 3), 규칙 번호 3을 출력, '''a''''와 '''')''''를 제거한다.

8. 스택과 입력 스트림 모두 '''$'''로 종료되어 파싱을 성공적으로 완료한다.

파서는 입력 문자열을 수락하고, 규칙 번호 목록 [ 2, 1, 3, 3 ]을 출력한다. 이는 입력 문자열의 가장 왼쪽 파생을 나타낸다.

: S → '''(''' S '''+''' F ''')''' → '''(''' F '''+''' F ''')''' → '''( a +''' F ''')''' → '''( a + a )'''
파서의 세 가지 단계:

비단말 기호가 스택 최상단: 파싱 테이블을 참조하여 적용할 규칙을 결정하고, 규칙 번호를 출력한다. 규칙이 없으면 오류를 보고한다.
단말 기호가 스택 최상단: 입력 스트림의 기호와 비교하여 일치하면 제거하고, 불일치하면 오류를 보고한다.
스택 최상단이 '''$''': 입력 스트림도 '''$'''이면 파싱 성공, 아니면 오류를 보고한다.

이러한 단계를 반복하여 입력을 완전히 파싱하거나 오류를 보고하며 종료한다.

4. 예제

다음과 같은 문법을 고려한다.

# S → F

# S → '''(''' S '''+''' F ''')'''

# F → '''a'''

이 문법에 대한 LL(1) 파싱 테이블은 다음과 같다.

	(	)	a	+	$
S	2		1
F			3

'''( a + a )''' 문자열에 대한 파싱 과정은 다음과 같다.

단계	동작 설명	동작 후 스택	동작 후 입력 문자열
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 확인. 두 문자가 같으므로 삭제.	+ F ) $	+ a )
7	입력 문자열과 스택 가장 위의 문자 + 확인. 두 문자가 같으므로 삭제.	F ) $	a )
8	입력 문자열에서 a를 읽고, 스택 가장 위의 문자 F 확인. 파싱 테이블에 의하여 규칙 3 적용.	a ) $	a )
9	입력 문자열과 스택 가장 위의 문자 a 확인. 두 문자가 같으므로 삭제.	) $	)
10	입력 문자열과 스택 가장 위의 문자 ) 확인. 두 문자가 같으므로 삭제.	$
11	입력 문자열과 스택 모두 빈 것을 확인하고 작동 종료.	$

파싱 과정에서 사용한 규칙은 순서대로 2, 1, 3, 3이다. 즉, '''( a + a )'''는 다음과 같이 가장 왼쪽 파생으로 파싱된다.

: S → '''(''' S '''+''' F ''')''' → '''(''' F '''+''' F ''')''' → '''( a +''' F ''')''' → '''( a + a )'''

5. 파싱 테이블 생성

LL(1) 파싱 테이블은 First 세트와 Follow 세트를 이용하여 생성한다.

파싱 테이블은 비단말 기호 ''A''와 터미널 기호 ''a''에 대한 항목 ''T''[''A'', ''a'']를 가진다. ''T''[''A'',''a'']는 다음 조건 중 하나를 만족하는 경우에 규칙 ''A'' → ''w''를 포함한다.

''a''가 '''Fi'''(''w'')에 포함되는 경우
ε가 '''Fi'''(''w'')에 포함되고, ''a''가 '''Fo'''(''A'')에 포함되는 경우

이는 모든 ''a'' ∈ '''Fi'''(''w'')·'''Fo'''(''A'')에 대해 ''T''[''A'', ''a'']가 규칙 ''A'' → ''w''를 포함한다는 의미와 같다.

파싱 테이블의 각 셀에 최대 하나의 규칙만 존재한다면, 파서는 어떤 규칙을 적용해야 할지 명확하게 알 수 있으며, 백트래킹 없이 문자열을 파싱할 수 있다. 이러한 문법을 ''LL''(1) ''문법''이라고 한다.

5. 1. First Set

First set|First 세트^영어은 특정 문법 기호에서 유도될 수 있는 문자열의 첫 번째 토큰 집합이다.

파싱 테이블을 채우기 위해서는 파서가 스택 맨 위에 있는 비터미널 ''A''를 보고 입력 스트림에서 기호 ''a''를 볼 때 어떤 문법 규칙을 선택해야 하는지를 결정해야 한다. 이 규칙은 ''A'' → ''w'' 형태여야 하며, ''w''에 해당하는 언어는 최소한 ''a''로 시작하는 문자열을 하나 이상 가져야 한다.

이러한 목적을 위해, ''w''의 "First-set"을 '''Fi'''(''w'')로 표기한다. First-set|First-set^영어은 ''w''에 있는 어떤 문자열의 시작 부분에서 찾을 수 있는 터미널 집합과, 빈 문자열이 ''w''에 속하는 경우 ε를 포함한다. 규칙 ''A''₁ → ''w''₁, …, ''A''_''n'' → ''w''_''n''을 가진 문법이 주어졌을 때, 모든 규칙에 대한 '''Fi'''(''w''_''i'') 및 '''Fi'''(''A''_''i'')는 다음과 같이 계산할 수 있다.

# 모든 '''Fi'''(''A''_''i'')를 빈 집합으로 초기화한다.

# Fi가 다음과 같이 정의된 모든 규칙 ''A''_''i'' → ''w''_i에 대해 Fi(''w''_''i'')를 '''Fi'''(''A''_''i'')에 추가한다.

#* Fi(''aw''') = { ''a'' } (모든 터미널 ''a''에 대해)

#* Fi(''Aw''') = '''Fi'''(''A'') (ε가 '''Fi'''(''A'')에 없는 모든 비터미널 ''A''에 대해)

#* Fi(''Aw''') = ('''Fi'''(''A'') \ { ε }) ∪ Fi(''w''') (ε가 '''Fi'''(''A'')에 있는 모든 비터미널 ''A''에 대해)

#* Fi(ε) = { ε }

# 모든 규칙 ''A''_''i'' → ''w''_''i''에 대해 Fi(''w''_''i'')를 '''Fi'''(''A''_''i'')에 추가한다.

# 모든 '''Fi''' 집합이 변경되지 않을 때까지 2단계와 3단계를 반복한다.

이는 다음 시스템의 최소 고정점 해이다.

'''Fi'''(''A'') ⊇ '''Fi'''(''w'') (각 규칙 A → ''w''에 대해)
'''Fi'''(''a'') ⊇ { ''a'' } (각 터미널 ''a''에 대해)
'''Fi'''(''w''₀ ''w''₁) ⊇ '''Fi'''(''w''₀)·'''Fi'''(''w₁'') (모든 단어 ''w''₀ 및 ''w''₁에 대해)
'''Fi'''(ε) ⊇ {ε}

여기서, 단어 집합 U와 V에 대해, 잘린 곱은

U \cdot V = \{ (uv):1 \mid u \in U, v \in V \}

로 정의되며, w:1은 길이가 2 이상인 단어 w의 초기 길이 1 접두사, 또는 w의 길이가 0 또는 1인 경우 w 자체를 나타낸다.

5. 2. Follow Set

Follow Set은 특정 비단말 기호 다음에 나타날 수 있는 토큰(단말 기호) 집합이다. 입력 스트림의 끝을 나타내는 특수 단말 기호인 '''$'''를 사용하고, 시작 기호는 ''S''를 사용한다.

비터미널에 대한 Follow-set을 계산하는 방법은 다음과 같다.

# '''Fo'''(''S'')를 { '''$''' }로 초기화하고, 다른 모든 '''Fo'''(''A''_''i'')는 빈 집합으로 초기화한다.

# ''A''_''j'' → ''wA_iw' '' 형태의 규칙이 있는 경우,

#* 터미널 ''a''가 '''Fi'''(''w' '')에 있으면, ''a''를 '''Fo'''(''A''_''i'')에 추가한다.

#* ε가 '''Fi'''(''w' '')에 있으면, '''Fo'''(''A''_''j'')를 '''Fo'''(''A''_''i'')에 추가한다.

#* ''w' ''의 길이가 0이면, '''Fo'''(''A''_''j'')를 '''Fo'''(''A''_''i'')에 추가한다.

# 모든 '''Fo''' 집합이 변경되지 않을 때까지 2단계를 반복한다.

이는 다음 시스템의 최소 고정점 해를 제공한다.

'''Fo'''(''S'') ⊇ {'''$'''}
'''Fo'''(''A'') ⊇ '''Fi'''(''w'')·'''Fo'''(''B'') (B → ... A w 형태의 각 규칙에 대해)

파싱 테이블에서 ''T''[''A'',''a'']는 다음 경우에만 규칙 ''A'' → ''w''를 포함한다.

''a''가 '''Fi'''(''w'')에 있거나
ε가 '''Fi'''(''w'')에 있고 ''a''가 '''Fo'''(''A'')에 있다.

테이블의 각 셀에 최대 하나의 규칙만 포함되어 있다면, 파서는 항상 어떤 규칙을 사용해야 하는지 알 수 있으며 백트래킹 없이 문자열을 파싱할 수 있다. 문법이 ''LL''(1) ''문법''이라고 불리는 것은 바로 이 경우이다.

5. 3. 충돌

LL(1) 문법은 파싱 테이블에 충돌이 없어야 한다.^[12] 충돌은 FIRST 집합과 FOLLOW 집합을 통해 정의된다.

FIRST(A): 비단말 기호 A에서 파생될 수 있는 모든 문자열의 첫 번째 위치에 나타날 수 있는 단말 기호들의 집합이다.
FOLLOW(A):
생성 규칙에서 A 바로 뒤에 오는 모든 비단말 기호 B의 FIRST(B)의 합집합이다.
B → wA 형식의 규칙에서, 모든 B의 FOLLOW(B)이다.

LL(1) 파싱 테이블에서 충돌은 다음과 같은 경우에 발생한다.

LL(1) 파싱 테이블 충돌 유형
충돌 유형	설명	예시
FIRST/FIRST 충돌	두 개의 서로 다른 문법 규칙에 대한 FIRST 집합이 동일한 비단말 기호에 대해 교차하는 경우
FIRST/FOLLOW 충돌	문법 규칙의 FIRST 집합과 FOLLOW 집합이 겹치는 경우. FIRST 집합에 빈 문자열(ε)이 포함되어 있으면, 어떤 대안을 선택해야 할지 알 수 없다.

5. 3. 1. 충돌 해결

LL(1) 파서에서 발생하는 충돌은 크게 두 가지 유형으로 나뉜다.

FIRST/FIRST 충돌: 서로 다른 두 문법 규칙의 FIRST 집합이 동일한 비단말 기호에 대해 겹칠 때 발생한다. 예를 들어:
S → E | E 'a'
E → 'b' | ε

: 위 예시에서 FIRST(E) = {b, ε}이고 FIRST(E a) = {b, a}이므로, 파싱 테이블의 'b' 칸에 충돌이 생긴다.

FIRST/FOLLOW 충돌: 특정 문법 규칙의 FIRST 집합과 FOLLOW 집합이 겹칠 때 발생한다. FIRST 집합에 빈 문자열(ε)이 있으면, 어떤 규칙을 적용해야 할지 모호해진다. 예를 들어:
S → A 'a' 'b'
A → 'a' | ε

: 위 예시에서 ''A''의 FIRST 집합은 {''a'', ε}이고, FOLLOW 집합은 {''a''}이므로 충돌이 발생한다.

이러한 충돌을 해결하기 위해 사용되는 기법은 다음과 같다.

좌-인수분해(Left-Factoring): 공통 부분을 묶어 충돌을 해결한다. 위의 FIRST/FIRST 충돌 예시는 다음과 같이 좌-인수분해를 통해 해결할 수 있다.
S → 'b' E | E
E → 'a' | ε

규칙 대입: 한 규칙을 다른 규칙에 대입하여 간접적인 충돌을 제거한다. 이 과정에서 FIRST/FIRST 충돌이 발생할 수도 있다.

좌측 재귀 제거: 좌측 재귀를 제거하여 충돌을 해결한다. 예를 들어:
E → E '+' T
E → T

: 위 규칙은 아래와 같이 좌측 재귀를 제거할 수 있다.

E → T Z
Z → '+' T Z
Z → ε

하지만 모든 문맥 자유 문법을 LL(k) 문법으로 변환할 수 있는 것은 아니다. 예를 들어 아래 문법은 어떤 LL(k) 문법으로도 표현할 수 없다.^[13]

S → A | B
A → 'a' A 'b' | ε
B → 'a' B 'b' 'b' | ε

6. LL(k) 파서

LL(k) 파서는 k개의 토큰을 미리 보고 파싱을 수행한다. 일반적인 $LL(k)$ 파서는 $k$ 개의 기호를 미리 볼 수 있다.^[11]

$LL(k)$ 파서는 다음 $k$ 개의 입력 기호를 읽지 않고 미리 볼 수 있는 능력을 가진 결정적 푸시다운 오토마타이다. 이 미리 보기 기능은 룩어헤드 버퍼의 내용을 유한 상태 공간에 저장하여 에뮬레이션할 수 있는데, 버퍼와 입력 알파벳 모두 크기가 유한하기 때문이다. 결과적으로 오토마타의 성능이 향상되는 것은 아니지만 편리한 추상화이다.

LL(1) 파서 구성을 응용하여 ''k'' > 1인 LL(''k'') 파서를 만들 수 있다.

잘린 곱은 $U \cdot V = \{ (uv):k \mid u \in U, v \in V \}$ 로 정의된다. 여기서 w:k는 길이가 k보다 큰 단어의 초기 길이-k 접두사를 나타내거나, w의 길이가 k 이하면 w 자체를 나타낸다.
'''Fo'''(''S'') = {'''$'''^k}
LL(1)에 대해 주어진 '''Fi''' 구성의 2단계에서도 '''Fi'''(αβ) = '''Fi'''(α) $\cdot$ '''Fi'''(β)를 적용한다.
'''Fo''' 구성의 2단계에서 ''A_j'' → ''wA_iw'''에 대해 단순히 '''Fi'''(''w''') $\cdot$ '''Fo'''(''A_j'')를 '''Fo'''(''A_i'')에 추가한다.

여기서 입력은 k개의 종료 마커 '''$'''로 접미사 처리되어 k개 전방 탐색 컨텍스트를 완전히 고려한다. 이 접근 방식은 ε에 대한 특수 사례를 제거하며, LL(1) 경우에도 동일하게 적용될 수 있다.

1990년대 중반까지 LL(''k'') 파싱 (''k'' > 1)는 파서 테이블이 최악의 경우 ''k''에서 지수 크기를 가질 수 있기 때문에 비실용적이라고 널리 여겨졌다.^[11] 이러한 인식은 1992년경 퍼듀 컴파일러 구축 도구 세트(PCCTS, 현재는 ANTLR)가 출시된 후 점차 바뀌었다. 이 도구를 통해 많은 프로그래밍 언어가 파서의 최악의 경우 동작을 유발하지 않고 LL(''k'') 파서로 효율적으로 파싱될 수 있다는 것이 입증되었다. 또한, 특정 경우에는 무제한 전방 탐색으로도 LL 파싱이 가능함이 밝혀졌다. 반대로, yacc와 같은 기존 파서 생성기는 고정된 하나의 토큰 전방 탐색을 가진 제한된 LALR(1) 파서 테이블을 사용하여 구축한다.

7. 비고

LL 파싱은 모든 문맥 자유 문법을 처리할 수 있는 것은 아니다. LL(1) 언어는 LR(1) 언어의 진부분집합이다.

참조

_[1] 간행물 Properties of Deterministic Top Down Grammars
_[2] 간행물 LL-Regular Grammars 1974
_[3] 간행물 LL-Regular Grammars https://www.scienced[...] 1975-11
_[4] Technical Report Properties of LL-Regular Languages https://docs.lib.pur[...] 1977-08
_[5] 간행물 LL (*) the foundation of the ANTLR parser generator 2011
_[6] arXiv The LL(finite) parsing strategy for optimal LL(k) parsing
_[7] 간행물 Parsing Expression Grammars: A Recognition-Based Syntactic Foundation 2004
_[8] 서적 Compiling with C# and Java https://books.google[...] Pearson Education
_[9] 서적 Compiler Construction Springer
_[10] 간행물 Property Grammars and Table Machines
_[11] 서적 Compiler Construction: 5th International Conference, CC '94, Edinburgh, U.K., April 7 - 9, 1994. Proceedings Springer Science & Business Media 1994-03-23
_[12] 웹사이트 LL Grammars http://www.cs.uaf.ed[...] 2010-05-11
_[13] 서적 Modern Compiler Design https://books.google[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com