TopDownParsing

oak_cassia·2022년 5월 25일
0

Compiler

목록 보기
5/9

탑다운 파싱

  • 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
    • AaαA \rightarrow a\alpha 인 경우 aa\in InitFirst(A)
  • First
    • aaFirst(B),ABαa|a \in First(B), A \rightarrow B\alpha 인 경우 aa \inFirst(A)

Follow

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

파싱 테이블

  1. AαA \rightarrow \alpha 일 때 a \in First(α\alpha) 이면
    • M[A, a]에 AαA \rightarrow \alpha 추가, αV\alpha \in V^*
  2. AαA \rightarrow \alpha 일 때 First(α)=ϵ(\alpha ) = \epsilon 이면
    • Follow(A)에 해당하는 원소에 AαA \rightarrow \alpha 추가
    • 위 경우 실질적으로 AϵA \rightarrow \epsilon 이다.
profile
벽에 붙은 달팽이 ↑i@

0개의 댓글