컴파일러구성 - [제2장]형식언어와 형식문법

컴파일러구성 - [제1장]형식언어와 형식문법

주요용어

1. 형식언어 : 어떤 알파벳 에서 얻은 기호 심볼들로 구성되는 문자열 스트림의 집합
2. 형식문법 : 형식언어를 생성하기 위한 규칙
3. 컨텍스트 프리 문법 : A는 Y이다. 단, A는 논터미날 기호이고 y는 V프라임에 속하는 문자열이다.
4. 촘스키 계층구조 : 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키가 4종류로 나눈 형식문법
5. 컨텍스트-센서티브 문법 : Y 이면 베타이다. 단, y의 절다값은 베타의 절다값보다 작거나 같으며 베타는 V프라임의 원소이다. 생성규칙에 y의 절대값은 베타의 절다값보다 작거나 같다는 제한을 가하는 것으로 바위측형 난컨트렉팅 문법에 속함
6. 공문자열 : 문자열의 길이가 0인 것, 엡실론 또는 람달로 표시
7. A이면 tB이고 A이면 t이다 또는 A이면 Bt 이고 A이면 t이다 . 단 t는 V프라임과 A의 교집합의 원소이고 B는 Vn첨자의 원소이다. 생성규칙에 따라 두가지 종류가 있다. A이면 tB이고 A이면 t이다.와 같은 생성규칙을 갖는 것을 우선형 right linear문법 이라고하고, A이면 Bt 이고 A이면 t이다 .와 같은 생성규칙을 갖는 것을 좌선형 left linear문법 이라고 한다.
8. 논터미널 : 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시
9. 터미널 : 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자, 기호등이 속한다.
10. 문법기호 : 터미널과 논터미널 기호를 문법기호 그라마 심벌 이라 하며 보통 V 보카블러리 로 표시한다
11. 튜링기계 : 언레스트릭스트 언어를 받아들이는 인식기
12. 유도 : 한 문자열에서 생성규칙을 한번 적용해서 다른 문자열로 바뀌는 것
13. 정규표현 : 정규문법을 가장 잘 표현할 수 있는 방법법

요점정리

• 2강에서는 컴파일러의 설계를 위한 형식 언어(formal language)와 이 언어를 생성하는 형식문법에 대해 알아보았다.
• 형식 언어란 어떤 알파벳(alphabet)에서 얻은 기호(symbol)들로 구성되는 문자열들의 집합을 말하며 이러한 형식 언어를 생성하기 위해 여러 규칙들을 이용하는데 이것을 형식 문법이라 한다.
• 형식문법은 논터미널 기호들의 유한집합 VN , 터미널 기호들의 유한집합 VT, 생성규칙(production rule)의 집합 P, 시작기호 S 로 구성되며 G ＝ (VN, VT, P, S) 로 표현한다.
• 형식문법에서 터미널(terminal) 기호는 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등이 여기에 속하고, 논터미널(non－terminal) 기호는 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시한다.
• 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키(Chomsky, N.)는Type0, Type1, Type2(=CFG), Type3(=정규문법)등의 4종류로 형식문법을 나누었으며, 이를 촘스키 Chomsky 계층구조(hierarchy)라고 부른다.
• 형식 문법을 표현하기 위해 정규표현(regular expression), 문법도표(syntax diagram), BNF(Backus-Naur From), EBNF(Extended BNF) 등의 방법을 사용한다.

연습문제

• 

  T ＝ {a, b, c} 가 주어졌을 때 다음 설명 중 틀린 것은?

  답을 체크하세요

  1. aⁿ = abc
  2. |abc| = 3
  3. T^* ＝ {ε, a, b, c, aa, ab, ac, …}
  4. T^＋ ＝ {a, b, c, aa, ab, ac, …}

  
  

  정답 :

  ①

  aⁿ 이란 a가 n개 나열된 문자열을 나타낸다. |abc| 는 문자열의 길이를 뜻하므로 3이다. 

  
  

• 

  문법 G가 다음과 같이 정의되어 있다.
  촘스키 분류법에 따르면 어디에 속하는가?
  

  G = ({S, B, C}, {a, b}, P, S)
  P : S → aS｜aB
  B → bC
  C → aC｜a

  답을 체크하세요

  1. type 0
  2. type 1
  3. type 2
  4. type 3

  
  

  

  정답 및 해설

  정답 :

  ④

  우선형 이므로 type 3 정규문법이다. 

• 

  문법 G가 다음과 같이 정의되어 있다.
  문법 G가 생성할 수 없는 것은?
  

  G = ({S, B, C}, {a, b}, P, S)
  P : S → aS｜aB
  B → bC
  C → aC｜a

  답을 체크하세요

  1. aba
  2. ababa
  3. aabaaa
  4. abaaa

  

  정답 및 해설

  정답 :

  ②

  S → aB → abC → aba
  S → aS → aaB → aabC → aabaC → aabaaC → aabaaa
  S → aB → abC → abaC → abaaC → abaaa
  ababa 는 생성될 수 없다. 

• 

  문법 G가 다음과 같이 정의되어 있다.
  문법 G가 생성하는 언어를 정규표현으로 표현한 것은?
  

  G = ({S, B, C}, {a, b}, P, S)
  P : S → aS｜aB
  B → bC
  C → aC｜a

  답을 체크하세요

  1. a^*ba^*
  2. a^*aba^*a
  3. a^*ab^*a^*a
  4. a^*+aba^*a

  

  정답 및 해설

  정답 :

  ②

  정규방정식으로 풀면,
  C = aC + a ⇒ C = a^*a
  B = bC ⇒ B = ba^*a
  S = aS + aB ⇒ S = aS + aba^*a
  ∴ S = a^*aba^*a

• 

  다음 문법에서 생성될 수 없는 것은?
  

  P: V₀ → aV₁
  V₁ → bV₀
  V₁ → a
  
  단, 출발 기호 = V0

  답을 체크하세요

  1. aa
  2. aba
  3. abaa
  4. ababaa

  

  정답 및 해설

  정답 :

  ②

  aba 는 생성될 수 없다.
  V0=aV1
  V1=bV0
  V1=a 따라서 V1=bV0+a
  V0=aV1=a(bV0+a)=abV0+aa=(ab )*aa 

• 

  다음의 production rule에 대한 설명 중 올바른 것은?
  

  <절대정수> : : = <숫자> | <절대정수> <숫자>
  < 숫자> : : = 0 | 1 | 2 | 3 | 4 | 5

  답을 체크하세요

  1. 절대정수로 11, 45, 112, 2315 등이 허용된다.
  2. 절대정수로 0을 포함하는 모든 수를 의미한다.
  3. 절대정수로 1을 포함하는 모든 수를 의미한다.
  4. 절대정수로 1, 5, 9, 10, 13 등이 허용된다.

  
  

  

  정답 및 해설

  정답 :

  ①

  규칙에서 숫자는 1부터 5까지 만 있다. 따라서 ②번과 ③번 그리고 ④번 모두 틀렸다.