컴파일러를 만들어 볼려고 합니다.

xmlParser의 이미지

제목은 굉장히 거창하지만, 컴파일러 이론을 구현할 수 있을 정도의 규모로 만들어 보고 싶습니다. 학교에서 컴파일러 시간때 많이 놀아서 졸업하고 나니 많이 아쉽다는 생각이 듭니다.

회사다니면서 짭나는 시간에 컴파일러를만들 생각을 하고 있습니다. 교육용으로 구현할 만한 문법(?)을 소개해 주시면 고맙겠습니ㅏㄷ.

ㄱ참고할마한 사이트나 소스를 소개해 주시면 더 고맙겠습니다.

새해 복 많이 받으세요~~~~

hyangii의 이미지

잡지 마소에서 11월부터 컴파일러 강의를 하더라구요, 3부작으로...
(10월부터?..)

윈32 환경에서 컴파일러 구현하던데.. 시간나시면 함 보시길.. :);;

kihongss의 이미지

컴파일러 책을 뒤져보시면 많이 나와있는,
미니 C나 미니 파스칼 정도부터 구현해보세요.

저는 학교 다닐때 미니파스칼 문법으로
ucode 생성 전까지만 만들어봤는데, 끝까지 다 못만들어서 계속 아쉽네요. :D

baram4x의 이미지

Small C Compiler ( 100k 좀 넘음... )
http://www.cpm.z80.de/small_c.html

Tiny C Compiler ( 200k ... )
http://fabrice.bellard.free.fr/tcc/

Portable Pascal Compiler
http://www.informatik.uni-trier.de/~ley/books/p4/pcom.p

그외는 검색엔진에서 찾아보시길...

sDH8988L의 이미지

흠...

도움을 드리는 답변은 아니고요. 그냥 궁금한 점이 있어서요...

단지, Scanner하고 Parser만 만드시지는 않을 거 같은데요. Target Machine은 어떻게 생각하고 계신지요?

x86 실행 Code를 만드시려고 하시고 계신가요?

예전에 제가 Compiler 수업을 들을 때는 작은 Simulator가 있어서 상당히 편했거든요. 물론, 실제 Machine과 같은 것은 아니고 Compiler가 만들어낸 간단한 Code만 돌아가는 Simulator 였습니다.

x86 Code를 만드신다면, 시간이 많이 들어갈 거 같아서요.

sozu의 이미지

sDH8988L wrote:
흠...

도움을 드리는 답변은 아니고요. 그냥 궁금한 점이 있어서요...

단지, Scanner하고 Parser만 만드시지는 않을 거 같은데요. Target Machine은 어떻게 생각하고 계신지요?

x86 실행 Code를 만드시려고 하시고 계신가요?

예전에 제가 Compiler 수업을 들을 때는 작은 Simulator가 있어서 상당히 편했거든요. 물론, 실제 Machine과 같은 것은 아니고 Compiler가 만들어낸 간단한 Code만 돌아가는 Simulator 였습니다.

x86 Code를 만드신다면, 시간이 많이 들어갈 거 같아서요.

예전에 제가 컴파일러 시간에 제작했을때는

컴파일러의 아웃풋은 간단하게 정의된 어셈 (Intermediate Language) 을 만들고

그것을 Interpreting 하는 시뮬레이터를 만들었습니다.

-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com

loveistt의 이미지

mips를 에뮬레이션 해주는 spimmips(프로그램 이름이 정확한지 모르겠군요..) 란 것이 있습니다. 윈도우용. 리눅스용 다 있습니다. 아무래도 risc 쪽이 편하지 않을런지..

:)

이한길의 이미지

전 쓸데 없는 프로트엔드쪽만 배우고 말아서 아쉽습니다....
부럽네요...

----
먼저 알게 된 것을 알려주는 것은 즐거운 일이다!
http://hangulee.springnote.com
http://hangulee.egloos.com

kslee80의 이미지

Compiler 의 Back-end 쪽은 보통 사람손으로 작성하지 않습니다.
아무리 꼼꼼한 사람이더라도 실수할 수 있기 때문이며, Back-end 쪽은 사소한 실수를
찾기가 매우 어렵기 때문에, Target Machine 의 스펙을 입력 받아서 해당 부분을
작성해 주는 Generator 를 사용합니다.

Front-end 쪽에서는 대표적인 LR Parser Generator 인 YACC 이 존재하며,
그외에 LL Parser Generator 들도 상당히 많습니다.
결국 Compiler 들은 많은 부분을 Generator 에 의존하는 셈이죠.
(물론, Compiler 시간에 흔히 이야기하는 LL 문법이나 LR 문법을 만족하는 경우에
국한된 이야기지요)

이런 Generator 들을 사용하면, 사람이 직접 작성해야 하는 부분은
보통 Semantic Checking 부분 정도가 됩니다만은, 이 부분만 하더라도
만만한 것은 아니죠.

그렇기 때문에 학부 Compiler 과정에서는
실제로 사용되는 언어인 C 나 C++, Java 가 아닌
PL/0 를 주로 사용합니다.

sDH8988L의 이미지

흠...

이미 다 아시고 계시는 거일텐데요...

Compiler의 Front End를 작성해 주는 Tool로 YACC을 쓸 수도 있지만, 저는 예전에 Antlr라는 것을 사용해 봤는데요. 이게 YACC보다는 휠씬 편한 거 같더라구요.

아시다시피, Compiler의 특성상 거의 다 문자열을 다루는 것들이고 또 Stack이나 Queue 등등의 Data Structure들을 많이 사용하는데요, 이럴 경우에는 아마래도 Java를 사용하는 것이 편하겠죠?

Antlr는 Java로 작성할 수 있기 때문에 전체적으로 Project가 상당히 편했었습니다. 쓸데없이 Code에 연연할 필요없이 Logic에만 신경쓸 수 있기 때문에 좋았죠.

Antlr Site입니다...

http://www.antlr.org/

그럼 20000

saxboy의 이미지

Quote:
전 쓸데 없는 프로트엔드쪽만 배우고 말아서 아쉽습니다....
부럽네요...

쓸데없다니요. 어떤 소프트웨어를 작성하더라도 꼭 필요한 지식이 컴파일러의 프론트엔드를 작성하면서 배우게 되는 것들인데요. lex & yacc 따위로 프론트엔드를 만들었다면 몰라도 직접 lexical analyzer와 어떤 종류가 되었든 간단한 파서를 하나 직접 꾸며보았다면 그것만으로도 대단한 소득입니다. 오히려 백엔드는 (optimization이 들어가지 않는다면) 더 노가다링이 심하지요.

sDH8988L의 이미지

saxboy wrote:
Quote:
전 쓸데 없는 프로트엔드쪽만 배우고 말아서 아쉽습니다....
부럽네요...

쓸데없다니요. 어떤 소프트웨어를 작성하더라도 꼭 필요한 지식이 컴파일러의 프론트엔드를 작성하면서 배우게 되는 것들인데요. lex & yacc 따위로 프론트엔드를 만들었다면 몰라도 직접 lexical analyzer와 어떤 종류가 되었든 간단한 파서를 하나 직접 꾸며보았다면 그것만으로도 대단한 소득입니다. 오히려 백엔드는 (optimization이 들어가지 않는다면) 더 노가다링이 심하지요.

그래도 역시 Semantic Routine과 Optimization을 해보지 않았다면, 진정한 Heart of Compiler에 대해서 해보지 않은 거라고 볼 수 있지 않을까요?

아시다시피, Compiler에서 가장 중요하게 취급되는 부분이 Sematic Action과 Optimization일텐데요.

사실, 제가 Compiler를 배워보면서 가장 힘들었던 부분과 배울 것이 많았던 부분이 Register Allocation, Scheduling, Data Flow Analysis들과 같은 Back-End 부분들이었거든요.

saxboy의 이미지

Quote:
그래도 역시 Semantic Routine과 Optimization을 해보지 않았다면, 진정한 Heart of Compiler에 대해서 해보지 않은 거라고 볼 수 있지 않을까요?

아시다시피, Compiler에서 가장 중요하게 취급되는 부분이 Sematic Action과 Optimization일텐데요.

사실, 제가 Compiler를 배워보면서 가장 힘들었던 부분과 배울 것이 많았던 부분이 Register Allocation, Scheduling, Data Flow Analysis들과 같은 Back-End 부분들이었거든요.

농담반 진담반이지만 (요즘의) 컴파일러에서 유독 optimization이 중요한 이유라면 프론트엔드에서는 더 이상 논문을 쓸만한 내용이 없기 때문이 아닐까요. 8)

단순히 제 생각일지도 모르지만 컴파일러를 공부하면서 배워야 할 가장 중요한 것이라면 "언어" - 인공언어이든 자연언어이든 - 를 체계적으로 처리할 수 있는 방법론이라고 생각합니다. 그리고 이 내용의 초석을 이루는 것이 프론트엔드부분이지요.

저는 언어에 관심이 많았던 편이라 인공언어와 자연언어를 모두 다루어 보았습니다만, 인공언어일수록 백엔드부분이 어려워지고 자연언어일수록 프론트엔드부분이 어려워지게 됩니다. 어떤 의미인지는 자명하겠지요?
그런 의미에서 컴파일러의 프론트엔드 부분을 제대로 공부해두는 것은 (컴파일러라는 한 분야를 떠나 전체적인 시각에서 생각해볼때) 훨씬 중요하다고 생각하고 있습니다. 백엔드에서 쓰는 몇가지 테크닉(이라고 해봐야 dependency로 그래프를 만들어 조작하는 내용이 대부분이지만)은 "컴파일러"에서만 쓰는 내용이지만 프론트엔드에서 사용하는 방법론들은 참 써먹을 수 있는 곳들이 많거든요. 조금 비관적인 시각이지만 오히려 백엔드와 관련된 이론들은 요즘 등장하는 jit나 vm따위에 휩쓸려서 점점 더 구식 테크닉이 되어간다는 생각이 들기도 합니다. 그렇다고 해서 백엔드 부분을 배우는 것에 대한 효용성을 부정하고 싶은 생각은 "전혀" 없고요. sDH8988L님의 말씀을 조목조목 반박하려는 의도도 아니니 오해가 없으셨으면 합니다.

저는 (전근대적이고 비과학적이지만) 컴파일러의 optimization은 1%의 성능향상을 위해 92.312%의 위험을 감수하는 짓이라고 생각하고 있습니다. 사실은 컴파일러의 최적화 옵션 따위를 잘 믿지도 않는 편이고요. 이건 제 개인적인 성향이니 너무 심각하게 받아들이시지는 않으셨으면 좋겠습니다.

이한길의 이미지

saxboy wrote:
Quote:
전 쓸데 없는 프로트엔드쪽만 배우고 말아서 아쉽습니다....
부럽네요...

쓸데없다니요. 어떤 소프트웨어를 작성하더라도 꼭 필요한 지식이 컴파일러의 프론트엔드를 작성하면서 배우게 되는 것들인데요. lex & yacc 따위로 프론트엔드를 만들었다면 몰라도 직접 lexical analyzer와 어떤 종류가 되었든 간단한 파서를 하나 직접 꾸며보았다면 그것만으로도 대단한 소득입니다. 오히려 백엔드는 (optimization이 들어가지 않는다면) 더 노가다링이 심하지요.

말씀데로 직접 구현해보았다면 좋았겠지요...
교수님이 그냥 문법 쓰고 바꾸고 구현한 코드 보여주면서 대충 이렇게 한다...
하지만 lex와 yacc가 있으니까 이걸로 쉽게 하면 된다고 하던데요...
그리고 lex와 yacc를 쓰는 숙제만 냈습니다...
쩝~

----
먼저 알게 된 것을 알려주는 것은 즐거운 일이다!
http://hangulee.springnote.com
http://hangulee.egloos.com

kslee80의 이미지

Antlr 이라는 이름과는 틀리게 LL Parser Generator 죠.

LL 문법보다 LR 문법이 더 넓은 범위의 문법을 표현 가능하기 때문에,
그리고 LL 과 LR 중 어떤 문법으로도 표현 가능한 경우에는
LR 쪽이 문법 자체가 더 간단하기 때문에
주로 LR Parser Generator 를 사용합니다.

그리고, C 만 하더라도 LL 문법으로 파싱하기가 까다롭습니다.
LL 로 가능은 합니다. 단지, 이론적인 가능일뿐, 실제로 Parser 를 만들어 내더라도
효용성 차원의 문제 때문에 C 는 LL 로 파싱할수 없다...라고 일반적으로 이야기하죠.
(C 는 실제로 if-else 의 ambiguity 때문에 굳이 LL Parsing 방법을 사용하겠다면
LL(2) 를 사용해야 하죠. 이는 똑같은 ambiguity 문제를 가지는 Java 도 마찬가지죠.
어짜피 if-else 의 ambiguity 는 LR Parsing 방법으로도 피하기는 쉽지 않지만,
피해가는 방법이 LL 보다는 LR 쪽이 더 쉽기 때문에 LR Parsing 를 사용하죠.
흔히 알고 있는 if-else 의 특성(if 문의 중첩시, else 문은 가장 가까운 if 문의
else 문장으로 동작) 도 LR Parsing 의 일반적인 ambiguity 해결 방식에 의해서
생겨난 특성이죠.
단, Java 의 경우는 LL 문법으로 작성된 문법 파일이 많기 때문에
LL Parsing 을 적용하기도 합니다)

굳이 Java 로 Parser 코드를 생성해 주는 Generator 를 써야 겠다면,
LR Parser Generator 중에 Java 코드를 만들어 주는
jCUP 이나 BYACC/J 같은 녀석을 사용하면 되겠죠.