[Compiler] Formal Language (형식 언어)

Language는 Nautral Language와 Formal Language로 나뉜다. Natural Language는 한국어, 영어, 중국어와 같은 일상 언어를 지칭한다. 이는 진화한다는 특징을 갖고 있다. 100년, 200년 전에 쓰이던 한국어와 현재 쓰이는 한국어가 다른 것을 생각해보면 된다. 두번째로는 언어에 융통성, 내지는 유연성이 있다. 두 사람이 표준어가 아닌 말을 하더라도 의사소통에는 지장이 없는 것을 생각해보면 된다. 반면, Formal Language는 유연성이 없고, 정확한 포맷을 갖고서, 엄격한 규칙을 갖고서 이야기를 해야한다. C, C++, Java와 같은 언어의 끝에는 세미콜론을 꼭 붙이는 것을 생각해보면 된다.

 

Formal Language를 알기 위해서는 Language와 Grammer 두가지를 알아야 한다. 먼저 Language부터 알아보자. 이를 정의하기 위해서는 몇 가지 준비가 필요하다.

 

먼저 알파벳(alphabet)을 정의해야한다. 알파벳은 심볼을 갖고 있는 유한집합을 말한다. 예를 들어서, T1={A, B, ..., Z, a, b, ..., z}, T2={do, switch, break, ..., while} 는 각각 A,B와 do,switch 등과 같은 심볼들을 원소로 갖고 있는 유한집합이다.

 

알파벳을 정의하면, 스트링(string)에 대해 이야기를 할 수 있다. 스트링은 심볼들을 이어 붙인 것(concat)을 말한다. T={0}인 알파벳이 있을 때 만들 수 있는 스트링은 0, 00, 000, ... 등이 있다. 그리고 T={a,b}인 경우에는 a, b, ab, ba, bb, aaa 등과 같은 스트링을 만들 수 있다. 컴퓨터 언어 관점에서는 심볼을 조합해서 변수를 만드는 걸 생각할 수 있다. 즉, 변수 = 스트링으로 생각할 수 있다.

 

이제 스트링의 길이(length of string)를 정의하면, 이는 스트링이 갖고 있는 심볼의 수로 정의된다. 위에서 말했던 예에서, T2의 심볼로 docase라는 스트링을 만들면 길이가 몇일까? 값은 2가 된다. 여기서 알파벳의 갯수가 6개라고 하여, 길이가 6이라고 말하는 실수를 하면 안된다. 스트링의 길이는 심볼의 갯수로 정의되기 때문에 docase의 경우 심볼 'do', 'case' 두개가 쓰였기 때문에 이것의 길이는 2가 된다.

 

위에서 스트링은 심볼들을 이어 붙인 것이라고 하였는데, 스트링을 이어 붙일 수도 있다. 이걸 concat of string이라고 하는데, 스트링을 시퀀셜하게 더한 것으로 정의한다. 예를 들어, u=abc, v=cba라는 두개의 스트링이 이어 붙이면 u.v라는 concat에 의해, u.v=uv=abccba와 같이 계산할 수 있다. concat을 한 스트링의 길이는 피연산자 스트링의 각 길이를 더한 것이 된다. |uv| = |u|+|v|. |u|=스트링 u의 길이. 그리고 이 연산은 교환 법칙이 성립하지 않는다. 티스, 토리라는 두개의 스트링을 순서를 바꿔서 concat을 하면 티스토리, 토리티스가 되는 걸 생각해보면 된다. 

 

*번외로 집합 정의하고 연산 갖고서 법칙따지는 게 대수 수업을 듣던 거랑 비슷한 느낌이 나서 뭔가 연관있을 것 같고 이거 이용해서 응용한 게 있지 않을까 구글링해봤는데, 있긴 있더라. 나는 안봤지만 궁금한 사람을 위해서 링크를 남긴다. (ㅇㄲㄴ)

 

여기까지 보면, 스트링의 길이는 항상 양수일 것만 같은데, 그렇지 않다. 길이가 0인 스트링도 정의한다. 우리는 이를 empty string이라고 한다. 보통 입실론이나 람다로 표현하는데, 이 포스팅에서는 'e'로 쓰겠다.

 

지금까지 스트링에 대한 이야기를 했다. 스트링이 뭐고, 길이는 어떻게 정의되며, 이들을 이어 붙이는 연산이 있다는 거. 그러면 이런 스트링들을 모아 놓은 집합을 생각할 수 있는데, T*, T+로 표기한다. T*는 T라는 알파벳으로 만들 수 있는 모든 스트링들을 모아 놓은 집합을 말한다. 여기서 T*에는 empty string이 포한된다. T+는 모든 스트링들을 모았는데, empty string은 포함되지 않는 걸 말한다. 즉, T+는 T*에서 empty string을 뺀 것이다. 이런 개념이 왜 필요하냐면, 우리가 어떤 알파벳이 있을 때, 이걸 조합해서 변수를 만들고 싶은데 그걸 알려주는 집합을 생각해보고 싶기 때문이다. 하지만, 이것만으로는 Language를 정의하기에 충분하지 않다. 여기에 한가지 조건이 더 필요하다.

 

알파벳 T의 Language는 T*의 부분집합을 말한다. 위의 T*만해도 충분해보이는데, 왜 부분집합까지 생각해야되는 걸까? 다시 생각해보면, 우리가 알파벳을 생각하고, 이걸로 스트링을 만드는 건 변수들의 목록을 만들고 싶기 때문이다. T={A,B,...,Z,_, a,b,...,z,.1,2,...,0} 이라는 알파벳을 갖고서 T*를 만들었는데 이걸 항상 모든 언어의 변수 목록이라고 말할 수 있을까? 그럴 수 없다. 예를 들어, C언어는 변수명에 123_abc와 같이 숫자를 먼저 작성하는 것을 금지한다. 또한 이는 각 언어마다 서로 다른 규칙들이 적용될 것이다. 그래서 이와 같은 점들을 피해주기 위해 T*의 부분집합으로 language를 정의하는 것이다.

 

여기까지 language에 대해서 알아보았다. 위에서 C, C++, Java와 같은 formal language는 뒤에 세미콜론을 꼭 붙여야 한다는 등의 엄격한 규칙을 갖고 표현이 된다고 이야기했다. 여기서 formal language에서 말한 문법적인 형식을 어떻게 표현해줄 것인가에 대한 이야기를 grammer가 해준다.

 

우선, production rule부터 알아보자. production rule P는 finite production rules의 집합으로 표현된다. 여기서 룰은  a -> b 와 같은 transformation을 이야기한다. 예를 들어서 production rule에는 S->aAS, S->a, A->SbA, A->ba, A->SS이 있다고 해보자. 여기서 S는 starting symbol이다. 스타팅 심볼은 스트링이 처음 쓰일 때 쓰는 심볼이다. 위의 production rule이 의미하는 건 각각, S는 aAS가 될 수 있고, S는 a가 될 수 있고, A는 SbA가 될 수 있다 등을 이야기한다. 여기서 대문자로 쓰여진 심볼들은 스트링을 만드는데, 끝날 때 보이는 심볼이 아니다. 이 심볼들은 항상 production rule에 의해 다른 심볼들을 유도해야하는데, 이를 non-terminal symbol이라고 한다. 반면, 소문자로 쓰여진 심볼들은 다른 심볼들을 유도하지 않아도 되는 심볼, 즉 스트링의 끝에서 보일 수 있는 terminal symbol이라고 한다. 그런데 위에서 나열한 것처럼 생성규칙을 쓰면 너무 길어지니까 간단하게, S -> aAS | a, A -> SbA | ba | SS 라고 'or' 표시로 쓸 수 있다.

 

그래서, Grammer라는 것은 총 네가지, 스타팅 심볼, 논터미널 심볼, 터미널 심볼, 생성규칙으로 구성할 수 있다. 예를 들어서, 터미널 심볼에는 a, b가 있다고 가정하고, 논터미널 심볼에는 S, A, B가 있다 하자. 이때 생성규칙을 S -> aA | bB | e, A -> bS, -> aS 라 하자. 그러면 이 문법 아래에 abba라는 스트링을 만들 수 있냐?는 질문을 할 수 있는데 S => aA => abS => abbB => abbaS => abba 와 같은 방식으로 만들 수 있으므로, abba는 저 생성규칙 아래에서 만들 수 있다.라고 답할 수 있다.