TopDownParsing

탑다운 파싱

• Left most derivation
• recursive descent parsing: 백트랙킹 사용으로 비효율, 무한루프 때문에 좌재귀를 없애야 한다.

predictive parser

• LL(k)
• 백트랙킹이 없다.
• 파싱 과정
  stack/input/action

1. 시작 심볼을 stack에 넣는다.
2. generate/match
   2-1. 테이블에 따라 top과 input 비교하고 변환
   2-2. top과 input 이 같으면 둘다 제거
3. mismatch나 테이블에 값이 없으면 error

Left recursion 제거하는 방법

• 직접 좌재귀는 S'을 만들어 제거
• 간접 좌재귀는 논터미널 기호를 RHS(오른쪽 거)로 변환

Left refactoring

• 공통인자를 묶어서 새로운 논터미널 심볼 생성
• 인자의 심볼의 수가 다수여도 동일하게 묶는다.

First

• 해당 논터미널 기호에서 유도해 나타낼 수 있는 터미널 기호 집합
• InitFirst
  • $A \rightarrow a\alpha$ 인 경우 $a\in$ InitFirst(A)
• First
  • $a|a \in First(B), A \rightarrow B\alpha$ 인 경우 $a \in$First(A)

Follow

• 해당 논터미널 기호 다음에 나오는 터미널 기호들의 집합
  • $\epsilon$은 포함하지 않는다.
  • Start Symbol은 $를 기본적으로 갖는다.
• InitFollow
  • $a \in V_T| B \rightarrow \alpha AX\beta, a \in First(X)$ 인 경우 $a \in$ InitFollow(A)
• Follow
  • $a| a\in Follow(B), B \rightarrow \alpha A$ 인 경우 $a \in$ Follow(A)
  • $\epsilon$으로 뒷 문자가 유도 될 수 있는 경우도 생각

파싱 테이블

1. $A \rightarrow \alpha$ 일 때 a $\in$ First($\alpha$) 이면
   • M[A, a]에 $A \rightarrow \alpha$ 추가, $\alpha \in V^*$
2. $A \rightarrow \alpha$ 일 때 First$(\alpha ) = \epsilon$ 이면
   • Follow(A)에 해당하는 원소에 $A \rightarrow \alpha$ 추가
   • 위 경우 실질적으로 $A \rightarrow \epsilon$ 이다.