'lex'에 해당되는 글 2건
- 2010.01.16 :: NCC 그 구현과 관련하여~~
- 2009.09.28 :: Parse Tree 그리기
4-2학기
2010. 1. 16. 01:34
NCC를 개발함에 있어
크게 3부분 정도로 나누어 고민했다고 할수 있다.
1. 문법정의
2. 심볼테이블 구성
3. 최적화 & 코드생성
1번 항목은 사실상 다른 조원이 거의 도맡아서 해서 내가 정확하게 어떤 아이디어로 접근하였는지 깊게는 알 수 없다.
하지만 정확한것인 ANSI C의 문법 Lexer의 정의를 어느정도 답습하였으며, 우리들만의 랭기지를 위한 여러가지 구성을 위하여 추려내고, 고쳐냈다는 점이다.
내가 중점적으로 맡아서 진행했던 2,3번 파트에 대해서 이야기를 하겠다.
내가 컴파일러를 작업을 시작하면서 가장 크게 고민했던 부분은 메모리상에 IDENTIFIER와 NUMBER, FUNCTION들을 어떻게 관리할것인가 하는 문제였다.
내가 결정한 부분은 다음과 같다.
1. 각각의 펑션은 따로 관리한다.
2. 펑션안의 변수들은 각각 관리된다.
3. 상수들은 통합되어 관리된다.
4. 스트링들 역시 통합되어 관리된다.
5. 각각의 펑션안에는 중간코드에 대한 정보가 담겨져 있다.
6. 중간코드드 확장시킨 3 ADDRESS체제를 따른다.
크게 위와 같은 구조로 결정하였다.
크게 펑션 매니저 클래스와 펑션 클래스가 존재한다.
클래스 매니저 클래스에서는 클래스 펑션들을 Vector로 관리하며 여러개수의 펑션들을 관리할 수 있게 한다.
각각의 펑션 클래스에는, 중간코드가 Vector로 관리되고, 변수 네임와 타입이 Vector로 관리된다. 그리고 펑션콜 인자의 개수가 역시 관리된다.
결국 우리가 참조하는 녀석은 펑션매니저를 통해 펑션클래스의 메소드를 호출하여 관리하게 되는것이다.
이러한 구조를 가지고있기에 우리가 일반적으로 알고있는 c언어의 구조를 어느정도 구현할 수 있었다.
여기에서 우리가 크게 고려해야 될 점은 다음과 같다.
a. 중간코드를 어떻게 생성할 것인가?
b. 변수는 어떻게 관리 할 것인가?
사실상 변수들은 새로운 identifier가 인식되었을때, 펑션 이름을 알수 있다면은 그 펑션 테이블을 찾아서 등록해주며 되기에 크게 문제가없다.
문제는 중간코드이다. 이놈의 중간코드는 책을 보아도 자세히 설명이 되어 있질않다.
책에 간단히 설명이 되어있는 부분중 제일 어려운 부분은 조건 판단 부분이다.
이 부분에 대한 설명이 전혀없다..
그래서 나는 이렇게 가정하고 작성을 하였고, 잘 작동함을 확인 할 수 있었다.
일반적으로 어셈블러는 CMP라는 명령어를 이용하여 비교를 수행한다. 그리고 그 결과는 상태 레지스터에 결과가 기록되고, 그 결과를 이용하여 JMP를 수행함으로써 조건분기가 가능하다.
나는 이점에서 착안하여 중간코드에서도 CMP라는 가상의 명령을 만들었고, 이 명령을 수행하면 가상의 상태레지스터에 결과가 기록된다고 가정하고 중간코드를 생성한다.
즉
A=3;
IF(A<5)
B++
ELSE
C++
이런 가상의 소스가 있다라고 한다면 중간 코드는
...
7. ASSIGN A, 3
8 CMP A, 5
9 JGE 11
10 INC B
11 JMP 13
12 INC C
대충 저런식이다.
CMP문만 본다면 A와 숫자 5를 비교해라
그리고 그다음줄에서는 만약 그 결과가 5이상의 결과라면, 12번 라인의 문장으로점프하라...
5보다 작다면 10번 문장을 수행하고 13라인으로 점프뛰어라 이다..
위와같이 구성하면 아무런 문제 없이 분기문을 수행 할 수 있다.
저 부분때문에 3일가량을 고민했다.
그 다음 나를 고민하게 만든것은 다중 루프문장이다.
FOR, WHILE을 Yacc Parser로 파싱하게 되면 조건 문을 생성하기 위한 문장의 파싱순서가 뒤집혀 있다라는 사실을 금방 알아 챌 수 있을것이다.
이 부분덕에 실제로 최종 검사시에 대부분의 팀이 다중 루프 구현을 실패했다...
(자세히 말하면 컴파일러의 전체적인 구성 자체를 실패했다라고 말하는 것이 옳겠다.)
내가 해결했던 방법은 다음과 같다.
for루프의 Inner Number카운트를 유지한다.
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
크게 3부분 정도로 나누어 고민했다고 할수 있다.
1. 문법정의
2. 심볼테이블 구성
3. 최적화 & 코드생성
1번 항목은 사실상 다른 조원이 거의 도맡아서 해서 내가 정확하게 어떤 아이디어로 접근하였는지 깊게는 알 수 없다.
하지만 정확한것인 ANSI C의 문법 Lexer의 정의를 어느정도 답습하였으며, 우리들만의 랭기지를 위한 여러가지 구성을 위하여 추려내고, 고쳐냈다는 점이다.
내가 중점적으로 맡아서 진행했던 2,3번 파트에 대해서 이야기를 하겠다.
내가 컴파일러를 작업을 시작하면서 가장 크게 고민했던 부분은 메모리상에 IDENTIFIER와 NUMBER, FUNCTION들을 어떻게 관리할것인가 하는 문제였다.
내가 결정한 부분은 다음과 같다.
1. 각각의 펑션은 따로 관리한다.
2. 펑션안의 변수들은 각각 관리된다.
3. 상수들은 통합되어 관리된다.
4. 스트링들 역시 통합되어 관리된다.
5. 각각의 펑션안에는 중간코드에 대한 정보가 담겨져 있다.
6. 중간코드드 확장시킨 3 ADDRESS체제를 따른다.
크게 위와 같은 구조로 결정하였다.
크게 펑션 매니저 클래스와 펑션 클래스가 존재한다.
클래스 매니저 클래스에서는 클래스 펑션들을 Vector로 관리하며 여러개수의 펑션들을 관리할 수 있게 한다.
각각의 펑션 클래스에는, 중간코드가 Vector로 관리되고, 변수 네임와 타입이 Vector로 관리된다. 그리고 펑션콜 인자의 개수가 역시 관리된다.
결국 우리가 참조하는 녀석은 펑션매니저를 통해 펑션클래스의 메소드를 호출하여 관리하게 되는것이다.
이러한 구조를 가지고있기에 우리가 일반적으로 알고있는 c언어의 구조를 어느정도 구현할 수 있었다.
여기에서 우리가 크게 고려해야 될 점은 다음과 같다.
a. 중간코드를 어떻게 생성할 것인가?
b. 변수는 어떻게 관리 할 것인가?
사실상 변수들은 새로운 identifier가 인식되었을때, 펑션 이름을 알수 있다면은 그 펑션 테이블을 찾아서 등록해주며 되기에 크게 문제가없다.
문제는 중간코드이다. 이놈의 중간코드는 책을 보아도 자세히 설명이 되어 있질않다.
책에 간단히 설명이 되어있는 부분중 제일 어려운 부분은 조건 판단 부분이다.
이 부분에 대한 설명이 전혀없다..
그래서 나는 이렇게 가정하고 작성을 하였고, 잘 작동함을 확인 할 수 있었다.
일반적으로 어셈블러는 CMP라는 명령어를 이용하여 비교를 수행한다. 그리고 그 결과는 상태 레지스터에 결과가 기록되고, 그 결과를 이용하여 JMP를 수행함으로써 조건분기가 가능하다.
나는 이점에서 착안하여 중간코드에서도 CMP라는 가상의 명령을 만들었고, 이 명령을 수행하면 가상의 상태레지스터에 결과가 기록된다고 가정하고 중간코드를 생성한다.
즉
A=3;
IF(A<5)
B++
ELSE
C++
이런 가상의 소스가 있다라고 한다면 중간 코드는
...
7. ASSIGN A, 3
8 CMP A, 5
9 JGE 11
10 INC B
11 JMP 13
12 INC C
대충 저런식이다.
CMP문만 본다면 A와 숫자 5를 비교해라
그리고 그다음줄에서는 만약 그 결과가 5이상의 결과라면, 12번 라인의 문장으로점프하라...
5보다 작다면 10번 문장을 수행하고 13라인으로 점프뛰어라 이다..
위와같이 구성하면 아무런 문제 없이 분기문을 수행 할 수 있다.
저 부분때문에 3일가량을 고민했다.
그 다음 나를 고민하게 만든것은 다중 루프문장이다.
FOR, WHILE을 Yacc Parser로 파싱하게 되면 조건 문을 생성하기 위한 문장의 파싱순서가 뒤집혀 있다라는 사실을 금방 알아 챌 수 있을것이다.
이 부분덕에 실제로 최종 검사시에 대부분의 팀이 다중 루프 구현을 실패했다...
(자세히 말하면 컴파일러의 전체적인 구성 자체를 실패했다라고 말하는 것이 옳겠다.)
내가 해결했던 방법은 다음과 같다.
for루프의 Inner Number카운트를 유지한다.
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
c++:
}
위의 문장의 경우
1. ASSIGN i, 0
2. CMP i, 10
3. JGE 점프 뛸 주소가 미결정 된 상태
4. INC i
5. ASSIGN j, 0
6. CMP j, 10
7. JGE 점프 뛸 주소가 미결정 된 상태
8. INC j
이렇게 주소가 생성 될 수 있을것이다.(본인이 이렇게 설명하는 이유는 파싱해 나가면서 바로 중간코드를 계속 생성했기 떄문이다.)
대충 저런식이다 하지만 어셈블러를 조금 하는 유저라면 저건 잘못된 포 루프 소스 라는것을 알 수 있다.
그래서 나는 중간에 끼워넣는 방식을 택했다.
소스를 기재해보면
1. ASSIGN i, 0
2. CMP i, 10
3. JGE FOR_카운트넘버_END (레이블명으로 점프주소 해결)
4. INC i
여기까지 순서대로 파싱한다면 생성이 가능하다.
그 이후 새로운 포 안의 문장이 나타나게 된다면
4번의 라인에 순서대로 끼워넣는다.
그러면
1. ASSIGN i, 0
2. LABEL FOR_1_START
2. CMP i, 10
3. JGE FOR_1_END (레이블명으로 점프주소 해결)
5. ASSIGN j, 0
6. LABEL FOR_2_START
6. CMP j, 10
7. JGE FOR_2_END
8. INC c
9. INC j
10. JMP FOR_2_START
11. LABEL FOR2_2_END
12. INC i
13. JMP FOR_1_START
14. LABEL FOR_1_END
위와같은 코드로 중간코드 생성식이 바뀐다.
물론 변수의 경우도 변수 테이블인덱스로 표기하지만, 그런건 구조체의 속성타입을 표기해줌으로써 처리가 가능하므로 개념적인 면으로 설명한다.
i++과 같은 식이 잡히는순간 레이블 생성식을 같이 중간코드에 생성시키기고 INC i의 라인넘버를 기억하고 있다가 그 위치에 끼워넣으면 된다...(간단하지만 귀찮다..)
그러면 백 페칭같은 기법을 사용하지 않고도 점프뛸 주소를 결정 지을 수 있다.
레이블명이 적힌 곳의 라인넘버를 찾으면 되기 떄문이다.
같은 방법으로 WHILE로 해결하면 똑같이 해결된다..(의외로 단순하다....)
어찌보면 이러한 방법은 정석적인 방법은 아니다.
책에서도 위와 유사한 기법을 소개는 하고있다..레이블명을 생성하여 처리하는 방법이나...내껀...조금 자신만의 스타일로 꼼수비슷하게 해결한 케이스라고 생각한다..
하지만....중간코드 생성에 대한 정보가 워낙 적어서,, 혼자만의 세상에서 고민하다 만들어낸 방법이므로
맞다, 틀리다라고 말할 순 없지만, 결과적으로 잘 돌아가므로 만족하는 방식이다.
펑션 콜을 할때는 인자를 넣어줘야 하는데 이는 역시 어셈과 비슷하게 푸시명령을 통해 해결하였다.
가령 int sum(int a, int b)와 같은 꼴의 펑션을 콜 한다면 sum(1, 10)이라고 가정해보면
push 1
push 10
call sum
이런식이다.
이러면 코드제너레이터는 이 푸시의 순서를 다시 뒤집어서 어셈블리어 코드로 제너레이션하는 방식이다.
문득 야밤에 내가 참여한 ncc텀에 대한 기억이 떠올라 가장 고민했던 부분에 대한 기록을 남긴다... 언젠가 이 경험이 토대가 되어, 스크립트 엔진의 베이스 코드가 될것이다...
가상변수, 간단한 스크립트를 통한 가상변수 제어, 미리 등록된 함수에 대한 콜의 지원등을 위한 스크립트 엔진 구상은 대충 끝났고..구현만 하면되는데...회사 입사한 이후에.......천천히 진행할 것이다...
심볼 테이블매니저 클래스의 경우 사실상 이틀정도 만에 구현이 다 끝났다.
심볼테이블 매니저 구성자체가 어려운건 아니기 떄문이다.
대신 중간코드 생성에서 한동안 고생을 했다...
그 이후 코드제너레이션 하는 부분은 의외로 빨리 끝났다.
3일정도..
3일만에 내가생성한 중간코드로, 어셈블링이 가능한 어셈블리어 코드를 생성해 냈으니...굉장히 신기했다...
결국 최종적으로 MASM 6.15와 LINKER를 통해 EXE파일을 생성해 냈다.
물론 PE binary... Microsoft Platform에서 돌아간다
최종적으로 우리의 컴파일러를 만들기 위해 gcc컴파일러와 g++컴파일러, STL Vector라이브러리를 이용했다;
최종 소스는 공개하고 싶지만....의외로 꽤 돌아가기도 하고, 텀 프로젝트 제출로 악용될수 있어 공개는 하지않는다. 다음포스팅때는 간단한 옵티마이제이션 부분이랑 코드제너레이션의 부분으로 설명하겠다..
마지막 학기의 열정을 제대로 쏟아부었던..(좀 뒤늦게 필 받았지만...) 컴파일러 텀 프로젝트....학부생활의 마지막 추억이다.... 같이 숱하게 새벽작업하며 밤샌 쩌로 킴..ㅎㅎㅎ
수많은 학우들이 매크로 어셈블러로 exe파일을 만들겠다고 해서 움찔했는데....괜히 쫄았었다...
인텔 어셈블리어를 접해본적이 없는 사람이 대부분인지라...다들 코드제너레이션까진 제대로 가지도 못했으니.... 덕분에 진도가 훅 나갔지만....;; 기회가 된다면 못다한 포인터와, MALLOC과 같은 것을 해보고싶다....차후에???..................심플 커널이랑, 게임프로젝트, 아이폰 버스 프로젝트 등한 후에..;
위의 문장의 경우
1. ASSIGN i, 0
2. CMP i, 10
3. JGE 점프 뛸 주소가 미결정 된 상태
4. INC i
5. ASSIGN j, 0
6. CMP j, 10
7. JGE 점프 뛸 주소가 미결정 된 상태
8. INC j
이렇게 주소가 생성 될 수 있을것이다.(본인이 이렇게 설명하는 이유는 파싱해 나가면서 바로 중간코드를 계속 생성했기 떄문이다.)
대충 저런식이다 하지만 어셈블러를 조금 하는 유저라면 저건 잘못된 포 루프 소스 라는것을 알 수 있다.
그래서 나는 중간에 끼워넣는 방식을 택했다.
소스를 기재해보면
1. ASSIGN i, 0
2. CMP i, 10
3. JGE FOR_카운트넘버_END (레이블명으로 점프주소 해결)
4. INC i
여기까지 순서대로 파싱한다면 생성이 가능하다.
그 이후 새로운 포 안의 문장이 나타나게 된다면
4번의 라인에 순서대로 끼워넣는다.
그러면
1. ASSIGN i, 0
2. LABEL FOR_1_START
2. CMP i, 10
3. JGE FOR_1_END (레이블명으로 점프주소 해결)
5. ASSIGN j, 0
6. LABEL FOR_2_START
6. CMP j, 10
7. JGE FOR_2_END
8. INC c
9. INC j
10. JMP FOR_2_START
11. LABEL FOR2_2_END
12. INC i
13. JMP FOR_1_START
14. LABEL FOR_1_END
위와같은 코드로 중간코드 생성식이 바뀐다.
물론 변수의 경우도 변수 테이블인덱스로 표기하지만, 그런건 구조체의 속성타입을 표기해줌으로써 처리가 가능하므로 개념적인 면으로 설명한다.
i++과 같은 식이 잡히는순간 레이블 생성식을 같이 중간코드에 생성시키기고 INC i의 라인넘버를 기억하고 있다가 그 위치에 끼워넣으면 된다...(간단하지만 귀찮다..)
그러면 백 페칭같은 기법을 사용하지 않고도 점프뛸 주소를 결정 지을 수 있다.
레이블명이 적힌 곳의 라인넘버를 찾으면 되기 떄문이다.
같은 방법으로 WHILE로 해결하면 똑같이 해결된다..(의외로 단순하다....)
어찌보면 이러한 방법은 정석적인 방법은 아니다.
책에서도 위와 유사한 기법을 소개는 하고있다..레이블명을 생성하여 처리하는 방법이나...내껀...조금 자신만의 스타일로 꼼수비슷하게 해결한 케이스라고 생각한다..
하지만....중간코드 생성에 대한 정보가 워낙 적어서,, 혼자만의 세상에서 고민하다 만들어낸 방법이므로
맞다, 틀리다라고 말할 순 없지만, 결과적으로 잘 돌아가므로 만족하는 방식이다.
펑션 콜을 할때는 인자를 넣어줘야 하는데 이는 역시 어셈과 비슷하게 푸시명령을 통해 해결하였다.
가령 int sum(int a, int b)와 같은 꼴의 펑션을 콜 한다면 sum(1, 10)이라고 가정해보면
push 1
push 10
call sum
이런식이다.
이러면 코드제너레이터는 이 푸시의 순서를 다시 뒤집어서 어셈블리어 코드로 제너레이션하는 방식이다.
문득 야밤에 내가 참여한 ncc텀에 대한 기억이 떠올라 가장 고민했던 부분에 대한 기록을 남긴다... 언젠가 이 경험이 토대가 되어, 스크립트 엔진의 베이스 코드가 될것이다...
가상변수, 간단한 스크립트를 통한 가상변수 제어, 미리 등록된 함수에 대한 콜의 지원등을 위한 스크립트 엔진 구상은 대충 끝났고..구현만 하면되는데...회사 입사한 이후에.......천천히 진행할 것이다...
심볼 테이블매니저 클래스의 경우 사실상 이틀정도 만에 구현이 다 끝났다.
심볼테이블 매니저 구성자체가 어려운건 아니기 떄문이다.
대신 중간코드 생성에서 한동안 고생을 했다...
그 이후 코드제너레이션 하는 부분은 의외로 빨리 끝났다.
3일정도..
3일만에 내가생성한 중간코드로, 어셈블링이 가능한 어셈블리어 코드를 생성해 냈으니...굉장히 신기했다...
결국 최종적으로 MASM 6.15와 LINKER를 통해 EXE파일을 생성해 냈다.
물론 PE binary... Microsoft Platform에서 돌아간다
최종적으로 우리의 컴파일러를 만들기 위해 gcc컴파일러와 g++컴파일러, STL Vector라이브러리를 이용했다;
최종 소스는 공개하고 싶지만....의외로 꽤 돌아가기도 하고, 텀 프로젝트 제출로 악용될수 있어 공개는 하지않는다. 다음포스팅때는 간단한 옵티마이제이션 부분이랑 코드제너레이션의 부분으로 설명하겠다..
마지막 학기의 열정을 제대로 쏟아부었던..(좀 뒤늦게 필 받았지만...) 컴파일러 텀 프로젝트....학부생활의 마지막 추억이다.... 같이 숱하게 새벽작업하며 밤샌 쩌로 킴..ㅎㅎㅎ
수많은 학우들이 매크로 어셈블러로 exe파일을 만들겠다고 해서 움찔했는데....괜히 쫄았었다...
인텔 어셈블리어를 접해본적이 없는 사람이 대부분인지라...다들 코드제너레이션까진 제대로 가지도 못했으니.... 덕분에 진도가 훅 나갔지만....;; 기회가 된다면 못다한 포인터와, MALLOC과 같은 것을 해보고싶다....차후에???..................심플 커널이랑, 게임프로젝트, 아이폰 버스 프로젝트 등한 후에..;
4-2학기
2009. 9. 28. 06:56
LEX, YACC을 이용하여 Parse Tree를 생성한 모습이다.
숱하게 삽질했다.......
어쨋든 어느정도 내가 만족할만한 수준으로 출력이 되는것을 확인했다.
ncurses라이브러리를 이용하여 출력하려 했으나, 좀 먼가 내키지 않아
터미널 화면을 컨트롤 하는 명령을 이용하여 약간의 잔재주를 부렸다.
약간 비겁한 방법이지만 스택을 이용하여 역 추적해가면서 자신의 parent를 찾는 방법을
택하였다.
뭐 구현이 되었으니.....만족한다.
며칠간 삽질하던끝에 어느 이른아침....완성하며.........am 6:55