[컴파일러 이론] 6. Bottom-up Parsing, LR grammars

LR grammar는 left-recursive, right-most derivation의 약자이다.

이 문법을 사용해 만들어진 파서는 shift-reduce parser라고 부른다.

 

---

Shift & Reduce

bottom-up parser는 derivation의 우변에 있는 내용을 좌변으로 되돌린다. 

이 과정을 reduce라고 한다.

즉 시작을 최종 식에서부터 하여 역으로 시작 심볼로 변환하는 방법이다.

 

right-most derivation은 변환해야될 식에서 오른쪽부터 살펴보며 reduce를 한다는 뜻이다.

int*int+int라는 에시에 대해 단계별로 parser가 동작하는 과정을 나타낸 것이다.

shift는 당장 reduce가 될 수 없을 때 stack에 임시 저장해놓는 행동이다.

---

Action Selection Problem

이 shift-reduce parser를 사용할 때 발생하는 선택 문제가 있다.

1. shift와 reduce가 모두 가능할 때 어떤 것을 할 것인지?

2. 두 가지 이상의 reduce가 적용가능할 때 어떤 것을 선택할 것인지?

 

아래 예시는 1번 선택 문제이다.

현재 상황에 T→int를 적용해 바로 reduce를 할 수도 있고,

T → int*T를 적용하기 위해 stack을 바로 소모하지 않고 input string의 *를 shift할 수도 있다.

이런 선택 문제들 중 몇개는 input string에서 몇개의 문자를 미리 확인할 수 있다면 해소가 될 수도 있다.

미리 보는 문자들을 lookahead라고 한다.

---

LR Style Grammar

LR(k)라는 문법은 LR방식 문법에 k개의 lookahead를 사용하는 문법을 의미한다.

그외 LALR, SLR같은 LR의 변형 문법들도 있다.

 

따라서 LR(0) grammar는 lookahead를 사용하지 않고, 즉 stack의 내용만 보고 action을 정해도 선택에 conflict가 발생하지 않는 문법을 의미한다.

 

---

LR(0) NFA Representation

앞에서 알아봤었던 NFA를 통해 shift-reduce parser를 표현할 수 있다.

점(.)을 추가해 나타낸다.

예를 들어, T → ( E ) 라는 production에서 점을 사용해 T → (.E )라고 표시했다면,

점 앞의 부분 '('이 stack에 있다는 뜻이고, 그 이후에 E가 나올 것을 기대하는 상태라는 뜻이다.

추가로 $를 붙여 S' → S $라는 기본 상태에서 시작한다.

 

위 T → (.E ) 예시에서 다음 글자가 정말 E라면 T → ( E. )으로 상태가 바뀐다.

또 NFA에서는 $\epsilon$ transition이 있기 때문에, 이 LR grammar에서 $\epsilon$transition은 기대하는 심볼로 시작하는 transition state로 이동하는 것으로 정의한다.

예를 들어 T → (.E )에서 $\epsilon$ transition을 하면 E → .S 같은 상태로 가게 된다.

 

아래 그래프를 보면 shift transition과 $\epsilon$ transition을 확실히 알 수 있을 것이다.

---

LR(0) DFA Representation

NFA는 DFA로 바꿔야 한다.

NFA의 $\epsilon$ transition들을 하나로 모은다.

가운데의 5개의 식이 들어있는 state를 예시로 설명하자면,

먼저 S→(.L)은 기본 식이고 여기서 $\epsilon$ transition을 적용하면 L에서 시작되는 식이 나오게 된다.

이렇게 나온 식 중 L → .S를 보면 한번 더 $\epsilon$ transition이 적용 가능하다. 

따라서 S로 시작하는 식도 추가된다.

 

이 DFA를 통해 우리의 목적이었던 어떤 상황에 shift를 할지, reduce를 할지 정할 수 있다.

점(.)오른쪽에 더 이상 문자가 없는 상태에 대해 reduce, 그 외에는 shift를 하면 된다.

 

---

예시

위에서 계속 예시로 사용했던 LR(0) CFG인 아래의 식을 통해 실제 bottom-up parsing을 해보자.

 

((a),b) 라는 string이 위 CFG에 의해 기술된 문법에 포함되는지 판단해보자.

 

시작 심볼은 S'이고, 아직 스택에 아무것도 없는 .S$가 들어있는 state1에서 시작한다.

((a),b)에서 첫 문자는 '(' 이므로 state1에서 S→.(L)이 선택된다.

stack	input
(	(a),b)

이 과정 이후 state3로 이동된다.

이번에도 (가 첫 문자이므로 자기자신으로 이동된다.

stack	input
((	a),b)

이번에는 a가 다음 문자이므로 state2로 이동한다.

stack	input
((a	),b)

state2는 reduce를 하므로 아래처럼 내용이 바뀐다.

stack	input
((S	),b)

이런 식으로 계속 진행해서 accept로 갈 수 있는지 확인하면 된다.

 

---

LR Parsing table generation

사람은 위 과정처럼 NFA를 따라가면 되지만 컴퓨터를 위해 parsing table이 필요하다.

state들을 row에, terminal과 non terminal을  column에 넣어주면 된다.

이후 표의 내용은 아래 원칙에 맞게 채워준다.

따라서 최종적으로 parsing table을 얻을 수 있다.

같은 ((a),b)예시에 대해 parsing table을 사용해 parsing을 한 예시이다.

기본적으로 똑같지만 state를 명시적으로 저장한다는 것이 다르다.

DFA에서는 직접 어떤 state에 있는지를 따라가며 분석했으므로 없어도 되었었다.

---

LR(0) grammar의 한계

효율적이고 좋아보이는 LR(0)이다.

하지만 어떤 state에 reduce가 오직 하나만 있어야 정상적으로 작동한다.

다른 reduce나 shift가 한 state안에 같이 있다면 문제가 발생한다.

---

Non LR(0) grammar

LR(0) 문법이 아닌 것 중 right associative한 production이 있다면 아래처럼 conflict가 발생할 수 있다.

 

이런 문제를 해결하기 위해 lookahead를 사용하는데 크게 3가지 정도의 방법이 있다.

각각 LR(1), LALR(1), SLR(1)이다. 

이런 방법들이 있다는 것만 소개하면서 syntax analysis 부분을 마치려고한다.

이제 다음 글 부터는 frontend의 마지막 단계인 semantic analysis를 알아보자.