4장 Lexical and Syntax Analysis 3(lecture 11)_Top-down parse

Top-down parser를 본격적으로 더 파고들어 보자

 

대표적인 top-down parsers 알고리즘은  recursive descent parser 이다. 이 과정을 자세히 알려면 11강 pdf파일 그림을 참조할 것.

 

(저작권문제가 될까봐 올리진 못함 ㅠ, 하나하나 올리는것도 일이고.. 아주아주 한가하면 직접 만들어 올리겠지만, 그럴일 없을듯..

공부하는 사람의 마음을 알기에 필요한분은 메일 주소 남기면 파일을 보내드리겠음. 근데 빨리보내준다곤 장담 못함;; 구글링하는게 젤 빠름.)

 

 

이 recursive descent parsing 알고리즘을 사용할 때 주의점이 있음 , 문법적 제한과 관련해서 이 접근방식에 한계가 있기 때문

 

 

고려해야할 사항

 

1. Left recursion //이것도 직접, 간접으로 나뉨

 

*direct left recusion

 

A-> A+B  와 같이 오른편으로 확장에 바로 자기 자신을 포함하는 형태, 그러면 계속 A 자기 자신을 계속 호출해서 알고리즘이 진행되지 않고 깊이 깊이 계속 내려가는 거지. 지금 같이 바로 자신을 다시 부르는 경우가 direct left recusion 임

 

-->Solution(direct left recursion을 제거하는 방법)

A와 관련된 규칙을 일반화 하면

 

 와 같이 A로 시작하는 녀석들과 A로 시작하지 않는 녀석들로 나눌 수 있다.

 

그럼 이제 A와 관련된 규칙을 아래처럼 바꿔주면 된다.

 

 //참고로 A' 규칙 맨 오른쪽 끝에 있는 문자는 아무것도 없다는 표시임.

 

A'가 다시 A'로 가는 거 아님? 이럴 수 있는데 잘보면 A'는 알파 뒤에 가 있음.

 

왜 위에 식으로 바꿔도 되는가에 대해서 잠깐 고민해봤음 // 두 규칙이 모든 표현을 똑같이 표현 가능한가.

 

A가 A로 분기하는 것이 끝나려면 언젠가는 A로 시작되지 않는 녀석으로 가야함. 결국은 언젠가는 첫시작이 베타에 있는 내용중 하나가 될거란 얘기, 근데 그냥 베타로만 표현하면 이전에 알파의 내용들은 표현할 방도가 없어짐.

그래서 A'를 만들어줌. A'는 left recursion이 생기지 않게  A'가 아닌 알파로 시작하도록 함.  알파로 그냥 끝나면 뒤에 붙이면 끝나지만, 초기 규칙을 생각해보면 알파들이 연달아 올 수 있으므로 그냥 알파만 두게 해선 안되고 알파뒤에 A'를 붙여야함. 

 

*Indirect Left recursion

 

A -> BaA

B -> Ab

 

이건 결국에 한 단계 떨어져 있지만 A->A~ 이런형태를 또 만들어 줄 수 있음. 아까 위에 direct Left recursion과 똑같은 문제가 발생하게 된다.

이것도 제거하는 방법이 있다고는 하는데, 이 책에선 다루지 않음. //나중에 궁금하면 구글링해보도록 하고 일단은 넘어가자

 

 

 

2. left factoring  // 내 생각: 이건 안돌아가는건 아니고 효율성 때문인 듯...

 

Pairwise disjointness test

 

이 테스트는 A와 같은 non-terminal들의 규칙에서 오른쪽에 오는 문자열을 검사하는 건데. 이 문자열의 시작이 모두 다르게 되기를 원함

 

A -> aB | bAb | Bb

B -> cB | d

 

처럼 말이야.

 

근데

 

S -> E+T | E*T | E/T  처럼 다 E로 시작하면 더 헤멜수 밖에 없음(이건 recursive descent 방식을 이해하면 이해 될거임)

 

일반화 해보자

 

처럼 모든게 알파로 시작됨. left factoring이란 문제임! . //이걸 해결해보는 건 앞에 left recursion을 지우는 것 보단 생각하기 쉽네. 아래처럼 만들면 됨.