자신에 대한 고찰

컴파일러 수업을 듣다보면 계속 Parallelism과 Vectorization에 대한 이야기를 나눈다. 그와중에 어떻게 하면 조금더 빠르게 결과를 뽑을 수 있을지가 관건이 된다. 사실 Parallelism을 구현하는데 가장 먼저 고려해야 될 상황이 코드내의 Loop가 얼마나 자원을 소비하냐이고, 또 얼마나 반복되는 작업을 하냐는 것이다. 그냥 이런 이야기를 나누고 개선시킬 수 있는 방법을 구현하는 프로젝트도 한다. 사실 Parallelism을 테스트하는데 가장 효과적인 방법이 위와 같이 이미지를 blending 처리하는 예제다. 어차피 이미지를 나타내기 위해서는 모니터상의 픽셀을 처리해야 되며, 해당 픽셀을 처리하기 위해서는 해당 이미지의 height과 width를 알아서 하나씩 접근해 색을 접근하는 방..

프로그램을 빠르게 실행시키고자 하는 욕망은 컴퓨터를 사용하는 사람이라면 누구나 가지고 있다. 물론 하드웨어 적으로 성능을 극대화시켜서 빠르게 처리할 수도 있겠지만 가장 이상적인 방법은 돈안들이고 처리 속도를 높이는 것이다. 당연히 이렇게 하려면 뭔가 소프트웨어적으로 최적화해줘야 할 것이다. 이때 컴파일러의 역할이 중요하게 작용한다. 물론 요새는 컴파일러 공부하는 사람들도 별로 없겠지만... 보통 속도를 높여야 할 작업은 사람이 느끼기엔 다르겠지만 보통은 데이터 연산을 처리하는데 필요할 것이고, 그런 데이터는 일반적으로 배열로 들어있다. 그래서 사람들이 생각하기엔 배열에 들어있으니까 한번의 사이클마다 배열의 열 또는 행에 있는 데이터를 한번에 처리하면 어떨까 싶어서 만든 개념이 Parallelization..

과제가 너무 밀려 있어서 한동안 블로그에 글을 못 올렸다.학교 과제로 제시되었던 내용은 지난 포스트에서 소개했던 Abstract Syntax Tree로 x86 assembly code를 만들기 위한 준비과정을 이행하는 것이었다. 그리고 블로그를 통해서 소개하지는 않았지만 이 AST를 만드는 과정 중에도 operation이나 parameter, condition 등에 대한 type checking 이 수행되어야 한다. 자세하게 말하자면 data type이 다른 연산을 코드 수행과정 내에서 최대한 배제시키려는 목적에서 이런 type checking을 수행하는 것이다. 가령 숙제의 reference grammar로 제시되었던 data type인 boolean과 integer 사이에서도 연산이 이뤄지지 않게끔 ..

요 근래 학교 과제가 있어서 블로그에도 글을 잘 못올렸다. 이번에 나온 과제는 compiler의 구성물중 parser를 만드는 것이었다. 프로그래밍 실력도 없는데 compiler를 만들어보라고 해서 애를 많이 먹었지만 그래도 덕분에 C++에 대해서 복습할 기회도 있어서 여러모로 좋은 기회였다. 지난 포스트는 scanner를 통해서 각 token을 뽑고 그 token이 어떤 성향을 띄는지를 출력할 수 있다는 것을 보여줬다. 그렇게 얻은 token들을 parser에 넣게되면 어떤 문법과 일치하는지 비교해주는게 대략적인 내용이다. 아무튼 그렇게 비교하기 위해서는 처음에 grammar에 대한 specification이 나와있어야 했고, 그 부분은 과제를 하기 전에 미리 주어졌다. 위에 제시된 형태가 EBNF로 ..

과제로 Compiler의 Lexcial Analysis를 담당하는 Scanner와 Parser를 만드는 것이 목적이다. 원래는 전반적인 부분을 모두 코딩하는 게 맞지만 교수님이 Grammar Specification을 미리 지정해줘서 그 것에 맞춰서 작성하면 된다.우선은 Scanner를 만들었는데 Scanner의 역할은 코드 내의 Token이 어디에 속하는지를 분류해주는 역할을 한다. 보통 test code로 다음과 같이 제공된다. 그러면 Scanner는 한 character씩 읽어나가면서 해당 구문이 어디에 속하는지를 화면상으로 보여줘야 한다. 유의할 점이 있다면 간혹 예외적인 구문이 있다는 것이다.그냥 character 별로 구분하는 거면 switch 구문을 사용해서 해당 character를 분별해내..

계속해서 shift reduce Parsing에 대해 다뤄보고 있다. 지난 포스트에서 소개한 건 현재 주어진 Production을 통해서 DFA를 구하는 LR(0) Parsing이었다. 잠시만 Rewind해보자 사실 이 건 정확한 답이라고 할 수 없다. 그때도 언급했었지만 효율적인 algorithm이라는 건 없고, heuristic을 활용해서 전개하는 방식이 위와 같은 건데 갑자기 왠 헛소리냐라고 생각할 수 있다. 그런데 우리가 간과한게 있으니 바로 conflict라는 것이다. Shift Reduce Parsing에서는 두가지 conflict가 있는데 하나는 Reduce-Reduce conflict 이고 다른 하나는 Shift-Reduce Conflict이다. 가령 다음과 같은 item이 있다고 가정해보..

지난 포스트에 이어서 Shift Reduce Parsing에 대해서 조금더 이야기 해보도록 하겠다. 어차피 Shift Reduce 방식도 전형적인 Bottom Up Parsing 중 하나이므로 substring에 대한 handle이 존재할 것이고, 그 handle로부터 pruning을 해나가면서 최종적으로 root node를 찾아나가는 것이 목적이다. 그런데 문제는 input string 중에서 어떤 걸 handle이라고 정의할 것이냐는 것이다. 지금 우리가 다루고 있는 내용은 지난 포스트 중에서 나왔지만 Context Free Grammar(CFG)를 바탕으로 설명되고 있다. 사실 가장 이상적인 Parsing이라면 한번에 handle을 인식하고 그에 따른 terminal string으로 바꿔주는 건데 ..

이번 포스트에서는 Bottom Up Parsing으로 해결하는 방법 중 하나인 Shift Reduce Parsing에 대해서 정리해보겠다. 일단 지난 포스트에서 잠깐 다룬 것처럼 Bottom Up Parsing을 하기 위해서는 일종의 Handle, 즉 Production의 반대 개념인 Reduction을 적용할 substring을 찾는 과정이 필요했고, 이걸 마지막에 Handle Pruning이라고 했다. 그런데 한번 생각을 해보자. 어차피 substring으로 나누는 건데 reduction을 한 나머지도 일종의 substring이 아닐까? 물론 그게 정확한 terminal이다 라고는 말 못하지만 아무튼 진짜 terminal일 수도 있고, 혹은 Nonterminal과 Terminal로 결합으로 구성되어 ..

이번에 다룰 내용은 Bottom up Approach를 통해서 Parsing하는 Bottom up Parsing이다. 말 그대로 아래에서 위로, leaves에서 root를 찾아가는 방식이다. 그런데 사실 다른 compiler의 내부 구조는 거진 Top Down이 아닌 Bottom up 방식으로 구현되어 있다. 사실 Top Down 방식에서 직관적으로 봤을 때 가장 풀기 어려웠던 점이 무엇인지를 생각해보자. 개인적으로 생각했을 때는 absolute한 path를 찾는데 시간이 많이 걸린다는 것이다. grammar라는게 가지치기를 통해서 여러 방향으로 뻗어나갈 수 있는 건데 Top Down 방식에서는 선택이 맞는지 틀린지를 직접 해보고 path를 결정할 수 있는 것이다. 또한 중간 결과가 맞았다고 해서 최종 ..

이번 포스트에서 다뤄볼 내용은 지난 포스트에서 언급했던 backtracking을 완전히 배제한 Predictive Parsing이다. 말 그대로 한단계 이후의 결과를 미리 예상하고 parsing path를 정하기 때문에 틀린 결과로 인한 backtracking을 할 필요가 없어진다. 보통 이런 개념을 lookahead라고 하고 몇단계를 미리 예상할 것이냐에 따라서 정도가 달라진다. 물론 그 depth가 커지면 그만큼 컴파일러의 성능도 나빠질 것이다. 그래서 일반적으로는 이 lookahead의 정도를 1로 둔다. 참고로 이런 Top Down parsing방식은 지난 포스트에서도 언급했었지만 왼쪽에서 오른쪽으로 가면서 분석하고(left-to-right) 왼쪽부터 derivation을 수행하기 때문에(left..

지난 포스트에서 Abstract Syntax Tree 즉, derivation을 생략한 필수적인 정보만 남긴 Tree를 정리했었고, 이걸 지금까지 하고 있는 Top Down Parsing에 적용해보는 것을 이번 포스트에서 정리해보려고 한다. Top Down Parsing이라는 것은 말 그대로 Tree의 맨 위에서부터 차례대로 Parsing한다는 의미를 가지고 있다. 그런데 우리가 보기 쉽게 Tree 형식으로 만들어놓는 것이지, 실제로 compiler가 볼때는 왼쪽에서 오른쪽으로 차례대로 string을 검색하는 형식을 취한다. 그 때 이걸 left Recursive라고 언급했었고, 바로 이런 방식때문에 Top Down Parsing을 Recursive Descent Parsing이라고 하기도 한다. 보통 ..

이전 포스트 중에서 Left Recursive와 Right Recursive를 설명하면서 Parse Tree 라는 것을 잠깐 언급한 적이 있다.말 그대로 해당 구문을 분석한 것이다. 그때 어떤 방향으로 분석하는지에 따라서 결과가 다르게 나올 수 있다고 했었다. 그런데 사실 이걸 판단하는 단계는 이전 과정에서 끝나는 것이고, 이 parse 방향이 정해지면 사실 결과만 빼놓고는 필요없는 내용이다. 우리가 필요로 하는 것은 terminal로 구성된 syntax일 뿐이다. 그래서 위의 parse tree 중 derivation 과정을 제외하고 필수적인 정보만 담은 tree를 Abstract Syntax Tree(AST)라고 한다. 물론 이름에서 담고 있듯 축약만 하고 있는 거지 Parse Tree와 동일한 정보..

지난 포스트를 통해서 Context Free Grammar에 대해 다뤘다. 간단히 요약해보자면 Regular Expression으로 표현하기 힘든 문법들이 존재하기 때문에 표현하기 위한 대체 방안으로 CFG를 언급했고, 여기서 Syntax Tree를 그려보았다. 여기서 Left Recursive문제가 발생하기 때문에 이를 해결하기 위한 방법으로 Left Factoring, 즉 terminal을 오른쪽에 배치해서 해결할 수 있다고 했다. 그런데 그때 잠깐 소개했던 내용중에 이런게 있었다. 이 때 이걸 Notational Convention이라고 소개했다. 이게 정의되어 있어야 어떤 부분을 terminal로 할지 또는 nonterminal로 할지를 정할 수 있었다. 사실 위의 내용은 사용자가 임의로 정한 n..

지난 포스트를 통해서 Regular Expression을 NFA->DFA를 거쳐는 일종의 Lexical Analysis을 정리했다. 그러면 이제 수행해야 될 것이 Syntax Analysis가 될 것이다. 그런데 한가지 짚고 넘어가야 될 부분이 있다. 과연 지금까지 다룬 방법으로 사용자가 넣는 모든 입력들을 이 Syntax Analysis를 처리할 수 있냐는 것이다. 예를 들어서 brace {()} 가 있는 구문을 보자 이걸 Regular Expression으로 어떻게 표현할 수 있을까? 맨처음 RE로 표현할 수 있는 기본적인 수칙에 의하면 분명 (*)* 로 표현해야 될 것이다. 그다음 작업이 FA로 바꾸는 작업인데 State Transition Diagram으로 표현할 수 있겠는가? 만약 brace 안..