[컴개/CI] Bottom-Up 구문 분석, LALR Parser

LALR Parsing

LR(1) 파싱의 문제점

LR(1) 파싱은 정교하기 때문에 상태의 개수가 어마어마하게 많다.

Pascal 언어를 통해 만들면 SLR은 수백 개, LR(1)은 수천 개의 상태가 나온다.

하지만 이렇게 많은 개수의 상태는 메모리에 과부화를 준다.

따라서 우리는 이러한 LR(1)의 상태 개수를 줄이고자 LALR 파싱을 시작하였다.

 

LALR Parsing

LR에서 두 상태의 core가 동일하면 하나의 상태로 묶어준다.

위 사진에서 두 개의 상태 중 일부가 동일한 것을 볼 수 있다.

동일한 부분을 LALR 파서에서는 묶어준다.

 

이러한 LALR 파싱은

1. SLR보다 많이 정교하다.

   LR(1)보다 이론적으로 less powerful하지만,

   실제 처리할 수 있는 의미 있는 문법의 종류는 거의 동일하다.

2. 파서 상태들의 개수는 일반적으로 SLR과 동일하다. -> LR(1)보다 상태 개수가 훨씬 적음

 

LALR(1) Parser 만들기

C1(LR(1)의 상태 전이도)에서 작성하는 방법

1. LR(1) 아이템과 C1을 만든다.

2. 같은 core를 가진 LR(1) 아이템 집합들을 한 개의 LR(0) 아이템 집합으로 만든다.

    이때, 각 아이템의 lookahead는 LR(1) 아이템의 lookahead 합집합으로 구성한다.

3. 단점: LR(1) 파서 상태를 다 만들고 시작해야 한다. -> 상태 수 극복 x

 

C0에서 작성하는 방법

1. LR(0) 아이템과 C0을 만든다.

2. 파싱 테이블의 shift와 accept, goto의 action은 모두 SLR과 동일하고

    reduce만 수정한다.

 

구문 분석 방법 정리

LL 파싱 테이블

non-terminal X terminal = 생성 규칙

FIRST/FOLLOW로 계산한다.

 

LR 파싱 테이블

LR states X terminals = {shift/reduce}

LR states X non-terminal = goto

아이템의 closure와 파서 상태들의 goto로 계산한다.

 

LL(1)는 LL(1) 테이블에 conflict가 없다는 뜻이다.

LR(0)는 LR(0) 테이블에 conflict가 없다는 뜻이다.

SLR는 SLR 테이블에 conflict가 없다는 뜻이다.

...

 

문법 종류들의 관계

위의 그림은 표현력에 대해 그린 모습이다.

가장 바깥에 있을 수록 표현력이 커진다.

이때, LL과 LR은 비교할 수 없다.

 

PL을 만드는 사람이 문법을 쉽게 짜면 compiler를 만드는 사람이 어려워진다.

PL을 만드는 사람이 문법을 어렵게 짜면 compiler를 만드는 사람이 쉬워진다.

즉, 쉬운 정도가 서로 반비례하다.

 

Syntax Analysis(구문 분석)

우리는 지금까지 구문 분석하는 방법에 대해 알아보았다.

 

1. Top-Down

backtracking을 진행해야 하므로 overhead가 크다. (LL)

 

2. Bottom-Up

컴퓨터와 더 친화적인 표현법이다.

guide 없이 backtracking을 해야 하므로 파서의 상태를 도입하였다. (LR)

Bottom-Up 구문 분석, L