자신에 대한 고찰

지난 포스트에서 NFA에서 DFA로 구하는 변하는 과정을 알아보았다. 그래서 최종적으로 나온 결과는 다음과 같다.그런데 유심히 살펴보면 뭔가 이상한 점이 있다. A가 initial state로 정해져 있긴 하지만 A에서 입력을 a,b로 받는 거나, C에서 a,b로 입력을 받는 것이나 결과가 똑같다. 만약 initial State가 C로 되어 있더라도 위와 별반 차이가 없을 것이다. 이처럼 Subset Construction Algorithm은 표현할 수 있는 모든 경우의 수에 대해 DFA를 구한 것이기 때문에 간혹 불필요한 State Transition이 표현되어 있기도 하다. 그래서 조금 더 노력해보면 이 state들을 합칠 수 있다는 결론을 내릴 수 있다. 이렇게 축약한 결과가 Minimum Stat..

지난 포스트에서 Regular Expression을 Non-deterministic FA로 바꾸는 방법 중 가장 보편화된 방법인 Thompson's Construction Algorithm (TCA)에 대해서 간단한 예제를 통해서 살펴보았다. 그런데 사실 NFA를 구한 것 자체는 정답을 찾기 위해서 필요한 경우의 수를 추려놓은 정도이기 때문에 여기서 확실한 정답을 선별하기 위해서는 DFA로 바꿀 필요가 있다. 그래서 여기까지 하면 Regular Expression | (Thompson`s Construction Algorithm) Non-deterministic Finite Automata | (Subset Construction Algorithm) Deterministic Finite Automata|..

지난 포스트를 토대로 Nondeterministic FA와 Deterministic FA를 구별해보았다. 간단히 요약해보면 경로를 찾는데 있어서 가능성 주목한 방식이 NFA가 될 것이고, 진짜 정답을 찾는 방식이 DFA가 될 것이다. 그래서 저번에 계층적으로도 표현했었지만 우리가 Lexical Analysis를 하는 궁극적인 목적은 Regular Expression 식을 NFA를 거쳐서 아주 간략한 DFA를 거치는 것이 되겠다. 그럼 먼저 해야 되는 작업이 RE를 NFA 형식으로 바꾸는 방식이 되는데 여기에는 Thompson`s Construction Algorithm (TCA) 라는 방법으로 정의되어 있는게 있다. 이 방법은 Regular Expression을 가장 기본적인 단위로 쪼개어 NFA에서 정..

지난 포스트를 통해서 Finite Automata를 잠깐 언급했다. 사실 써놓고 무슨 내용인지는 나 자체도 이해가 안가지만 특정 문구를 뽑아내기 위한 Regular Expression이 나오면 이를 Finite State 형태로 구현하는 것 자체가 Finite Automata 라고 했던 것 같다. 즉, 오른쪽의 수식을 하나의 State Diagram으로 변환해주는 과정 자체가 Finite Automata를 구현하는 단계라고 볼수 있다. 위의 수식은 표현하자면 state를 나눠놓고 0일때의 입력이 어떻게 들어왔느냐에 따라서 state의 변화 정도를 표현한 것이다. 예를 들어 첫번째 입력이 a로 들어오면 b가 들어올때까지 state가 유지되는 것이다. Regular Expression 식도 그 이전 포스트에..

이전 포스트에서 계속 다룬 내용은 Compiler 의 동작 수행시 가장 먼저 이뤄지는 Lexical Analysis 이 뭔지를 살펴보고, Regular Expression을 통해서 코드 상의 string을 뽑아낼 수 있는 것을 보았다. 이렇게 살펴보면 사람이 작성한 코드는 무척이나 많은 요소들로 구성되어 있는 것을 알 수 있다. 먼저 alphabet들이 있을 것이고, 그 alphabet으로 구성된 string이 있을 것이다. 그 중 의미를 지닌 keword도 들어갈 수 있다. 또는 어떤 연산을 위한 Number도 들어가 있고, Operator, Bracket, Whitespace 등등이 사람이 작성한 코드에 적어도 하나씩 포함되어 있다. 그러면 이전 포스트에서 말한 Regular Expression 방법..

지난 포스트에서 했던 이야기를 다시 해보자면 컴파일러가 하는 역할은 사람이 작성한 코드를 컴퓨터가 인지할 수 있게끔 번역해주는 역할이며, 가장 먼저 선행되어야 할 기능이 구문을 Token별로 잘라주는 Lexical Analysis이었다. 이를 위해서는 구문을 잘라내기 위한 특정 Pattern이 필요한데 보통 이걸 Regular Expression 방식을 사용해서 처리한다고 언급했었다. 이번 포스트에서는 그 Regular Expression에 대해서 조금 정리해보고자 한다. 우선 String의 구성요소에 대해서 알아볼 필요가 있을 듯 하다. 보통은 구문 또는 단어라는 말로 다들 알고 있다. 그럼 이 String을 잘게 쪼갤 수 있을까 한번 Compiler라는 단어를 예로 들어보자우선 첫번째 구성요소는 접두..

다른 포스트에서도 이야기 했었지만 compiler가 하는 가장 기본적인 역할은 사용자가 특정 목적에 의해서 만든 코드를 컴퓨터가 알아먹을 수 있게끔 컴퓨터의 언어로 번역해주는 것이다. 그런데 참 신기하지 않은가? 우리가 ">>" 라고 작성하면 대부분의 사람은 오른쪽으로 shift 하는 걸로 생각하지만 만약 에 들어있는 >> 는 우리가 생각하는 그런 의미를 담지 않는다. 단지 parentheses 일 뿐이다. 그런데 컴파일러가 설치되어 있는 컴퓨터는 i>>2 와 에 들어있는 >>를 잘 구분한다. 여기서 컴파일러에 대해서 전혀 모르는 사람이라도 컴퓨터 내부에 이런 어휘나 규칙을 정해놓은 무언가가 있을 거라는 짐작을 할 수 있을 것이다. 보통 이런 걸 구분하는 요소를 Lexeme (어휘소) 라고 하고, 컴파일..

Compiler의 기본 구성은 다음과 같이 나눌 수 있다.- Lexical Analysis- Syntex Analysis- Semantic Analysis- Optimization- Code Generation 보통 Compiler의 가장 기본적인 역할은 high level language를 low level language로 바꿔주는 번역기의 역할일텐데, 초기에 등장한 프로그래밍 언어들은 위의 요소들이 비슷한 비중을 차지했다. 하지만 현대의 컴파일러는 다른 것보다 code optimization이 중요시되고 있다. 마침 OCW 중 Computer Language Engineering 수업중에 Code Optimization에 관한 내용을 쉬운 예제를 토대로 소개하고 있어서 한번 정리해보고자 한다.예제는..