[SLR구문분석특강]KNOU 컴파일러구성 24.10.26_ 특강 필기
★SLR 구문분석 특강 ★
<목차>
1. Top-Down 구문분석
2. Bottom-Up 구문분석
3. Shift - Reduce 구문분석
4. FIRST
5. FOLLOW
<학습 전 SLR구문분석은 어디에 쓰이는가? 뤼튼에 물어보기 >
Q. SLR 구문분석은 어느 분야에 쓰이고 정확히 어떤 의미인가?
A.
SLR 구문분석은 주로 컴퓨터 과학 및 자연어 처리(NLP) 분야에서 사용됩니다. SLR은 "Simple LR"의 약자로, LR 파싱 기법 중 하나로, 문법을 기반으로 입력 문자열을 분석하여 구문 트리를 생성하는 과정입니다.
SLR 구문분석의 주요 사용 분야:
프로그래밍 언어 컴파일러: 소스 코드를 분석하여 구문 오류를 찾고, 문법 구조를 이해하는 데 사용됩니다.
자연어 처리: 문장을 분석하여 의미를 이해하고, 기계 번역, 감정 분석 등의 작업에 활용됩니다.
데이터 형식 검증: 특정 데이터 형식이 정의된 문법을 따르는지 검증할 때 사용됩니다.
SLR 구문분석의 의미:
SLR 구문분석은 입력된 문자열이 주어진 문법에 맞는지를 확인하고, 그에 따라 구문 트리를 생성하는 기법입니다. 이 과정에서 SLR 파서는 상태 전이와 스택을 사용하여 입력을 처리하며, 문법의 각 규칙에 따라 어떤 동작을 수행할지를 결정합니다.
이러한 방식은 문법이 유한 상태 기계로 표현될 수 있을 때 효율적으로 작동하며, 복잡한 문법 구조를 처리하는 데 강력한 도구입니다.
연구 결과 및 중요하면서 가장 어려운 부분
컴파일러 기말고사의 90%가 구문분석에서 나온다.
어휘분석은 출석수업을 통해 학습하지만, 구문분석은 혼자서 공부하기에는 어렵기 때문에
특강을 준비했고, 가장 핵심적인 SLR 구문분석이라는 것을 배우게 된다.
보통 구문분석이라고 하면 TOP DOWN / BOTTOM UP 구문 분석이 있는데,
TOP DOWN은 단점이 너무 많기 때문에
요즘은 BOTTOM UP 구문분석을 사용하고 있다.
BOTTOM-UP 안에서 SHIFT REDUCE /FIRST / FOLLOW가 세부적으로 나온다.
파싱표를 만들 때 FIRST와 FOLLOW의 기호를 알아야한다.
1. Top-Down 구문분석
시작 기호 --> 문장
예) id + id * id 좌단 유도 하라
문법
E -> E+ E (1번째 규칙 )
E -> E* E (2번째 문법 규칙)
E -> id (좌단의 E에 적용)
좌단유도 과정 (왼쪽 또는 오른쪽 중 왼쪽 부터 유도)
1번째 규칙에 있는 좌단 E에 id를 적용하고 2번째 문법 규칙을 적용한다.
id를 유도하기 위해
E -> E + E
-> id + E
-> id + E *E
-> id + id * E
-> id + id * id
** 더 이상 유도할 것이 없는 경우 '터미널'이라고 한다.
-> 터미널이란, 종료지점!!
But, 논터미널 기호는 'E'와 같다. 문법 규칙의 왼편에 있는 것은 논 터미널이라고 한다.
좌단 또는 우단 유도에 있어서 기준은 논터미널을 기준으로 생각하면된다.
** 기말고사 또는 워크북에
좌단유도한 것이 아닌 것은? 우단 유도한 것은? 과 같은 문제가 출제된다.
**
문법을 보고 유도해서 나오면 yes (True)
문법을 보고 유도했는데 안 나오면 no (False)
**
문법을 보고 유도하는 연습을 많이 해야 구문분석을 이해할 수 있다.
시작 트리(루트)
E Top
/ | \ |
E + E |
| / | \ |
| E * E |
| | | ↓
id id id Bottom
2. Bottom-Up 구문분석 ( Top-Down의 반대)
E -> E + E
E -> E * E
E -> id
id + id * id
reduce -->E + id * id
-->E + E * id
-->E + E * E
-->E + E
-->E
시작 트리(루트)
E Top
/ | \ ↑
E + E |
| / | \ | (reduce : 거꾸로 올라간다.)
| E * E |
| | | |
id id id Bottom
TOP-DOWN 의 트리 형식에서 하단에서부터 시작해서 reduce하면서 올라가는 것
시작 기호가 나오면 reduce 할게 없을 때 끝이난다.
문장을 계속 리듀스하다가 시작기호 나올 때까지 !!
Bottom에서 올라가면서 구문분석하는 것이 바로 Bottom-Up 구문분석이다.
올라가는 과정에서 reduce를 하면서 올라가고, 시작기호가 나오면 끝
(*늘 기준은 Non터미널(대문자) 관점에서 볼 것)
시작기호 나오면 YES (True)
시작기호 안나오면 NO (False)
오른쪽부터 유도 과정을 거치기에 이것은 우단 유도 과정이 된다.
우단 유도 과정
컴파일러 관점에서 아래의 id라는 시작기호가 굉장히 중요하다.
id + id * id
-> E + id * id
-> E + E * id
-> E + E * E
-> E + E
-> E
현재 노란색 표시가 'Handle'이다.
문제 풀이 :
id+id*id문장 읽고 , id어 ! 핸들이네!!
id 읽어서 리듀스 과정을 표현하고
엇 또 id핸들이네 이것도 리듀스해주자
그러고 E*E가 핸들이네 하면 리듀스해주고
어 E+E 전체가 핸들이네 하고 리듀스해줘서
시작기호 E까지 오게된다.
구문분석에서 가장 필요한 정보는 Handle이고
어떻게 하면 이 Handle을 정확히 찾아서 구문분석에 전달할까??할 때
필요한 것이 바로 파싱표이다.
파싱표를 만드는 것이 목표가 된다.
* 문제 풀 때 아래 기본적인 틀은 알아야 문제 맞출 수 있다.
//
<핵심정리>
BOTTOM-UP 문장 시작 -> 시작 기호 찾을 때까지 리듀스 하는 것
문장의 유도 과정은 우단 유도다 .
TOP-DOWN 시작 기호- >문장 끝날 때까지
문장의 유도 과정은 좌단 유도다.
//
3. Shift - Reduce 구문분석 (아래와 같은 단계,스택,입력,구문분석행동 표가 시프트리듀스구문분석)
reduce 한다(문법규칙 거꾸로 적용하는 것 의미)
스택, 입력버퍼 모두 비어있을 때 맨 마지막을 $ 라고 표현 할 것이다.
(예) id+id*id
** +, * 는 리듀스할 수 있는 게 아니다. shift하면 스택에 더해지는구나.
| 단계 | 스택 | 입력 | 구문분석행동 |
| 0 | $ | id+id*id$ | shift id |
| 1 | $id | +id*id$ | reduce E -> id |
| 2 | $E | +id *id$ | shift + |
| 3 | $E+ | id*id$ | shift id |
| 4 | $E+id | *id$ | reduce E -> id |
| 5 | $E+E | *id$ | shift * |
| 6 | $E+E* | id$ | shift id |
| 7 | $E+E*id | $(입력버퍼에 아무것도 없다) | (reduce 할것만 남음) reduce E -> id |
| 8 | $E+E*E | $ | reduce E -> E*E |
| 9 | $E+E | $ | reduce E -> E+E |
| 10 | $E | $ | accept (YES == TRUE) |
위와 같은 표처럼 하는 단계를 알려줄 수 있는 게 파싱표이다.
위의 그림에서 오른쪽이 SLR 파싱표인데, 숫자 옆에 'S'는 Shift 이고 'r'은 reduce라는 것을
알면 쉽다.
입력 기호는 2번째 행에서 찾으면 된다.
상태는 5번 상태로 만들어주고, 5번 상태에서 +를 보면 r6이 나오고 ,
reduce6가 되는거니깐, 스택에 있는 것을 6번 규칙 F->id 로 리듀스해라.
스택에는 상태가 있어야한다. 근데 리듀스하고 나면 늘 상태가 없어진다.
그런 경우에는 상태를 찾는 방법에서 0번상태에서의 F를 보면 된다 .
GOTO함수의 논터미널을 찾고 0번 상태를 찾아서 해당하는 상태로 바꿔준다.
LR(0)항목은 무엇인가? (마킹 되어있는 상태)
A-> XYZ
[A-> . XYZ] 읽을 항목의 앞에 . 이 있다. -> Closure 항목
[A-> X.YZ] - \ 커널
[A->XT.Z] - /
[A-> XYZ.] -> reduce 항목
*closure와 reduce를 이용할 것.
Closure란?
[A ->aBb]이라는 규칙에서
논터미널 B를 생성규칙의 왼쪽으로
갖는 LR(0)항목들의 집합
:B를 읽고자한다. B를 유도할려고한다.
[B ->aCb]
4. FIRST
5. FOLLOW