JJING_LOG

Lexical analysis (Scanning) source code를 읽고 token으로 나눈다. token : 집합적 의미를 갖는 문자 sequence token은 컴파일러의 parser에 의해 처리된다. - Token categories Reserved words : IF, THEN 등 Special symbols : +, - 등 Integers, doubles, floats, delimiters 등 - 입력 문자열에서 token을 식별한다. lexeme(string value) : token을 구성하는 실제 문자 시퀀스 token의 실제 text : "137", "int" 등 token : lexeme이 속한 general class - 오류가 거의 감지되지 않는다. 유효한 토큰, 잘못된 토큰 ..

Convert an ε-NFA to a DFA Regular expression을 -> NFA automata로 만들고 -> DFA automata로 변환 ex) - Regular expression : (a + b)*abb - ε-NFA : 1. start symbol의 ε-closure를 구해라 ε-closure(0) = {0, 1, 2, 4, 7, 8} -> A라는 state라고 하겠다. Ds = {A} -> Ds라는 곳에다가(queue라고 생각) A를 추가 아래 처럼 그림 그리기 2. Ds에 있는 element를 pop 한다. -> A 나온다. A는 {0, 1, 2, 3, 7, 8}이라는 state다. {0, 1, 2, 3, 7, 8}에서 a로 갈 수 있는 state를 찾는다. : {0, 1, 2..

Finite automata (유한 오토마타) 유한 오토마타는 edges가 다음과 같은 유한 전이 그래프다. 비공식적 표현 입력 기호의 스트림 또는 sequence에 응답하는 동안, 기계가 취할 수 있는 모든 가능한 state 및 transitions(전환)을 캡처하는 상태 다이어그램 (상태 전의도) A state에서 a 마킹시 B state가 된다. A에서 a 입력시 B로 transition한다. 이러한 state들이 유한개 있다. Recognizer for "Regular Languages" 정규 언어를 인식하는 수학적 모델 어휘 분석기 종류 2개 Deterministic finite automata Non-Deterministic finite automata Deterministic finite a..

Regular expressions (정규표현) 정규 표현은 언어(regular languages)를 설명하는 대수적 방법이다. e가 정규식이면 L(e)가 정의하는 언어다. Definition of regular expressions Basic 1 : a가 기호라면, a는 Regular expression이고, L(a) = {a} a를 regular expression으로 표현시 bold 체로 정의 Basic 2 : ε은 regular expression, L(ε) = {ε} Basic 3 : ø은 regular expression, L(ø) = ø Induction 1 : r, s가 regular expression이라면, r+s도 regular expression L(r+s) = L(r|s) = L(..

Computability, Decidability, Undecidability 모든 입력에 대해 함수가 정의되어 있는지 결정 Automata theory 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학 "장치"는 물리적 하드웨어일 필요가 없다. 컴퓨터 과학의 근본적인 질문은 다양한 모델의 기계가 할 수 있는 것과 없는 것을 알아본다. Motivations ex) 문자열을 입력하고 다음 두 가지 가능한 답변을 반환하는 일종의 black box를 가정 Black box에 input으로 문자열 w를 입력했을 때 YES -> w는 언어에 속한다. NO -> w는 언어에 속하지 않는다. Language로부터 유효한걸 어떻게 기술할 것인가? Automaton : 언어를 ..

컴파일러 (Compiler) 언어 X를 언어 Y로 변환해주는 컴퓨터 프로그램이다. Source Program -> Compiler -> Target Program ex) Source language : high-level language (C / C++) Target language : object code || 어셈블리어 컴파일러가 필요한 이유 1. 폰 노이만 아키텍처 (Von Neumann architecture) 폰 노이만 아키텍처를 따르기 위해선 코드 또는 프로그램이 순차적으로 작성되어야 한다. 2. Machine language (기계어) 기계어로 코드를 작성하는 것은 매우 시간이 많이 걸리고 지루하다. 3. Assembly language (어셈블리어) Assembler : symbolic c..