컴파일러구성 - [제11강] LALR 구문분석

컴파일러구성 - [제11강] LALR 구문분석

·CLR 파싱표의 효율화 ·LR(0)에서 LALR파싱표 구성

컴파일러 용어정리

• LALR
  LookAhead LR 방법으로 lookahead 정보를 이용하기 때문에 SLR 방법보다 훨씬 강력하고 파싱표의 크기는 CLR에서 core가 같은 항목들을 한데 묶음으로써 SLR과 같은 크기로 구성할 수 있다. 그러나 LR(0) 항목의 집합을 구한 후 파싱표를 만들기 위해 reduce 항목이 있는 각 상태에서 lookahead 기호를 구하는 데 상당한 시간과 노력이 소요된다.
• LR(0) 항목
  LR(0) 항목은 다음과 같이 3종류로 나누어진다.
     1) [A → α․β]에서 α≠ε 인 kernel 항목
     2) [A → ․α]와 같은 closure 항목
     3) [A → α․]와 같은 reduce 항목
• LR(1) 항목
  LR(0)항목에서 lookahead 정보를 첨가한 것.
  LR(1) 항목은 [A → α․β, a]형태를 가지며
  여기서 A → αβ ∈ P이고 a ∈ V_T ∪ {$} 이다.
  A → α․β를 core라 부르며 LR(0) 항목과 같은 의미이다.
• lookahead
  LR(1) 항목 [A → α․β, a]에서 a를 항목의 lookahead라 부르며, reduce 항목 일 때 그 기호에 대해서 reduce 행동을 하는 것을 뜻한다. 
• LA(P, [A → α․β])
  P상태에서 A다음에 나올 수 있는 터미널의 집합인데, 그것은 P상태에서 거꾸로 α 만큼 올라간 상태에서 A다음에 나올 수 있는 터미널들과 같다.

요얌정리

1. LALR은 LookAhead LR 방법으로 lookahead 정보를 이용하기 때문에 SLR 방법보다 훨씬 강력하고, 파싱표의 크기는 CLR에서 core가 같은 항목들을 한데 묶음으로써 SLR과 같은 크기로 구성할 수 있다. 또한, 모호하지 않은 context-free 문법으로 표현된 거의 모든 언어를 인식할 수 있으며, 오류를 초기에 탐지할 수 있다.
2. LALR 파싱표는 LR(1)에서 유도하는 방법과 LR(0)에서 유도하는 방법이 있다.
3. 먼저 LR(1)에서 유도하는 방법은 같은 core를 가진 LR(1) 항목 중에서 LR(0) 항목 만을 합해준다. 그리고 reduce 항목의 lookahead는 이들 LR(1) 항목의 lookahead의 합으로 정해준다. 이를 알고리즘으로 표현하면 다음과 같다.
4. 두 번째 방법인 LR(0) 항목으로부터 LALR 파싱표를 구성하는 방법은 SLR 방법과 유사하다. 먼저 정의된 문법의 LR(0) 항목 집합의 canonical collection을 구성한다. 그러면 파싱표의 shift와 accept 그리고 GOTO 행동은 SLR과 같고, reduce행동은 각 reduce 항목의 lookahead에 의해 결정되므로, 이를 위해서 LR(0) 항목 집합의 canonical collection으로부터 reduce 항목의 lookahead를 구한다.
5. LALR방법은 LR(0) 항목의 집합을 구한 후 파싱표를 만들기 위해 reduce 항목이 있는 각 상태에서 lookahead 기호를 구하는 데 상당한 시간과 노력이 소요된다. 이러한 관계로 최근의 LALR 방법에 대한 연구는 lookahead를 보다 효율적으로 구하는 데 많은 관심이 고조되고 있다.

• 

  다음은 LALR 구문분석에 관한 설명이다. 틀린 것은?

  답을 체크하세요

  1. lookahead 정보를 이용하기 때문에 SLR 방법보다 훨씬 강력하다.
  2. LALR 파싱표를 구성하기 위해서는 반드시 CLR 파싱표를 구해야만 한다.
  3. lookahead 기호를 구하는데 상당한 시간과 노력이 소요된다.
  4. CLR 파싱표보다 LALR 파싱표가 훨씬 작다.

  정답 :

  ②

  ② 번이 틀렸다.
  LALR 파싱표는 LR(1)에서 유도하는 방법과 LR(0)에서 유도하는 두 가지 방법이 있다. 

• 

  다음은 CLR 그래프를 이용하여 파싱표를 구성하는 과정이다. CLR 그래프로부터 LALR의 파싱표를 구할 수 있다. 다음은 core가 같은 상태를 찾는 과정인데 틀리는 것은?
  

  

  
  
  

  

  

  

  답을 체크하세요

  1. I₁ ∪ I₅ ‗⇒ I₁₅
  2. I₃ ∪ I₆ ‗⇒ I₃₆
  3. I₄ ∪ I₇ ‗⇒ I₄₇
  4. I₈ ∪ I₉ ‗⇒ I₈₉

  정답 :

  ①

  ① CLR 그래프를 살펴보면 I₁ 과 I₅ 는 같은 core 가 없다.

  여기서 core가 같은 상태를 찾으면 된다. 우선 상태 I3와 I6가 같은 core를 가지므로,
  I3 ∪ I6 ⇒ I36 ＝ {[C → c·C, c/d/$], [C → · cC, c/d/$],
  [C → ·d, c/d/$]}
  같은 방법으로
  I4 ∪ I7 ⇒ I47 ＝ [[C → d·, c/d/$]},
  I8 ∪ I9 ⇒ I89 ＝ {[C → cC·, c/d/$]} 이다.
  따라서 LALR 파싱표는 다음과 같다. 

• 

  (3-5) 다음은 CLR 그래프로부터 LALR의 파싱표를 구하는 과정이다.
  I₄₇ 을 구하면?

  

  
  
  

  

  

  

  답을 체크하세요

  1. [[C → d․]
  2. [[C → d․, $]
  3. [[C → d․, c/d]
  4. [[C → d․, c/d/$]

  정답 :

  ④

  I₄ ∪ I₇ ⇒ I₄₇ ＝ [[C → d․, c/d/$]},

• 

  (3-5) 다음은 CLR 그래프로부터 LALR의 파싱표를 구하는 과정이다.
  I₈₉ 을 구하면?

  

  
  
  

  

  

  

  답을 체크하세요

  1. [C → cC․]
  2. [C → cC․,$]
  3. [C → cC․, c/d]
  4. [C → cC․, c/d/$]

  정답 :

  ④

  I₈ ∪ I₉ ⇒ I₈₉ ＝ {[C → cC․, c/d/$]} 

• 

  (3-5) 다음은 CLR 그래프로부터 LALR의 파싱표를 구하는 과정이다.
  다음 중 I₃₆ 에 속하지 않는 것은?

  

  
  
  

  

  

  

  답을 체크하세요

  1. [C → ․ d, c/d]
  2. [C → ․ d, c/d/$]
  3. [C → c․C, c/d/$]
  4. , [C → ․ cC, c/d/$]

  정답 :

  ①

  I₃ ∪ I₆ ⇒ I₃₆ ＝ {[C → c․C, c/d/$], [C → ․ cC, c/d/$],
                          [C → ․ d, c/d/$]}