제 7 장  LR 파서

제 7 장 LR 파서 상향식 파싱 기법으로 LR 속성을 가진 문맥-자유 문법을 효율적으로 파싱하는 파서를 LR 파서라 한다.

7.1 LR 파싱 개념 LR(k) 파서에서 L은 입력 스트링을 왼쪽에서 오른쪽으로 읽는다는 의미이고, R은 우단 유도를 역으로 구성한다는 의미이다. 또한 k는 입력 스트링에서 미리보기하는 심볼의 수이다. 이러한 LR 파서에는 여러 특성이 있다.

파싱 테이블에는 이동-환원 파싱 알고리즘에서 이용하는 정보인 이동과 환원을 결정하는 파싱 정보가 들어있다. 파서는 각각 다른 방법으로 얻은 정보로 자신의 파싱 테이블을 구성한다. 단순 LR 파서는 LR(0) 아이텀과 FOLLOW 정보를 사용하여 파싱 테이블을 구성한다. 캐노니컬 LR 파서는 LR(1) 아이텀을 사용하여 파싱 테이블을 구성한다. LR(1) 아이텀은 LR(0) 아이텀과 미리보기 심볼로 만든다. 미리보기 LR 파서는 케노니컬 LR 파싱 테이블을 재구성한다.

LR 파서 모델 그림 7.1 LR 파서의 일반적인 모델

7.2 LR 파싱 테이블 LR 파싱 테이블은 LR 파싱 루틴이 제어하는 테이블이 두 개 있는데 각각 액션(action) 테이블과 점프(goto) 테이블이다. 액션 테이블의 열에는 상태 번호가 있고 행에는 프로그램에서 사용하는 터미널 심볼들 점프 테이블의 열에는 상태 번호가 있고 행에는 문법의 생성 규칙에서 사용하는 넌터미널 심볼들 액션 테이블에 있는 이동과 환원 액션 정보는 아래 형식                      이동 정보: (이동, 상태번호)                      환원 정보: (환원, 생성규칙)

LR 파싱 테이블 구조 그림 7.8 LR 파싱 테이블의 구조

7.3 LR 파싱 드라이버 LR 파싱 드라이버는 LR 파싱 테이블 내용을 아래와 같이 이용한다. <이동, 상태번호>   action(상태번호, 입력 터미널 심볼)⊢액션(이동, 환원 혹은 수락) <이동, 상태번호> 입력 스트링의 맨 앞에 있는 터미널 심볼을 스택으로 이동하고 다음 터미널 심볼과 대응할 상태번호를 스택에 넣으라는 의미 <환원, 생성규칙번호> 스택의 톱에 있는 핸들을 생성규칙 번호에 해당하는 생성규칙의 넌터미널로 환원하라는 의미 점프테이블의 상태번호는 핸들이 넌터미널로 환원한 후의 새로운 상태번호

일반적인 LR 파서 구성 (#s0 X1 s1 X2 ....... Xm sm : ai ai+1 ....... an ↲) 스택의 #는 스택의 시작을 나타내는 기호 입력 스트링의 ↲는 스트링의 맨 마지막 기호 스택 속의 Si 는 상태번호이며 문법 심볼 Xi 는 Xi ∈ V 로 넌터미널과 터미널 중의 하나 입력 스트링을 구성하는 터미널 a1, a2......., an 는 토큰 스트림 ai 는 맨 앞에 있는 현재 읽혀질 터미널 심볼로 스택의 톱에 있는 심볼과 대응하고 ai+1 .......  an↲는 아직 읽혀지지 않은 프로그램 문장의 터미널 심볼

예 7.1 리스트를 생성하는 아래의 간단한 문법 G 에 대한 LR 파싱 테이블을 살펴보고 이 파싱 테이블에 의한 파싱 과정을 살펴보자.      G: L → L , E  | E           E → a 이 문법 다시 쓸 수 있다. 번호는 각 생성규칙 번호를 의미한다.        G: 1. L → L , E            2. L → E            3. E → a

액션 테이블 점프 테이블 a , ↲ L E 상 태 번 호 <이동,3> 1 2 <이동,4>       액션 테이블 점프 테이블 a , ↲ L E 상 태 번 호 <이동,3>   1 2 <이동,4> <수락> <환원,2> 3 <환원,3> 4 5 <환원,1> 그림 7.3 리스트를 생성하는 문법 G 에 대한 LR 파싱 테이블

리스트 입력 a,a,a↲의 파싱 과정 예 (#0 : a,a,a↲)⊢ 이동 3 (#0a3 : ,a,a↲)⊢ 환원 3                (#0E2             :       ,a,a↲)⊢ 환원 2 (#0L1              :       ,a,a↲)⊢ 이동 4          (#0L1,4           :       a,a↲)⊢ 이동 3          (#0L1,4a3       :          ,a↲)⊢ 환원 3 (#0L1,4E5       :          ,a↲)⊢ 환원 1                (#0L1             :         ,a↲)⊢ 이동 4                (#0L1,4          :           a↲)⊢ 이동 3                (#0L1,4a3       :            ↲)⊢ 환원 3                (#0L1,4E5       :           ↲)⊢ 환원 1                (#0L1             :           ↲)⊢ 수락

예 7.2 산술 수식을 생성하는 아래의 간단한 문법 G 에 대하여 LR 파싱 테이블을 살펴보고 파싱 테이블에 의하여 산술 수식 a + a * a↲를 파싱하는 과정을 살펴보자.             G: E  → E + T | T                  T  → T * F  | F                  F  → ( E )    | a 이 문법을 아래와 같이 다시 쓴다.             G: 1. E  → E + T                     2.  E  → T                  3. T  → T * F                  4. T  → F                  5. F  → ( E )                  6. F  → a

그림 7.4 산술 수식을 생성하는 간단한 문법 G 에 대한 LR 파싱 테이블 상태 액션 테이블 점프 테이블 a + * ( ) ↲ E T F s5   s4 1 2 3 s6 acc r2 s7 r4 4 8 5 r6 6 9 7 10 s11 r1 r3 11 r5 그림 7.4 산술 수식을 생성하는 간단한 문법 G 에 대한 LR 파싱 테이블

입력 스트링 a + a * a↲를 파싱하면 (#0 : a +a * a↲)⊢ 이동 5 (#0a5 : +a * a↲)⊢ 환원 6                     (#0F3                  :     +a * a↲)⊢ 환원 4                     (#0T2                 :      +a * a↲)⊢ 환원 2                     (#0E1                 :      +a * a↲)⊢ 이동 6                     (#0E1+6               :      a * a↲)⊢ 이동 5 (#0E1+6a5             :      * a↲)⊢ 환원 6                     (#0E1+6F3             :     * a↲)⊢ 환원 4                     (#0E1+6T9             :     * a↲)⊢ 이동 7                     (#0E1+6T9*7          :       a↲)⊢ 이동 5                     (#0E1+6T9*7a5      :     ↲)⊢ 환원 6                     (#0E1+6T9*7F10    :     ↲)⊢ 환원 3                     (#0E1+6T9             :     ↲)⊢ 환원 1                     (#0E1                     :     ↲)⊢ 수락

LR 파싱 드라이버 function LR_Parsing_Driver( ) {    {     input: token sequence, augmented grammar, stack and the parsing table;     output: parsing tree;         /*     초기 스택 상태와 입력 큐 상태, (#s0             :   ai   ai+1 .......  an ↲)     */                   /*     파싱이 진행 중인 스택과 입력 큐 상태, (#s0 X1 s1 X2  .......  Xm sm        :   ai   ai+1 .......  an ↲); */ /*     스택 톱 심볼(상태번호)와 입력 심볼을 아래처럼 비교한다   */ /*   이동 액션이면 스택 톱에 입력 심볼을 이동하고 상태번호를 넣는다   */ if (ACTION(sm, ai ) == "shift s ")  (#s0 X1 s1 X2  .......  Xm sm ai s       :   ai+1 .......  an ↲); /* 환원 액션이면 스택에서 상태번호를 포함하여 β를 제거한다   */ if (ACTION(sm, ai ) == "reduce  A →β")          {                                              (#s0 X1 s1 X2  .......  Xm-r sm-r       :   ai ai+1 .......  an ↲)                        (#s0 X1 s1 X2  .......  Xm-r sm-r As   :   ai ai+1 .......  an ↲)  /*   (r = |β|, GOTO(sm-r, A) = s)  */          } if (ACTION(sm, ai) == "accept") printf ("parsing is completed normally"); if (ACTION(sm, ai) == "error") ERROR( );     }

실습 7. 1 그림 7. 4의 파싱 테이블과 아래 문법을 이용하여 산술 수식 a 실습 7.1 그림 7.4의 파싱 테이블과 아래 문법을 이용하여 산술 수식 a * b + c을 LR 파싱하는 과정을 보이시오(문법에서 터미널 심볼 b와 c는 그림 7.4의 파싱 테이블에서 심볼 a와 같이 취급한다).  G:  1. E → E + E        2. E → T        3. T → T * F       4. T → F       5. F → ( E )       6. F → a|b|c

실습 7.2 그림 7.4의 파싱 테이블과 아래 문법을 이용하여 산술 수식 a + b ( c을 LR 파싱하는 과정을 보이시오(문법에서 터미널 심볼 b와 c는 그림 7.4의 파싱 테이블에서 심볼 a와 같이 취급한다).             G:  1. E  → E + T                  2.  E  → T                 3. T  → T * F                  4. T  → F                  5. F  → ( E )                  6. F  → a | b | c

7.5 LR 파싱 테이블 만들기 아래의 문법을 살펴보자. G: 1. E → TE′ 2. E′ → +TE′ 3. E′ → ε           4.  T → FT′                                                          5.  T′ → *FT′           6.  T′ → ε           7.  F → (E)           8.  F → a

7.4.1 LR(0) 아이텀의 캐노니컬 모음 구하기 LR(0) 아이텀 모음을 구하려면 아래와 같이 첨가 문법과 두 함수가  필요하다. 첨가 문법 closure 함수 goto 함수

정의 7.1 LR(0) 아이텀은 생성 규칙의 오른쪽 어떤 위치에 점(·)을 찍은 생성 규칙이다. LR(0) 아이텀의 정의에 따라 A → XYZ  ∈ P 이면 아래는 각각은 LR(0) 아이텀이다.                                  [A →   ·XYZ]                                  [A →  X ·YZ]                                  [A →  XY ·Z]                                  [A →  XYZ ·]

아이텀 A → ε 는 [A →  · ] 이다. 점 뒤에 있는 심볼을 마크 심볼이라하고, A가 첨가 문법의 시작 심볼(즉, A = S ′) 이고,  α≠ ε 이면 [A → α·β] 아이텀을 커널 아이텀이라 한다.  또한 closure  연산을 수행한 결과인 [A → ·α] 아이텀을 closure 아이텀이라 한다. 이 때 [A → α·β]는 α에서 유도되는 입력 스트링을 방금 모두 보았다는 것이고, 다음 보는 심볼이 β에서 유도되는 입력 스트링이면 생성규칙 A → αβ· 에 의해 환원될 수 있다.

정의 7.2 첨가 문법은 아래와 같은 특성으로 주어진 문법 G = (VN, VT, P, S)에서, G 의 넌터미널이 아닌 새로운 시작 넌터미널 심볼 S ′을 G ′ = (VN ∪{S ′}, VT, P∪{S ′→ S}, S ′) 와 같이 문법 G 에 추가한 새로운 문법이다. 1. VN 은 넌터미널 심볼의 유한 집합이다. 2. VT 은 터미널 심볼의 유한 집합으로 VN ∩VT =∅, VN ∪VT = V 이다. V 는 알파벳 집합이다. 3. P 는 생성규칙의 유한 집합으로 아래의 형식을 가지는데 α는 널이 아 니다. α→ β (α∈V+, β∈V * ) 4. S ′는 시작 넌터미널 심볼로서 S ′ ∈VN

정의 7. 3 어떤 시작 넌터미널부터 우단유도를 수행하여 S ⇒ 정의 7.3 어떤 시작 넌터미널부터 우단유도를 수행하여 S ⇒*αAω ⇒αβ1β2ω 와 같은 유도가 발생하면 문장형식 αβ1β2ω에서 스트링 αβ1 를 활성 접두사라 한다. 예 7.3 산술 수식을 생성하는 아래 문법 G에 대해 활성 접두사를 알아보자.             G:  E  → E + T | T                 T  → T * F  | F                  F  → ( E )   | a 정의에 따르면 이 문법은 우단 유도를 통하여 E ⇒* T * F 에서 T * 가 활 성 접두사이다.

정의 7.4 closure 함수는 아래와 같이 새로운 아이텀을 생성한다.          closure(I ) = I ∪ {B → ·γ | A → α·Bβ∈closure(I), B → γ∈P}

closure를 계산하는 함수 function CLOSURE( ) {    {     input: augmented grammar G′ = (VN ∪{S′}, VT, P∪{S′→S}, S′) and a item I;     output: new items; closure = I ;          while (change) {        /*  새로운 아이텀이 생기면 아이텀이 더 이상 없을 때까지 계속 추가한다.   */                if  ( A →α·Bβ∈closure &&  B → ·γ∈  P)                       if  (B → ·γ ∉ closure) closure = closure ∪ {B → ·γ};            }    }

closure 구하는 예 아래 산술 수식을 표현하는 첨가문법에서 아래  산술 수식을 표현하는 첨가문법에서                          E '→  E                              E →  E + T | T                                                            T →  T * F | F                              F → ( E ) | a I 가 한 아이텀 {[E ' → · E]}의 집합이면 closure (I) 는 아래와 같이 구한다. closure ([E ′→ · E ])에서 점( ·) 바로 오른쪽에 있는 심볼을 들여다보면 알고리즘의 A →α·Bβ에서 B 에 해당하는 넌터미널 E 가 있다.  이 넌터미널 E 은 B → ·γ 에 해당하는 생성 규칙이므로 아직 생성할 심볼이 있다는 의미이다. 그러므로 이 넌터미널 E 에서 closure를 다시 적용하여 아이텀을 새로 생성하여 아이텀 집합 I 에 추가한다.

closure 구하는 예 그러면 아래와 같은 집합이 만들어진다. closure(I) = closure ( [E ′→ · E ])                   = { [E ′→ · E ], [E → · E + T ], [E → · T ], [T → · T  * F ],                         [T → · F ], [F → · ( E ) ], [F → · a ] } 그러나 closure ( [E → E · + T ]) 인 경우에는 점( ·) 바로 오른쪽에 있는 심 볼 + 가 B → ·γ 와 같은 생성 규칙이 없으므로 결과는 아래와 같다. closure(I) = closure ( [E → E · + T ]) = { [E → E · + T ] }

정의 7.5 goto 함수는 아래와 같이 새로운 아이텀을 생성한다.              goto(I, X ) = closure ([A → αX·β] | [A → α·Xβ]∈I }) goto 함수는  한 아이텀에서 이미 본 마크 심볼이 넌터미널 심볼이면, 마크 심볼을 뛰어 넘어 그 다음 심볼을 미리보기하여 새로운 closure 를 계산하는 함수이다. [A → α·Xβ]와 같은 아이텀에서 X를 뛰어 넘어 [A → αX·β] 아이텀에 대하여  다시 closure 를 계산한다.

goto 구하는 예 첨가 문법의 한 아이텀 집합 I = {[E ′ → E · ], [E → E · + T ]} 에서 goto 함수를 살펴본다. goto(I, + ) = closure ([E → E + ·T]) 이다. closure ([E → E + ·T ]) 는 새로운 T 를 보고 있기 때문에   closure 함수 정의에 따라 T 에 대하여 새로운 closure 를 구한다. closure ([E → E + ·T ]) 는 아래와 같다.     goto(I, + ) =   closure ([E → E + · T ])          = {[E → E + ·T], [T → ·T * F], [T → ·F], [F → ·( E )], [F → · a]

정의 7.6 캐노니컬 모음은 아래와 같이 계산한다.        C = {closure ({[ S ' → ·S ]})} ∪{ goto (I, X ) | I∈C, X ∈V } 캐노니컬 모음은 첨가 문법에 있는 시작 심볼의 커널 아이텀에서 시작하여 closure 를 계산하여 만든 closure 집합의 각 아이텀에 대하여  goto 함수를 수행하여 만드는 새로운 아이텀을 추가한다.

캐노니컬 모음 구하는 예 I 가 두 개의 아이텀 {[E → E · ], [E → E · + T ] } 의 집합이면, 각 아이텀에서 점(·)의 바로 오른쪽에 + 가 있는 아이텀 I 를 검사함으로서 goto (I, +) 를 계산한다. 이때 아이텀 [E → E ·] 는 + 가 없기 때문에 해당 아이텀이 아니지만 [E  → E · + T] 는 이러한 아이텀에 해당한다. 그러므로  + 를 뛰어 넘어 점을 찍으면 아이텀 [E  →  E + · T ]를 구할 수 있다. 그러면 다시 아이텀 [E  →  E + · T ]를 가지고 closure([E  →  E + · T ]) 를 계산한다. 그러면 goto(I, +) 는 아래와 같이 여러 개의 아이텀을 만든다.

이 경우는 goto (I, +) 에 대해서만 만들어진 결과이다.                         E → E + · T                         T →  · T * F                         T →  · F                         F  → · ( E )                         F →  · a 이 경우는 goto (I, +) 에 대해서만 만들어진 결과이다. 그러나 위의 여러 아이텀 각각에서 다시 goto 함수를 수행한다. 예를 들어, [T →  · T * F]에서는 goto (I, T)를 구할 수 있고  [F  → · ( E )]에서는 goto (I, ()를 구할 수 있다. 그러면 아이텀 [F  → ( · E )]를 가지고 closure([F  → ( · E )]) 를 계산하여 새로운 아이텀 모음, Ii을(i = 0, 1,..., n-1) 구한다. 단 I ≠ Ii 이다.

첨가 문법에 대한 LR(0) 아이텀의 캐노니컬 모음, C, 을 구하는 함수 function Construction of Canonical Collection of Set-of-Items ( ) {        input: augmented grammar G ′ = (VN ∪{S ′}, VT, P∪{S ′→ S}, S ′)                     and kernel item [ S ' → ·S ];                          output: Set-of-Items;                          C = closure ([S '  → · S ]);                          for (more sets of items can be added to C) {     for (each I∈C)           if (goto(I, X) ≠∅ && goto(I, X) ∉ C)                        C =  C ∪ goto(I, X);    } }

LR(0) 아이텀의 집합에 대한 캐노니컬 모음 구하기      G :   E →  E + T | T                                           T →  T * F | F             F → ( E ) | a 이 문법에 시작 생성 규칙 E '→  E 을 추가하면 아래의 첨가 문법으로 변형한다.   (0) E ‘ →  E            (1) E →  E + T            (2) E →  T                                          (3) T →  T * F            (4) T →  F            (5) F → ( E )            (6) F → a

이 첨가 문법에 대한 아이텀 집합 구하기 단계1. 커널 아이텀 [E ' → · E] 에 대하여, E ' → α· Eβ ∈closure(I ) 이고, · E 와 같이 점(·) 바로 오른쪽에 있는 E는 다시 생성규칙 있어서 E → E + T∈P 이고 E → T∈P 이므로, B → ·γ 에 해당하는 아이텀은 아래와 같다. 이 두 아이텀은 아이텀들의 집합인 I0에 포함한다.                [E  → · E + T]                [E  → · T] 또한 같은 방법으로 · T 와 같이 점(·) 바로 오른쪽에 있는 T는 다시 생성규칙이 있어서 T  → T  * F∈P 이고 T  → F∈P 이므로, B → ·γ 에 해당하는 아이텀은 아래와 같다. 이 두 아이텀도 마찬가지로 I0에 포함한다.               [T  → · T  * F]               [T  → · F]

이 첨가 문법에 대한 아이텀 집합 구하기 단계 1. F 에 대해서도 적용하면 다음 아이텀이 I0에 포함한다.               [F  → · ( E )]               [F  → · a] 더 이상 A → α·Bβ 에 해당하는 아이텀이 없어서 추가할 것이 없으므로 closure(I )는 아래와 같은 아이텀들의 집합 I0 를 구한다. I0 : E ' → · E       E  → · E + T       E  → · T       T  → · T  * F       T  → · F       F  → · ( E )       F  → · a

단계 2 I0 의 아이텀 중에서 · E에 대한 아이텀 [ E ' → · E]와 [E  → · E + T] 를 적용하면 아래와 같다.          goto(I0, E) =  closure ([E ' → E ·] | [E ' → · E]∈ I0})          goto(I0, E) =  closure ([E  → E · + T] | [E  → · E + T]∈ I0}) goto(I0, E)의 결과인 새로운 아이텀 집합 I1 는 아래와 같다. I1 : E ' → E ·      E  → E · + T

단계 3 같은 방법으로 다음과 같다.          goto(I0, T) =  closure ([E  → T ·] | [E  → · T]∈ I0})          goto(I0, T) =  closure ([T  → T · * F] | [ T  → · T  * F]∈ I0}) goto(I0, T)의 결과인 새로운 아이텀 집합 I2 는 아래와 같다. I2 : E  → T ·       T  → T · * F

단계 4 I0 의 아직 수행하지 않은 아이텀에 적용          goto(I0, F) =  closure ([T  → F ·] | [ T  → · F]∈ I0}) goto(I0, F)의 결과인 새로운 아이텀 집합 I3은 아래와 같다. I3 : T  → F ·

단계 5 I0 의 아직 수행하지 않은 아이텀에 적용          goto(I0, F) =  closure ([F  → ( · E )] | [F  → · ( E )]∈ I0}) 이 경우에는 I0에서와 같은 경우이므로 아래 아이텀들을 반복하여 추가한다.      [E  → · T]      [T  → · T  * F]      [T  → · F]      [F  → · ( E )]      [F  → · a]

새로운 아이텀 집합 I4 는 아래와 같다. I4 : F  → ( · E )       E  → · E + T       E  → · T       T  → · T  * F       T  → · F       F  → · ( E )       F  → · a

단계 6 I0 의 아직 수행하지 않은 아이텀에 적용          goto(I0, F) =  closure ([F  →  a · ] | [F  → · a]∈ I0}) goto(I0, a)의 결과인 새로운 아이텀 집합 I5 는 아래와 같다. I5 : F  → a ·

단계 7 I1 아이텀 집합에서[E → E · + T]에 대해서만 goto 함수를 적용          goto(I1, +) =  closure ([ E  → E + · T ] | [ E  → E · + T]∈ I1}) goto(I1, +)의 결과인 새로운 아이텀 집합 I6 은 아래와 같다. I6 : E  → E + · T       T  → · T  * F       T  → · F       F  → · ( E )       F  → · a

단계 8 I2 아이텀 집합에서 [T → T · * F]에 대해서만 goto 함수를 적용          goto(I2, *) =  closure ([ T  → T * · F ] | [ T  → T · * F]∈ I2}) goto(I2, *)의 결과인 새로운 아이텀 집합 I7 은 아래와 같다. I7 : T  →  T  * · F       F  → · ( E )       F  → · a

단계 9 I4 아이텀 집합에서 적용          goto(I4, E) =  closure ([F  → ( E · )] | [ F  → ( · E )]∈ I4})          goto(I4, E) =  closure ([E → E · + T ] | [ E  → · E + T]∈ I4}) goto(I4, E )의 결과인 새로운 아이텀 집합 I8 은 아래와 같다. I8 : F  → ( E · )      E → E · + T

단계 10 I6 아이텀 집합에서 적용          goto(I6, T) =  closure ([E  → E + T · ] | [E  → E + · T]∈ I6})          goto(I6, T) =  closure ([T → T · * F] | [T  → · T  * F]∈ I4}) goto(I6, T )의 결과인 새로운 아이텀 집합 I9 는 아래와 같다. I9 : E  → E + T ·      T  → T · * F

단계 11 I7 아이텀 집합에서 적용          goto(I7, F) =  closure ([T  → T * F · ] | [T  →  T  * · F]∈ I7}) goto(I7, F)의 결과인 새로운 아이텀 집합 I10은 아래와 같다. I10 : T  → T * F ·

단계 12 I8 아이텀 집합에서 적용          goto(I8, )) =  closure ([F  → ( E ) · ] | [F  → ( E · )]∈ I8}) goto(I8, ) )의 결과인 새로운 아이텀 집합 I11은 아래와 같다. I11 : F  → ( E ) ·

캐노니컬 LR(0) 아이텀 모음과 상태 전이 오토마타

7.4.2 LR(0) 아이텀에서 단순 LR 파싱 테이블 구성 캐노니컬 아이텀 모음은 어떤 스트링 뒤에 올 심볼이 무엇인지를 알려주는 것이 목적이므로 이 아이텀들로부터 파싱에 필요한 정보를 테이블로 구성한다.

7.4.2.1 이동 액션 만들기 LR(0) 아이텀 집합의 각 아이텀에서 점 바로 뒤에 있는 심볼이 터미널인 [A → α·aβ] 형식을 찾는다. 아이텀이 이 형식을 가지며, 동시에 점 바로 뒤의 심볼에 대하여 이 아이텀 집합(Ii) 에서 goto (Ii, a) = Ij 와 같이 다른 아이텀 집합(Ij)으로 전이가 있으면 ACTION (i, a) =  "이동 j " 를 넣는다.  이 의미는 생성규칙 A → αaβ에서 오른쪽 스트링 αaβ이 A 로 환원할 수 있도록 αaβ를 핸들로 만들기 위해 a 를 스택으로 이동하라는 것이다.

아이텀 집합의 캐노니컬 모음에서 예 아이텀 집합에서 [A → α·aβ] 형식을 찾는다. 그러면 I0에서 아이텀 F → · (E) 와 F →  · a 가 이 형식에 해당하며, goto (I0, ( ) = I4이며,  goto (I0, a) = I5이다. 터미널 심볼 ( 와 a 에 대한 액션 테이블에 들어갈 내용은 아래와 같다. ACTION(0, ( ) = “이동, 상태번호 4” ACTION(0, a ) = “이동, 상태번호 5”

각 아이텀 집합 I4, I6, I7, I8, I9 에서 이 형식에 해당하는 아이텀은  아래와 같다. I4 : F  → · ( E )       F  → · a I6 : F  → · ( E )        F  → · a I7 : F  → · ( E )       F  → · a I8 : F  → ( E · )        E → E · + T I9 : T  → T · * F

액션 테이블 내용 ACTION(4, ( ) = “이동, 상태번호 4” ACTION(4, a ) = “이동, 상태번호 5”

7.4.2.2 환원 액션 만들기 LR(0) 아이텀 집합의 각 아이텀에서 점 바로 뒤의 심볼이 더 이상 존재하지 않는 [A → α·] 형식을 찾는다. 이 형식의 아이텀에 대해서는 FOLLOW(A) 에 속하는 모든 터미널 심볼인 a ∈ FOLLOW(A) 에 대하여 ACTION(i, a) =  "환원 생성규칙 A → α" 를 넣는다. 이 의미는 생성규칙 A → αaβ에서 오른쪽 스트링 αaβ이 A 로 환원하기 위해서는 스트링 αaβ 다음 심볼을 보고 결정한다는 것이다. 또한, A의 FOLLOW 는 스트링αaβ 다음에 나타날 터미널 심볼이다.

환원 정보 구하기 아이텀 집합에서 [A → α·] 형식과 a ∈ FOLLOW(A) 를 찾는다. I2에서 아이텀 E → T · 이고 { ), +, ↲} ∈ FOLLOW(E) 이다. 그러므로 터미널 심불 ), +, ↲ 각 각에 대한 액션 테이블에 들어갈 내용은 아래와 같다. ACTION(2,  ) ) = “이동, E → T ” ACTION(2, + ) = “이동, E → T ” ACTION(2, ↲) = “환원, E → T ”

환원 정보 구하기 같은 방법을 계속하면, 각 아이텀 집합 I3, I5, I9, I10, I11에서 이 형식에 해당하는 아이텀은 아래와 같다. I3 : T  → F ·   I5 : F  → a ·   I9 : E  → E + T ·       I10: T  → T * F ·  I11: F  → ( E ) · FOLLOW 심볼은 아래와 같다. FOLLOW(E) = { +, ), ↲} FOLLOW(T) = { +, *,  ), ↲} FOLLOW(F) = { +, *,  ), ↲}

액션 테이블 내용 ACTION(3, + ) = “환원, T → F ” ACTION(5, + ) = “환원, F → a ” ACTION(5, * ) = “환원, F → a ” ACTION(5,  ) ) = “환원, F → a ” ACTION(5, ↲ ) = “환원, F → a ” ACTION(9, + ) = “환원, E  → E + T ” ACTION(9,  ) ) = “환원, E  → E + T ” ACTION(9, ↲ ) = “환원, E  → E + T ” ACTION(10, + ) = “환원, T  → T * F ” ACTION(10, * ) = “환원, T  → T * F ” ACTION(10,  ) ) = “환원, T  → T * F ” ACTION(10, ↲ ) = “환원, T  → T * F ” ACTION(11, + ) = “환원, F  → ( E ) ” ACTION(11, * ) = “환원, F  → ( E ) ” ACTION(11,  ) ) = “환원, F  → ( E ) ” ACTION(11, ↲ ) = “환원, F  → ( E ) ”

7.4.2.3 수락 액션 만들기 LR(0) 아이텀 집합의 각 아이텀에서 점 바로 뒤의 심볼이 더 이상 존재하지 않은 [S ′ → S · ] 형식을 찾아서 ACTION(i, ↲) =  "수락, 파싱 종료" 를 넣는다. ACTION(1, ↲ ) = “수락”

단순 LR 파싱 테이블 구성 알고리즘 function Constructing an SLR parsing table( ) {           {            input: augmented grammar G ′ and C = { I0, I1, ... , In }, of sets of items for G ′;             output: SLR Parsing Table with ACTION and GOTO from C;                    if ([A → α·aβ] ∈ Ii  &&  goto (Ii, a) = Ij) ACTION(i, a] =  "shift  j ";                    if ([A → α·] ∈ Ii  &&  A ≠ S ′)                              {                                    for ( all  a ∈ FOLLOW(A) )                                            ACTION(i, a) =  "reduce  A → α" ;                               }                    if ([S ′ → S · ] ∈ Ii)  ACTION(i, ↲) =  "accept";                    if ( goto(Ii, A)  =  Ij)   GOTO(i, A) =  j;                    if (there are  undefined entry) ACTION(i, VT) =  "error";                 }

실습 7.3 아래 문법에 대한 단순 LR 파싱 테이블을 구성하시오. G :  1. S → L = R       2.  S → R       3.  L → * R       4.  L → a       5.  R → L

제 7 장 끝