Lexical Analysis는 앞서 배운 Formal Language, Regular Expression, Finite Automata 등을 이용하여 character를 분석하는 과정이다. 그 character 사이에서 이름, 키워드, 특수한 마크가 있는지 알아내야 한다. 이 부분에서 공백, 주석과 같이 처리하지 않는 부분도 걸러져야 한다. Lexical Tokens 개념 Token이란 언어에서 인식을 하는 부분을 말한다. 각각 type들이 정해져 있으며 ID는 변수명, 함수명 NUM은 정수, REAL은 실수, 각종 예약어들과 연산자들이 이에 해당한다. 반면에 주석, 전처리기와 같은 문자들은 인식을 하지 않는다 ex ) #define, #include, //aaa Two Types of Tokens 토..

이번엔 오토마타에서 Reqular Expression으로 변환하는 과정을 알아보도록 하자 바로 바꾸기 보다는 Formal language로 바꾼 뒤 변환하는게 이해하기가 더 쉽기 때문에 Formal language로 변환하는 과정 먼저 알아보자 이 오토마타를 Regular Expression으로 변환해보자 먼저 Formal Language로 변환하면 이러한 모양이 된다. p -> 0q | 1p q -> 0r | 1p r -> 0r | 1r | epsilon 이를 Regular Expression으로 변환하면 [1] p = 0q + 1p [2] q = 0r + 1p [3] r = 0r + 1r + epsilon 이 된다. 먼저 [3]을 정리하면 r = (0+1)r + epsilon = (0+1)* 이 되고..

처음에 배웠던 Formal Language 에서 Finite Automata로 변환하는 방법을 알아보자. Formal -> Automata S -> 0S S -> 1B S -> 1 B -> 0S B -> 1 앞의 0과 1이 선택지이고, 뒤에 문자가 도착지 이므로, automata 표로 이렇게 나타낼 수 있다. 해당 automata를 그림으로 표현하면 이와 같이 표현할 수 있다. f는 S->1과 같이 선택지가 더이상 없을경우 finish이기 때문에 f가 되는것이다. Automata -> Formal 사실 Automata Design에서 Formal language로 바꾸는데에는 바로 보고 바꿀수 있다. 그림에서 p가 1일때 q로 가고 하는 걸 쭉 정리하면 formal lang이 되기 때문이다. 그래서 전부..

이번엔 DFA에서 State를 줄여나가는 방법이다. 먼저 state를 2개로 만든 모양이다. 빨간색 부분을 1구역, 파란색 부분을 2구역 이라고 보자. 1구역에는 A, B, D가 있고 2구역에는 C,E가 있다. ABD는 각각 a 일때 1구역에 머물러있고, b 일때는 A는 1로, 나머지는 2구역으로 이동한다. 표로 정리하면 이렇게 된다. a일 경우와 b가 같아야 한 state로 묶을 수 있으며, 현재 ABD state는 B,D경우가 다르므로 하나의 state로 만들 수 없다. 그러면 좀 더 쪼개서 3개의 state로 만들어보자. 구역을 3개로 나누어 보았다. 이렇게 되면 각 구역에서 선택지에 따라 일정한 곳으로 이동하게 된다. 이러한 식으로 정리가 가능하다. 그럼 각각 1, 2, 3을 다시 오토마타로 만들..

오토마타 경우의 수중에 ε는 아무 조건 없이 갈 수 있는 경우를 말한다. 이 경우를 묶어서 ε-closure라고 부른다. ε - NFA 예시 1에서 epsilon을 통하여 무조건 갈 수 있는 경우를 e-closure(1)이라고 표현합니다. closure(1)일때 a가 주어지면 2로 가게되고 2에서는 epsilon으로 갈 수 있는 곳이 없기 때문에 자기 자신 closure(2)가 됩니다. c가 주어진다면 3으로 이동하게 되고 3에서는 epsilon으로 4로 이동할 수 있기 때문에 closure(3)이 되고 자기 자신과 4를 포함한 [3,4]가 됩니다. 이 방법은 DFA로 변환할 때 2의 n승 만큼 터미널을 만드는게 아니라 e-closure를 통해 epsilon으로 갈 수 있는 터미널들을 정의하고 직접 가보..

Non-Deterministic Finite Automata(NFA) 는 어디로 갈지 확실하게 정해지지 않은 오토마타이다. q0에서 선택지가 a일때 , q1일수도 있고 q2일수도 있다는 이야기이다. 그래서 이러한 NFA를 Deterministic Finite Automata(DFA)로 바꾸어야 하는게 목표이다. NFA의 예시 이와 같은 그림으로 나타낼 수 있다. 근데 경우의 수에 따라 화살표가 정해지지 않으니 좀 헷갈리는 부분들이 많이 있다. 이 오토마타에 1001을 입력하면 어떻게 될까?δ∪ 먼저 q0 에서 시작하기 때문에 δ({q0}, 1011) 에서 시작한다. 시작에서 1이면 q1또는 q3으로 갈 수 있다. δ({q1,q3}, 011) 가 된다. 이는 δ(q1, 11) ∪ δ(q2, 11)로도 표기..