컴파일러구성 - [제12강] Top-down 구문분석

컴파일러구성 - [제12강] Top-down 구문분석

LL조건 ·Recursive descent 구문분석 ·Predictive 구문분석

컴파일러 용어정리

• top-down 구문분석
  주어진 문자열과 같은 문장을 생성하기 위하여 시작기호로부터 생성규칙을 적용하여 유도해 나가는 방법
  top-down 구문분석의 종류에는 recursive-descent 구문분석과 predictive 구문분석이 있다.
• backtracking
  생성규칙이 잘못되어 주어진 문자열을 생성할 수 없으면 그 생성규칙에서 보았던 문자열을 다시 검조하여 다른 생성규칙을 갖고 유도를 시도하는 방법으로 구문분석의 효율을 저하시킨다.
•  LL 구문분석
  backtracking 하지 않고 구문분석 할 수 있는 방법으로 입력기호를 보고 적용될 생성규칙을 결정적으로 선택하여 유도하는 방법으로 현재의 입력 기호와 터미널이 같지 않으면 주어진 문장을 틀린 문장으로 판단한다.
• LL 문법
  LL 구문분석 조건을 만족하는 문법
• LL 조건
  LL 조건은 임의의 생성규칙 A → α| β ∈ P에 대해서 다음 조건을 만족해야 한다.
  1. FIRST(α) ∩ FIRST(β) ＝ ø;
  2. if ε ∈ FIRST(α) then
  FOLLOW(A) ∩ FIRST(β) ＝ ø

요점정리

1. top-down 방식은 주어진 문자열과 같은 문장을 생성하기 위하여 시작기호로부터 생성규칙을 적용하여 유도해 나가는 방법이다. 이 과정에서 생성규칙이 잘못되어 주어진 문자열을 생성할 수 없으면, 그 생성규칙에서 보았던 문자열을 다시 검조하여 다른 생성규칙을 갖고 유도를 시도한다. 이와 같은 과정을 backtracking이라 부르며 한 입력기호를 여러 번 반복하여 검조하기 때문에 시간이 매우 많이 걸린다.
2. top-down 방법은 실제적인 컴파일러의 구문분석의 알고리즘으로 사용하기에는 부적당하다. 따라서 backtracking하지 않고 결정적으로 구문분석 할 수 있는 방법이 요구되며 이와 같은 구문분석 방법을 LL 구문분석이라 부르며 이 조건을 만족하는 문법을 LL 문법이라 한다.
3. LL 구문분석은, backtracking을 없애고 left-recursion 이 발생하면 right-recursion으로 바꾸어주며, 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재하면 left-tracking 함으로써 일반적인 구문분석을 하는 방법이다.
4. LL방법은 주어진 문자열과 같은 문장을 생성하기 위하여 현재의 입력기호를 보고 적용된 생성규칙을 결정적으로 선택하여 유도한다. 그리고 현재의 입력기호와 생성된 터미널 기호가 같지 않으면 주어진 문장을 틀린 문장으로 간주한다. 이와 같이 결정적으로 구문분석을 하기 위해서는 주어진 문법이 어떤 특정한 조건을 만족해야하는데, 이 조건을 LL조건이라고 부른다.
5. recursive-descent 구문분석은 하나의 구문분석기가 backtracking 없이 그의 입력을 인식하기 위해서 재귀적 프로시저(recursive procedure)의 집합을 사용하는 방법으로서, 구문분석의 행동을 결정적으로 하기 위해서 생성규칙의 lookahead를 사용한다. strong LL 문법을 사용하는데, 생성규칙의 lookahead를 이용하여 생성규칙을 결정적으로 선택할 수 있는 문법을 strong LL 문법이라고 부른다.
6. predictive 구문분석은 recursive-descent 구문분석의 방법에서 생성규칙이 바뀔 때마다 구문분석기를 바꾸지 않고 파싱표만 고쳐서 구문분석기를 구현하는 방법으로서, bottom-up 구문분석기와 마찬가지로 입력버퍼와 스택, 구동기 프로그램으로 구성된다. predictive 구문분석은 LL(1)문법을 가지고 구문분석을 하기 때문에 LL(1) 구문분석 방법이라고 한다.

연습문제

• 

  다음 구문분석에 대한 설명 중 틀린 것은?

  답을 체크하세요

  1. LR 파싱표를 구성하는 방법은 SLR, CLR, LALR 방법이 있다.
  2. SLR은 구현하기 쉽지만 완전하지 못하고, CLR은 가장 적당하지만 구현하기가 매우 힘들다.
  3. Top-down 구문분석 중 backtracking을 하지 않은 것을 LL 구문분석이라고 한다.
  4. Bottom-up 구문분석의 종류에는 Recursive-descent 구문분석과 Predictive 구문분석이 있다.

  정답 :

  ④

  CLR 은 lookahead를 구해야 하므로 과정이 복잡하고 시간이 오래 걸리며 파싱표가 커진다는 단점이 있다.
  Top-down 구문분석의 종류에는 Recursive-descent 구문분석과 Predictive 구문분석이 있다. 

• 

  다음 중 Top-down 구문분석과 관계 있는 것은?

  답을 체크하세요

  1. LL
  2. SLR
  3. CLR
  4. LALR

  정답 :

  ①

  LL 구문분석은 Top-down 구문분석이다.
  Top-down 방법은 실제적인 컴파일러의 구문분석 알고리즘으로 사용하기에는 부적당하다. 따라서, backtracking를 하지 않고 결정적으로 구문분석할 수 있는 방법이 요구된다. 이와 같은 구문분석 방법을 LL 구문분석이라 부르며 이 조건을 만족하는 문법을 LL 문법이라 한다.

• 

  Top-down 구문분석과 관계 없는 것은 ?

  답을 체크하세요

  1. back tracking
  2. left recursion
  3. 우파스
  4. left factoring

  정답 :

  ③

  3번의 우파스는 Bottom-up 구문분석과 관계가 있다.

• 

  다음 중 Top-down 구문분석에 대한 설명 중 틀린 것은?

  답을 체크하세요

  1. backtracking 의 경우 효율을 떨어뜨리므로 left-factoring을 해야 한다.
  2. left-recursion의 경우 무한 루프에 빠지므로 right-recursion으로 바꾸어주어야 한다.
  3. 이러한 문제점을 해결한 결정적인 구문분석을 LL 구문분석이라고 한다.
  4. 일반적으로 Bottom up 방식보다 편리하므로 자주 사용된다.

  정답 :

  ④

  일반적으로 문법적인 제약이 없는 Bottom up 방식을 사용한다. 

• 

  다음은 Top-Down 구문분석에서 predictive 파싱표를 구성하는 과정이다. 빈칸 ‘가’에 들어갈 내용은?
  

  문법
        1) E → TE'
        2) E' → ＋TE'
        3) E' → ε
        4) T → FT'
        5) T' → ＊FT'
        6) T' → ε
        7) F → (E)
        8) F → id
  
          FIRST(E) ＝ FIRST(T) ＝ FIRST(F) ＝ { ( , id }
          FOLLOW(E) ＝ FOLLOW(E') ＝ {), $}
          FOLLOW(T) ＝ FOLLOW(T') ＝ {＋, ), $}
          FOLLOW(F) ＝ {＋, ＊, ), $}
  
  [파싱표]
  

  VT VN	id	+	＊	(	)	$
  E	E → TE'			E → TE'
  E'		E'→ ＋TE'			( 가 )	E' → ε
  T	T → FT'			T → FT'
  T'		T'→ ε	T'→ ＊FT'		T'→ ε	T'→ ε
  F	F → id			F → (E)

  답을 체크하세요

  1. E'→ ε
  2. E → TE'
  3. F → (E)
  4. E' → ＋TE'

  정답 :

  ①

  문법에서
      E' → ε
     FOLLOW(E') ＝ {), $}
  알고리즘을 적용하면
      M[E', ) ] :＝ E' → ε
      M[E', $ ] :＝ E' → ε