정규 표현 정규 표현(regular expression)은 정규 언어를 표현하기 위한 한 방법으로, 정규 언어에 속해 있는 스트링의 모양을 직접 기술하는 형태를 가진다. 정규 표현의 기본 소자는 Φ, ε, 그리고 terminal 심벌이다. Φ는 공집합을, ε은 집합 { ε }, a ∈ VT는 집합 { a }를 나타내는 정규 표현이다. 만일 e1과 e2가 정규 언어 L1, L2를 나타내는 정규 표현이라면, (e1) + (e2)는 L1∪L2를, (e1) ∙ (e2) L1 ∙ L2를, (e1)* L1* = { ε } ∪ L11 ∪ L12 ∪ ... ∪ L1n ∪ ...인 , 즉 closure를 의미한다. 여기서 union 연산에 해당하는 + 연산은 교환법칙이 성립하며, 접속 연산인 concatenation..

정규 언어 앞선 포스팅에서는 문법의 생성 규칙에 따라 4가지 문법으로 분류하였다. 이렇게 4가지 문법에 따라 분류한 언어는 각 문법에 의해 생성되는 언어를 가지는데, 이번 포스팅에서는 정규 문법과 정규 문법으로 생성되는 언어인 정규 언어에 대해 알아보겠다. 정규 언어(regular language)는 토큰의 형태를 기술하는데 사용하며, 이를 표현하는 방법으로는 정규 문법, 정규 표현, 유한 오토마타가 있다. 이렇게 정규 문법을 이용한 어휘 분석(Lexical analysis)은 소스 코드를 토큰 단위로 분해하는데 사용된다. Type 3 Grammar인 정규 문법에 대해 기억해보자. A -> tB | t, A -> Bt | t 형태의 생성 규칙을 가지는 문법이 정규 문법이다. 여기서 전자는 nonter..

문법의 분류 이전 포스팅에서는 유도, 문법과 언어의 관계, 문법 등 문법과 관련된 내용을 알아보았다. 이번 포스팅에서는 앞에서 알아보았던 문법들의 분류를 알아보겠다. 문법은 Noam Chomsky에 의해 생성 규칙인 Product Rule에 따라 4종류로 구분한다. 이렇게 구분되는 문법을 알아보자. Type 0 문법(unrestricted grammar, UG) Type 0 문법은 생성 규칙에 어떠한 제한도 두지 않는 문법이다. 하지만, 문법의 정의에 따라 생성 규칙 a -> b에서 a는 빈 스트링, 즉 empty 스트링이 될 수 없다. Type 1 문법(context - sensitive grammar, CSG)생성 규칙 a -> b에서 b의 길이가 a보다 긴 문법이다. 즉, CSG에서는 |a| Ty..

문법(Grammar) 이전 형식언어 포스팅에서는 언어의 정의에 대해 알아보았다. 언어는 스트링을 원소로 갖는 집합으로 정의될 수 있는데, 그렇다면 이렇게 정의된 언어를 어떻게 표현할 수 있을까? 유한 언어는 그 집합에 포함된 스트링을 모두 열거하여 표현할 수 있으나, 무한 언어는 그 언어의 유한 표현을 찾아야 한다. 이전 포스팅에서도 짧게 알아보았듯, 1. 집합을 이용한 조건 제시법, 2. 문법, 3. 인식기 이용과 같은 방법을 이용해 무한 언어의 유한 표현이 가능하다. 언어를 정의하기 위한 문법은 심벌의 분리된 두 집합인 VN, VT로 표시하는 두 심벌의 집합을 사용한다. 여기서 VN은 nonterminal 심벌의 집합, VT는 terminal 심벌의 집합이다. nonterminal 심벌은 문법에서..

언어 컴파일러 개론 포스팅에서 컴파일러의 전단부를 위해서 언어(Language)를 잘 정의해야 하는 것을 알았다. 이렇게 잘 정의된 언어를 형식 언어(Formal Language)라 하며, 보통 문장의 집합으로 정의된다. 잘 정의된 언어는 문장의 집합으로 정의되며, 알파벳(Alphabet)은 문장을 이루는 기본적인 심벌(Symbol)로, 알파벳 T는 심벌들의 유한 집합이다. 언어의 정의알파벳과 스트링 알파벳 T에 대한 스트링(String)은 알파벳 T에 속하는 심벌이나 T에 속하는 하나 이상의 심벌들을 나열한 것이다. 쉽게 말해 스트링은 알파벳의 유한 집합이다. 스트링의 길이는 스트링을 구성하는 심벌들의 개수이며, 어떤 스트링 w의 길이는 |w|로 표기한다. 예시 몇 가지를 살펴보자. T1 = {ㄱ, ..

개요 프로그래밍 언어론 포스팅에 이어 형식언어 내용을 포스팅해보려 한다. 사용한 교재가 이름부터 '컴파일러 입문'이지만 교재의 중반부는 형식언어론과 관련된 부분이고, 중후반부는 LL, LR 구문 분석 등과 같은 컴파일러와 관련된 부분이다. 추가로, 프로그래밍 언어론에서 사용한 용어들이 꽤나 많이 등장하여 프로그래밍 언어론과 연결하여 공부하면 꽤 좋은 내용이라고 생각한다. 번역기와 컴파일러 번역기(translator)란 한 프로그래밍 언어로 작성된 프로그램을 입력으로 받아 이와 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하는 시스템 프로그램을 뜻한다. 여기서 입력되는 프로그램을 소스 프로그램이라 하며 이 프로그램을 기술한 언어를 소스 언어(source language)라 한다. 그리고 ..