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..

트리 노드로 이루어진 자료구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식노드 또한 0개 이상의 자식노드를 갖는다. 트리에는 싸이클이 존재할 수 없다. 각 노드느 부모 노드로의 연결이 있을수도 없을수도 있다. 비선형 자료구조로 계층적 관계를 표현 기본 용어 노드 : 한 정보 아이템 + 다른 노드로 뻗어진 가지 차수 : 한 노드의 서브트리 수 단말 노드 : 차수 = 0 비단말노드 : 차수 != 0 형제 : 부모가 같은 노드 리프 노드 : 자식이 없는 노드 부모 자식 트리의 차수 : 그 트리의 노드의 최대 차수 조상 : 루트에서부터 그 노드에 이르는 경로상의 모든 노드 레벨 루트 : 레벨 1 자식 : 부모 + 1 트리의 높이, 깊이 : 최대 레벨 산술식 A + ..

이중 연결리스트 각 노드가 선행노드와 후속 노드에 대한 링크를 가지는 리스트 노드의 왼쪽링크와 오른쪽 링크를 가지고 헤드노드를 가진다. 노드 구조 typedef struct node *nodepoint; typedef struct node { nodepoint llink; int data; nodepoint rlink; } 노드 삽입 void dinsert(nodepoint node, nodepoint newnode) { newnode -> llink = node; newnode -> rlintk = node -> link; node -> rlink -> llink = newnode; node -> rlink = newnode; } 노드 삭제 void ddelete(nodepoint node, nodep..

연결리스트 (Linked list) 노드를 연결시킨 자료구조 노드는 데이터와 포인터를 가지고 있다. 장점 길이가 가변적 단점 데이터를 바로 찾아낼 수 없고, 전부 탐색해야 한다. 노드 구조 typedef struct listNode listNode *listpoint; typedef struct listNode{ int data; listpoint link; }; 저렇게 정의를 어떻게 하는지 이해가 안 됐는데 암묵적 허용(?)이라고 한다. 두 개의 노드 가진 연결리스트 생성 listpointer create2() { listpoint first, second; Malloc(first, sizeof(listNode); Malloc(second, sizeof(listNode); second -> link =..

관계관계엔터티의 인스턴스 사이의 논리적인 연관성으로서, 존재의 형태나 행위로서 서로에게 연관성이 부여된 상태ex ) [강사]가 [수강생]을 가르친다. 관계의 패어링 (Paring)패어링 : 엔터티 안에 인스턴스가 개별적으로 관계를 가지는 것관계 : 패어링의 집합관계 패어링 : 각 엔터티의 인스턴스들은 자신이 관련된 인스턴스들과 관계의 어커런스로 참여하는 형태 UML(Unified Modeling Language)연간관계존재적 관계, 실선으로 표현ex) DB팀에 만쥬사원이 소속되어 있다. => DB팀과 만쥬사원은 존재의 형태의존관계행위에 의한 관계, 점선으로 표현ex) 고객이 주문을한다. => 고객과 주문은 행위에 의한 관계 관계 표기법관계명엔터티가 관계에 참여하는 형태관계시작점 : 관계가 시작되는 편관계..