4장 Lexical and Syntax Analysis 2(lecture 10)

이전에 이어서 이번엔 parser(=syntax analyzer)에 대해 알아볼거

 

parser의 목적 :

 

1. 모든 syntax error를 발견하고 , 적절한 진단 메세지를 제공하여 해당 error를 해결하는 것

 

2. 프로그램에 parse tree를 제공하는 것(tree 형태로 문장구조를 분석한게 parse tree임)

 

 

 

parser는 CFG를 통해 정의된 생성 규칙을 따르며 그 생성 규칙들이 실행되는 방식은 2가지로 나뉨

 

top-down방식과 bottom-up방식

 

cf. CFG(context free grammar) - 언어학, 전산학에서 사용되는 형식의 문법

 

 

 

*top-down은 말그대로 위에서 아래로 tree가 확장하는 형태 

// 점차 확장하는 형태이므로 일명 bad pick 잘못된 선택을 했을시에 back track이 필요하다.

 

*bottom-up은 아래이서 위로 tree가 줄어드는 형태

 

두 개의 그림은 아래에 자세한 설명할 때 삽입하겠음.

 

 

둘의 간단한 비교

 

-top-down방식의 알고리즘이 더 쉬움

 

-문법(grammar)중에는 top-down 방식으로는 parse(문법적으로 분석) 되지 않는 경우가 있다.

그러나 거의 대부분의 문장구조(CFGs)는 bottom-up 방식으로 parse 가능함.

//의미가 grammar랑 CFG랑 그냥 같은 의미로 쓴 것 같음. 문장 전체적인 뜻은 말장난같이 뭔가 싶었는데

아마 bottom-up 방식으로 분석되지 않는 경우보다 top-down으로 분석되지 않는 경우가 많다는 늬앙스인 것 같다.

 

 

 

*Top Down Parser

 

 L L (k) grammar를 이용함

 1 2  3

 

1. 첫번째 L은 Left-to-right 로 input을 스캔한다는 것

2. 두번째 L은 derivation 하면 Leftmost derivation 을 생성됨을 의미

3. k는 미리보기 할 수 있는 토큰의 수 // look ahead가 IT분야에서 여러 뜻이 있는데 여기선 현재 처리하면서 미리 읽어올 수 있는 토큰의 수인듯

 

보통 k가 1, 즉 하나 정도의 입력을 미리 읽어 오는 게 유용하다고 함.

(이 1개를 읽는 다는게 뭔 의미냐면은 A->bB | cBb | a 라는 규칙이 있으면 우리가 얻어야할 최종결과가 abcd이면 앞에 a하나만 비교해서

선택을 한다는 것. k=2면 ab를 보고 선택을 하겠지. 그렇게 하면 선택을 할 순 없어서 syntax error가 나겠지만.)

 

leftmost라는건 가장 parse tree에 가장 왼쪽에 있는 녀석이 non-terminal이면 terminal 될 때까지 먼저 확장 시키는 거.

 

 

 

top-down parsing algorithm들 중에 유명한 방식은

 

1.코드를 이용해 실행되는 방식인 Recursive descent

2. 테이블을 이용해 실행되는 방식인 LL parsers         // 이거 위에 있는 LL(k) grammar와 다른건가? LL(K) grammar 를 테이블 이용해서 하는 알고리즘인가 봄.  

// 이 둘은 추후 다룬다 

 

 

 

*Bottom Up Parser

 

L R grammar를 이용함

1 2

 

1. L은 Left-to-right 로 input을 스캔한다는 것

2. R은 derivation을 하면 rightmost derivation이 생성됨 // 여기서 내가 착각한게 parse tree 진행이 rightmost인 것처럼 생각했었음.

 

cf. 이것의 parse order는 rightmost derivation의 역순임.

 

 

 

                왼쪽        오른쪽

이제 규칙이   A -> bB | cBb | a 일때  규칙 화살표의 역방향으로 가는 것임. 이전에 top-down에선 오른쪽의 문자열 중에 첫번째 하나만으로 비교해서 확장 해나갔지만, 이제는 오른쪽에서 왼쪽으로 가므로 하나이상의 문자를 선택해서 왼쪽으로 가도록 한다. 성공적으로 왼쪽으로 이동 할 때 해당하는 오른쪽이 (즉, bB ,cBb, a 중 옳은 하나) handle이라고 불림.

 

이해돕는 예시)

Grammar                                                   

 

S->aAc

A->aA | b

 

 

aabc 를 bottom up parse

 

먼저 aabc 안에서 handle 찾아봄, c로 끝나는 친구가 S이지만 맞는게 없음, 그 다음 왼쪽으로 한칸가서 b를 A로 바꿀 수 있는 걸 확인

 

aabc -> aaAc

 

그 다음 A부터 시작해서 보면 aA가 보임 aA를 A로 바꿀 수 있음

 

aaAc->aAc

 

그 다음은 그냥 딱 보임 aAc->S

 

결국 derivation을 보면 aabc->aaAc->aAc->S  // 맨 오른쪽부터 처리함

 

위 예시는 아주 간단한 거였고 실제 bottom-up parser는 맞는 handle을 찾는 것이 어렵다고 함.

 

 

 

 

Complexity of parsing

 

애매하지 않은 문법을 처리하는 parser는 복잡하고 비효율적이다. 의 시간이 걸림 // 문법이 애매하지 않아도 이렇게 복잡함.

 

parsing 과정에서 빈번한 back up과 reparse가 필요함

 

컴파일러는 애매하지 않은 문법들의 일부만 떼어서 처리하면 선형시간(O(n))에 해결이 가능하다.