1. 다음은 컴파일러와 관련된 설명들이다. 틀린 것은?

  ① 정규언어는 어휘분석에서 단어들을 표현하는데 사용된다.  

  ② 유한오토마타는 정규언어를 인식한다.  

  ③ 푸시다운 오토마타는 구문분석과 관련이 있다.

  ④ Context-Free-언어는 단어들을 표현하는데 사용된다.  

 

※ (2～5) 다음 문법을 보고 물음에 답하라.

    
1) S →   aAS

2) S →   a

3) A →   SbA

4) A →   SS

5) A →   ba

 
 

2. 다음은 aaaa를 좌단유도하는 과정이다. 빈 칸에 알맞은 것은?

    
    S ⇒ aAS
⇒ (     )

      :
        ⇒ aaaa

 
  ① aAa                               ② aaSS

  ③ aSSa                                ④ aSSS

 

3. 다음은 aaaa를 우단유도하는 과정이다. 빈 칸에 알맞은 것은?

    
    S ⇒ aAS
⇒ (     )

       :

      ⇒ aaaa

 
  ① aAa                               ② aaSS

  ③ aSSa                                ④ aSSS

 

4. First(A)는?    

  ① a                                  ② a, b    

  ③ a, b, ε                     ④ a, b, $

 

5. Follow(A)는?  

  ① a                                  ② b    

  ③ a, b                               ④ a, b, $

 

6. 다음 문법에 대한 설명으로 가장 적당한 것은?

    
    E →  E + E | E * E | id

 
  ① id + id * id를 유도하면 오직 하나의 유도트리가 생성된다.  

  ② 구문분석기를 구성하는 것이 단순하고 쉽다.

  ③ 구문분석기를 구성하는 것은 복잡하지만 구문분석 시간이 빠르다.  

  ④ 모호한 문법이므로 모호하지 않은 문법으로 바꾸어 주어야 한다.

 

컴파일러구성, UNIX시스템  6－1

 
3 학년   2 교시

 7. 다음 문법을 ε-free 문법으로 바꾸려고 한다. 빈칸에 알맞지 않은 것은? (단, ∣표시는 생략한다)

    
    P : S →  bSaS ∣ ε

⇒ P'는

    S' →  S ∣ ε

    S →  (                  )

 
   ① ba                               ② SaS  

   ③ baS                               ④ bSaS

 

 8. 다음은 주어진 문법에서 단일 생성규칙을 효율화시키는 과정의 일부이다. 빈칸 ‘가’에 알맞은 것은?   

    
       E →  E ＋ T ∣ T

      T →  T ＊ F ∣ F

     F →  (E) ∣ a  

 

  ⇒

         E →  E ＋ T ∣ ( ‘가’ )

 
   ① F                

   ② T ＊ F

   ③ T ＊ F | F      

   ④ T * F | (E) | a

 

※ (9～10) 다음은 주어진 생성규칙을 적용하여 문장 cabd를 유도하는 과정이다.

    
        S →  cAd

      A →  a ∣ ab

 (cabd 유도과정)    

  S →  cAd  →  cad  

   주어진 문장이 아니므로 다시 되돌아가서 A → ab를 적용한다.

  S →  cAd  →  cabd    

 
 

 9. 이처럼 다시 되돌아가는 문제점을 무엇이라고 하는가?

   ① back tracking        

   ② left recursion

   ③ 단일 생성규칙        

   ④ left factoring

 

10. 이 문제점을 해결하는 방법은?

   ① left-factoring      

   ② backtracking

   ③ ε생성규칙제거      

   ④ 연산자 우선순위

 

11. 다음 구문분석에 대한 설명 중 잘못 설명된 것은?  

   ① Top-down 구문분석 방법은 backtracking 문제를 갖고 있다. 

   ② Bottom-up 방법은 터미널 노드부터 시작하여 루트 노드를 향하는 반면에, Top-down 방법은 루트 노드로부터 터미널 노드를 향하여 파스트리를 만들어 나간다.

   ③ Shift-reduce 구문분석은 Top-down 방법으로 시작기호로부터 출발하여 유도에 의하여 주어진 문자열을 찾아간다.

   ④ backtracking을 방지하기 위하여 LL(k) 문법을 사용하게 되었다.