[Compiler] 02. 형식 언어 (1) - 언어

형식 언어

컴파일러를 만들기 위해서는 언어에 대한 이해가 선행되어야 한다는 것을 지난 장에서 살펴보았다.

언어에 대해서 잘 이해하고, 체계적으로 전개하기 위해서는 "잘 정의된 언어"가 어떤것인지 알아야 한다.

이처럼 잘 정의된 언어를 형식 언어라고 부른다.

형식언어는 보통 문장의 집합으로 정의된다.

 

2장에서는 언어를 형식적으로 정의하고, 언어를 표현하는 방법으로 사용되는 문법을 정의한다.

 

형식 언어의 기본 개념

형식언어는 문장들의 집합으로 정의된다.

 

Alphabet

알파벳은 문장을 이루는 기본 심볼(기호)들의 유한 집합이다.

 

형식언어이론에서는 알파벳이 보통 소문자 a, b, c... 과 같은 심벌들을 사용한다.

 

String (sentence, word)

알파벳 T에 대한 스트링은 알파벳 T에 속하는 심벌이나 T에 속하는 하나 이상의 심벌들을 나열한 것이다.
즉, 알파벳 T에 속하는 하나 이상의 기호들의 유한 수열을 말한다.

 

형식언어이론에서는 스트링을 나타내는 심벌로 u, v, w등을 사용한다.

w = abba의 의미는 스트링 w가 abba라는 스트링 값을 갖는다는 의미이다.

 

Length

스트링의 길이는 스트링을 이루는 심벌들의 개수를 말한다. 어떤 스트링 w의 길이는 |w|로 표기한다.

 

Concatenation

두개의 문자열을 연결해서 새로운 문자열을 만드는 연산을 말한다. 스트링 u, v를 접속할 때는 uv로 표기한다.

 

이때 u를 prefix, v를 suffix라고 부른다.

 

Reverse

w의 역은 다음과 같이 표현한다. w^R 

 

만약 w=abc 였다면, w^R=cba이다.

 

Empty String

string의 길이가 0인 것을 empty string이라고 하며, 엡실론 혹은 람다로 표기한다.

 

T star and T dagger

알파벳 T는 항상 유한집합이다.
T*는 알파벳 T에 속한 심벌로 만들 수 있는 스트링의 전체 집합으로, empty string을 포함하는 스트링의 무한집합이다.
T+는 T*에서 empty string을 제외한 T의 심벌로 만들 수 있는 스트링의 전체 집합으로, 무한집합이다.

 

 

Language

알파벳 T에 대하여 언어 L은 T*의 부분 집합이다.
L={a,ba,bba}일떄,
L^0 = {ε}, L^2={aa,aba,abba,baa,baba,babba,bbaa,bbaba,bbabba}

 

즉, 우리는 T*에 속하는 특정 형태의 집합을 언어라고 생각할 수도 있고, 만약 이런 언어에 속하는 스트링의 수가 유한개라면, 이를 유한언어라고 한다. 만약 언어에 속하는 스트링의 수가 무한개라면 이는 무한언어라 한다.

이떄 여기서 말하는 언어는 단지 스트링의 집합일 뿐 의미의 개념을 포함하지 않는다.

 

L star, dagger

언어 L의 star와 dagger는 다음과 같다.
L* (L-star) : L의 모든 거듭제곱의 합집합
L+ (L-dagger): L* - L^0