[컴파일러 개론]LL 파싱과 FIRST, FOLLOW

TOP-DOWN 구문분석 유도과정과 비슷 -> 유도 트리가 파스트리가 됌

시작: -시작 심벌(S)의 첫번째 생성 규칙으로 유도하여 문자열 생성 

진행: - 유도 과정에서 생성된 문자열과 입력 문자열을 차례로 비교 

*유도된 문자열과 입력문자열이 같으면 계속 비교해 나감 

*유도 과정에서 생성된 문자열에 NONTERMINAL이 나오면 이 N의 첫번째 생성규칙으로 또 다시 유도하여 새 문자열 생성 후 비교해 나감 -> 여기서 뭔가 안나온다 다르면 ? -------------------------------->BackTracking 

 

BackTracking이란 비교한 두 문자가 같지 않을경우 Parsing했는데 원하는 값이 안나온다면 직전 생성 규칙을 잘못 적용한 것이므로 원위치 시키고 다른 생성규칙을 적용한다. 만약 더 이상 대체할 생성규칙이 없게 된다면 input문자열은 틀린 문장으로 인식한다. 

예제에 1번 생성규칙을 적용했을 때  3번 4번 둘 다 일치하지 않으므로 백트래킹을 2번을 다시 선택함.

 

LL파싱

 

-왼쪽에서 오른족으로 읽어가며(Left to right scanning) 

-좌파스(Left Parse)를 생성 top down 파싱을 따름 

 

-결정적으로 (deterministic)파싱 : 입력 문자를 보고 적용될 생성 규칙을 결정적으로 선택하여 유도, 준비가 필요

:각 입력 문자당 적용될 생성 규칙을 미리 뽑아 두고 시작 

: 한 입력 문자에 두 개 이상의 규칙 해당되면? 파싱 불가능!!(단점)  

ex-> A->c A->b 불가능

장점!! (Backtracking)이 없다!!! :  당연하지 Nonterminal 하나당 하나씩의 규칙이니간 뒤로 돌아가도 하나밖에 선택 못함.... 

Top down방식의 시간 낭비를 줄임 

 

LL파상 방법 

- 결정적 파싱이 되는 문법을 선별하건 다듬어서 그것만 받고(결정적 파싱), 각 입력 문자당 적용될 생성 규칙을 미리 뽑아두고 시작...! 이를 위해, 규칙으로부터 필요한 정보를 파악하여 모으기(set) FIRST, FOLLOW등~

 

FIRST

-nonterminal 로부터 유도되어 첫 번쨰로 나타날 수 있는 terminal의 집합.  ㄷ

입력값에 따라 규칙을 선택함 ex A-> aB , A-> BC, B->bx 이고 입력 String이 abc라면 첫번째 terminal값이 a임으로 첫 번째 규칙 A->aB를 선택한다, 만약 규칙에 첫번째 값이 nonterminal이라면 계산이 필요하다 .

 

FIRST계산 방법 

 

null  생성규칙 X-> null 형태로 

A가 null로 유도할 수 있으면 A가 nullable하다고 한다.

 

First를 구하는 방법으로 Ringsum을 이용할 수 있다. 

Ringsum 첫 번째 단계 

null을 표함하고 있는가?

->yes  -> A+B =(A-null) union B

-> no -> A+B=A

 

그 이후 First 집합에 nonterminal값들이 섞여 있을떄 FIRST( a , A , b, B ) ->  First(a) + First(A) +First(b) + First(B)로 표현한다.  

여기서 S에 d가 들어오면 당연히 오류

여기서 유의점 FIRST(S)와 같은 경우 nonterminal 두개가 연속 그럴땐 첫번째것하고만 하고 뒤에꺼 무시한다. FIRST(A)랑만 반복적으로 구함. 

밑 사진을 보면 명확해짐 

공집합시 First(b)와 union됌, 하지만 예상치 못한 terminal에 대한 힌트가 없을 떄 어떻게 해야 할까,,

First의 한계  A-> XX과 같은 생성 규칙이 있을 때 nonterminal A가 nullable한 경우에서 문제 발생 , FIRST만 가지고는 생성규칙을 결정적으로 선택할 수 없다. 위의 예 

 

A의 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정하는 것이 맞음.-> follow 

 

nonterminal 다음 terminal의 심볼이 매우 중요해짐 A-> Ba  

 

FOLLOW를 계산하는 방법

1.시작심벌은 $를 초기값으로 갖는다. FOLLOW(S) = {$}

2.생성 규칙의 형태가 A-> aBb, b!=null 일 때 FIRST(b)에서 null을 제외한 terminal 심벌의 B의 FOLLOW에 추가 

FOLLOW(B) =FOLLOW(B) union (FIRST(b)-{null}) 

3.형태가 A->aB 이거나 A->aBb 에서 FIRST(b)에  null이 속하는 경우 즉 B=>null , A의 FOLLOW 전체를 B의 FOLLOW에 추가  -> FOLLOW(B)= FOLLOW(B) union FOLLOW(A)

 A FOLLOW전체를 B의 FOLLOW에 추가? 왜? 왜냐하면 A->aBe이고 B-> Df 라면 parsing해도  B의 FOLLOW 뒤에는 A의 FOLLOW e가 포함됌 

 위 1,2,3번으로 기출풀기 FOLLOW는 FIRST가 주어짐