구문 분석 : 상향식 구문 분석

주어진 문장이 문법에 맞는지 아닌지를 검사하기 위해 입력된 문자열을 읽어가면서 감축에 의해 시작 기호를 찾아가는 방법

주어진 문자열이 시작 기호로 감축되면 올바른 문장이라고 판단하여 파스 트리를 생성,

아니면 에러 메시지를 출력

 

감축과 핸들

S =>* αAw => αβw의 유도 과정이 존재할 때 문장 형태 αβw에서 β를 A로 대체하는 것을 감축(reduce)이라하고, β를 문장 형태 αβw의 핸들이라 함.

즉, 한 문장 형태에서 감축되는 부분이 핸들

 

 

우단 유도와 핸들 찾기

id + id * id에 대해 우단 유도 과정을 보이고 핸들 찾기

1. E -> E + T

2. E -> T

3. T -> T * F

4. T -> F

5. F -> (E)

6. F -> id

 

우단유도

E

=> E + T (1)

=> E + T * F (13)

=> E + T * id (136)

=> E + F * id (1364)

=> E + id * id (13646)

=> T + id * id (136462)

=> F + id * id (1364624)

=> id + id * id (13646246)

상향식 구문 분석은 우단 유도의 역순, 역으로 따라가면 됨

 

우문장 형태	핸들	감축에 사용될 생성 규칙
id1 + id2 * id3	id1	F -> id
F + id2 * id3	F	T -> F
T + id2 * id3	T	E -> T
E + id2 * id3	id2	F -> id
E + F * id3	F	T -> F
E + T * id3	id3	F -> id
E + T * F	T * F	T -> T * F
E + T	E + T	E -> E + T
E

 

핸들 대체

유도 과정들이 있을 때 각 문장 형태에서 핸들을 찾아 시작 심볼로 감축되는 과정

 

이동-감축(shift-reduce) 구문 분석

- 스택과 입력 버퍼를 사용하여 구현

- 스택은 보통 파싱 스택이라 부르며 문장 형태에서 핸들을 찾을 때까지 필요한 문법 심볼들을 유지하고 입력 버퍼는 주어진 문자열을 보유

 

이동-감축 구문 분석기의 행동

- 이동(shift) : 현재의 입력 기호를 스택의 톱에 옮기는 것을 의미, 스택의 톱에 핸들이 나타날 때까지 계속

- 감축(reduce) : 핸들이 스택의 톱에 나타나면 스택의 톱이 핸들의 오른쪽 끝이 되고 핸들의 

- 수락(Accept)

- 에러(Erorr)

 

과정

1. 입력 문자열을 읽고 핸들을 발견

2. 핸들을 찾으면 감축하고 부분 파스 트리를 구성

3. 같은 방법으로 계속 진행

4. 입력 문자열을 모두 읽은 후 시작 기호를 만나면 주어진 문장은 맞는 문장

 

예시

E -> E + E

E -> E * E

E -> id

E -> (E)

일 때 id + id * id에 대해 이동-감축 구문 분석

 

구문 분석 전 생성되는지 우단유도..

E

=> E + E

=> E + E * E

=> E + E * id

=> E + id * id

=> id+ id * id

되니까 이동-감축 구문 분석기도 accept 해야 함

근데 파싱표 없이 일단 우단유도 역순으로 구문 분석만 해도

핸들을 어떻게 찾을 건지, 핸들에 대해 생성 규칙이 여러 개 존재 시 문제가 됨

-> 우선순위 구문 분석

 

 

연산자 우선순위 구문 분석

- 연산자 상호 간의 우선순위 관계에 의해 핸들을 찾는 방법

- 연산자 우선 순위 문법이 필요

 

연산자 우선 순위 문법

- 연산자 우선순위 문법은 연산자 문법이면서 2개의 터미널 기호 사이에 많아야 1개의 연산자 우선순위를 갖는 것(뭐가 더 크거나, 작거나, 같거나.. 하나만 해야 한다는 것)

- 이 문법에 의해 정의된 언어를 연산자 우선순위 언어라 함

- 어떤 문법이 주어졌을 때 그 문법이 연산자 우선 순위 문법인지 바로 알 수 없음. 우선순위 관계는 연산자 우선순위 파싱표를 만들어야 알 수 있음

 

연산자 우선순위 구문 분석 방법

- 연산자 우선 순위 문법이 주어졌을 때 생성 규칙의 문법 기호 상호 간, 연산자 우선순위 관계에 의해 핸들을 찾는 방법

- 파싱표를 작성하기 쉽고, 연산자 간 우선 순위를 정하여 구문 분석을 할 수 있어 산술식을 위한 구문 분석 방법으로 적절

- 반면 구문 분석되는 문법의 범위가 작고, 터미널과 터미널만의 우선 순위 관계에 의해 핸들을 찾아 구문 분석이 완전하지 않음

 

1.만약 연산자 θ1이 연산자 θ2보다 우선순위가 높다면 θ1 ⋗ θ2, 그리고 θ2 ⋖ θ1

2. 만약 연산자 θ1과 θ2가 동일한 우선순위이고 연산자들이 왼쪽 결합 법칙을 가지면 θ1 ⋗ θ2, 그리고 θ2 ⋗ θ1 (오른쪽 결합 법칙이면 θ1 ⋖ θ2, 그리고 θ2 ⋖ θ1 )

3. 모든 연산자 θ에 대해 θ ⋖ id, id ⋗ θ, θ ⋖ (, ( ⋖ θ, ) ⋗ θ, θ ⋗ $, θ ⋖ $ 이고 또한 다음과 같이 되도록 함

- ( ≗ )    $ ⋖ (    $ ⋖ id

- ( ⋖ (    id ⋗ $   ) ⋗ $

- ( ⋖ id  id ⋗ )    ) ⋗ ) 

- id도 (E)도 모두 하나의 E로 축소가 되어야 한다는 것. 또한 전체 표현식은 $ ~ $가 되어야 함

 

예시

E -> E + E

E -> E * E

E -> id

E -> (E)

 

스택	관계	입력 기호	행동	핸들
$	⋖	id + id * id$	이동
$id	⋗	+ id * id$	감축	id
$E		+ id * id$

근데 구문 분석이 완전히 이루어지지 않음

우선 순위 문법을 이용한 방법은 문법의 제약이 많고, 여러 개의 핸들 등에도 문제가 있음

-> LR 구문 분석을 사용

 

 

LR 구문 분석

- 결정적인 상향식 구문 분석 방법

- 입력 문자열을 왼쪽에서 오른쪽으로 읽어가며, 출력으로 우파스를 생성

- LR parser

 

장점

- 모호하지 않은 문맥 자유 문법으로 쓰인 모든 프로그래밍 언어에 대해 구성이 가능

- 가장 일반적인 역추적이 없는 결정적인 이동-감축 구문 분석 방법

- 입력을 왼쪽에서 오른쪽으로 검조하며 구문 오류를 쉽게 분석 가능

 

단점

- 직접 LR 구문 분석기 작성하는게 굉장히 방대한 작업

 

LR 구문 분석 종류 (파싱표 구성에 따름)

- SLR(simple LR) 구문 분석 : LR(0) 항목의 집합과 FOLLOW

- CLR(canonical LR) 구문 분석 : LR(1) 항목의 집합

- LALR(lookahead LR) 구문 분석 : LR(0) 항목의 집합과 lookahead로부터 또는 LR(1) 항목의 집합

 

LR 구문 분석기의 구성

- 이동-감축 구문 분석기와 마찬가지로 구동 프로그램 및 action(입력 기호를 보고 수행할 액션)과 GOTO(어떤 상태로 가야 하는지) 두 부분을 포함한 파싱표로 구성, 파싱표의 행동도 이동-감축 구문 분석기와 같음

- 구동 프로그램은 LR 구문 분석기가 모두 같으나 파싱표는 다름

 

장단점

- SLR은 구현하기가 쉬우나 강력하지 못함

- CLR은 가장 강력하지만 구현하기 어려움

- LALR은 중간 형태

SLR < LALR < CLR 범위

 

LR 파싱표 행동 구성

상태번호 \ 기호	ACTION 표	GOTO 표
	VT ∪ {$}	VN
0 1 2 ..	이동 감축 수락 에러	상태 번호

 

LR 파싱표의 4가지 행동

1. 이동

- ACTION[Sm, ai] = 이동 S

- Sm상태에서 입력기호 ai를 본 행동이 이동 S라는 것은, [ 입력 기호를 스택으로 이동하고 다음 상태를 S로 만들기 위해 S도 스택에 넣는다는 의미 ]

 

2. 감축

- ACTION[Sm, ai] = 감축 A -> α

- ~.. 스택에서 핸들 α를 제거하고 스택에 생성 규칙의 왼쪽 부분을 다음 상태와(GOTO) 함께 스택에 넣는다

 

3. 수락

4. 에러

 

 

LR(k) 문법

- LR(k) 문법은 모든 항목(entry)에 대해 유일하게 정의되는 파싱표를 만들 수 있는 문법

- 여기서 k는 lookahead의 길이

 

증가 문법

G = (VN, VT, P, S)에서 G에 새로 추가된 문법

G' = ( VN, ∪ { S' }, VT, P ∪ { S' -> S }, S' )

- S' : 새로 추가된 시작 기호

- S' -> S : 추가된 생성 규칙

- 생성규칙 S'->S를 두는 이유는 주어진 문장이 안전하게 수락되게 하기 위함

 

증가 문법 만들기

E -> E + E

E -> E * E

E -> id

E -> (E)

 

S' -> E

E -> E + E

E -> E * E

E -> id

E -> (E)

이러면 된다

 

LR(0) 항목

- 생성 규칙의 오른쪽에 점 기호를 가진 생성 규칙

 

LR(0) 항목 구하기

생성 규칙 A -> BCD에 대해 LR(0)

- A -> •BCD, A -> B•CD, A -> BC•D, A -> BCD•  네가지 항목

 

LR(0) 항목 A -> B•CD는 B는 이미 읽었고 CD는 앞으로 읽을 기호임을 나타냄

A -> BCD•는 BCD를 모두 읽었고 이제 BCD를 A로 감축할 수 있음을 나타냄

- LR(0) 항목을 만들기 위해 생성 규칙의 오른쪽에 점 기호를 찍는 것을 마킹한다고 함

- 점 기호 다음에 있는 기호를 마크 기호라 부름

 

LR(0) 항목의 세가지 종류

- LR(0) 항목 [ A -> α•β ] 에서 α≠ε 이거나 A = S'이면 커널 항목

- LR(0) 항목 [ A -> •α ]와 같이 점 기호가 생성 규칙 처음에 있는 항목이 클로저 항목

- LR(0) 항목 [ A -> α• ]와 같이 생성 규칙 끝에 점 기호가 있는 항목을 감축 항목

 

정규 항목 집합(canonical collection)이 불리는, 어떤 문법에 대한 LR(0) 항목으로 구성된 집합은

LR 파싱표를 구성하는데 반드시 필요함

주어진 문법에 대해 정규 항목 집합을 구성하려면 하나의 증가 문법과 2개의 함수 CLOUSURE, GOTO 정의 필요

 

CLOSURE(I)를 구하는 규칙

- I가 문법 G에 대한 LR(0) 항목으로 구성된 집합이면 CLOSURE(I)는 다음 두 가지 규칙에 따라 구함

- 초기에 I에 속한 모든 LR(0) 항목을 CLOSURE(I)에 추가한다

- [A → α•Bβ]가 CLOSURE(I)에 포함되어 있고 B → γ의 생성 규칙이 존재하는 경우, B → •γ가 CLOSURE(I)에 포함되어 있지 않으면 이 항목을 CLOSURE(I)에 추가. 새로운 LR(0) 항목이 CLOSURE(I)에 더 이상 추가할 수 없을 때까지 적용

- CLOSURE(I) = I ∪ {[B → •γ] | [A → α•Bβ] ∈ CLOSUR(I), B→γ ∈P}

 

간단히 말하면, 점 뒤의 비단말을 전개해서 모든 가능성을 펼치는 작업

점(•) 뒤에 비단말 X가 있으면
X의 모든 생성 규칙을 •가 맨 앞에 오도록 추가한다.
그리고 새로 추가된 항목들에서도 점 뒤가 비단말이면 계속 확장한다.

 

예시

E' -> EE -> E + T | TT -> T * F | FF -> (E) | id에서 LR(0) 항목 E' ->  •E와 E -> E + •T의 클로저를 구하기

 

CLOSURE([ E' -> •E ]) = { [ E' -> •E ], [ E -> •E + T ], [ E -> •T ],  [ T →•T * F ], [ T -> •F ], [ F -> •(E) ], [ F -> •id ]  }

 

CLOSURE([ E -> E + •T ]) ={ [ E -> E + •T ],  [ T →•T * F ], [ T -> •F ], [ F -> •(E) ], [ F -> •id ] }

 

GOTO 함수

- LR(0) 항목의 GOTO 함수는 I가 항목의 집합이고 X ∈ V이면 GOTO(I, X) = CLOSURE( { [A → αX•β] | [A → α•Xβ ∈ I } )

 

간단히, 상태 I에서 기호 X를 읽고 난 후 도착하는 다음 상태 점을 X 뒤로 움직인 뒤 클로저를 취하여 얻는 상태 집합

 

I = { [ E' ->  •E], [E -> E• + T] } 일 때 GOTO(I, +) ?

- I 안에서 점 뒤에 X가 있는 항목을 찾고
- 점을 X 뒤로 옮긴 뒤
- 그 결과에 대해 CLOSURE

GOTO(I, +) = CLOSURE( [E -> E + •T] )

= { [ E -> E + •T ],  [ T →•T * F ], [ T -> •F ], [ F -> •(E) ], [ F -> •id ] }

 

 

LR(0) 항목 집합의 정규 항목 집합

- LR(0) 항목 집합의 정규 항목 집합은 C0로 표기, C0 = { CLOSURE( { [S′ →•S] ) } ∪ {GOTO (I, X) | I ∈ C0 , X ∈ V }

 

처음에 I0 = CLOSURE({S′ → •E}) 구하고

 

이미 구한 모든 상태 I에서 가능한 모든 기호 X 에 대해

GOTO(I, X)를 계산해서 새 집합이 나오면 그걸 새로운 상태로 추가

더 이상 새로운 상태가 안 나올 때까지 이걸 반복하면
→ 그때 모인 모든 상태들의 집합이 C0

 

예시

1) E → E + T 

2) E → T 

3) T → T * F 

4) T → F 

5) F → (E) 

6) F → id

에 대해 LR(0) 항목 집합의 정규 항목 집합

 

1. 증가 문법 만들기

S' -> E

1) E → E + T 

2) E → T 

3) T → T * F 

4) T → F 

5) F → (E) 

6) F → id

 

2. LR(0) 항목 집합의 정규 항목 집합은 다음과 같음

- I0 = CLOSURE( [ S' -> •E ]  ) = { [S' -> •E], [E →•E+T], [E →•T], [T →• T*F], [T →•F], [F →•(E)], [F →•id] }

- GOTO(I0, E) = I1 = CLOSURE([S′ → E•], [E → E•＋T]) = {[S′ → E•], [E → E•＋T]}

이런식으로 T, F, (, ), *, +, id 들을 I1, I2, .. 등 새로 생기는 모든 상태 I에 대해서 더 없을 때까지 구하면 됨