8. LR 구문 분석 8-1. LR 파서 8-2. LR(0) 아이템의 집합 8-3. SLR 파싱 테이블 구성 방법 8-4. CLR 파싱 테이블 구성 방법 8-5. LALR 파싱 테이블 구성 방법 8-6. 모호한 문법 8-7. 구문 분석기의 작성

8-1. LR 파서(p314|p296) LR 구문 분석 정의 결정적인 bottom-up 방법으로, LR은 입력 스트링을 왼쪽에서 오른쪽으로 읽어가며(Left to right scanner) 출력으로 우파스(Right parse)를 생성하기 때문에 붙여진 이름이다.

LR 파서의 특징 대부분의 프로그래밍 언어 인식 ② LL파서보다 일반적인 사용 ① LR은 모호하지 않은 CFG문법으로 쓰여진 대부분의 프로그래밍 언어 인식 ② LL파서보다 일반적인 사용 ③ 강력한 구문 분석 능력(에러가 발생하면 즉시 에러를 찾을 수 있음)  compiler의 파싱 알고리즘으로 LR 방법 많이 사용  그러나 실제 정의된 문법으로부터 parsing table 구성 어려움

Parser 제작 시스템 (PGS : Parser Generator System)

LR 파싱테이블 생성 방법 Simple LR(SLR ) - LR(0) items, FOLLOW Canonical LR(CLR ) - LR(1) items Lookahead LR(LALR ) - LR(1) items LR(0), Lookahead

LR 파서 정의 bottom-up 방법으로 주어진 스트링을 결정적으로 구문 분석하는 구문 분석기(syntax analyzer)를 말한다. Sm . 구문 분석기 파싱 테이블 a1 a2 … an$ 출력 입력 스택 스택 : S0X1S1 … XmSm (Si: 상태, Xi  V : 문법 기호) 버퍼 : a1a2…an$

LR Parser 형상(configuration) : 현재의 파싱 상태를 나타내는 표기법 (S0X1S1XmSm , aiai+1…an$) 1. shift ACTION[Sm , ai] = shift S (다음 상태) (S0X1S1…XmSm , aiai+1…an$) =>(S0X1S1…XmSmaiS , ai+1…an$) 입력 심벌을 스택에 넣고 다음 상태를 S로 만들기 위해 S도 역시 스택에 push한다는 의미 2. reduce ACTION[Sm, ai] = reduce A  , || = r , 2  r 만큼 pop off (S0X1S1 … XmSm , aiai+1 … an$) (S0X1S1 … Xm-rSm-r , aiai+1 … an$) 새로운 S GoTo(Sm-r , A) = S (S0X1S1 … Xm-rSm-rAS , aiai+1 … an$)

3. accept 4. error ACTION[Sm , ai] = accept ACTION[Sm, ai] = error Sm상태에서 입력 심벌 ai를 본 행동이 error라면 입력 스트링이 틀린 스트링이라는 의미이며, 그에 따른 작업을 하게 된다. 일반적으로 오류 복구 루틴을 불러 오류를 처리한다.

<예1> & <예2> 1. LIST LIST, ELEMENT 2. LIST ELEMENT 3. ELEMENT a 파싱 테이블: 파싱 과정: 스트링 a,a (0 , a, a$) (0 a 3 , , a$) (0 ELEMENT 2 , , a$) (0 LIST 1 , , a$) (0 LIST 1, 4 , a$) (0 LIST 1, 4 a 3 , $) (0 LIST 1, 4 ELEMENT 5 ,$) (0 LIST 1 , $) ACTION Table GOTO Table 심벌 상태 a , $ LIST ELEMENT S3 1 2 S4 acc r2 3 r3 4 5 r1 S3 R3 GOTO2 R2 GOTO1 S4 S3 R3 GOTO5 R1 GOTO1 accept

8-2. LR(0) 아이템의 집합(p319| p300) 정의8.2 LR(0) 아이템은 생성 규칙의 오른쪽에 dot symbol을 가진 생성 규칙이다. <예제 3> 생성 규칙의 형태가 AXYZ일 때, [A.XYZ], [AX.YZ], [AXY.Z], 그리고 [AXYZ.] 등은 모두 LR(0)아이템이다.

정의8.3 문법 G=(VN, VT, P, S)일 때, G의 추가된 문법은 G' = (VN ∪ {S'} , VT , P ∪ {S'→S} , S')이다. 여기서 S'가 새로운 시작 심벌이며, 새로운 생성 규칙 S'→S를 추가된 생성 규칙(augmented production)이라 부른다. 새로운 시작 생성 규칙 S'→S를 두는 이유는 주어진 입력 스트링을 인식할 시점을 규정하기 위한 것 즉, 생성규칙 S'→S로 reduce될 때 올바른 스트링으로 인식

정의8.4 LR(0) 아이템에서 점 심벌(dot symbol) 다음에 심벌이 있으면, 이 심벌을 마크 심벌(mark symbol)이라 부른다. 예) LR(0) 아이템 [A→ X.YZ]에서 마크 심벌은 Y이고 [A→ XYZ.]은 마크 심벌을 갖고 있지 않다.

정의8.5 LR(0) 아이템 [A→ α.β ]에서, α ≠ ε이면 kernel 아이템이라 하고 [A→.α]인 경우처럼 점 심벌이 처음에 있는 아이템을 closure 아이템이라 한다. 그러나 S'가 새로운 시작 심벌일 때, 아이템 [S' →.S]는 kernel 아이템이 된다. 또한 [A → α.]와 같이 생성 규칙 끝에 점 심벌이 있는 아이템을 reduce 아이템이라 말한다.

LR(0) 아이템 [A→ α.β ]의 의미 ① 이제까지 α로부터 유도될 수 있는 입력 스트링을 봄 ② 앞으로 β로부터 유도될 수 있는 스트링을 본다면, 생성규칙 A→αβ로 reduce 할 수 있다.

정의8.6 Viable prefix S ⇒ αAω ⇒ αβ1β2ω의 유도과정이 있을 때 αβ1이 된다. : Viable prefix는 주어진 문법으로부터 우측 유도과정 도중에 만들어지는 우문장 형태의 prefix *

정의8.7 만일 S ⇒ αAω ⇒ αβ1β2ω의 유도과정이 존재하고 ω∈ VT 이면, viable prefix αβ1에 관해 LR(0) 아이템 [A→β1.β2]를 valid하다고 말한다. : LR(0) 아이템 [A→β1.β2]가 valid하다는 의미는 parsing stack의 내용이 αβ1 일 때, shift할 것인가 또는 reduce할 것인가를 결정하게 해준다. : 만일 β2   이면 → 아직까지 handle이 stack top 부분에 있지 않은 것이기 때문에 shift 만일 β2 =  이면 → [A→β1 ]의 형태가 되어 β1이 handle이기 때문에 이 생성규칙으로 reduce * *

정의8.7 따라서 임의의 LR문법에서 모든 valid prefix에 관해 valid 한 LR(0) 아이템의 집합을 모으면, 주어진 스트링을 구문분석 할 수 있는 LR파서(파싱 Table)를 구성할 수 있다.

정의8.8 I를 정의된 문법의 아이템 집합이라 하면, I의 CLOSURE는 다음과 같이 정의된다. CLOSURE(I) = I ∪ { [B→. ] | [A → α.Bβ] ∈ CLOSURE(I) , B → ∈ P } : 마크 심벌이 [A → α.Bβ]와 같이 nonterminal인 경우, 이 nonterminal을 lhs로 갖는 LR(0) 아이템도 같은 집 합에 속해야 한다.

예5) 다음과 같은 문법이 주어졌을 때, CLOSURE를 구해보자 예5) 다음과 같은 문법이 주어졌을 때, CLOSURE를 구해보자. (p322| p303) S’ → G G → E=E | f E → E+T | T T → T*f | f CLOSURE({[S’→.G ]}) = {[S’→.G], [G →.E=E], [G → .f], [E→.E+T], [E→.T],[T→.T*f], [T→.f] } CLOSURE({[E→ E.+T]}) = {[E→ E.+T]}. :마크 심벌이 terminal일 때 CLOSURE는 자기자신

정의 8.9 GOTO 함수의 정의 마크 심벌을 파싱하여 이동한 다음 상태를 구하는 함수 여기서, I는 아이템의 집합이고 X ∈ V이다. GOTO(I, X) = CLOSURE( { [A → αX.β] | [A → α.Xβ] ∈I }) : 즉, I 상태에서 X를 파싱하여 이동한 상태는 마크 심벌이 X인 LR(0) item들을 모두 고려하여 점 심벌을 마크 심벌 다음으로 위치시킨 LR(0) item들의 CLOSURE 연산 결과

예6 ) 앞의 예5에서 주어진 문법에 대하여 GOTO함수 구하기 (p323| p304 ) S’ → G G → E=E | f E → E+T | T T → T*f | f (1) I = {[G → E.=E], [E→ E.+T]}일 때, GOTO(I, +) = CLOSURE({[E→ E+.T]}) = {[E→ E+.T], [T→ .T* f], [T→ .f]} (2) I = {[E→ .T], [T→ .T*f], [T→ .f]}일 때, GOTO(I, T) = CLOSURE({[E→ T.],[T→ T.*f]}) = {[E→ T.],[T→ T.*f]}

추가된 생성규칙(S'→S)에서부터 차례로 CLOSURE 함수와 GOTO 함수를 적용하여 LR(0)아이템 집합을 구할 수 있고, 이 원소로 갖는 집합을 canonical collection이라 부르고 C0으로 표기 C0 = { CLOSURE( {[S'→ .S]} ) } ∪ {GOTO(I, X) | I∈C0, X∈V} 예 7) p324| p305 예 8) p326| p306 예 9) p327| p307

주어진 문법으로부터 C0 구성 방법( Alg 8.2,p323| p305) 먼저 시작 상태는 추가된 생성 규칙의 LR(0)아이템 [S'→ .S]의 CLOSURE  이 상태가 I0 상태 GOTO 함수를 이용하여 다음 상태를 구하여 I1 상태 이와 같은 과정으로 각 마크 심벌에 따라 GOTO 함수를 적용하여 상태를 만들어 나가며, 새로 만든 상태가 기존의 상태와 다르면 새로운 상태로 추가 각 상태에서 새로운 상태가 더 이상 만들어지지 않을 때까지 계속 하나의 상태는 LR(0)아이템 집합이고 , C0는 상태들의 집합 C0 = { I0, I1, … In }

8-3. SLR 파싱 테이블 구성 방법(p328| p308) SLR이란 Simple LR C0와 FOLLOW 정보를 이용하여 파싱 테이블을 구성하는 방법 C0 = { I0, I1, , In } 파싱 테이블의 상태 i는 Ii로부터 구성 파싱 테이블의 크기 : (상태수)  (문법 심벌의 개수) |C0|  ( |V| + 1) 파싱 테이블은 2차원 배열 M[ i, a ]로 구성 상태번호, 문법 심벌

SLR 파싱 테이블을 작성하는 방법 (p328|p308~ ) 만일 LR(0) 아이템 [A.a]가 상태 i에 있고 a가 terminal심벌이면 shift 행동이므로, i 상태에서 마크 심벌 a를 보고 j 상태로 가는 GOTO 함수가 존재한다면, ACTION 테이블의 상태 i와 심벌 a가 만나는 곳에 상태 번호 j를 적는다. if [A  .a]  Ii and GOTO(Ii, a) = Ij then M[i, a] := shift j ;

아이템 [A .]가 상태 i에 있다면, reduce 행동이므로 nonterminal A의 FOLLOW를 구하여 ACTION테이블의 상태 i와 FOLLOW 심벌이 만나는 곳에 reduce 생성 규칙 번호를 적는다. if [A  .]  Ii then for each a  FOLLOW(A) do M[i,a] := reduce A  상태 i에 LR(0) 아이템 [S'S.]가 있다면 accept 행동이므로 ACTION 테이블의 상태 i 와 $심벌이 만나는 곳에 accept를 적는다. if [S'S.]  Ii then M[i, $] := accept

if [A  .B]  Ii and GOTO(Ii, B) = Ij then M[i, B] := j; 만일 LR(0)아이템 [A.B]가 상태 i 에 있고 B가 nonterminal 심벌일 때, 상태 i 에서 마크 심벌 B를 보고 상태 j로 가는 GOTO 함수가 존재한다면 GOTO 테이블의 상태 i 와 nonterminal 심벌 B가 만나는 곳에 상태 번호 j를 적는다. if [A  .B]  Ii and GOTO(Ii, B) = Ij then M[i, B] := j; 이렇게 해서 정의되지 않은 파싱 테이블의 엔트리는 모두 error가 되며, 첨가된 생성 규칙의 LR(0) 아이템 [S' .S]를 포함하는 상태가 초기 상태가 된다.

예제 10) SLR 파싱 테이블 (p329|p309~) 1. E  E + T 2. E  T 3. T  T * F 4. T  F 5. F  (E) 6. F  id (1) 추가된 생성 규칙 : 0. S'  E 1. E E + T 2. E  T 3. T  T * F 4. T  F 5. F  (E) 6. F  id

(2) C0 및 GOTO그래프(p330| p310) I0 I1 I6 I9 [S’  .E] [E.E+T] [E.T] [T.T*F] [T.F] [F.(E) [F.id] E [S’E.] [EE.+T] + [EE+.T] [T.T*F] [T.F] [F.(E)] [F.id] T [EE+T.] [TT.*F] + T I2 [ET.] [TT.*F] * T * I3 I7 I10 F F [TF.] [TT*.F] [F.(E)] [F.id] F [TT*F.] I4 F ( id [F (.E) ] [E .E+T] [E .T] [T .T*F] [T .F] [F .(E)] [F .id] ( ( I8 I11 E [F(E.)] [EE.+T] ( [F(E). ) I5 id id id [Fid.]

FOLLOW의 계산 FOLLOW(E) = { $, +, ) } FOLLOW(T) = { *, +, ), $ } FOLLOW(F) = { *, +, ), $ } (4) 파싱 테이블

(5) 스트링 a*a+a를 위한 구문 분석 과정(p332|p312) 단계 스 택 입력 심벌 구문 분석 내용 출력 a*a+a$ shift 5 1 0a5 * a+a$ reduce 6 6 2 0F GOTO 3 3 0F3 reduce 4 4 0T GOTO 2 5 0T2 shift 7 0T2*7 7 0T2*7a5 +a$ 8 0T2*7F GOTO 10 9 0T2*7F10 reduce 3 10 11 reduce 2 12 0E GOTO 1 13 0E1 shift 6 14 0E1+6 a$ 15 0E1+6a5 $ 16 0E1+6F 17 0E1+6F3 18 0E1+6T GOTO 9 19 0E1+6T9 reduce 1 20 21 accept

정의 8.10 8-4. CLR 파싱 테이블 구성 방법(p334| p313) LR(0)아이템에 lookahead정보를 첨가한 것이 LR(1)아이템이라고 한다. LR(1)아이템은 [A., a]의 형태를 이루며 여기서 AP이고 aVT{$}이다. 첫 번째 부분 A.를 core라고 부르며 LR(0) 아이템과 같은 의미를 갖는다. 두 번째 부분 a를 아이템의 lookahead라 부르며, reduce 아이템일 때 그 심벌에 대하여 reduce 행동을 하는 것을 뜻한다.

정의 8.11 CLR 파싱 테이블 작성 방법 I가 LR(1) 아이템의 집합이라면, CLOSURE(I) = I  {[B., b] | [A.B, a]  CLOSURE(I), B  P, b  FIRST(a)}이다. CLR 파싱 테이블 작성 방법 만일 LR(1) 아이템 [A.a, a]가 상태 i에 있고 a가 terminal이면 shift 행동이므로, i 상태에서 마크 심벌 a를 보고 j상태로 가는 GOTO 함수가 존재한다면 ACTION 테이블의 상태 i와 심벌 a가 만나는 곳에 상태 번호 j를 적는다. if [A.a, u]Ii and GOTO(Ii, a) = Ij then M[i, a] := shift j.

만일 LR(1) 아이템[A., a]가 상태 i에 있다면 reduce 행동이므로, ACTION테이블의 상태 i와 lookahead 심벌 a가 만나는 곳에 reduce 생성 규칙 번호를 적는다. if [A., u]  Ii then M[i, u] := reduce A. 만일 LR(1) 아이템[S’S.,$]가 상태 i에 있다면 accept행동이므로, ACTION 테이블의 상태 i와 $심벌이 만나는 곳에 accept를 적는다. if [S’S.,$]  Ii then M[I, $] := accept. 만일 LR(1) 아이템 [A.B, a]가 상태 i에 있고 B가 nonterminal일 때, i 상태에서 마크 심벌 B를 보고 j 상태로 가는 GOTO 함수가 존재한다면 GOTO 테이블의 상태 i와 심벌 B가 만나는 곳에 상태 번호 j를 적는다. if [A.B, u]  Ii and GOTO(Ii, B) = Ii then M[i,B] := j.

8-5. LALR 파싱 테이블 구성 방법 정의 LookAhead LR 방법으로 아이템의 lookahead 정보를 이용하기 때문에 SLR방법 보다 훨씬 강력하고, 파싱 테이블의 크기는 CLR에서 core가 같은 아이템들을 한 데 묶음으로써 SLR와 같은 크기로 구성 가능 모호하지 않은 context-free 문법으로 표현된 거의 모든 언어를 인식할 수 있기 때문에 요즈음 대부분의 파서 제작 시스템에서 사용된다.

LALR 파싱 테이블 작성 방법 C1에서 작성하는 방법 같은 core를 가진 LR(1) 아이템 집합들을 한 개의 LR(0)아이템 집합으로 만들고, 각 아이템의 lookahead는 이들 LR(1)아이템의 lookahead의 합집합으로 구성하는 방법 예를 들면 C1의 Ii와 Ij와 같은 core를 갖고 있다면, Iij상태로 통합되어 한 개의 상태로 된다. 이 때, lookahead는 두 아이템이 갖고 있는 lookahead의 합집합이 된다. [A.,a] … [A.,b] [A.,a/b] Ii Ij Iij

8-6. 모호한 문법(p350|p328 ~ ) 정의 모호한 문법에서 구문 분석 행동의 순위 shift-reduce 충돌인 경우 모든 모호한 문법은 LR문법이 될 수 없다. 파싱 테이블 작성시 항상 shift-reduce충돌이나 reduce-reduce충돌을 야기 모호한 문법에서 구문 분석 행동의 순위 shift-reduce 충돌인 경우 reduce되는 생성 규칙과 입력 심벌의 순위를 비교하여 결정하는데, 생성 규칙의 순위가 높으면 reduce를 그렇지 않으면 shift를 선택하는 것이 일반적이다. 같은 순위인 경우에는 결합 법칙을 이용하는데, 좌측 결합을 만족하면 reduce를, 우측 결합을 만족하면 shift를 선택한다.

Reduce-reduce 충돌인 경우 reduce되는 생성 규칙들의 순위를 비교하여 어느 생성 규칙을 reduce할 것인가를 결정하는데 순위가 높은 것을 선택 생성 규칙의 순위는 그 생성 규칙 내에 있는 terminal 심벌로 결정할 수 있으며, 또는 YACC에서와 같이 특별히 명시하는 방법이 있다. PGS의 입력 명세서에서 먼저 기술되는 생성 규칙이 순위가 높도록 정할 수 있다.

8-7. 구문 분석기의 작성(p359|p339~ ) 기본 구성 파싱 테이블과 구문분석을 수행하는 실행 루틴으로 구성 파싱 테이블은 2차원 배열로 행은 terminal 심벌과 nonterminal 심벌이며, 열은 상태 번호가 된다. 구문 분석기의 행동은 행과 열이 만나는 곳에 정의 shift되는 상태는 양의 정수 값으로, reduce되는 생성 규칙 번호는 음의 정수 값으로 나타낸다. 그리고 accept는 추가된 생성 규칙 번호로 reduce될 때이며, error는 0으로 표시된다.

특정 언어의 구문 분석기 구현 1. 문법 고안 2. PGS를 이용 파싱 테이블 작성 1. 문법 고안 2. PGS를 이용 파싱 테이블 작성 파싱 테이블을 참조하여 구문분석을 수행하는 실행 루틴으로 작성 문법 PGS 토큰 스트림 파싱 결과 파싱 테이블 구동 루틴