Context free grammar(CFG) $G = (V_N, V_T, P,S)$ $V_N$ : non-terminal symbols들의 집합 $V_T$ : terminal symbols들의 집합 $V_N \cap V_T = \varnothing, V_N \cup V_T = V$ $P$ : productions $\alpha \rightarrow \beta, \alpha \in V^+, \beta \in V^*$ $\alpha \in V_N, \beta \in V^*$ $S$ : 시작 기호(non-terminal symbol) Context free language(CFL) context free grammar에 의해 생성된 언어 $L(G) = \{w|w \in V_T^*\space and\space..

Lex란? 어휘 분석기(Scanner)를 생성하는 프로그램 문자 입력 스트림의 어휘적 처리를 위해 디자인된 프로그램 생성기 입력 : 정규 표현, 일부 코드 출력 : 프로그램 source(정규표현, 일부 코드 조각) → lex → yylex(프로그램을 만드는 분석기) 입력 → yylex → 출력 어휘 분석 단계를 수행하기 위해 파서 생성기와 함께 사용됨 lex : 정규 표현만 인식 Yacc : context free grammar를 인식하는 parser 생성 입력 토큰을 인식하기 위한 저수준의 분석기가 필요 어휘 수준에서 변환, 분석, 통계정보 수집을 위해 단독으로 사용됨 Lex with Yacc 통계정보를 위한 Lex Lex의 일반적인 형식 {definitions} %% {rules} %% {user s..

어휘 분석(Lexical analysis, Scanning) 소스코드를 읽고 토큰으로 나누는 것 토큰 : 의미를 가지는 문자열 토큰은 파서에서 처리 토큰 종류 예약어 : if, then 특별한 기호 : +, -, ... integer, double, float, 구분자 입력된 문자열에서 토큰을 인식 lexeme : 토큰을 구성하는 실제 문자열 token : lexeme이 속하는 일반적인 클래스 에러가 거의 감지되지 않음 유효한 토큰 or 유효하지 않은 토큰 위치를 벗어난 토큰, 선언되지 않은 변수, 철자가 틀린 키워드 등을 찾을 수 없음 정규 표현의 확장 1번 이상 반복 $(0+1)(0+1)^* or (0|1)(0|1)^* \rightarrow (0|1)+$ 어떤 문자 메타문자 .(period) : 매칭..

Finite automata 유한오토마타(Finite automata) 정규 언어인지 아닌지 판단하는 인식기 유한 전이 그래프 유한개의 상태들 특정 상태에서 어떤 입력을 받으면 다른 상태로 전이하는 것을 표현 시작 상태에서 목표 상태까지 도달이 가능하면 인식이 가능한 언어이고, 도달할 수 없으면 인식 불가능한 언어 정규 언어를 인식하는 수학적 모델 어휘분석기 사용 Deterministic / Non-Deterministic finite automata Deterministic finite automata(DFA) $D = (Q,\Sigma, \delta, q_0, F)$ $Q$ : 상태들의 집합 $\Sigma$ : 입력 기호(알파벳)들의 집합 $\delta$ : 전이 함수, $\delta : Q \tim..

Regular expressions(정규표현) 정규표현(Regular expression) 정규언어를 표현하는 대수적인 방법 e가 정규표현이면 L(e)는 e를 정의하는 언어 정규표현의 정의 a가 어떤 기호이면, a는 정규표현이고, L(a) = {a} $\epsilon$은 정규 표현이고, L($\epsilon$) = {$\epsilon$} $\varnothing$은 정규 표현이고, L($\varnothing$) = $\varnothing$ 유도식 r과 s가 정규 표현이면, r+s도 정규 표현이고, $L(r+s) = L(r) + L(s)$ + 대신에 | 를 쓰기도 한다. L(r|s) = L(r) $\cup$ L(s) {r, s} r과 s가 정규 표현이면, rs도 정규 표현이고, $L(rs) = L(r)L(s..

Theory of Computation 계산 이론 Computability, Decidabillity, Undecidability 계산 가능한 함수인가? 함수가 종료 가능한가? 증명이 무엇인가? Languages and Automata 언어란 무엇인가? 언어를 어떻게 정의하는가? 언어 안의 단어를 어떻게 인식할 것인가? Complexity 공간과 시간을 너무 많이 사용하면 안 됨 P (polynomial time)= NP(non-deterministic polynomial time) 계산 가능성, 결정 가능성, 결정불가능성 함수가 모든 입력에 대해 정의되는지 결정하는 것은 어려움 3n + 1문제 오토마타 이론(Automata theory) 계산 능력이 있는 추상기계와 그 기계를 이용해서 풀 수 있는 문제..

프로그램 실행 과정 컴파일러 : 소스코드를 목적코드로 컴파일 링커 : header나 목적 코드들을 연결 로더 : 메모리에 적재 컴파일러(Compiler) X 언어를 Y언어로 번역해 주는 컴퓨터 프로그램 소스 프로그램을 컴파일러가 목적 프로그램으로 번역 소스 언어 : 고수준언어(C/C++) 목적 언어 : 목적 코드(기계어) 컴파일러가 필요한 이유 폰노이만 아키텍처는 기계어가 순차적으로 작성되어 있어야 함 기계어 : 실제 기계가 작동하도록 하는 숫자로 된 코드 기계어로 코드를 작성하는 것은 시간이 많이 들고 어렵다. 어셈블리어 : 명령어와 메모리 위치가 주어진 기호 형식으로 표현됨 어셈블러 : 어셈블리어를 기계어로 번역 어셈블리어는 기계어보다 더 빨리, 정확히 작성 가능하나 여전히 작성하기 어려움 고수준 언..

Overview of Wireless LANs 무선 전송 매체 비싼 가격, 에러율이 높음, 고속화 어려움, 신뢰성이 낮음 안정성 라이선스를 받아야 함 응용 LAN확장 용이 안테나와 안테나 간의 통신 건물 간 interconnect 옮겨 다니면서 통신 Ad hoc networking : 컴퓨터와 컴퓨터 간의 direct 통신 Single Cell LAN Extension 기지국 CM(control module) – 백본망 연결 UM(user moduel) Multi Cell LAN Extension 무선에서 전송할 수 있는 거리 제한받음 지역별로 나눠서 CM을 설정 두 개의 영역에서 같은 주파수를 사용하면 안 됨 Cross-Building Interconnect 빌딩과 빌딩 사이의 통신 Point to p..

Introduction 기술적인 빠른 변화 LAN의 사용처 많음 빠른 속도 필요 10M->100M(Fast) Fast and Gigabit Ethernet Fiber Channel High Speed Wireless LANs High speed LAN의 특징 CSMA/CD Precursors ALOHA 최초의 버전 패킷 라디오 네트워크를 위해 개발됨 스테이션이 언제라도 프레임을 전송할 수 있음 잘못된 프레임을 받을 수 있음 -> 무시 이용률이 낮음 최대 이용률 18% 성능을 향상하기 위해 slotted ALOHA방식 나옴 Slotted ALOHA Time slot으로 나눔 Slot에 동기 되어 전송 다음 slot이 시작할 때 전송 망가지는 크기가 ALOHA의 1/2 최대 이용률이 38% 망의 상태를 보지..

Local Area Networks (LANs) LAN의 기본요소 : 토폴로지, 매체, wiring layout, medium access control(mac) 프로토콜 LAN Topologies Station의 물리적 배치 (a) 버스 (b) 트리 (c) 링 – closed loop (d) 스타 – center에 연결된 형태 Bus and Tree 버스를 확장하면 트리구조 버스를 연결하기 위해 탭이 필요 – t탭 하나의 매체를 통해 full duplex – 동시에 주고받음 매체를 통해 전파 한 군데에서 보내면 여러 군데에서 다 받음 터미네이터가 필요 터미네이터는 신호가 반사되지 않도록 신호를 흡수 트리는 버스를 합성한 것 No closed loops 트리의 시작은 headend에서 모든 곳에서 다 수..

Principles of Cellular Networks Cellular network는 이동성을 제공하기 위해 만들어짐 무선이라는 자원은 상당히 제한된 자원임 -> 효율적으로 사용해야 함 제한 요소를 해결하기 위한 방식 => cellular 면적을 여러 개의 cell로 나누고 경우에 따라서 cell에서 같은 주파수를 동시에 사용 25 채널 CDMA는 60 채널 반경 80km (하나의 셀이 80km) 하나의 셀 내에서는 같은 주파수를 동시에 사용할 수 없음 같은 주파수를 재사용하기 위해서는 셀 사이즈가 작을수록 좋음 Cellular Network Organization 모바일 기술의 주요 기술 각각의 셀은 base station(기지국)을 가짐 Base station은 하나의 셀을 커버 커버하는 간격 =..

혼잡이란 혼잡은 네트워크를 통해 전송되는 패킷의 수가 네트워크가 패킷을 다룰 수 있는 용량에 도달하면 발생 혼잡 제어의 목적은 성능이 급격하게 떨어지는 레벨 이하로 패킷의 수를 유지하는 것 데이터 네트워크는 큐의 네트워크이다. 일반적으로 80% 이용률이 되면 문제가 생김 유한한 큐는 데이터를 잃어버릴 수 있다는 것을 의미 노드의 큐 각각의 링크는 최소 한쌍의 버퍼를 가짐 하나는 전송버퍼 하나는 수신버퍼 큐의 상호작용 뒤의 큐가 다 차면 앞의 노드가 보낼 수 없음 이상적인 네트워크 이용 실제 - 혼잡 제어 X 혼잡 제어의 매커니즘 Backpressure Choke packet : 혼잡이 발생하면 choke packet을 source에 전송 Implicit : 지연, 폐기, 간접적 Explicit : 패킷에..