컴파일러구성 - [제6장] Context-free 문법의 효율화

컴파일러구성 - [제6장] Context-free 문법의 효율화

유도 트리 모호성 Context-free 문법의 효율화 푸시다운 오토마타

컴파일러 용어정리

푸시다운 오토마타 (push-down automata) : context-free 언어를 받아들이는 인식기

유도트리(derivation tree) : 구문분석을 하는 과정에서 문장이 유도되는 과정을 트리형태로 표현하는 것

모호성(ambiguous) : 문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖은 경우

단일 생성규칙(single production) : 생성규칙들 중 생성규칙의 오른편이 단 한 개의 논터미널로 구성되어 있는 생성규칙이 존재하는 경우

backtracking : 문장을 유도하다가 일치하지 않아서 다른 문법 규칙을 적용하기 위하여 다시 이 전 위치로 돌아가는 현상.

left-factoring : 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우, 공통된 prefix를 인수분해하는 것

prefix : 전위표기, 앞에 있는 기호

left-recursion 문법이 어떤 문자열 α에 대해 A ‗⇒ Aα의 유도과정이 존재하는 경우

요점정리

1. context-free 언어는 자연언어를 표현하기 위해 도입되었으며, 정규언어보다 표현범위가 넓어서, 이것을 인식하는 푸시다운(push-down) 오토마타를 구현하는 일은 유한 오토마타를 구현하는 일보다 훨씬 복잡하고 어렵다.
2. 유도 과정의 각 단계에서 문장형태의 가장 왼쪽에 있는 논터미널 기호를 계속해서 대체하는 경우를 좌단유도(leftmost derivation)라 하며, 반대로 가장 오른쪽에 있는 논터미널 기호를 계속해서 대체하는 경우를 우단유도(rightmost derivation)라 한다.
3. 구문분석의 방법은 크게 두 종류가 존재하며, 하나는 Top-down 구문분석이고 다른 하나는 Bottom-up 구문분석이다. 또한 구문분석을 하는 과정은 문장이 유도되는 과정을 트리형태로 표현하는데, 이를 유도트리(derivation tree) 또는 파스트리(parse tree)라 한다.
4. 문장이 효율적으로 인식되기 위하여 context-free 문법이 가지고 있는 비효율적인 부분들인 모호성, 불필요한 생성규칙, 모호성, ε-생성규칙, 단일 생성규칙, backtracking, left-recursion 등을 제거해야 한다.
5. 불필요한 기호(useless symbol)는 터미널 문자열을 생성할 수 없는 논터미널 기호이거나 또는 시작기호로부터 도달 불가능한(unaccessible) 기호를 말한다.
6. 모호한 문법은 연산자의 우선순위(precedence)와 결합법칙(associativity)을 이용하여 모호하지 않은 문법으로 바꿀 수 있다.
7. backtracking은 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우 발생하는데 이를 해결하기 위하여 left-factoring을 해야 한다. left－factoring은 공통된 prefix를 인수분해 하는 것이다.
8. 푸시다운 오토마타는 유한상태 제어(finite state control)와 입력 테이프(tape) 외에 무한정의 용량을 가진 스택(stack)으로 구성되며, 비결정적 오토마타(NPDA : Nondeterministic Push-Down Automata)와 결정적 오토마타(DPDA : Deterministic Push-Down Automata)의 두 종류가 있다.

연습문제

• 

  다음은 정규언어와 Context-Free-언어에 대한 설명이다. 물음에 답하시오.
  ‘가’에 적당한 것은 ?
  

  IF A = B THEN C := D ELSE E := D
  정규언어는 IF, A, =, B, ... 등의 단어들을 표현하는 것이고 ( 가 ) 는 전체문장이 IF - THEN - ELSE 문장이라는 것을 표현하는 것이다.

  답을 체크하세요

  1. 정규언어
  2. Context-Free-언어
  3. 푸시다운 오토마타 (Pushdown-Automata)
  4. 유한오토마타 (Finite-Automata)

  정답 :

  ②

  문장은 Context-Free 언어로 표현한다.

• 

  (2~3번 문제)다음 문법을 보고 물음에 답하라
  다음은 aaaa를 좌단유도하는 과정이다. 빈 칸에 알맞은 것은?
  

  <문법>
  1) S －－→ aAS
  2) S －－→ a
  3) A －－→ SbA
  4) A －－→ SS
  5) A －－→ b

  <문제>
  S => aAS
    => (    )
    :
    => aaaa

  답을 체크하세요

  1. aAa
  2. aaSS
  3. aSSa
  4. aSSS

  정답 :

  ④

  좌단 유도이므로 다음과 같이 왼쪽이 먼저 유도된다.
  S => aAS
    => aSSS
    => aaSS
    => aaaS
    => aaaa

• 

  (2~3번 문제)다음 문법을 보고 물음에 답하라
  다음은 aaaa 를 우단유도하는 과정이다. 빈 칸에 알맞은 것은?
  

  <문법>
  1) S －－→ aAS
  2) S －－→ a
  3) A －－→ SbA
  4) A －－→ SS
  5) A －－→ b

  <문제>
  S => aAS
    => (    )
    :
    => aaaa

  답을 체크하세요

  1. aAa
  2. aaSS
  3. aSSa
  4. aSSS

  정답 :

  ①

  우단 유도이므로 다음과 같이 오른쪽이 먼저 유도된다.
  S => aAS
    => aAa
    => aSSa
    => aSaa
    => aaaa

• 

  다음의 문법을 보고 답하라.
  위 문법의 특성은?
  

  연습문제 설명

  E －－→ E + E | E * E | id id －－→ 숫자

  답을 체크하세요

  1. 모호하다.
  2. 정규 문법이다.
  3. 유일한 유도트리를 생성한다.
  4. 단일 생성 규칙을 갖는다.

  정답 :

  ①

  id + id * id 를 우단유도하면 다음과 같이 두가지 유도트리가 생성되므로 이 문법은 모호하다.
  
  E → E + E
     → E + E * E
     → E + E * id
     → E + id * id
     → id + id * id
  
  E → E * E
     → E * id
     → E + E * id
     → E + id * id
     → id + id * id

• 

  다음 문법을 ε-free 문법으로 바꾸려 한다. 빈칸에 알맞지 않은 것은?
  

  연습문제 설명

      P : S －－→ bSaS | ε
  => P'는
      S' －－→ S | ε
      S －－→ (                  )

  답을 체크하세요

  1. ba
  2. SaS
  3. baS
  4. bSaS

  정답 :

  ②

  S －－→ ε을 대입하여 풀이해 보면 bSaS, baS, bSa, ba
  SaS 는 생성되지 않는다. 

• 

  생성규칙의 오른쪽이 단 한 개의 논 터미널로 구성된 것은?

  답을 체크하세요

  1. back tracking
  2. left recursion
  3. 단일 생성규칙
  4. left factoring

  정답 :

  ③

  단 한 개의 논 터미널로 구성되어 있는 생성규칙들을 단일 생성규칙이라고 하며 효율을 떨어뜨리므로 제거해 주어야 한다.

• 

  다음 문법과 관계없는 것은?

  S → cAd
  A → a｜ab

  답을 체크하세요

  1. 같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재한다.
  2. left-factoring을 해 주면 문제가 해결된다.
  3. 단일 생성규칙을 갖고 있다.
  4. backtracking 이 발생한다.

  정답 :

  ③

  backtracking 이 발생하며 left-factoring을 해 주면 문제가 해결된다.
  단일생성규칙은 없다. 

• 

  다음은 주어진 문법에서 left-recursion을 제거하는 과정이다.
  빈칸 ‘가’ 에 알맞은 것은 ?
  

  연습문제 설명

  E －－→ E * T ∣ T
  T －－→ T + F ∣ F
  F －－→ id
  
  ====>
  E －－→ TE'
  E’－－→ ( 가 )

  답을 체크하세요

  1. *TE'
  2. +TE'
  3. *TE' ∣ ε
  4. +TE' ∣ ε

  정답 :

  ③

  E －－→ TE'
  E’－－→ (*TE' ∣ ε)
  T －－→ FT'
  T'－－→ +FT' ∣ ε
  F －－→ (E) ∣ id

• 

  푸시다운 오토마타는 7개의 요소로 구성된다.
  다음 설명 중 틀린 것은 ?
  

  연습문제 설명

  M ＝ (Q, ∑, T, δ, q₀, z₀, F)

  답을 체크하세요

  1. Q : 상태들의 유한집합
  2. ∑ : 입력기호들의 유한집합
  3. T : 스택기호들의 유한집합
  4. z₀ : 시작상태

  정답 :

  ④

  푸시다운 오토마타는 7개의 요소로 구성된다.
  M ＝ (Q, ∑, T, δ, q₀, z₀, F)
  여기서
  z₀ ∈ T : 스택의 시작기호