갱스터의 블로그

DNS(Domain Name System) DNS란 인터넷에 연결된 컴퓨터의 이름과 IP 주소를 매핑해주는 분산 시스템을 말한다. 우리는 어떤 사이트에 접속할 때 'http://naver.com'과 같이 도메인을 이용하여 접근할 수 있다. 도메인을 이용하여 접근을 하기 위해서는 실제 네트워크에서 사용하는 ip 주소로 변환하는 과정이 필요한데, 이러한 모든 일련의 과정을 DNS(Domain Name System)라고 한다. 도메인의 체계는 위 사진과 같다. 1. 최상위 도메인(TLD) 루트 바로 아래 도메인으로 각 국가 정보를 2자리 영문 약자로 표기한다. 2. 차상위 도메인(SLD) 최상위 바로 아래 도메인으로 최상위 도메인에서 정의된 문자열을 제외한 모든 문자열을 사용할 수 있다. 3. 하위 도메인(S..

인터넷 속도 측정 https://speed.nia.or.kr/index.asp NIA 인터넷 속도측정 NIA 한국지능정보사회진흥원에서 제공하는 인터넷속도 품질측정 시스템 speed.nia.or.kr 인터넷의 속도 측정은 위 사이트로 진행할 수 있다. 이때, 인터넷의 속도를 측정하는 곳이 외국에 있다면 당연히 그 속도는 느리게 나올 것이다. 위 사이트는 속도를 측정하는 국가에 맞추어 국가를 설정해준다. https://www.speedtest.net/ Speedtest by Ookla - The Global Broadband Speed Test Use Speedtest on all your devices with our free desktop and mobile apps. www.speedtest.net 속..

Intorduction Example: Salmon-Sea Bass Problem Bayesian Classifier에 대해 학습하기에 앞서 하나의 예를 먼저 들어보자. 우리는 연어와 베스를 구별하는 일을 할 때 두 가지의 선택지가 있다. 첫 번째는 사람이 구별하는 것이고, 두 번째는 자동화 시스템이다. 그렇다면 우리는 어떤 것을 선택할 것인가? 당연히 자동화 시스템을 통해 분류하는 것이 이득이므로 후자를 고를 것이다. 따라서, 전문가만이 할 수 있던 일을 알고리즘이 해결함으로써 이점이 높다. 이때 ML이 아닌 자동화 시스템을 사용한다면 if문(전통적)을 통해 분류를 진행할 수 있다. 하지만 ML을 통해 성능을 높여보자. 컨베이어 벨트에 연어로 베스를 통과시키면 우리는 카메라로부터 길이나, 밝기, 너비 ..

Machine Intelligence Early AI 사람에겐 어렵지만, 컴퓨터에게 쉽다. 예로 수학적인 규칙이나, search가 있다 Modern AI 사람에게는 쉽지만 형식적으로 표현하기 어렵다.(컴퓨터에 가르치기 어려움) 직관적인 정보와 비공식적인 지식이 있다는 특징이 있다. 예로 사람의 말을 이해하는 것이나, 손으로 쓴 숫자를 인식하는 것이 있다. Machine Learning ML의 분류는 다음과 같다. Task T를 수행하는 능력을 Performance P로 측정할 때, Expression E로 T의 P가 향상되는 것을 ML이라고 한다. (1997, Mitchell) 이때, 엑셀로 한 계산이나 E로 P가 향상되지 않는 경우거나, If문을 통한 분류는 ML이 아니라고 할 수 있다. 위 사진과 같..

LALR Parsing LR(1) 파싱의 문제점 LR(1) 파싱은 정교하기 때문에 상태의 개수가 어마어마하게 많다. Pascal 언어를 통해 만들면 SLR은 수백 개, LR(1)은 수천 개의 상태가 나온다. 하지만 이렇게 많은 개수의 상태는 메모리에 과부화를 준다. 따라서 우리는 이러한 LR(1)의 상태 개수를 줄이고자 LALR 파싱을 시작하였다. LALR Parsing LR에서 두 상태의 core가 동일하면 하나의 상태로 묶어준다. 위 사진에서 두 개의 상태 중 일부가 동일한 것을 볼 수 있다. 동일한 부분을 LALR 파서에서는 묶어준다. 이러한 LALR 파싱은 1. SLR보다 많이 정교하다. LR(1)보다 이론적으로 less powerful하지만, 실제 처리할 수 있는 의미 있는 문법의 종류는 거의 ..

Shift와 Reduce의 의미 입력으로 '((a),b)'이 들어 온 경우 아래와 같이 파싱할 수 있다. SLR Parser 앞선 LR(0)의 파싱 테이블은 conflict가 발생한다. 왜냐하면 reduce 시에 모든 셀에 대해 reduce를 채우기 때문이다. 따라서 이러한 LR(0)의 충돌을 줄이기 위해 SLR(Simple LR) Parser가 등장했다. SLR 파싱 테이블은 약간의 노력을 더해 LR(0)의 conflict를 줄이고 정교하게 만들어 주는 것으로 I1이 [X -> β.]를 포함할 때, M[I1, a] = 'reduce X -> β'이다 (단, a ∈ FOLLOW(X)) 즉, 파싱 테이블에서 X의 팔로우에 속하는 터미널에 대해서만 reduce를 진행한다는 의미이다. 나머지는 LR(0)과 동..

LR Parsing: 파서 상태 파서는 파싱 테이블을 통해 현재 상태, 입력 심벌을 보고 shift 할 지, reduce 할 지 결정하고(action), 파서의 상태로 변경한다.(goto) 그렇다면 '상태'란 무엇일까? LR(0) 아이템 LR(0)은 lookahead 없이 파싱하는 shift-reduce 형태이다. LR(0)의 파싱 테이블은 파서 상태를 정하고, 각 파서 상태들의 상태 전이도를 테이블에 담아내는 형태로 만들어진다. 이때, LR(0)item이란 rhs에 점('.') 심벌을 가진 생성규칙이라고 할 수 있다. 생성 규칙의 형태가 A -> XYZ일 때, [A -> .XYZ], [A -> X.YZ], [A -> XY.Z], [A -> XYZ.] 모두 LR(0) item이라 할 수 있다. 또, 생성..

YACC YACC는 LALR 파서 생성기로, Yet Another Compiler Compiler의 약자이다. Lex와 함께 AT&T Bell Lab.에서 70년대 유닉스 운영체제용으로 개발하였으며 유닉스 표준으로 채택되었는데, 요즘은 GNU Flex(Lex)/Bison(YACC)을 더 많이 사용한다. 위와 같은 흐름으로 진행된다. foo.y 파일이 들어오면 yacc나 bison을 통해 y.tab.c파일로 만들어지고, y.tab.c파일은 gcc를 통해 컴파일된다. 이때 .y 파일의 형태는 아래와 같은데, 해당 구조는 lex/flex와 동일하다. LR Conflict 위와 같은 생성 규칙이 있다. 스택에 $ E * E 가 있고, 입력 버퍼에 + ... $가 있을 때, reduce를 해야 할 것인지, shi..

위 사진은 앞 포스트에서 보여준 reduce 과정이다. 이 과정을 stack을 통해 시행해보자. 초기 상태는 스택에 $, 입력 버퍼에는 입력 스트링과 $를 모두 넣는다. accept 상태는 스택의 top에 시작 심벌이 있고 입력은 모두 읽은 상태이다. 스택의 top 모습을 보고 reduce와 shift를 한다. 이때 reduce 할 때는 입력 버퍼에 영향이 없다. 이때, 우리는 shift와 reduce를 어떻게 판단할 수 있을까? 스택에 β가 있고 입력 글자가 b일 때, β = αγ이고, X -> γ가 있다면, 스택을 αX로 만들 것인지, βb로 만들 것인지에 대한 고민에 빠진다. 또, 여러 가지 reduce가 있는 경우 스택 중 어디까지 handle로 봐야 하는 것일까.즉, 스택이 β = αγ일떄, X..

Top-Down vs. Bottom-Up 아래는 입력이 '(a + a)'가 들어온 경우 Top-Down과 Bottom-Up 방식으로 파싱한 과정이다. 이때, Bottom-Up 방식이 조금 더 자연스럽다. 이때, Top-Down에 비해 Bottom-Up 방식이 더 강력한데, 생성 규칙을 선택할 때, Top-Down에 비해 더 많은 토큰을 볼 수 있기 때문이다. 따라서 Top-Down으로 파싱 시 불가능했던 left-recursion을 파싱할 수 있다. 위 그림에서 볼 수 있듯이 Top-Down 방식은 파싱 시 root를 찾아야 하지만, Bottom-Up은 root를 찾을 필요 없이, 아래에서만 파싱할 수 있으므로 표현력이 더 강하다고 볼 수 있다. Bottom-Up Parsing Bottom-Up = 우파..