갱스터의 블로그

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 = 우파..

지금까지 알아보았던 LL(1)파싱 방법을 통해 파서를 만들 수 있다. LL 파서는 두 가지 방법으로 만들 수 있다. 1. Recursive descent parser 2. Predictive parser 이제 각 방법의 특징과 어떻게 파서를 만들 수 있는지 설명하겠다. Recursive descent parser recursion을 이용하고, 각 non-terminal마다 하나의 procedure를 둔다. 직관적이고, 쉽다는 장점이 있지만, 생성 규칙이 바뀌면 구문 분석기를 고쳐야 한다는 점에서 융통성이 떨어진다는 단점이 있다. 모든 terminal 심볼 a에 대한 파서 코드 모든 non-terminal 심볼 A에 대한 파서 코드 아래는 위 로직을 코드로 구현한 예시이다. /* S -> aAb * A -..

FIRST의 한계 우리는 이전 포스트에서 FIRST에 대해 학습하였다. 하지만 이런 FIRST에도 한계가 존재한다. A -> XXX와 같은 생성 규칙이 있을 때, non-terminal A가 nullale한 경우 문제가 발생하게 된다. 왜냐하면 FIRST만 가지고 생성 규칙을 결정적으로 선택할 수 없기 때문이다. S -> Ab, S -> c, A -> ε의 경우 입력 문자열로 'b'가 들어온 경우 S -> Ab, 'c'가 들어온 경우 S -> c로 유도한다.FIRST(S) = {b, c}이기 때문이다. 하지만, 문법이 S -> Ab, S -> c, A -> a, A -> ε인 경우FIRST(A) = {a, ε}인데, FIRST(S) = FIRST(A) ⊕ FIRST(b)이므로 FIRST(S) = {a, ..