[컴파일러] LR 파서 문제 풀이

안녕하세요 밥한그릇입니다.

컴파일러 과목의 LR(top-down) 파서 문제풀이 포스팅에 이어, LR (bottom-up) 파서 문제풀이 포스팅을 작성해보려합니다.

https://nsa901.tistory.com/114

[컴파일러] LL 파서와 LR 파서

앞선 개념 내용은 이전 포스팅에 설명해두었으니, 참고하시면 좋습니다.

이 포스팅에서는 parsing table일 이용해 LR 파서가 동작하는 예제를 풀어보는 시간을 갖겠습니다.

 

자 그럼, 시작합니다.

---

출처 : https://www.geeksforgeeks.org/bottom-up-or-shift-reduce-parsers-set-2/

우선, 알고있어야할 한가지는 LR parser는 bottom-up parsing의 방식을 사용하며, 그 과정은 right-most derivation(우측 우선 유도) 과정의 역순을 따른다는 것입니다.

이는 유도과정의 역순으로 되돌려, 현재 결과로부터 초기 symbol을 얻어내는 방식입니다.

이 경우 사람이 parsing table을 구현하는 것은 매우 어렵고 복잡해지므로, 프로그램이 이를 대신 해주게 됩니다. 

따라서 이번 시간에는 parsing table의 구현 없이, 이미 주어진 parsing table이 있을 때 어떻게 parsing이 이루어지는 지 예제를 통해 살펴 보게 될 것입니다.

 

참고로, LR parsing table의 구조는 아래와 같이 ACTION table과 GOTO table이 합쳐진 형태로 구성되었으며, LL에서와 마찬가지로 stack과 input buffer를 사용하여 parsing을 수행합니다. 그럼 전반적으로 LR parser 프로그램이 작동하는 구조가 다음과 같이 됩니다.

 

LR parser 프로그램의 작동 구조

---

 

먼저 LR parser에 주어진 parsing action은 다음과 같다는 걸 다시 복습하고 갑시다.

• shift : input symbol을 스택에 push (그 위에 상태 n을 저장)
• accept : parsing 끝남
• error : syntax에 오류
• reduce : handle을 non-terminal로 치환.

LR parsing table을 이용한 parsing 예제

input 프로그램으로 a, a 를 넣었을 경우 (input = a, a$)의 예시를 살펴봅니다.

 

주어진 예제는, Grammer rule과 파싱 테이블, 시작상태 Stack : 0 과 input : a, a$ 만 써놓고 직접 다시 풀어볼 수 있습니다.

따라서, 이 포스팅을 본 후에는 혼자서 그렇게 빈 종이에 다시 풀어보기를 권장합니다.

 

정리

1. shift
   ex. [STACK] 0 , [INPUT] a,a$ 일 때
   → M[0, a] = s3 이므로 input의 a를 stack으로 밀어넣고 맨 위에 번호 3도 넣어줌
   → [STACK] 0a3, [INPUT] ,a$
2. reduce
   ex. [STACK] 0a3 , [INPUT] ,a$ 일 때
   → M[3, “,”] = r2 이므로 2번 문법규칙을 적용
   input의 “,”과 스택의 3을 지움, 2번 문법 규칙(ELEMENT→a)에 따라 0a 상태를 0 ELEMENT로 바꿈
   그 다음, r2의 2를 스택에 넣음
   → [STACK] 0 ELEMENT 2, [INPUT] a$ 일 때
3. acc
   ex. [STACK] 0 LIST 1, [INPUT] $일 때
   M[1, $]에 acc 있음. 끝낸다는 뜻이므로 parsing 종료

 

마찬가지로 Stack의 top은 문자열의 앞부분에 있다는 점을 주의하며, 위와 같이 parsing을 수행하시면 됩니다.

 

---

아래는 직접 예제의 시작상태부터 3번째 상태까지 풀어본 내용입니다. 참고바랍니다.

 

0이 시작 상태.

스택의 top에 있는 상태(state)와 입력 기호를 가지고 action 테이블을 찾아간다.

1. stack의 top 0(state), a(입력) 가지고 테이블 찾아감
   → s3 나옴. (= 3번 규칙을 가지고 shift 해라)
   a를 shift함 (stack에 푸시해줌) + stack의 top에 3번 써줌
   → 끝난 stack 상태 : 0 ➡️ 0 a 3
2. stack의 top 3(state), “,” (입력) 가지고 테이블 찾아감
   → r3 나옴. (= 3번 규칙을 가지고 reduce 해라)
   a를 ELEMENT라는 symbol로 reduce 해야함
   현재 stack : 0 a 3
   — 여기에서 상태번호 포함해서 a를 pop 해서 없앤다 (”a 3”을 pop)
   — a가 있던 자리를 Element로 바꾼다
   — stack 상태는 0 Element 인데, 이때 0과 Element를 가지고 GOTO 테이블 찾아간다.
   → 2 나옴
   → 2를 push
   → 끝난 stack 상태 : 0 a 3 ➡️ 0 Element 2
   
   
3. stack의 top 2(state), “,”(입력) 가지고 테이블 찾아감
   → r2 나옴. (= 2번 규칙을 가지고 reduce 해라)
   Element를 List라는 symbol로 reduce 해야함
   현재 stack : 0 Element 2
   — 여기에서 상태번호 포함해서 Element를 pop 해서 없앤다 (”Element 2”을 pop)
   — Element가 있던 자리를 List로 바꾼다
   — stack 상태는 0 LIST 인데, 이때 0과 LIST를 가지고 GOTO 테이블 찾아간다.
   → 1 나옴
   → 1를 push
   → 끝난 stack 상태 : 0 Element 2 ➡️ 0 LIST 1

… 다 적기에 너무 많으니 더이상의 내용은 생략합니다. 알아서 풀어보도록 합시다.

---

자 이렇게 LR parsing table을 이용해 parsing하는 예제를 풀어보았습니다.

파서 관련 예제 풀이는 이렇게 LL과 LR 모두 끝내게 되었네요.

 

추가로 설명이 필요한 내용, 지적, 궁금한 점 등이 있으면 댓글 달아주세요.

제 포스팅이 도움이 되셨다면 공감버튼 눌러주시면 감사하겠습니다. ^^