[컴파일러] 3. 예측 파서

 

 

파싱(Parsing)

• 하향식(Top Down)
  • 파스트리를 루트에서 시작하여 아래로
  • 쓸만한 파서를 쉽게 만들수 있지만, 속도가 느리고, 복잡한 경우는 어려워짐
• 상향식(Bottom Up)
  • 파스트리를 리프에서 시작하여 위로
  • 넓은 범위의 문법과 번역 계획 처리 가능

문법 예시

type -> simple | ^id | $ϵ$

simple -> integer | char | num dotdot num

 

예측 파싱법(순환적 내림차순 파싱법(Recursive-descent parsing)

• 예측기호(lookahead)를 이용하여 파싱시에 백트랙킹을 하지 않는 방법
• 입력을 처리하는 프로시저들의 실행 순서가 바로 파스트리로

백트랙(backtrack)

• 비 단말에서 생성규칙을 선택할 경우, 주어진 입력에 맞지 않아 다른 생성 규칙을 선택하기 위해 재시도를 하는 것

First($\alpha$)

• 비단말 기호 $\alpha$로부터 생성된 하나 이상의 문자열의 첫번째 기호로 나오는 토큰의 집합
• 예측기호가 속하면 $\alpha$규칙이 적용
• ex) 위 예시의 simple의 경우, first(simple) = {integer, char, num}

$ϵ$규칙의 사용

• 순환적 내림차순 파서에서 사용- 사용할 생성규칙이 하나도 없을 때

 

프로시저의 2가지 일

1. 예측 기호를 읽고 어떤 생성규칙을 사용할 것인지 결정
   • 예측기호가 FIRST에 속하면 $\alpha$가 오른쪽에 가진 생성규칙 선택
   • 두개 이상의 생성 규칙이 있으면, 예측파싱 불가능
   • 어떤 규칙의 FIRST에도 속하지 않으면, 오른쪽에 $ϵ$이 있는 규칙 사용
2. 생성규칙의 오른쪽을 그대로 입력하듯 처리
   • 오른쪽의 비단말에 해당 프로시저를 수행
   • 예측기호와 일치하는 토큰은 다음 입력을 읽도록 함
   • 예측기호와 토큰이 일치하지 않으면 오류 처리

 

오른쪽 순환으로 교체

• 왼쪽 순환은 무한반복이 됨.
• 왼쪽 순환 규칙은 A-> A$\alpha$ | $\beta$
• 이것을 A->$\beta$R, R-> $\alpha$R | $ϵ$ 으로