[컴파일러] LL(1) 파서 문제 풀이
참고로, LL(1) 파서는 한 글자만 내다보고 parsing 을 수행한다는 뜻입니다. k 글자까지 내다본 뒤 parsing을 수행하는 경우 LL(k) 파서라고 불립니다.
저는 이 포스팅의 예시 문제에서 predictive parser, 그러니까 non-deterministic LL 파서만 다룰 것입니다.
또, non-terminal과 terminal, 그리고 문법으로 non-terminal에서 terminal을 유도(derivation)하는 내용에 대해 대략 안다고 가정하고 설명하겠습니다.
기본적인 개념 내용은 제 이전 포스팅에서 설명해놓았으니 참고바랍니다.
https://nsa901.tistory.com/114
[컴파일러] LL 파서와 LR 파서
안녕하세요 밥한그릇 입니다. 제가 이번에 학교에서 수강한 컴파일러 과목의 기말고사 시험이 끝난 지 이틀이 지났네요.. 시간을 많이 들여 강의노트를 정리한 페이지를 만들고, 거의 통째로 외
nsa901.tistory.com
LL 파서 (top-down parser)
예제 1 : Parsing table에 따라 파싱하기
아래의 예시는 어떤 소문자들로만 이루어진 프로그래밍 언어를 입력으로 준 경우입니다.
이를 어떤 초기 상태(대문자)에서 말단 상태(소문자)로 확장시켜야합니다. 그게 아래 주어진 LL 파서의 역할입니다.
이 예시와 같이, 보통 그 문법 규칙의 번호가 표의 칸(entry)에 주어집니다.
이제 parsing 방법을 설명해볼까요.
stack에 non-terminal이 들어가고 terminal이 input으로 주어집니다. non-terminal과 input을 앞에서부터 읽어가면서, 이 두개가 주어졌을 때의 규칙을 parsing table에서 찾아 수행하는 게 기본입니다.
여기서 먼저 한가지 주의해야 할 점은 $가 있는 쪽이 EOF(stack의 바닥)이라는 점입니다.
여기서 stack은 거꾸로 되있어 맨 앞에 $가 붙어 있다고 보면 됩니다. (= stack의 top(맨위)는 맨 뒤의 문자)
파싱 테이블을 보고 LL(1) parsing 하는 방법은 다음과 같이 소개 되어있습니다.
(X는 stack의 top에 있는 symbol, a는 현재 input symbol을 의미)
- X = a = $이면 종료 (accept)
- X = a이면 stack에 있는 X(=a)와 읽는 중인 input의 맨 앞에 있는 a 동시에 Pop 해서 버림
- X가 non-terminal일 경우
표를 찾아봐서 X (nontermial) → a(terminal)로 변하는 규칙 있으면 거기 있는 규칙번호를 사용 (= M[X,a]에 있는 규칙 사용)
→ 그 규칙번호에 있는 문법의 결과(유도)로 X 치환 - 위의 어느 규칙도 만족하지 않고, 표 찾아봤는데 찾은 칸이 비어있으면 error
말은 쉽지만 잘 이해가 가지 않죠?
먼저 예제를 보면서 같이 풀어보면 이해가 될 거에요.
순서대로 Stack, input, Actions일 때 시작상태라고 합시다.
1. stack에 있는 것은 $S , input은 aabbb$ 일텐데 여기서 stack의 top(맨 앞)이 S, input의 맨 앞이 a입니다.
이때 S와 a가 만나는 표를 보니 1이 써져있군요. 그러면 Stack의 top 있는 S에다가 규칙 1을 적용해줍니다.
S였던 문자열을 규칙 1에 맞게 aSb로 치환해주었어요.
그럼 [stack] $S, [input]aabbbb$인 상태에서, [stack] $bSa , [input]aabbbb$ 인 상태로 변했죠.
2. 이어서 해볼까요. [stack] $S, [input]aabbbb$인 상태에서, [stack] $bSa , [input]aabbbb$ 인 상태에서 또 시작해봅니다.
stack의 top은 a, input의 맨 앞은 a네요. 같은 값이 나왔으므로 두 값 모두 pop 해서 버립니다.
이제 상태가 [stack] $bS , [input]abbbb$ 가 되었어요.
... 이런 식으로 쭉 진행을 하게 되는 거에요.
3. 마지막에 아무 값도 안 남고 stack과 input 모두 $ 만 남아 비어있게 된 상태가 되면 parsing을 종료합니다.
예제 2 : Parsing table 구현하기
Parsing table을 구현한다는 것은, non-terminal X 상태일 때 input의 맨 앞에 terminal a가 주어질 경우 적용할 규칙을 정한다는 것입니다. 그리고 그 규칙은 표의 M[X, a] 위치에 적어줍니다.
따라서, parsing table을 구현하기 위해서는 FIRST와 FOLLOW 알고리즘이 필요합니다.
input의 맨 앞에 주어진 non-terminal a를 찾아야하기 때문에 FIRST 알고리즘이 필요한 것입니다. 그리고 이 non-terminal이 다른 문자열(terminal)을 생성하지 못하고 사라지는 경우(= A→ε 인 경우)에, 그 뒤에 올 다음 terminal을 찾아와야하기 때문에 FOLLOW 알고리즘이 필요하다고 이해하면 됩니다.
FIRST(X)와 FOLLOW(X) 알고리즘 이해하기 (예제)
문법 규칙을 풀이하면 FOLLOW(X), FIRST(X)를 손쉽게 구할 수 있습니다.
다음은 그 예제입니다.
첫번째로 FIRST 알고리즘 예제를 살펴봅니다.
FIRST(X)를 구하려면 우변에 non-terminal X를 갖는 규칙들을 먼저 보아야합니다.
시험삼아 예제 2의 FIRST(E)를 구해볼까요?
FIRST(E)를 구하자는 것은 즉, non-terminal E가 유도한 최종 문자열(=terminal)의 앞 문자를 구하자는 것입니다.
좌변에 E를 가지는 식을 보니 1번 규칙인 E -> TE'가 보입니다. E를 유도했을 때 앞에 T라는 non-terminal이 유도되어나오는 모양인데요.
그러면 E가 유도한 terminal의 앞글자는 곧 T가 유도한 terminal의 앞 문자겠군요. 그러면 또 T를 좌변에 갖는 규칙을 볼까요.
이제 3번 규칙인 T->FT'가 보입니다. 이제 T가 유도한 terminal의 맨 앞 문자는 곧 F가 유도한 terminal의 맨 앞 문자라는 걸 알게되죠.
이제까지 FIRST(E)=FIRST(T)=FIRST(F)인 셈입니다.
F를 좌변에 가지는 규칙을 보니, F -> (E) | id가 있습니다. F는 (E)와 id를 유도한다는 것이죠. F가 유도하는 terminal의 맨 앞 문자는 "(" 또는 id 입니다. 그러면 FIRST(F) = {(, id}라고 적을 수 있습니다.
그 다음으로 FOLLOW 알고리즘 예제를 살펴봅니다.
FOLLOW(X)를 구하려면 우변에 non-terminal X를 갖는 규칙들을 먼저 보아야합니다.
시험삼아 FOLLOW(F)를 구해볼까요?
FOLLOW(F)를 구하자는 것은 즉, non-terminal F의 바로 다음에 올 문자를 구하는 것입니다.
우변에 F를 가지는 식을 보니 3번 규칙인 T-> FT'와 4번 규칙인 T'->*FT'가 보입니다. 이럴 경우는 어떻게 FOLLOW(F)를 구할까요?
먼저 확실한 것은, F 다음에 무조건 non-terminal T'가 나오네요. 이럴 경우 F의 바로 다음에 올 문자에는 T'의 맨 앞 문자도 포함되겠죠?
그러니 FOLLOW(F)에는 FIRST(T')를 먼저 포함시켜줍니다.
그런데 이때 만일 T'가 ε이 되어버리는 경우는요? 그럼 F 바로 다음엔 뭐가 올까요?
예를 들어 현재까지 문자열이 Tabc이고 T를 FT'로 유도하여 FT'abc가 되었다고 해봅시다.
이때 T'가 ε이 되어 사라지면 Fabc가 됩니다. 그러면 이 F 바로 뒤의 a 부분은 어떻게 찾아야 나올까요? 예, 바로 FOLLOW(T)입니다. 처음의 Tabc 상태에서 그 뒤에 있던게 abc니까요. 그러면 FOLLOW(F)에는 FOLLOW(T)도 포함되게 됩니다.
이때, FOLLOW(F)의 결과에서는 ε를 제외해야합니다.
이유 : 기본적으로 FOLLOW의 결과는 절대 ε(공집합)이 포함될 수 없습니다. 왜냐하면 문자열의 끝인 EOF가 항상 $이므로 ε 대신 최소한 $이 들어가게 되기 때문이죠.
결론적으로, FOLLOW(X)는 A->XB일 때 FIRST(B) + FOLLOW(A) - {ε}로 계산할 수 있습니다.
만일 A->X일 경우 FOLLOW(X) - {ε}이겠지만요.
A → XB 일때, FOLLOW(X) = FIRST(B) + FOLLOW(A) - {ε}
A → X 일때, FOLLOW(X) = FOLLOW(A) - {ε}
FOLLOW(X)와 FIRST(X) 이용해서 Parsing table 채우기
비어있는 표와, FIRST(X), FOLLOW(X) 그리고 X에 관한 문법 번호만 있으면 parsing table을 만들 수 있습니다.
간단하게 규칙을 제시하면 다음과 같습니다.
NonTerminal A,B,C가 nullable이 아니라면, First(A,B,C)를 기록한다.
NonTermianl A,B,C가 nullable이라면, Follow(A,B,C)를 기록한다.
- FIRST(X)는 X를 terminal로 유도했을 때 맨 앞에 나오는 terminal.
- FOLLOW(X)는 A→XB일 때 : FOLLOW(A) + FIRST(B) - {ε}임
- 주의) X가 start symbol일 경우 $ 추가하기!!
정리
- A는 non-terminal이고, FIRST(A) 또는 FOLLOW(A)는 non-terminal이다.
- M[A, FIRST(A)]에 'A → (해당 FIRST(A)를 유도한 규칙)'의 규칙 번호를 적어준다.
- FIRST(A)에서 ε인 경우에만, M[A, FOLLOW(A)]에 A → ε 의 규칙 번호를 적어준다.
무작정 표를 채우려면 어려워보이지만, 정리하자면 위와 같은 과정을 따라 문제를 풀 수 있습니다.
위에 나온 표를 비워놓은 빈 표를 준비합시다. 이제 제 설명을 따라가며 표의 칸에다 번호를 적어봅시다.
한번, non-terminal E'의 줄에 있는 칸들을 채워볼까요?
우선 FIRST(E')가 뭔 지 먼저 알아봅시다. FIRST(E') = {+, ε }이 나오네요.
이제 M[E, FIRST(E')]의 자리에 규칙번호를 채워야해요.
그러니 M[E',+]의 자리에는 +가 맨 앞에 나오는 규칙인 E'->+TE'의 규칙번호 2를 적어줍니다.
이제 M[E', ε]를 채우려 하니... ε 는 non-terminal에 없죠. 그러면 어디에다가 어떤 규칙을 써야할까요?
이때는 M[E', FOLLOW(E')]의 자리에 E'에서 ε 를 유도하는 규칙의 규칙번호를 대신 써주면 된답니다.
보니까 3번 규칙이 E'-> ε 로 ε 를 유도하네요. FOLLOW(E')는 {), $}이니, M[E', )]와 M[E',$]의 자리에 그 규칙번호인 3을 써줍니다.
이 과정을 반복하면 LL 파싱 테이블을 어렵지 않게 구현할 수 있습니다.
예제 3 : 이 문법은 예측 parsing이 가능한가? (LL condition)
LL 파서의 모든 경우에서 deterministic parsing, 즉 예측 parsing이 가능한 것은 아닙니다.
앞서 보여드린 parsing table의 각 칸에 쓰인 규칙 번호가 한 개가 아니라면 어떻게 될까요? 표의 칸 하나에 번호 여러 개가 쓰여있을 경우 말이에요.
이 경우 한 규칙을 사용해보고, 그게 안되면 다시 돌아나와서 다른 것을 선택하는 backtracking이 일어나게 됩니다. 이런 경우를 non-deterministic LL parser라고 부르지요.
예측 parsing이 가능하다는 것, 즉 detereministic parser라는 것은 파싱 테이블에서 각 칸이 겹치지 않고 하나의 규칙만 가지게 되는 경우와 같습니다.
그러한 예측 parsing의 조건은 다음과 같습니다.
A → a | ß 일 때
- FIRST(a)와 FIRST(ß) 겹치지 않아야한다.
- a가 ε 유도하는 경우, FOLLOW(a)와 FIRST(ß)가 겹치지 않아야한다.
한번 이해를 해볼까요.
LL condition을 "파싱 테이블의 규칙이 한 칸 당 하나씩 있을 경우의 조건"으로 바라보면 쉽게 이해할 수 있습니다.
첫번째 조건에서, FIRST(a)와 FIRST(ß)가 겹치면 유도결과가 둘다 똑같은 문자로 시작하는 것이겠죠. 이러면 테이블 구현 시 M[A,FIRST(A)]를 작성할 때 적을 칸이 겹치겠네요. 서로 다른 terminal을 유도하니 다른 규칙번호를 쓰는데, 칸이 겹치니 여러 개 규칙번호가 한 칸에 들어갈 수 밖에 없는 상황이 벌어질 거에요.
두번째 조건에서는, a가 ε되면 그 바로 뒤에 FOLLOW(A)의 terminal들이 나오게 되겠죠.
이때 FIRST(B)가 FOLLOW(B)와 같은 경우를 예를 들어볼까요. A123의 상태에서 유도규칙을 적용하여 a123과 ß123으로 만들었다고 해봅시다 이때 a가 ε이 되어 사라지고 ß가 FOLLOW(A)와 같은 1으로 시작할 경우 두가지를 모두 볼 거에요. 앞선 경우는 123, 뒤의 경우는 1(~~)123라는 문자열이 만들어집니다. 이때, 완성된 파싱테이블으로 파싱할 때 M[A, 1]을 찾는 경우 앞의 결과물과 뒤의 결과물의 규칙 칸이 또 겹칠 수 있습니다. 저는 이렇게 첫번째 조건과 두번째 조건을 이해했습니다.
이제 예제를 통해, 다음 문법 규칙은 LL condition을 만족하는 지 아닌 지 한번 풀어봅시다.
G1의 경우 먼저 볼까요.
FIRST(S)인 iCtSS’와 a가 서로 겹치는 가? → X → 1번째 조건 만족
둘 중 어느 것도 우변이 ε 생성하지 않음 → 2번째 조건 만족
그럼 이제 G2의 경우를 봅니다.
S’의 우변에 ε 있음 (2번째 조건 봐야함)
ε 생성하는 문법 이외에 다른 문법은 S’ → eS
FIRST(eS) = e
FOLLOW(S’)와 FIRST(eS)가 겹치는가? → FOLLOW(S’)에 e 있으므로 겹침
→ 2번째 조건 만족하지 않는다!
⇒ LL(1) 조건을 만족하지 않음!
이런 방식으로 LL 조건을 만족하는 지 아닌 지 검사해볼 수 있습니다.
컴파일러 과목을 공부할 때 제게 특히 어려웠던 부분이 이 부분인데요. 이 부분에 대한 설명 자료가 얼마 없기도 하고 해서 누군가에게 도움이 될까 싶어 만들어본 포스팅입니다. 쉽게 풀어 설명하는 것을 목표로 노력했네요.
제 포스팅이 도움이 되었다면 공감 버튼 눌러주세요^^
질문이나 추가 설명 요청, 지적 등은 댓글로 남겨 주시면 감사하겠습니다.
'IT > 학과 공부' 카테고리의 다른 글
| [전공] C에서의 변수의 scope와 lifetime (0) | 2022.06.11 |
|---|---|
| [컴파일러] LR 파서 문제 풀이 (0) | 2022.06.11 |
| [컴파일러] LL 파서와 LR 파서 (0) | 2022.06.10 |
| C에서 시그널을 보내고 처리하는 방법 (kill, signal, sigaction) (0) | 2022.01.06 |
| [KOCW] 운영체제 3차시 - 프로세스 관리 (0) | 2021.11.08 |
