[컴파일러] Bottom-up Parsing

👑 Bottom-up 파싱

Bottom-up parsing은 입력 문자열을 분석하여, 이를 구문 트리의 리프에서부터 상위로 올라가며

파싱하는 기법이다. 리프 노드부터 시작하여 상위 노드로 합쳐 나가며, 최종적으로는 시작 기호를

생성하는 것이 목표이다. 이러한 방식으로 파싱을 완료하면 입력 스트링이 주어진 문법에 맞다는

것을 증명할 수 있게 된다.

Bottom-up parsing은 스택과 파싱 테이블을 사용하여 Shift와 Reduce를 반복하는 과정을

통해 파싱을 수행한다. Bottom-up parsing의 핵심은 Reduce, Handle, Shift 이다.

각 용어는 다음과 같다.

• Reduce

  • S ⇒ αβω이고 A → β의 생성규칙이 존재할 때, αβω에서 β를 A로 대체하는 것

  • 즉, 파싱 결과는 입력 문자열에서 시작 기호가 나올 때까지 차례로 reduce하여 얻을 수 있다.

• Handle

  • 어떠한 문장 형태에서 reduce될 부분을 의미한다.

  • S ⇒ αβω 에서 A로 대체되는 β가 handle이다.

  • 만약 동일한 문장 형태에서 서로 다른 두 개 이상의 handle이 존재한다면 이는 모호함을
    나타낸다.

• Shift

  • 스택의 top에 handle이 나타날 때까지 입력 심볼을 스택으로 옮기는 과정이다.

하지만, 파싱 과정에서 다음과 같은 문제점들에 직면할 수 있다.

• Shift 할지 Reduce 할지 어떻게 정할 것인가.

• reduce 방법이 여러 가지인 경우 어떤 것을 선택할 것인가.

따라서 이 문제들을 해결하기 위해 파서 상태라는 개념을 사용한다.

👑 LR(0)파싱 & 파싱 테이블

LR 파싱은 Left-to-right로 입력을 읽으며, 가장 오른쪽에서부터 리덕션을 수행하는 기법이다.

파싱을 위해 파싱 테이블을 사용하며, 이 테이블은 액션(Action)과 고투(Goto) 테이블로 구성된다.

• 액션 테이블(Action Table)

  • 각 상태와 입력 심볼에 따라 Shift, Reduce, 또는 Accept 동작을 결정하는 데 사용된다.

• 고투 테이블(Goto Table)

  • 특정 nonterminal을 만났을 때 다음 상태로 이동하는 지점을 정의하며, Reduce 이후에 사용된다.

💡 LR(0) 파싱 테이블

LR(0) 파싱 테이블을 만들기 위해서는 파서 상태들을 정의하고, 파싱 과정에서 어떤 상태가

어떻게 전이 되는지를 정의해야 한다. 파서 상태들을 정의하기 위해 LR(0) 아이템과 Closure, goto에

대한 개념들을 알아야 한다.

• LR(0) 아이템

  • LR(0) 아이템은 점(dot)을 포함한 문법 규칙이다.

  • 이 점은 입력의 어느 부분까지 파싱이 진행되었는지를 나타낸다.

  • 예를 들어 규칙 A → B C 가 있다면 LR(0) 아이템은 다음과 같이 나타낼 수 있다.

    • A → .BC : 아직 아무것도 읽지 않았음을 의미한다.

    • A → B.C : B까지 파싱되었고, C를 파싱할 것으로 기대하는 상태이다.

    • A → BC. : C까지 파싱했고, 이 상태에서 reduce가 가능하다.

• Closure

  • Closure는 LR(0) 아이템 집합에 새로운 아이템들을 추가하는 과정이다.

  • 주어진 아이템 집합을 시작으로 초기 Closure 집합을 만들며, 아이템 중 . 다음에
    nonterminal이 있는 경우 해당 nonterminal을 정의하는 규칙을 새로운 아이템으로 추가한다.

  • 위 과정을 더 이상 새로운 아이템을 추가할 수 없을 때까지 반복하는 것이 Closure 연산이다.

S' → S
S → A B
A → a
B → b

위와 같은 문법이 있을 때, 초기 아이템 S' → .S 에 대해 Closure를 계산하면 다음과 같이 진행된다.

• 초기 상태: {S' → .S}

• 점 뒤에 S가 있으므로 S에 대한 정의를 추가: {S' → .S, S → .A B}

• 새로 추가된 아이템에서 점 뒤에 A가 있으므로 A에 대한 정의를 추가:
  {S' → .S, S → .A B, A → .a}

• 이후, A → .a는 점 뒤에 nonterminal이 없으므로 추가 연산이 필요하지 않다.

결과 Closure는 {S' → .S, S → .A B, A → .a} 이 된다.

• goto

  • Goto는 파싱 테이블의 상태 전이를 구성하는 중요한 부분이다.

  • 현재 상태에서 특정 심볼을 읽었을 때 다음 상태로 이동하는 규칙을 정의한다.

  • Goto 함수는 LR(0) 파싱 테이블에서 상태 전이를 구성하는 데 사용되며, 각 상태에 대해 점(dot)
    뒤의 심볼이 나타났을 때 이동할 다음 상태를 결정한다.

  • goto 를 구하는 방법은 다음과 같다.

    • 현재 상태로 지정된 아이템 집합 I를 선택한다.

    • I의 각 아이템에 대해 점(dot) 뒤에 위치한 심볼을 확인한다. A → α.Xβ 에서 X

    • 각 아이템에서 점 뒤에 있는 심볼을 X라고 할 때, 점을 X의 오른쪽으로 한 칸 옮겨 새로운 아이템을
      만든다. A → α.Xβ 아이템을 A → αX.β 로 만든다.

    • 위와 같은 과정을 통해 변경된 아이템들로 새 집합을 구성한 후, 이 집합에 대해 다시 Closure
      연산을 적용하여 완성된 아이템 집합을 만든다.

LR(0) 아이템과 Closure 연산, goto는 LR(0) 파싱 테이블을 구성할 때 필수적인 역할을 한다. 각 상태는

이들 아이템과 연산을 기반으로 생성되며, 파서가 각 단계에서 할 수 있는 Shift와 Reduce 동작을

결정하는데 중요한 정보를 제공한다.

💡 LR(0) 파싱 테이블 그리는 과정

LR(0) 파싱 테이블을 만드는 과정을 간단히 요약하면 다음과 같이 나타낼 수 있다.

• Augmented Grammar 추가

  • 시작 기호 S에 대한 새로운 시작 기호 S'을 추가한다.

• 시작 상태의 Closure 계산

  • 새로운 시작 규칙 𝑆′ → .S을 포함하는 초기 상태를 생성한다.

  • 이 상태에 대해 Closure를 계산하여 완전한 시작 상태를 만든다.

• Goto 연산을 통해 다음 상태 생성

  • 시작 상태에서 각 심볼에 대해 Goto 연산을 수행하여 다음 상태를 생성한다.

  • 각 상태에서 .을 이동시키고, 그 결과로 나온 새로운 상태에 대해 다시
    Closure를 계산하여 상태 집합을 확장해 나간다.

• 파싱 테이블 구성

  • 생성한 각 상태에 대해 액션(Action) 테이블과 고투(Goto) 테이블을 채운다.

예시

S → ( E ) | id
E → S | E + S

Step 1 : Augmented Grammar 추가

S' → S
S → ( E ) | id
E → S | E + S

Step 2 : 시작 상태의 Closure 계산

첫 번째 상태 $ I_0 $ 는 Closure([S' → . S])에 대해 구하는 것으로부터 시작한다. 점 뒤에

있는 S에 대한 규칙들을 추가한다.

$ I_0 = Closure([S’ → .S]) = \lbrace S’ → .S, \quad S → .( E ), \quad S → .id \rbrace $

Step 3 : Goto 연산을 통해 다음 상태 생성

$ Goto(I_0, \; S) $ 는 아이템 S' → S .으로 만들 수 있으며, Closure를 계산할 필요가 없다.

$ I_1 = \lbrace S’ → S.\rbrace $

$ Goto(I_0, \; ‘()’ $ 는 아이템 S → ( . E )을 포함하는 상태를 생성한다. 점 뒤에 E가 있으므로

아이템을 추가하기 위해 Closure를 계산한다.

• E에 대한 규칙 추가

  • E → . S
  • E → . E + S

• S 에 대한 규칙을 다시 추가 (E → . S)

  • S → . ( E )
  • S → . id

따라서 $ I_2 = \lbrace S → ( . E ), \quad E → . S, \quad E → . E + S, \quad S → . ( E ), \quad S → . id \rbrace $

$ Goto(I_0, \; id) $ 는 아이템 S → . id 를 포함한 상태를 생성한다.

$ I_3 = \lbrace S → id . \rbrace $

$ Goto(I_2, \; E) $ 는 $ I_2 $ 의 아이템 S → ( . E ) 와 E → . E + S를 포함한 상태를 생성한다.

두 아이템 모두 . 뒤에 terminal 기호가 오기 때문에 closure는 계산할 필요가 없다.

$ I_4 = \lbrace S → ( E . ), \quad E → E . + S \rbrace $

$ Goto(I_2, \; S) $ 는 $ I_2 $ 의 아이템 E → . S를 포함한 상태를 생성하여 구한다.

$ I_5 = \lbrace E → S . \rbrace $

$ Goto(I_4 \; +) $ 는 $ I_4 $ 에서 +를 읽을 때의 규칙을 정의한다. 따라서 E → E + . S 가 만들어지며

이 아이템을 closure 연산하여 구할 수 있다.

$ I_6 = \lbrace E → E + . S, \quad S → . ( E ), \quad S → . id \rbrace $

위와 같은 방식으로 모든 상태들과 트랜지션을 구하면 다음과 같다.

이제 위의 정보를 가지고 파싱 테이블을 그릴 수 있다. 위 문법의 파싱 테이블은 다음과 같다.

👑 SLR & LR(1) & LALR

• SLR(Simple LR)

  • LR(0) 보다 정교하며, conflict를 줄인 파서이다.

  • LR(0)의 파싱 테이블에서는 reduce가 모든 터미널에 포함되지만, SLR에서는 FOLLOW 집합을
    사용하여 특정 터미널 칸에만 reduce를 적용하여 conflict를 줄인다.

• LR(1)

  • SLR보다 강력한 파서로, 각 상태에 하나의 look-ahead 심볼을 사용하여 더 복잡한 문법을 인식할 수 있다.

  • 하지만 SLR보다 구현이 복잡하고 메모리와 시간이 더 많이 소요된다.

• LALR(Look-Ahead LR)

  • SLR과 LR(1)의 절충형으로, SLR의 간단함과 LR(1)의 강력함을 결합하였다.

  • 일반적으로 사용되며, 많은 컴파일러가 LALR 파서를 사용한다.

LR 계열의 파서들은 각기 장단점이 있지만, 일반적으로 파싱할 문법에 따라 적합한 유형을 선택하여

사용한다. Bottom-up 파싱은 이러한 LR 파서들의 도움으로 효율적인 구문 분석이 가능하며, 복잡한

프로그래밍 언어 문법을 표현할 때 특히 유용하다.