목차
📁 LR Parsing : 파서 상태
파서는 파싱테이블을 보고 – 현재 상태, 입력 심벌을 보고 shift 할지 reduce 할지 결정하고 (action) – 파서 상태도 변경시킴 (goto)
📁 LR 파싱 테이블
LR(0)이란, LOOKAHEAD 없이 shift-reduce 형태로 파싱하는 것을 말한다.
LR(0)에서 사용되는 파싱 테이블을 만드는 절차는 다음과 같다.
1. LR(0) 아이템과 Closure 등을 이용하여 파서 상태가 될 만한 것들이 무엇인지 정한다.
2. GOTO를 이용하여 각 파서 상태들 간의 상태 전이도(DFA : Deterministic Finite Automata)를 만든다.
3. 위 결과를 파싱 테이블에 담아낸다.
📁 LR(0) 아이템
LR(0) 아이템이란, RHS에 점('.') 심벌을 가진 생성규칙을 말한다.
참고로 [X → a . b]의 의미는 “ a 만큼은 이미 매치됨” – 앞으로 b가 올 가능성 있음. (b 는 ‘마크심벌’ 이라함)
1. 생성 규칙의 형태가 A→XYZ일 때
- [A→.XYZ]
- [A→X.YZ]
- [A→XY.Z]
- [A→XYZ.] 등은 모두 LR(0)아이템
2. 생성 규칙이 A → ε 일때
- [A→.] 는 LR(0) 아이템
예를 들어, 아래와 같은 문법에서 등장할 수 있는 LR(0) 아이템은 다음과 같다.
📁 closure
closure([A→ a.Xb])란, “a 까지 parse됐고, X를 parse 할 것으로 기대하는 상태”를 의미한다.
1. t가 terminal 심벌일 때,
2. X가 Nonterminal 심벌일 때,
예를 들어, 아래 문법에 대해 closure({[S’ →.G]})와 closure({[E →E.+T]})를 구해보자.
1) closure({[S’ →.G]})은 '.' 다음에 Nonterminal 심벌이 오므로 closure에서 정의한 두 번재 규칙을 사용한다.
2) closure({[E →E.+T]})은 '.' 다음에 terminal 심벌이 오므로 closure에서 정의한 첫 번재 규칙을 사용한다.
두번째 예시로, 아래 문법에 대해 closure({[S’ → . S]})를 구해보면 다음과 같다.
📁 goto
예를 들어, 아래 문법에 대해 goto(I, +)와 goto(I, T)를 구해보면 다음과 같다.
참고로, A -> ε 생성규칙에 대한 goto는 없다.
아래 문법에 대해, terminal 심벌과 nonterminal 심벌을 구분하여 goto를 구해보자.
1. Terminal Symbol에 대한 goto
2. Nonterminal Symbol에 대한 goto
🌱 파서 상태 만들기
1. 생성규칙 'S' -> S'을 추가한다.
2. 시작상태 [S' -> . S]의 closure를 구한다.
3. 그 다음 상태들은 goto를 계산하여 C0 방법으로 만들어낸다.
📁 C0
C0란 추가된 생성규칙 S' -> S에서부터 차례로 closure와 goto를 적용하여 얻은 모든 타당한 LR(0) 아이템의 집합을 말한다.
C0 = {I0,I1, ..., In}이라면, I0는 {S' -> S}의 closure이고, 다른 것들은 여기서부터 각 마크심벌에 따라 goto를 적용하여 만든 상태인 것이다.
🌱 아이템의 분류
1. [A→X.Y] : X != ε 일때 kernel item
2. [A→.X] : closure item
3. [A→X.] : reduce item
예를 들어 아래 문법에 대한 C0와 Transition을 구해보면 다음과 같다.
📁 LR(0) Parsing Table 구성하기
1. 파서 상태로 C0 = {I0,I1, ..., In} 과 transition 이용
2. goto(I1 ,a)= I2 면: M[I1 ,a] = ‘shift I2 ’
3. goto(I1 ,N)= I2 면: M[I1 ,N] = ‘goto I2 ’
4. I1 이 [X → β .] 를 포함한다면: M[I1 ,*] = ‘reduce X → β ’
5. I1 이 [S’→S.]를 포함한다면: M[I1 , $] := ‘accept’
예를 들어 위와 같은 문법의 파싱 테이블 형태는 다음과 같이 시작한다.
이후 다음과 같이 완성된다.
