컴파일러

문법 : Grammer

생각없는 개발자 2022. 9. 19. 00:26

 언어는 스트링들을 원소로 갖는 집합이다. 유한 언어의 경우에는 그 집합에 속한 모든 스트링을 열거함으로써 쉽게 표현 할 수 있지만, 무한 언어는 그 언어의 유한 표현을 찾아야 한다. 이러한 유한 표현의 방식으론 다음과 같이 세가지가 존재한다.

  1. 조건제시법
  2. 문법
  3. 인식기

이 중에서도 문법을 다루고자 한다. 문법은 다음과 같이 네가지 요소로 정의 할 수 있다.

G = (Vn, Vt, P, S)
  • Vn : nonterminal 심벌의 유한 집합
  • Vt : terminal 심벌의 유한 집합
  • P : 생성 규칙(production rule)의 유한집합
  • S : Vn에 속하는 심벌로서 다른 nonterminal들과 구별하여 시작 심벌(start symbol) 또는 문장 심벌(sentence symbol)이라 한다

처음에는 "이게 무슨 말이지?" 싶다 차근차근 알아가 보자. 다음은 문법의 예시이다. 생성규칙 A → B는 A구조를 B구조로 정의한다는 것이며, A를 B로 대체할 수 있다는 것을 의미한다. 

생성 규칙의 왼쪽이 같은 경우에는 '|'를 활용하여 간단히 나타낼 수 있다. 예를 들어 A → B1, A → B2 가 있을때 A → B1 | B2로 표기 가능하다는 것을 의미한다. 즉 위 생성규칙을 간단히 표현하면 다음과 같다.

문법은 생성규칙에 따라 4가지 종류로 나뉜다.

  • Type 0 문법(unrestricted grammer) : 생성 규칙에 어떤 제한도 두지 않는다. 다만, 문법의 정의에 따라 생성 규칙 A  B에서 A는 empty 스트링이 될 수 없다는 것이다.
  • Type 1 문법(context-sensitive grammer) : 생성 규칙 A  B에서 B의 길이가 A의 길이보다 길다.
  • Type 2 문법(conetxt-free grammer) : 모든 생성 규칙은 A  a의 형태를 갖는다. 여기서, A는 하나의 nonterminal 심벌이며, a는 V*에 속하는 스트링이다. 즉, 생성 규칙의 좌측은 하나의 nonterminal이며 우측은 terminal과 nonterminal로 이루어진 스트링이다.
  • Tyep 3 문법(regular grammer) : 정규 문법의 생성 규칙은 두가지 형태로 표현 될 수 있는데 첫 번째 형태를 우선형 문법, 두 번째를 좌선형 문법이라고 한다.
    1. A  tB 혹은 A  t, 여기서 A,B ∈ Vn이고, t ∈ Vt*이다.
    2. A  Bt 혹은 A  t, 여기서 A,B ∈ Vn이고, t ∈ Vt*이다.
댓글수1