컴파일러와 인터프리터

HandyPost는 한 도영(HDNua)이 작성하는 포스트 문서입니다.


github: https://github.com/HDNua/JSCC


문서: 

03. 컴파일러와 인터프리터.pdf

 

1. 개요

컴파일러와 인터프리터의 개념, 기계어와 어셈블리에 대해 간단히 공부하고, 컴파일러와 인터프리터의 차이를 올바르게 이해하여 후에 우리가 작성할 프로그램이 어떠한 것인지를 분명하게 정의한다.

 

2. 상식

컴퓨터가 처음에 등장했을 때는 모든 것을 오로지 01로만 표현했다. 처음에 필자가 이 말을 들었을 때 필자는 01로만 프로그래밍을 해본 경험이 없었기 때문에, 사실 이 말은 그렇게 와 닿지 않았다. 01로 표현했다고 하는데 도대체 뭘 어떻게 했다는 건지 적절한 예시가 없기 때문이었다. 사실 초보자나 비전공자에게 01로 컴퓨터를 만들었다는 것 이상을 설명하면 벙찐 표정으로 고개만 끄덕이고 있을 게 분명하므로 설명해봐야 소용이 없는 일이긴 하다. 하지만 우리는 이제 나름 컴파일러를 만든다는 사람, 즉 작성한 소스 코드를 기계어로 번역하는 프로그램을 개발하는 사람이다. 따라서 우리가 이것을 모른다는 건 말이 안 되는 것 같다. 이 문서에서는 컴퓨터의 개론적인 부분을 다루어 실제로 기계어가 무엇이며, 이것으로 어떻게 컴퓨터를 만들 수 있다는 건지에 대한 단서를 제공할 것이다. (컴퓨터는 알다시피 아주 복잡한 기계이므로, 필자 수준의 지식에서 온전하게 설명하기 힘들다) 이야기를 시작하기 전에 먼저, 프로그래머라면 상식적으로 알고 있어야 하는 내용을 정리하는 시간을 가지는 것이 좋겠다.

2.1) 컴파일 & 링크 & 빌드

초창기의 컴퓨터는 기계어로 프로그래밍을 했다. 그러나 기계어는 사람이 이해하기 아주 어려워서, 이를 보다 편하게 사용하기 위해 이런 방법을 생각했다.

- 기계어의 집합을 더 간단하게 표현하는 텍스트 문서를 만든다. 예를 들어 C는 긴 코드를 간단하게 표현하기 위해 함수나 매크로(macro)를 사용할 수 있는데, 기계어로 10줄짜리의 코드를 매크로 A로 정의하고 문서에는 A만 써넣는 경우를 생각하자.

- 이 텍스트 문서를 기계어로 자동 번역하는 프로그램 A를 만든다.

- 텍스트 문서를 프로그램 A를 이용하여 기계어로 자동 번역한다. 이 프로그램을 실행하면 위에서 예시로 작성한 문서의 A가 기계어 10줄로 번역된다.

이렇게 하면 필요할 때마다 텍스트 문서만 수정하여 프로그램을 간단하게 만들 수 있다. 위 내용은 사실 순서가 이상한데, 다시 한 번 순서를 맞춰보자.

- 일정한 형식으로 작성된 문서를 기계어로 자동 번역하는 프로그램 A를 먼저 만든다.

- 이후에 프로그램을 만들 때마다 A가 번역할 수 있도록 일정한 형식으로 문서를 작성한다.

- 문서 작성이 완료되면 프로그램 A를 실행하고 파일을 넘겨서, A가 자동으로 번역해준 기계어 파일을 얻게 된다.

그리고 바로 여기서 사용되는 프로그램 A컴파일러(compiler)라고 하고, 이때 작성한 일정한 형식의 컴퓨터 명령을 소스 코드(source code), 소스 코드가 저장된 텍스트 파일을 소스 코드 파일(source code file) 또는 간단히 소스 파일(source file), 그리고 이를 번역하는 행위를 컴파일(compile)이라고 한다.

컴퓨터가 발전하고 작성하는 소스 코드의 양이 늘어남에 따라, 한 파일에 모든 소스 코드를 작성하는 방식이 불편하다는 것을 깨닫게 되었다. 사람들은 소스 코드를 다른 파일에 분리하는 방법을 생각해냈다. 원래 하나였던 파일을 분리했으므로, 프로그램을 완성하려면 분리했던 파일은 모두 연결해야 한다. 이렇듯 분리된 파일을 모아 하나의 실행 가능한 파일을 만들면 이를 두고 파일들을 링크(link)했다고 하고, 이때 사용되는 프로그램을 링커(linker)라고 한다.

종합하면, 우리는 기계어를 이용하지 않고 실행 파일을 생성하기 위해 다음의 순서를 거친다.

- 소스 코드를 작성하고 파일로 저장한다.

- 저장한 소스 파일을 컴파일러를 이용하여 컴파일 한다. 목적 파일이 생성된다.

- 컴파일러가 생성한 목적 파일들을 링커를 이용하여 링크 한다. 실행 가능한 목적 파일이 생성된다.

링커는 실행 가능한 목적파일을 생성한다. 컴파일러가 생성하는 파일과 링커가 생성하는 파일의 차이는 생성한 목적 파일이 실행 가능 하느냐에 있다.

컴파일과 링크 과정을 합쳐 빌드(build)라고 하고, 이때 사용되는 프로그램을 빌더(builder)라고 한다.

2.2) 메모리

우리가 C 이상의 고급 언어를 사용할 때는 변수가 정의되는 위치를 별도로 고려하지 않는다. 당연한 말이지만 이는 원래부터 그렇게 프로그래밍이 가능했던 것이 아니다. 메모리는 바이트의 집합이고 변수를 사용하려면 빈 바이트를 찾아서 정의하려는 변수의 크기만큼을 메모리에서 확보하는 작업을 거쳐야 한다. 이에 대해 자세히 알아보자.

프로그램을 실행하면 해당 프로그램을 위한 메모리 공간을 운영체제가 마련해준다. 프로그램 내부의 지역 변수, 전역 변수, 문자열 상수와 같은 데이터는 모두 이 메모리 공간 내에서 정의되고 사용된다. 이 메모리 공간은 크게 네 가지의 영역으로 구분할 수 있는데 각각 다음과 같다.

- 코드 영역(code area): 실행할 프로그램의 기계어 명령이 올라오는 메모리 영역이다.

- 데이터 영역(data area): 정적 변수 및 전역 변수, 문자열 상수 등 프로그램 실행 시에 정의되고 프로그램이 종료될 때 해제되는 데이터를 저장하는 영역이다.

- 힙 영역(heap area): 동적 할당한 데이터를 저장하는 영역이다.

- 스택 영역(stack area): 지역 변수 등 임시적으로 사용되는 데이터를 저장하는 영역이다.

이 정도로 다음 내용을 진행하기 위한 상식들을 정리할 수 있었다.

2.3) 중간 단계 언어

먼저 생각해보자. C는 익히 알고 있듯이 기계어보다 사람이 이해하기 쉬운 고급 언어다. 또한 우리는 C를 이용하여 작성한 소스 코드를 실행 가능한 파일로 만들기 위해 컴파일 과정을 거쳐야 한다. 그렇다면 우리가 작성한 소스 코드와 기계어 사이에 중간 단계의 언어가 있어서, 우리의 소스 코드가 이 중간 단계의 언어로 먼저 번역된 다음, 번역된 중간 단계의 언어가 기계어로 번역되는 상황도 생각할 수 있다. 번역할 거면 바로 번역하지 왜 가운데 단계가 하나 더 들어가느냐고 묻는다면, 사실 생각대로 없어도 된다(없는 것이 당연히 번역이 더 빠르게 된다). 그러나 이것이 문제되는 이유 첫 번째는 기계어에 대해 우리가 아는 것이 하나도 없다는 점이고, 기계어를 안다손 쳐도 소스 코드를 하나하나 기계어로 번역하는 과정은 무지하게 헷갈린다는 점이다. 둘째는 C 이외의 다른 언어에 대한 컴파일러 B를 새롭게 개발하는 상황이 왔을 때 이 과정에서 사용한 중간 단계 언어 번역기를 그대로 사용할 수 있다는 이점이 있기 때문이고, 셋째는 기계어는 기계마다 그 내용이 다르기 때문에 기계가 바뀔 때마다 해당 기계에 맞는 기계어로 번역해야 하는데, 중간 단계 언어 번역기가 도입되면 이 과정이 아주 단순해지기 때문이다. 다음 이미지를 보면 이에 대해 이해할 수 있다.



이는 여기서만 사용되는 기술이 아니다. Java 프로그래밍 언어는 JVM이라는 가상 머신에서 실행되기 전에 중간 단계 언어인 자바 바이트 코드로 변환된다. C# 프로그래밍 언어는 IL이라는 중간 단계 언어로 컴파일 된다. 이제 여러분도 중간 단계 언어가 필요하다는 사실을 받아들일 수 있을 것이다.

 

3. 인터프리터(interpreter)

인터프리터(interpreter)란 컴파일 과정을 거치지 않고 소스 코드를 바로 해석하여 결과를 출력하는, 소스 코드 실행기 프로그램을 말한다. 컴파일러와 많은 부분이 공통적이지만 차이도 많은데 이에 대해 간단하게 얘기해보자. 먼저 컴파일러는 소스 코드를 기계어로 번역하는 행위를 한다. 이는 인터프리터도 수행하는 작업이다. 컴퓨터에 명령을 내리려면 기계어로 작성해야 하니까. 그런데 컴파일러는 기계어를 번역한 후에 그 즉시 프로그램을 실행하지는 않는다. 반면 인터프리터는 실행기이므로 번역과 분석이 끝나면 프로그램을 실행하여 결과를 바로 내놓는다. 이것이 컴파일러와의 첫 번째 차이다.

다른 점 또 하나는, 컴파일러는 기계어로 번역을 한 후 목적 파일을 생성하는 반면 인터프리터는 그렇지 않다는 점이다. 컴파일 하는 데 시간이 걸리지만, 컴파일이 끝난 프로그램은 완전히 분석된 상태이므로 다시 코드를 분석할 필요 없이 바로 실행할 수 있다는 점 및 최적화가 용이하다는 점, 실행 속도가 빠르다는 점이 장점으로 꼽히며, 이는 곧 인터프리터의 단점도 된다. 인터프리터는 실행 중에 동적으로 소스 코드를 분석하고, 최적화가 어려우며, 실행 중에 매번 분석을 진행하므로 컴파일러로 번역한 프로그램보다 느릴 수밖에 없다. 하지만 인터프리터는 결과를 바로 확인할 수 있다는 점, 컴파일 하는 데 시간이 걸리지 않는다는 점을 장점으로 꼽을 수 있다.

이와 같이 인터프리터에 대해 간단히 알아볼 수 있었다.

 

4. JSCC의 개발 방향

JSCC는 컴파일러와 인터프리터가 결합된 형태로 작성할 것이다. JSCC를 실행하고 작성한 소스 코드 파일을 입력으로 넣으면, JSCC 내부의 컴파일러 모듈(Compiler)이 소스 코드는 필자가 독자적으로 만든 중간 언어로 번역하여 텍스트 형식의 목적 파일에 기록한다. 그렇게 생성한 목적 파일은 다시 JSCC 내부의 링커 모듈(Linker), 생성된 목적 파일을 모아 실행 가능한 목적 파일을 새롭게 생성한다. 그리고 최종적으로 JSCC 내부의 실행기 모듈(Runner)이 링커가 생성한 실행 가능한 목적 파일을 가상머신처럼 실행하여 결과를 화면에 출력한다.

이와 같이 JSCC의 개발 방향에 대해 살펴볼 수 있었다.

 

5. 단원 마무리

이전에 공부한 내용에 비해 아주 짧은 내용을 공부했다(1장의 소개 글보다도 짧다!). 이는 2주 만에 60쪽 가까이를 공부한 여러분에게 내용을 다시 한 번 되짚어볼 기회를 주는 것이 좋겠다고 생각한 필자의 판단이다(사실 이게 원피스 같은 만화도 아니고 올라오면 바로바로 챙겨봐야 할 이유는 전혀 없지만). 다음에 배울 내용은 CIL이라고 하여 필자가 기계어에 더 적응하기 쉽도록 C를 이용하여 고안한 기계어와 C의 중간 언어인데, 이를 공부하면 어셈블리 언어는 차이점을 배우는 정도로 단순하게 공부할 수 있으리라 생각한다.

'알려주기' 카테고리의 다른 글

[JSCC] 5. NASM 어셈블리 언어  (0) 2015.05.29
[JSCC] 4. CIL 어셈블리 언어  (0) 2015.05.25
[JSCC] 2. C의 선언  (0) 2015.05.25
[JSCC] 1. 스택과 계산기  (0) 2015.05.25
[JSCC] JSCC: JavaScript로 개발하는 C Compiler  (16) 2015.05.25
Posted by 누아니
,

[JSCC] 2. C의 선언

알려주기 2015. 5. 25. 15:08

github 페이지를 만들었습니다.

github: https://github.com/HDNua/JSCC


-----


C의 선언

HandyPost는 한 도영(HDNua)이 작성하는 포스트 문서입니다.


소스: 

02_cdecl.zip



문서: 

02. C의 선언.pdf


 

1. 개요

C에서 가장 자주 사용되는 선언을 복습하고, 이것이 특정한 규칙에 의해 정의되는 것임을 올바르게 학습하여 C 프로그래밍 언어의 선언에 대해 보다 본질적으로 이해하고, 계산기 프로젝트와 결합하여 변수를 정의하고 연산이 가능하게 할 수 있음을 보인다.

 

2. 기본적인 선언

C 컴파일러를 만들려는 우리인 만큼 C에서 변수 및 함수를 정의하는 형태는 모두 알고 있을 것이라고 생각한다. 아래 예제를 올바르게 이해하고 활용할 수 있는 정도라면 된다.

01_c_declarations.cpp

#include <iostream>

using namespace std;

// 함수의 선언

int sum(int a, int b);

int mul(int a, int b);

int main(void) {

// int형 변수의 선언과 사용

int int_var;

int_var = 10;

cout << "변수: " << int_var << endl;

// int형 변수의 배열의 선언과 사용

int int_arr[3];

int_arr[0] = 5, int_arr[1] = 2, int_arr[2] = 3;

cout << "배열: ";

for (int i = 0; i < 3; ++i)

cout << int_arr[i] << ' ';

cout << endl;

// int형 포인터 변수의 선언과 사용

int *int_ptr;

int_ptr = &int_var;

*int_ptr = 20;

cout << "포인터: " << *int_ptr << endl;

// int형 변수의 2차원 배열의 선언과 사용

int int_arr2d[2][3] = { // 23열의 행렬로 생각하면 편하다

{ 1, 2, 3 },

{ 4, 5, 6 }

};

cout << "2차원 배열: " << endl;

for (int r = 0; r < 2; ++r){

for (int c = 0; c < 3; ++c) {

cout << int_arr2d[r][c] << ' ';

}

cout << endl;

}

// int형 포인터 변수에 대한 포인터 변수

// int형 더블 포인터의 선언과 사용

int **dptr = &int_ptr;

**dptr = 30;

cout << "더블 포인터: " << **dptr << endl;

// int형 변수 두 개를 인자로 받고

// int형 값을 반환하는 함수에 대한 포인터 선언

int(*fptr)(int, int);

fptr = sum;

cout << "fptr = sum; fptr(3, 5): " << fptr(3, 5) << endl;

fptr = mul;

cout << "fptr = mul; fptr(3, 5): " << fptr(3, 5) << endl;

return 0;

}

int sum(int a, int b) { return a + b; }

int mul(int a, int b) { return a * b; }

필자가 공부했던 책에서는 포인터의 배열과 배열에 대한 포인터와 같은 내용도 가르쳤으나, 이에 대해서는 바로 다음에 C 프로그래밍 언어의 선언 방식을 설명하면 이해할 수 있는 내용이므로 먼저 알고 있을 필요는 없다.

 

3) 복잡한 선언

3.1) typedef

typedef 키워드는 형식을 정의하는 데 사용된다. 다음은 typedef를 사용하는 예제이다.

02_typedef.cpp

#include <iostream>

using namespace std;

int sum(int a, int b) { return a + b; }

int mul(int a, int b) { return a * b; }

int main(void) {

// Dataint 형식으로 정의한다

typedef int Data;

Data data = 10;

cout << "변수: " << data << endl;

// DataPtrData에 대한 포인터 형식으로 정의한다

typedef Data *DataPtr;

DataPtr data_ptr = &data;

cout << "포인터: " << *data_ptr << endl;

// DataArr를 크기 3Data 변수의 배열 형식으로 정의한다

typedef Data DataArr[5];

DataArr data_arr = { 1, 2, 3 };

cout << "배열: ";

for (int i = 0; i < 3; ++i) cout << data_arr[i] << ' ';

cout << endl;

// FuncPtr(int, int)과 같이 인자를 받고

// int형 값을 반환하는 함수에 대한 포인터 형식으로 정의한다

typedef int(*FuncPtr)(int, int);

FuncPtr fp = sum;

cout << "fp(3, 5): " << fp(3, 5) << endl;

fp = mul;

cout << "fp(3, 5): " << fp(3, 5) << endl;

return 0;

}

typedef 키워드를 함수 내부에서 사용할 수 있다는 사실에서부터 놀랐을 수도 있다. 이후에도 설명할 것이지만 사실 typedef 키워드는 extern 키워드와 같은 선언의 요소이며 typedef로 정의된 문장 또한 선언의 일종이다. typedef 뒤에는 반드시 선언이 따라온다. 후에 복잡한 선언을 분석하면서 이에 대해 논의할 것이다. 참고로 위 예제는 C++ 언어로 작성되었지만, C언어에서도 이 내용은 성립하며, 방금 말했듯 typedef로 작성된 문장은 선언문이므로 함수 내부에서 사용할 때 코드 중간에 넣으면 컴파일 시에 오류가 발생한다(C에서 선언은 반드시 함수의 위 부분에 있어야 한다).

typedef가 무엇인지 알고 있으니, typedef를 이용해 다음 문장들을 선언해보라. 반드시 한 문장에 정리할 필요는 없고, 여러 개의 typedef 문장을 사용해도 좋다.

- integerint 형식의 변수입니다.

- characterchar 형식의 변수입니다.

- intPtrint형 변수에 대한 포인터 변수입니다.

- intArr는 크기가 5int형 변수의 배열입니다.

- intFuncIntCharInt(int, char, int) 형식으로 인자를 받고 int형 값을 반환하는 함수입니다.

답은 다음과 같다.

int integer;

char character;

int *intPtr;

int intArr[5];

int intFuncIntCharInt(int, char, int);

이 문제는 너무 쉽다고 느꼈을 수 있다. 그렇다면 다음을 해결해보라. 당연히 typedef를 이용한다.

- intArrArr((int형 변수 3개의 배열) 2개의 배열)입니다.

- intPtrArr((int형 변수에 대한 포인터 변수) 5개의 배열)입니다.

- intArrPtr((int형 변수 4개의 배열)에 대한 포인터 변수)입니다.

- intFuncComp((((int, int) 형식으로 인자를 받고 int형 값을 반환하는 함수)에 대한 포인터)를 인자로 받고 int형 값을 반환하는 함수)입니다.

답은 다음과 같다.

typedef int intArr3[3];

intArr3 intArrArr[2];

typedef int *intPtr;

intPtr intPtrArr[5];

typedef int intArr4[4];

intArr4 *intArrPtr;

typedef int (*Comp)(int, int);

int intFuncComp(Comp comp);

이 문제도 해결했다면 더 복잡한 다음 문제를 보자.

- qsort는 다음과 같은 함수입니다.

> 반환형: 값을 반환하지 않습니다.

> 첫 번째 인자 basevoid형 포인터 변수입니다.

> 두 번째 인자 nelemunsigned형 변수입니다.

> 세 번째 인자 widthunsigned형 변수입니다.

> 네 번째 인자 fcmp는 다음과 같은 함수에 대한 포인터 변수입니다.

>> 반환형: int형 값입니다.

>> 첫 번째 인자와 두 번째 인자는 모두 const void형 포인터 변수입니다.

- signal은 다음과 같은 함수입니다.

> 반환형: int형 변수를 인자로 받고 void형 포인터 값을 반환하는 함수에 대한 포인터입니다.

> 첫 번째 인자 signal_numberint형 변수입니다.

> 두 번째 인자 signal_handlerint형 변수를 인자로 받고 void형 포인터 값을 반환하는 함수에 대한 포인터입니다.

답은 다음과 같다.

typedef const void *CVP;

typedef int Compare(CVP, CVP);

void qsort(void *base, unsigned nelem, unsigned width, Compare fcmp);

typedef void (*SignalHandler)(int);

SignalHandler signal(int signal_number, SignalHandler signal_handler);

사실 이렇게 끔찍한 코드가 필요한 일은 거의 없지만, 이해하는 것은 필요하다. 무엇보다 컴파일러를 만들려는 우리인 만큼 선언이 어떤 의미를 가지고 있는지는 명확하게 이해하고 있는 것이 이치에 맞다.

그런데 사실 typedef는 선언을 위해 반드시 필요한 키워드는 아니다. typedef를 이용한 선언은 typedef 키워드가 없이도 얼마든지 가능하다. 즉 우리는 위 예제에서 모든 typedef 키워드를 없애고도 제시하는 선언을 만들어낼 수 있다. 그것이 어떻게 가능할까? 물론 signal도 가능한데, 이는 어떻게 선언해야 하는가?

 

3.2) 선언 분석의 규칙

C의 선언은 다음을 규칙으로 한다.

- 이름을 기준으로 한다.

- 이름의 오른쪽부터 해석한다. 오른쪽의 해석이 끝나면 왼쪽을 해석한다.

- 이름에 가까운 괄호부터 먼저 해석한다.

이 세 가지 규칙만으로 C의 모든 선언을 분석할 수 있다. 다음 예제들을 보자.

int var; // var: int

이름은 var이다. 이름의 오른쪽에 요소가 없으므로 왼쪽 분석을 진행한다. 다른 요소가 없으므로 분석이 끝난다. varint.

int arr[5]; // arr: array[5] of int

이름은 arr이다. 이름의 오른쪽에 있는 배열 기호를 획득한다. 이름의 오른쪽에 더 이상 요소가 없으므로 왼쪽 분석을 진행한다. 다른 요소가 없으므로 분석이 끝난다. arrarray[5] of int, 즉 크기가 5int형 배열이다.

int *ptr; // ptr: pointer to int

이름은 ptr이다. 이름의 오른쪽에 요소가 없으므로 왼쪽 분석을 진행한다. 왼쪽에 있는 포인터 기호를 획득한다. 다른 요소가 없으므로 분석이 끝난다. ptrpointer to int, int형 변수에 대한 포인터 변수다.

int arr2d[3][5]; // arr2d: array[3] of array[5] of int

이름은 arr2d이다. 이름의 오른쪽에 있는 배열 기호를 차례로 획득한다. 오른쪽 분석이 끝나고 왼쪽을 분석하는데, 왼쪽에 남은 요소가 없으므로 분석이 끝난다. arr2darray[3] of array[5] of int, ((int형 변수 5개의 배열) 3개의 배열)이다. 이 부분이 혼란스러울 수 있는데 typedef를 이용하여 다음과 같이 정의된 것이라고 이해하면 될 것이다.

typedef int intArr5[5];

intArr5 arr2d[3];

int *ptrarr[5]; // ptrarr: array[5] of pointer to int

이름은 ptrarr이다. 이름의 오른쪽에 있는 배열 기호를 획득한다. 오른쪽 분석이 끝나고 왼쪽을 분석한다. 왼쪽에 있는 포인터 기호를 획득한다. 다른 요소가 없으므로 분석이 끝난다. ptrarrarray[5] of pointer to int, ((int형 포인터 변수) 5개의 배열)이다.

int (*arrptr)[5]; // arrptr: pointer to array[5] of int

이름은 arrptr이다. 이름의 오른쪽에 있는 배열 기호를 획득하는데, 괄호를 먼저 해석해야 하므로 괄호 바깥은 해석하지 않는다. 괄호 안에 있는 건 *arrptr뿐이고 현재 arrptr의 오른쪽에 아무 것도 없으므로 왼쪽 분석을 진행하여 포인터를 먼저 획득한다. 괄호 내에서 분석할 것이 없으므로 괄호를 탈출한다. 그리고 다시 오른쪽부터 분석을 진행한다. 오른쪽에 있는 배열 기호를 획득한다. 남은 요소가 없으므로 분석을 종료한다. arrptrpointer to array[5] of int, ((int형 변수 5개의 배열)에 대한 포인터 변수).

int fnc(); // fnc: function() returning int

이름은 fnc. 이름의 오른쪽에 있는 함수 기호를 획득한다(이때 괄호의 의미는 fnc가 함수라는 것을 나타내는 것이지, 선언 분석에서 먼저 분석해야 함을 의미하는 것은 아니다). 오른쪽의 분석이 끝났으므로 왼쪽을 분석하는데 왼쪽에 요소가 없으므로 분석이 끝는다. fncfunction() returning int, int형 값을 반환하는 함수다.

아래에 제시되는 것은 올바른 분석 방법을 설명하기 위한 적법한 선언이지만, 실제로는 C의 특수성 등과 같은 이유로 컴파일러가 정상적으로 해석할 수 없는 선언문이 섞여있다.

int arr_fnc()[5]; // arr_fnc: function() returning array[5] of int

이름은 arr_fnc이다. 이름의 오른쪽에 있는 기호를 차례로 획득하므로, 함수 기호를 획득하고 배열 기호를 나중에 획득하게 된다. 오른쪽의 분석이 끝났는데 왼쪽에 아무 것도 없으므로 분석이 끝난다. arr_fncfunction() returning array[5] of int, (int형 변수 5개의 배열)을 반환하는 함수다. (실제로 적용할 수 없음)

int *ptrarr_fnc()[5]; // ptrarr_fnc: function() returning array[5] of pointer to int

이름은 ptrarr_fnc이다. 이름의 오른쪽에 있는 기호를 차례로 획득하므로, 함수 기호를 획득하고 배열 기호를 나중에 획득하게 된다. 오른쪽의 분석이 끝났으므로 왼쪽을 분석하여 포인터 기호를 획득한다. ptrarr_fncfunction() returning array[5] of pointer to int, ((int형 변수에 대한 포인터 변수) 5개의 배열)을 반환하는 함수다. (실제로 적용할 수 없음)

int (*arr_fncptr)()[5]; // arr_fncptr: pointer to function() returning array[5] of int

이름은 arr_fncptr이다. 이름의 오른쪽에 있는 기호를 차례로 획득하는데 괄호를 먼저 해석해야 한다. 괄호 내에는 오른쪽에 요소가 없으므로 왼쪽을 진행하여 포인터 기호를 획득한 후 괄호를 탈출한다. 이후 다시 오른쪽에 있는 함수 기호와 배열 기호를 차례로 획득하고 분석이 끝난다. arr_fncptrpointer to function() returning array[5] of int, ((int형 변수 5개의 배열)을 반환하는 함수)에 대한 포인터다. (실제로 적용할 수 없음)

int (*arrptr_fnc())[5]; // arrptr_fnc: function() returning pointer to array[5] of int

이름은 arrptr_fnc이다. 이름의 오른쪽에 있는 기호를 차례로 획득하는데 괄호를 먼저 해석해야 한다. 괄호 내에 함수 기호가 있으므로 먼저 획득한 후, 왼쪽에서 포인터 기호를 획득하고 괄호를 탈출한다. 이후 다시 오른쪽에 있는 배열 기호를 획득하고 분석이 끝난다. arrptr_fncfunction() returning pointer to array[5] of int, ((int형 변수 5개의 배열)에 대한 포인터)를 반환하는 함수다. 위의 예제와 달리 이 선언은 실제로 적법한 선언인데 그 이유는 나중에 밝히겠다.

char (*(*x[3])())[5]; // x: array[3] of pointer to function() returning pointer to array[5] of char

이름은 x. 이름의 오른쪽에 있는 배열 기호를 획득하고 포인터 기호를 획득한 후 괄호를 탈출한다. 이후 남은 부분에 대해 다시 괄호 내의 기호를 해석하여 함수 기호를 얻고 포인터 기호를 획득한 후 괄호를 탈출한다. 이후 오른쪽의 배열 기호를 획득하면 남는 요소가 없으므로 분석이 끝난다. xarray[3] of pointer to function() returning pointer to array[5] of char. 아주 길지만 정리해서 말하면, x((((char형 변수 5개의 배열)에 대한 포인터)를 반환하는 함수)에 대한 포인터) 3개의 배열이다. 놀랍게도 이 선언 또한 적법한데 그 이유는 위와 같다.

 

이 내용을 코드로 정리하면 다음과 같다.

int var; // var: int

int arr[5]; // arr: array[5] of int

int fnc(); // fnc: function() returning int

int *ptr; // ptr: pointer to int

int arr2d[3][5]; // arr2d: array[3] of array[5] of int

int *ptrarr[5]; // ptrarr: array[5] of pointer to int

int (*arrptr)[5]; // arrptr: pointer to array[5] of int

int fnc(); // fnc: function() returning int

int arr_fnc()[5]; // arr_fnc: function() returning array[5] of int

int *ptrarr_fnc()[5]; // ptrarr_fnc: function() returning array[5] of

// pointer to int

int (*arr_fncptr)()[5]; // arr_fncptr: pointer to function() returning

// array[5] of int

int (*arrptr_fnc())[5]; // arrptr_fnc: function() returning pointer to

// array[5] of int

char (*(*x[3])())[5]; // x: array[3] of pointer to function() returning

// pointer to array[5] of char

이와 같이 C의 선언에 대해 이해할 수 있었다.

 

3.3) dcl: C의 선언 분석 프로그램

이제 우리는 C의 선언이 어떠한지 이해했으므로, C의 선언을 분석하는 dcl 프로그램을 작성할 수 있다. 이 예제는 The C Programming Language에 나온 것을 기반으로 작성하는 것이다.

이를 설명하기 전에 몇 가지 중요한 용어를 알려주고 진행하겠다.

- 예약어(keyword): 프로그래밍 언어에서 특정한 용도로 사용되기 때문에 사용자가 임의로 사용할 수 없는 단어를 말한다. int, char와 같은 자료형과 for, if와 같은 반복문, 조건문을 위한 예약어 등이 이에 속한다.

- 식별자(identifier): 개체를 식별하는 데 사용할 수 있는 이름을 의미한다. 변수 이름, 함수 이름, 사용자가 새롭게 정의한 자료형의 이름 등이 있다. C는 식별자라면 지켜야 할 규칙이 있는데, 바로 알파벳, 밑줄(_), 숫자만 가능하며, 첫 글자는 밑줄 또는 알파벳이어야 한다는 것이다.

- 태그(tag): 구조체, 공용체 및 열거 형식과 같은 사용자 정의 자료형을 지칭하는 이름이다. 식별자와 작성하는 규칙은 같지만 식별자와는 다르다. 예를 들어 다음의 문장이 적법한 이유는 태그는 식별자가 아니기 때문에 식별자를 중복으로 정의하는 것이 아니기 때문이다.

struct node node;

다만 이 경우 typedef 키워드를 이용해 node를 정의했다면 이 경우는 식별자로 인정된다.

typedef struct node node;

다음은 dcl 프로젝트를 위한 개념으로, 이 프로그램에서만 그렇다고 납득해야 하는 부분이다.

- 선언문(declaration-statement): 선언을 하는 문장이다. 형식은 다음과 같다.

declaration-statement: <형식(type)> <선언자(declarator)> ;

- 형식(type): 선언할 대상이 자료를 보관하는 방법을 말한다. int, char 등이 여기에 속한다.

선언문은 간단하게 형식과 선언자로 나눌 수 있다.

int var; // 형식: int / 선언자: var

int *ptr; // 형식: int / 선언자: *ptr

int arr[5]; // 형식: int / 선언자: arr[5]

int fnc(); // 형식: int / 선언자: fnc()

const int MAX; // 형식: const int / 선언자: MAX

- 직접 선언자(direct-declarator): 선언을 할 때 사용되는 이름 등 직접적으로 선언을 하는 데 사용되는 단어를 말한다.

- 선언자(declarator): 직접 선언자의 앞에 *가 붙어, 해당 직접 선언자가 포인터임을 나타낸다.

다음은 선언자와 직접 선언자 간의 관계를 나타낸 것이다.

declarator: * direct-declarator (1)

direct-declarator: <이름> (2)

(declarator) (3)

direct-declarator() (4)

direct-declarator[<크기>] (5) (이때 크기는 생략 가능)

사실 이 내용만 가지고는 선언자와 직접 선언자를 이해하기 아주 어렵다. 예를 들어보자. 이 예제에서 선언자를 dcl, 직접 선언자를 dirdcl이라고 간단하게 표기하겠다.

(*pfa[])()

pfa는 이름이므로 dirdcl이다. pfadirdcl이므로 pfa[] 또한 dirdcl이다. (5)에 의해 dirdcl[] 또한 정의에 의해 dirdcl이기 때문이다. *pfa[]pfa[]dirdcl이므로 (1)에 의해 dcl이다. (*pfa[])(3)에 의해, *pfa[]dcl이므로 dirdcl이 되고, (*pfa[])()dirdcl()의 꼴이므로 (4)에 의해 dirdcl이다.

여기서 완전하게 이해하지 못했다고 하더라도 일단은 진행할 수 있으니, 이제 dcl 프로그램을 만들어보자. 입력에 대해 다음과 같이 출력이 나오는 것이 목표다. 테스트의 편의를 위해 무한히 반복하다가, 입력으로 세미콜론이 처음 문자로 들어오면 종료하도록 하자.

입력

출력

int var;

int arr[];

int *ptr;

int arr2d[][];

int *ptrarr[];

int (*arrptr)[];

int fnc();

int arr_fnc()[];

int *ptrarr_fnc()[];

int (*arr_fncptr)()[];

int (*arrptr_fnc())[];

char (*(*x[])())[];

;

var: int

arr: array of int

ptr: pointer to int

arr2d: array of array of int

ptrarr: array of pointer to int

arrptr: pointer to array of int

fnc: function returning int

arr_fnc: function returning array of int

ptrarr_fnc: function returning array of pointer to int

arr_fncptr: pointer to function return- ing array of int

arrptr_fnc: function returning pointer to array of int

x: array of pointer to function return- ing pointer to array of char

다음은 필자의 dcl 구현이다. 먼저 main을 보자.

03_dcl_main.cpp

// 식별자로 가능한 문자인지 확인합니다.

bool is_namch(char ch) { // 식별자 문자라면 참입니다.

return is_alnum(ch) || (ch == '_');

}

bool is_fnamch(char ch) { // 첫 식별자 문자라면 참입니다.

return is_alpha(ch) || (ch == '_');

}

// 형식을 획득하여 문자열로 반환합니다.

std::string get_type(StringBuffer &buffer_input);

// 선언자를 분석하고 결과를 출력합니다.

void dcl(StringBuffer &buffer_input);

// 직접 선언자를 분석하고 결과를 출력합니다.

void dirdcl(StringBuffer &buffer_input);

int main(void) {

try {

const int MAX_INPUT_SIZ = 256;

char input[MAX_INPUT_SIZ];

while (true) {

// 입력을 받고 버퍼를 초기화한다

std::cin.getline(input, MAX_INPUT_SIZ);

if (input[0] == ';') {

break;

}

StringBuffer buffer(input);

// 형식을 획득한다

std::string type = get_type(buffer);

while (is_space(buffer.peekc())) { // 형식과 선언자 사이의 공백을

buffer.getc(); // 무시하고 포인터를 선언자 앞으로 옮긴다

}

// 선언자를 분석한다

dcl(buffer);

if (buffer.peekc() != ';') // 문장 종료 기호가 없으면 예외

throw Exception("문장 종료 기호가 없습니다.");

std::cout << type.c_str() << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

ptr에 대해 프로그램은 다음과 같이 진행된다.

코드

버퍼 상태

출력

StringBuffer(input)

int *ptr;

 

get_type(buffer)

*ptr;

 

while (is_space(...)) ...

*ptr;

 

dcl(buffer)

;

ptr: pointer to

if (peekc() != ';') ...

;

ptr: pointer to

cout<<type

;

ptr: pointer to int

이 정도로 main 함수는 간단하게 이해할 수 있다. get_type과 공백을 제거하는 부분은 독자 스스로도 구현할 수 있을 정도로 어렵지 않다. 그러면 이제 정말 중요한 dcl 함수를 살펴보자.

03_dcl_main.cpp

void dcl(StringBuffer &bin) { // 선언자를 분석하고 결과 출력

// declarator: * direct-declarator (1) *을 분석한다

int pointer_count = 0;

char ch;

while (bin.is_empty() == false) { // 버퍼에 문자가 남아있는 동안

ch = bin.getc(); // 문자를 획득하고 확인한다

if (ch == '*') { // *라면 그만큼 포인터를 출력하기 위해

++pointer_count; // 카운터를 증가시킨다

}

else { // *가 아니라면 포인터를 되돌리고 탈출한다

bin.ungetc();

break;

}

}

// declarator: * direct-declarator (2) direct-declarator를 분석한다

dirdcl(bin); // *을 모두 획득했으므로 직접 선언자를 분석한다

while (pointer_count > 0) { // 선언자의 분석이 오른쪽에서 먼저 진행되므로

std::cout << "pointer to "; // 왼쪽에서 획득한 기호를 오른쪽의 분석이

--pointer_count; // 종료된 후에 출력해야 한다

}

}

선언자의 정의 그대로 코드로 옮긴 것이다 주석도 있으니 노력하면 이해할 수 있다.

dcl의 내부를 알았으니 예를 들어보자. ptr에 대해 이 함수는 다음과 같이 진행된다.

코드

버퍼 상태

출력

dcl(StringBuffer &)

*ptr;

 

while (c == '*') ...

ptr;

 

dirdcl(bin)

;

ptr:

while (pc > 0) ...

;

ptr: pointer to

arr에 대해서는 다음과 같이 진행된다.

코드

버퍼 상태

출력

dcl(StringBuffer &)

arr[];

 

while (c == '*') ...

arr[];

 

dirdcl(bin)

;

arr: array of

while (pc > 0) ...

;

arr: array of

이제 마지막으로 dirdcl의 내부를 보자.

03_dcl_main.cpp

void dirdcl(StringBuffer &bin) { // 직접 선언자를 분석하고 결과 출력

char ch = bin.peekc();

if (is_fnamch(ch)) { // direct-declarator: 이름 (2)

std::string identifier = "";

while (bin.is_empty() == false) {

ch = bin.getc();

if (is_namch(ch) == false) {

bin.ungetc();

break;

}

identifier += ch;

}

if (identifier.empty()) // 식별자에 추가된 문자가 없다면 예외

throw Exception("올바른 식별자 이름이 아닙니다.");

std::cout << identifier.c_str() << ": ";

}

else if (ch == '(') { // direct-declarator: (declarator) (3)

bin.getc(); // ( 문자를 해석해서 진입했으므로 다음으로 넘긴다

dcl(bin);

if (bin.peekc() != ')') // 닫는 괄호가 없으면 예외

throw Exception("닫는 괄호가 없습니다.");

bin.getc(); // ) 괄호 검사를 진행했으므로 다음으로 넘긴다

}

// direct-declarator: direct-declarator() (4)

// direct-declarator: direct-declarator[] (5)

while (bin.is_empty() == false) {

ch = bin.peekc();

if (ch == '(') { // 함수 기호 획득

bin.getc(); // ( 괄호를 해석해서 진입했으므로 넘긴다

if (bin.peekc() != ')') // 닫는 괄호가 없으면 예외

throw Exception("잘못된 함수 기호입니다.");

bin.getc(); // ) 괄호를 해석했으므로 다음으로 넘긴다

std::cout << "function returning ";

}

else if (ch == '[') { // 배열 기호 획득

bin.getc(); // [ 괄호를 해석해서 진입했으므로 넘긴다

if (bin.peekc() != ']') // 닫는 괄호가 없으면 예외

throw Exception("잘못된 배열 기호입니다.");

bin.getc(); // ] 괄호를 해석했으므로 다음으로 넘긴다

std::cout << "array of ";

}

else { // 이외의 경우 반복문을 탈출한다

break;

}

}

}

이 함수는 크게 direct-declarator4, 5번 정의를 기준으로 구분할 수 있다. 위는 이름과 괄호, 아래는 함수 기호와 배열 기호에 관한 구문이다. 이제 dcl 프로그램의 모든 구현을 보았으니 다른 선언의 해석이 어떻게 진행되는지를 관찰할 수 있다. arrptr을 예제로 고르자. 편의를 위해 ap라고 하겠다.

코드

버퍼 상태

출력

dcl1 호출

(*ap)[];

 

while (ch == '*') ...

(*ap)[];

 

dirdcl1 호출

(*ap)[];

 

if (ch == '(') 진입

(*ap)[];

 

bin.getc()

*ap)[];

 

dcl2 호출

*ap)[];

 

while (ch == '*') ...

ap)[];

 

dirdcl2 호출

ap)[];

 

if (is_fnamch(ch)) 진입

ap)[];

 

while (is_namch(ch)) ...

)[];

ap:

dirdcl2 종료

)[];

ap:

dcl2) while (pc > 0) ...

)[];

ap: pointer to

dcl2 종료

)[];

ap: pointer to

if (ch != ')') ...

)[];

ap: pointer to

bin.getc()

[];

ap: pointer to

while ("()" || "[]") ...

;

ap: pointer to array of

dirdcl1 종료

;

ap: pointer to array of

dcl1) while (pc > 0) ...

;

ap: pointer to array of

dcl1 종료

;

ap: pointer to array of

코드가 재귀적으로 호출되기 때문에 혼란스러울 수 있으니 주의 깊게 보기 바란다. 다른 모든 예제도 이 방법을 이용하여 출력을 예상할 수 있다. 그러나 원서에도 나와 있지만, 이 프로그램은 완전하지 않다. const와 같은 키워드를 처리할 수 없고, 공백을 잘못 입력했을 때 오작동할 수도 있으며, 함수의 인자에 대해 어떤 것도 하지 않았다. 재귀적인 사고에 약한 사람이라면 이 예제를 분석하고 개선하면서 재귀적인 능력이 비약적으로 상승할 것이다. 또 후에 기회가 된다면 K&Rdcl 구현을 반드시 살펴보라. 이 코드보다 아주 간단명료해서, 이해하는 데 도움이 많이 될 것이다.

이와 같이 C의 선언을 분석하는 프로그램을 만들고 테스트해볼 수 있었다.

 

4. 계산기와의 결합

1장에서 복합 연산이 가능한 계산기를 만들었고 여기서 C의 선언 방식을 공부하면서 식별자를 읽어내는 방법을 이해했다. 그렇다면 이 상태에서 바로 C 컴파일러를 만들 수 있을까?

 

 

 

 

 

해볼까?

 

4.1) 무엇이 필요한가?

선언과 계산기로 만들겠다고 했으니 당연히 두 모듈이 모두 필요하다. 다음을 가져온다.

- 계산기 모듈: 01_StackAndCalc.06_read_infix.06_read_infix.cpp

- 선언 분석 모듈: 02_cdecl.03_dcl.03_dcl_main.cpp

- StringBuffer 클래스

이때 이전에 구현한 모듈을 리팩토링할 것이다. 리팩토링(refactoring)이란 내부 논리나 구조를 바꾸고 개선하는 유지보수 행위이다. 그럼 이전에 구현한 프로그램에 개선할 점이 있다는 뜻인데, 과연 이 필자란 사람은 어떤 부분을 개선할 생각인걸까?

바로 정답을 말하자면 모든 모듈이다. 애초에 하나의 목적을 가지고 있지 않았던 코드들을 하나로 묶으려면 아주 잘 만든 라이브러리가 아닌 이상 코드의 수정은 불가피하다(라이브러리를 사용하지 않고 바로 프로그래밍을 공부하는 학부생 수준에서라면 이런 현상은 더 자주 일어난다). 이는 필자가 이전 모듈을 올바른 방향으로 작성하지 못했다는 뜻도 된다. 하지만 이런 과정을 통해 우리는 앞으로 리팩토링할 때 어떤 부분을 개선하고 줄여야 하는지를 연습하여 후에 있을 큰 프로젝트에서 실수가 일어나지 않도록 할 수 있게 된다.

사실 우리가 작성한 코드의 양이 그렇게 많지 않은 만큼, 선언 분석을 공부하여 얻은 지식을 이용해 프로그램을 처음부터 새롭게 작성하는 것도 좋은 방법이다. 필자는 두 방법을 모두 보일 생각이다. 먼저 작성된 코드가 있는 것을 수정하는 리팩토링이 더 설명하기 간단하므로 이것을 먼저 진행하겠다.

프로젝트를 새롭게 생성하고 C Compiler라는 뜻으로 이름을 cc라고 하자. main 소스 파일을 생성하고 다른 소스 파일을 모두 복사하여 프로젝트에 붙인다. 그러면 main을 포함하여 총 5개의 파일이 프로젝트에 있게 된다.

그런데 사실 선언 분석 모듈과 계산기 모듈은 서로 같이 사용하는 함수가 있다. 기본 판별 함수로서 소스의 위에 정의한 is_digit, is_lower와 같은 함수들이 바로 그렇다. 이 함수들은 이후의 모든 프로젝트에서도 반드시 자주 사용될 함수들이기 때문에, 모듈 각각의 소스 파일이 아닌 다른 소스 파일로 옮겨야 한다. 그래야 모듈에 필요 없는 코드가 줄어들고 가독성이 높아져 생산성에 기여하게 된다.

앞으로 수식 해석 모듈은 read expression을 줄여서 rdx, 선언 분석 모듈은 dcl이라고 부르겠다. 또한 모든 모듈이 공유하는 함수는 common 파일에 기록하는 것으로 하겠다. 예를 들어 기본 판별 함수의 원형은 common.h에 기록하고, 그 구현은 common.cpp에서 할 것이다. 즉 다음과 같다.

common.h

#ifndef __COMMON_H__

#define __COMMON_H__

#include <string>

// 예외 형식 Exception에 대한 임시적인 정의입니다.

typedef std::string Exception;

// 기본 판별 함수입니다.

bool is_digit(char ch); // 문자가 숫자라면 참입니다.

bool is_lower(char ch); // 소문자라면 참입니다.

bool is_upper(char ch); // 대문자라면 참입니다.

bool is_alpha(char ch); // 알파벳이라면 참입니다.

bool is_alnum(char ch); // 알파벳 또는 숫자라면 참입니다.

bool is_space(char ch); // 공백이라면 참입니다.

// 식별자로 가능한 문자인지 확인합니다.

bool is_namch(char ch); // 식별자 문자라면 참입니다.

bool is_fnamch(char ch); // 첫 식별자 문자라면 참입니다.

#endif

common.cpp

#include "common.h"

// 기본 판별 함수입니다.

bool is_digit(char ch) { // 문자가 숫자라면 참입니다.

return ('0' <= ch && ch <= '9');

}

bool is_lower(char ch) { // 소문자라면 참입니다.

return ('a' <= ch && ch <= 'z');

}

bool is_upper(char ch) { // 대문자라면 참입니다.

return ('A' <= ch && ch <= 'Z');

}

bool is_alpha(char ch) { // 알파벳이라면 참입니다.

return is_lower(ch) || is_upper(ch);

}

bool is_alnum(char ch) { // 알파벳 또는 숫자라면 참입니다.

return is_digit(ch) || is_alpha(ch);

}

bool is_space(char ch) { // 공백이라면 참입니다.

return (ch == ' ' || ch == '\t' || ch == '\n');

}

// 식별자로 가능한 문자인지 확인합니다.

bool is_namch(char ch) { // 식별자 문자라면 참입니다.

return is_alnum(ch) || (ch == '_');

}

bool is_fnamch(char ch) { // 첫 식별자 문자라면 참입니다.

return is_alpha(ch) || (ch == '_');

}

그리고 이에 따라 각 모듈에서 정의했던 판별 함수를 삭제하고 헤더 파일을 추가하여 리팩토링한다. 이때 rdx 모듈에 정의되어있는 clear_input_buffer 또한 common으로 옮기겠다. 이 함수가 iostream 헤더에 정의되어있는 cin 객체를 사용하기 때문에, common 소스 파일에 iostream 헤더를 추가해야 한다.

다음은 정의했던 스택을 read_infix 소스 파일이 아닌 소스 파일로 분리하는 작업이다. Stack.h 파일을 만든다. Stack은 템플릿 클래스이기 때문에 컴파일 시에 구현 전체의 정의를 컴파일러가 반드시 알아야 한다. 즉 이 경우 Stack은 헤더 파일에 그대로 구현하고 별도의 cpp 파일을 만들지 않는다.

Stack.h

#ifndef __HANDY_STACK_H__

#define __HANDY_STACK_H__

 

// 형식에 자유로운 스택을 만들기 위해 템플릿 클래스로 변경

template <typename Data>

class Stack {

static const int MAX_STACK_SIZ = 256;

Data _list[MAX_STACK_SIZ];

int _count;

private:

inline bool is_full() const { return _count == MAX_STACK_SIZ; }

public:

Stack() : _count(0) {}

void push(const Data &data) {

if (is_full()) throw Exception("Stack is full");

_list[_count++] = data;

}

Data pop() {

if (is_empty()) throw Exception("Stack is empty");

return _list[--_count];

}

Data top() const {

if (is_empty()) throw Exception("Stack is empty");

return _list[_count - 1];

}

inline bool is_empty() const { return _count == 0; }

inline int count() const { return _count; }

};

 

#endif

아니면 굳이 신뢰도도 성능도 떨어지는 우리 스택을 쓸 게 아니라 C++ 표준 템플릿 라이브러리가 지원하는 스택 클래스를 쓰는 것도 좋다. 다만 STLstackpop 함수의 구현이 일반적인 구현과 달라 예제에서 불편할 수 있어 넣지 않았는데, 우리가 사용하던 스택을 그대로 사용하고 싶다면 Stack만 리팩토링하는 방법을 사용할 수도 있다. 예를 들면 다음과 같다.

Stack.h

#ifndef __HANDY_STACK_H__

#define __HANDY_STACK_H__

#include <stack>

template <typename Data>

class Stack {

std::stack<Data> stack;

public:

Stack() {}

void push(const Data &data) {

stack.push(data);

}

Data pop() {

Data popValue = stack.top();

stack.pop();

return popValue;

}

Data top() const {

return stack.top();

}

inline bool is_empty() const { return stack.empty(); }

inline int count() const { return stack.size(); }

};

#endif

이렇게 스택 클래스의 리팩토링도 끝났다. 이제 각각의 모듈에 존재하는 main 함수를 적당히 이름을 바꾸고 컴파일 하라.

main.cpp

#include <iostream>

using namespace std;

int main(void) {

int main_rdx(), main_dcl();

main_rdx(); // read expression

main_dcl(); // analyze declaration

return 0;

}

두 함수 모두 정상적으로 실행됨을 확인할 수 있다.

 

4.2) StringBuffer 클래스 개선

모듈을 합치는 건 성공했고 모두 잘 동작한다. 하지만 이것만으로 끝이 난 건 아니다. 컴파일러라면 사칙 연산 이외에 더 많은 연산이 가능해야 하고, 변수를 읽어내고 변수로 연산할 수 있어야 한다. 자료형은 바꾸기만 하면 된다고 생각할 수도 있으니 일단 int형이라고 가정해보자. 연산은 사칙 연산에서 연산자를 추가하고 확장하면 어떻게 될 것 같다. 우선 변수를 읽어야 하므로 수식 해석 모듈을 수정하자. 문자열을 인자로 넘기던 함수에 StringBuffer 클래스를 적용한다.

그런데 생각해보자. rdxdcl 모듈은 모두 정수를 읽을 수 있어야 한다. 사실 정수뿐만이 아니라 식별자 획득, 공백 제거 등의 기능은 모두 필요하며 아주 자주 사용된다. 우리는 이러한 기능을 함수로 묶어내야 함을 알고 있는데, 이를 수행하는 함수를 StringBuffer 클래스의 메서드로 넣으면 어떨까? 다음은 StringBuffer 클래스에 새롭게 추가할 메서드이다.

- std::string get_number(); // 수를 획득한다.

- std::string get_identifier(); // 식별자를 획득한다. 키워드 획득 시에도 사용할 수 있다.

- std::string get_operator(); // C 연산자를 획득한다.

- void trim(); // 현재 위치에서 공백이 아닌 문자가 나올 때까지 포인터를 옮긴다.

- std::string get_token(); // 현재 위치 다음에 존재하는 공백이 아닌 기호(token)를 획득한다.

이전에 설명하지 않은 중요한 단어 중에 토큰이 있는데, 토큰(token)은 의미를 지닌 기호, , 문자 또는 문자열을 의미한다. 위에 제시한 함수들은 모두 다음과 같이 가정하고 있으므로 사용 시에 반드시 알고 있어야 한다.

- get_XXX() 함수는 모두 알아서 공백을 무시하고 가장 근접한 토큰을 반환한다.

- get_XXX() 함수는 토큰 획득에 실패하면 Exception 형식의 예외를 던진다.

- get_XXX() 함수는 해석 가능한 문자까지만 해석한다.

> get_number() 함수는 버퍼에 123x456이 남은 경우 123을 반환하고 포인터가 x456으로 이동한다.

> get_identifier() 함수는 버퍼에 v1_2+x8이 남은 경우 v1_2를 반환하고 포인터가 +x8로 이동한다.

> get_operator() 함수는 발견된 연산자 중 가장 긴 것을 반환한다. ++a++와 같은 입력이 들어오면 ++ 연산자를 뜻하는 정수를 반환하고 포인터가 a++로 이동한다.

그럼 이제 StringBuffer 클래스에 이를 구현해보자. 여기서 헤더와 소스가 몇 가지 바뀐다.

- 위에서 제시한 메서드를 StringBuffer의 멤버로 추가

- common 헤더 파일을 StringBuffer의 헤더 파일에 추가

- Exception 형식을 나타내는 StringBufferException 정의

- 소스 파일에 정의했던 Exception 정의를 삭제하고 포함한 string 헤더 파일을 제외

먼저 가장 간단한 trim 메서드부터 구현해보자.

StringBuffer.cpp

void StringBuffer::trim() {

while (is_empty() == false) { // 버퍼에 문자가 남아있는 동안

if (is_space(str[idx]) == false) // 공백이 아닌 문자를 발견하면

break; // 반복문을 탈출한다

++idx; // 공백이면 다음 문자로 포인터를 넘긴다

}

}

코드의 흐름을 주석을 통해 모두 적었으니, 쉽게 이해할 수 있을 것이다. 다음은 정수를 획득하는 get_number 메서드를 구현하자.

StringBuffer.cpp

std::string StringBuffer::get_number() {

trim(); // 공백 제거

if (is_empty()) // 버퍼에 남은 문자가 없다면 예외

throw StringBufferException("Buffer is empty");

else if (is_digit(str[idx]) == false) // 첫 문자가 숫자가 아니면 예외

throw StringBufferException("invalid number");

std::string value;

while (is_empty() == false) {

if (is_digit(str[idx]) == false)

break;

value += str[idx];

++idx;

}

return value;

}

우리는 이미 이 부분을 연습했으므로 역시 어렵지 않다. 다음은 식별자를 획득하는 get_identifier 메서드의 구현이다.

StringBuffer.cpp

std::string StringBuffer::get_identifier() {

trim(); // 공백 제거

if (is_empty()) // 버퍼에 남은 문자가 없다면 예외

throw StringBufferException("Buffer is empty");

else if (is_fnamch(str[idx]) == false)

throw StringBufferException("invalid identifier");

std::string identifier;

while (is_empty() == false) {

if (is_namch(str[idx]) == false) // 식별자 문자가 아니라면 탈출

break;

identifier += str[idx];

++idx;

}

return identifier;

}

is_digit 메서드가 is_namch 메서드로 바뀐 것을 제외하고는 크게 바뀌지 않았으므로 분석하는 것이 어렵지 않다. 다음은 get_operator의 구현인데 이것도 크게 복잡하지 않다.

StringBuffer.cpp

std::string StringBuffer::get_operator() {

trim();

if (is_empty())

throw StringBufferException("Buffer is empty");

char ch = str[idx++]; // 현재 문자를 획득하고 포인터를 이동한다

std::string op;

switch (ch) {

case '+': op = ch; break;

case '-': op = ch; break;

case '*': op = ch; break;

case '/': op = ch; break;

default: throw StringBufferException("invalid operator");

}

return op;

}

switch 구문이 이상하다고 생각할 수도 있는데, 이에 대해서는 후에 자세히 다룰 것이다. 마지막으로 get_token의 구현이다.

StringBuffer.cpp

std::string StringBuffer::get_token() {

trim();

if (is_empty())

throw StringBufferException("Buffer is empty");

char ch = str[idx];

std::stringstream ss; // 문자열 스트림 생성

if (is_digit(ch)) { // 정수를 발견했다면 정수 획득

ss << get_number(); // cout 출력 스트림처럼 사용하면 된다

}

else if (is_fnamch(ch)) { // 식별자 문자를 발견했다면 식별자 획득

ss << get_identifier();

}

else { // 이외의 경우 일단 연산자로 획득

ss << get_operator();

}

return ss.str(); // 스트림에 담긴 문자열을 std::string 객체로 반환한다

}

이제 이것이 정상적으로 동작하는지 확인하는 프로그램을 만들자. 정상 동작을 확인하려면 모든 토큰이 제대로 읽혀지는지를 봐야 한다. 테스트의 편의를 위해 무한히 입력받다가, 적법하지 않은 문장(세미콜론) 등이 들어오면 종료하도록 하자. 입력에 대해 다음 출력이 나오면 성공이라고 하겠다.

입력

출력

123 *456+var1/ var2

test

test object HELLOWORLD

;

[123][*][456][+][var1][/][var2]

[test]

[test][object][HELLOWORLD]

Program ended

다음은 필자의 구현이다.

StringBufferV2Main.cpp

#include <iostream>

#include "common.h"

#include "StringBuffer.h"

int main(void) {

try {

const int MAX_INPUT_SIZ = 256;

char input[MAX_INPUT_SIZ];

while (true) {

clear_input_buffer();

std::cin.getline(input, MAX_INPUT_SIZ);

StringBuffer buffer(input);

while (buffer.is_empty() == false) {

std::string token = buffer.get_token(); // 토큰 획득

std::cout << '['<< token.c_str() << ']'; // 감싸서 출력

}

std::cout << std::endl;

}

return 0;

}

catch (Exception &ex) {

// 정수 획득 실패, 식별자 획득 실패 후

// 연산자 획득 메서드인 get_operator에서 던진 예외를

// main 함수에서 받는다.

// 따라서 exinvalid operator가 된다.

std::cerr << "Program ended" << std::endl;

return 1;

}

}

이제 제법 쓸 만하게 StringBuffer 클래스를 개선했으니, 본격적으로 rdx 모듈을 수정해보자.

 

4.3) rdx 모듈 개선

지금 우리의 목표는 컴파일러를 만드는 것이다. 그러려면 적어도 다음의 문장은 분석해야 한다.

123 *456+var1/ var2

따라서 rdx 모듈은 최소한 이 문장을 분석할 수 있어야 한다. 이전에 작성한 rdx 모듈은 정수 피연산자만 가능했으므로, 이 부분을 StringBuffer 클래스를 이용해 개선할 것이다. 이를 위해 rdx 모듈을 생각보다 많이 리팩토링 해야 한다. 다음은 우리가 어떻게 모듈을 리팩토링 할 것인지를 보이기 위해 소스 파일의 위 부분을 가져온 것이다.

rdx.cpp

#include <iostream>

#include <sstream>

#include <vector>

#include "common.h"

#include "Stack.h"

#include "StringBuffer.h"

const int MAX_EXPR_LEN = 256;

// 식을 계산하고 값을 정수로 반환합니다.

int calculate(const char *expr);

// 연산자의 우선순위를 정수로 반환합니다.

int op_pri(const std::string &op);

// 식을 후위 표기법으로 변환합니다.

static std::vector<std::string> infix_to_postfix(const char *infix);

// 후위 표기법으로 표현된 식을 계산하고 값을 정수로 반환합니다.

int calculate_postfix(const std::vector<std::string> &postfix);

sstream, vectorStringBuffer 클래스가 소스에 추가되었다. 또한 calculate 함수를 제외한 나머지 세 함수의 원형이 바뀌었다. 이는 StringBuffer 클래스가 토큰을 획득할 때 std::string 형식으로 획득하여 반환하기 때문에, 인자 또한 이러한 형태로 수정하는 것이 사용하기가 편하기 때문이다. 벡터 클래스가 추가됨으로써, 중위 표기식을 분석하여 토큰을 해석한 후에, 후위 표기식에서 다시 토큰을 StringBuffer 클래스를 통해 읽어야 하는 불편함을 없애고 코드를 간결하게 만들었다. 또한 static 키워드를 이용해 외부에서 infix_to_postfix 함수를 호출하지 못하게 하여 코드의 안정성을 높였다. 다음은 수정된 calculate 함수 및 op_pri 함수의 구현이다.

rdx.cpp

int calculate(const char *expr) { // calculate infix expression

// 중위 표기식을 후위 표기식으로 변환한다

std::vector<std::string> postfix = infix_to_postfix(expr);

return calculate_postfix(postfix); // 변환된 후위 표기식을 분석하고 반환한다

}

int op_pri(const std::string &op) { // get operator's priority

int priority = 0;

switch (op[0]) {

case '+': priority = 1; break; case '-': priority = 1; break;

case '*': priority = 2; break; case '/': priority = 2; break;

default: throw Exception("Invalid operator");

}

return priority;

}

이제 중위 표기법으로 표현된 식을 후위 표기법으로 변환하는 infix_to_postfix 함수를 고치자.

rdx.cpp

static std::vector<std::string> infix_to_postfix(const char *infix) {

StringBuffer bin(infix);

Stack<std::string> opStack;

std::vector<std::string> postfix; // 후위 표기식의 토큰을 저장할 벡터

while (bin.is_empty() == false) {

bin.trim();

char ch = bin.peekc();

// 정수라면 획득하고 바로 출력한다 (피연산자)

if (is_digit(ch))

postfix.push_back(bin.get_number());

// 식별자라면 획득하고 바로 출력한다 (피연산자)

else if (is_fnamch(ch))

postfix.push_back(bin.get_identifier());

// 이외의 경우 연산자로 획득한다

else {

std::string op = bin.get_operator();

if (op == "(") // 여는 괄호라면 그냥 넣는다

opStack.push(op);

else if (op == ")") { // 닫는 괄호를 발견한 경우의 처리

if (opStack.is_empty() == false) {

// get operator priority

while (opStack.is_empty() == false) {

std::string top = opStack.top();

if (top == "(") // 여는 괄호를 찾았다면 종료

break;

else

// 우선순위가 낮은 연산자를 스택에서 꺼내

// 후위 표기식에 추가

postfix.push_back(opStack.pop());

}

// 올바른 괄호 쌍이 존재하는지 확인

if (opStack.top() != "(")

throw Exception("Invalid parenthesis");

// 스택에 있는 여는 소괄호를 버린다

opStack.pop();

}

}

else {

if (opStack.is_empty() == false) {

// get operator priority

int new_pri = op_pri(op);

while (opStack.is_empty() == false) {

std::string top = opStack.top();

if (top == "(") // 여는 괄호를 찾았다면 종료

break;

else if (new_pri <= op_pri(top))

postfix.push_back(opStack.pop());

else

break;

}

}

opStack.push(op);

}

}

}

// 스택에 남은 연산자를 모두 출력한다

while (opStack.is_empty() == false) {

std::string op = opStack.pop();

if (op == "(") // 위에서 처리되지 않은 소괄호가 있다면 예외 처리

throw Exception("Invalid parenthesis");

postfix.push_back(op);

}

return postfix;

}

main에서 테스트하여 이 함수가 잘 동작함을 확인할 수 있다. 당연히 main 함수 내부에서 main_rdx 함수를 호출해야 한다.

rdx.cpp

int main_rdx(void) {

try {

char expression[MAX_EXPR_LEN] = "";

while (true) {

std::cout << "Enter expression: ";

clear_input_buffer();

std::cin.getline(expression, MAX_EXPR_LEN);

if (expression[0] == ';')

break;

std::vector<std::string> &postfix = infix_to_postfix(expression);

for (int i = 0, len = postfix.size(); i < len; ++i) {

std::cout << postfix[i] << ' ';

}

std::cout << " : " << calculate(expression) << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

이제 calculate_postfix 함수를 수정하면 끝난다. 이를 위해 먼저 다음의 함수를 소개한다.

rdx.cpp

int strtoi(const std::string &str) { // 문자열을 정수로 변환한 값을 반환합니다.

int digit, value = 0;

for (int i = 0, len = str.length(); i < len; ++i) {

digit = str[i] - '0';

value = 10 * value + digit;

}

return value;

}

std::string 문자열을 정수로 변환하는 함수다. 토큰을 모두 std::string으로 저장했으니 이러한 변환은 반드시 필요하므로 구현했다. 그러면 이제 calculate_postfix의 구현을 보이겠다. 그런데 사실 이 코드에는 아직 구현하지 않은 부분이 있다. 어떤 부분일까?

rdx.cpp

int calculate_postfix(const std::vector<std::string> &postfix) {

int value;

Stack<int> paramStack;

for (int i = 0, len = postfix.size(); i < len; ++i) {

const std::string &token = postfix[i];

if (is_digit(token[0])) { // 정수라면 변환해서 푸시

value = strtoi(token);

paramStack.push(value);

}

else if (is_fnamch(token[0])) { // 식별자라면 값을 가져와서 푸시

// value = get_identifier_value(token);

value = -1;

paramStack.push(value);

}

else { // 이외의 경우 연산자로 처리한다

const std::string &op = token;

// 스택에서 두 개의 피연산자를 꺼낸다

int right = paramStack.pop();

int left = paramStack.pop();

// 획득한 연산자로 연산한다

switch (op[0]) {

case '+': value = left + right; break;

case '-': value = left - right; break;

case '*': value = left * right; break;

case '/': value = left / right; break;

default: throw Exception("Invalid operator");

}

// 연산 결과를 다시 스택에 넣는다

paramStack.push(value);

}

}

if (paramStack.count() != 1) // 스택에 남은 피연산자가 1개가 아니면 예외

throw Exception("Unhandled operand found");

return paramStack.pop(); // 하나 남은 피연산자를 반환한다

}

사실 바로 보이는데, 식별자에서 값을 가져오는 부분이 구현되지 않았다. 왜 그랬을까?

식별자에서 값을 가져오려면, 먼저 식별자가 정의되어있어야 한다. 변수를 정의하지 않고 사용할 수 없는 것처럼 말이다. 그러려면 식별자를 정의하는 표를 별도로 가지고 있어야 한다. 이 문제를 설명하기 위해 아직 식별자에서 값을 가져오는 부분을 구현하지 않았다. 우리는 식별자 표를 만든 다음 위에서 주석 처리되어있는 get_identifier_value 함수를 구현할 것이다.

그런데 생각해보자. 식별자 표는 어디에 정의해야 할까? rdx인가, dcl인가? rdx 모듈은 식을 계산할 때 식별자 표로부터 정보를 가져와야 한다. dcl 모듈은 선언을 분석한 후 획득한 식별자 정보를 식별자 표에 넣어야 한다. 필자의 프로그래밍 경험으로는, 두 모듈이 하나의 자료에 접근하는 경우에는 자료를 독립적으로 만들어놓고 접근자, 설정자 함수를 이용해 자료를 주고받는 형태가 가장 나았다. 따라서 이 예제에서도 식별자 표 정보를 갖고 있는 새로운 모듈을 만들고, rdxdcl이 함수를 통해 이 모듈과 자료를 주고받도록 할 것이다. 이 새로운 모듈의 이름은 식별자 표(table)라는 뜻으로 tbl이라고 하겠다.

다음과 같이 tbl 모듈의 식별자 표 Table을 구현할 수 있다. 먼저 헤더를 보자.

Table.h

#ifndef __IDENTIFIER_TABLE_H__

#define __IDENTIFIER_TABLE_H__

#include "common.h"

#include <string>

#include <map>

class Table {

static Table *_instance; // 싱글톤 객체를 가리키는 정적 필드

std::map<std::string, std::string> _table; // 실제 식별자 표 객체

private: // tbl을 싱글톤 객체로 만들기 위해 생성자를 숨긴다

explicit Table();

~Table();

public:

// tbl 싱글톤 객체의 인스턴스를 가져옵니다.

static Table *instance();

// 식별자에 대한 접근자, 설정자 함수입니다.

std::string &get(const std::string &identifier);

void set(const std::string &identifier, const std::string &value);

};

#endif

싱글톤이라는 단어를 처음 듣는 독자가 있을 수도 있다. 싱글톤(singleton)이란 프로그램에 하나 이상 생성되지 않는 유일한 객체를 말하며, 이렇게 싱글톤을 이용하여 프로그램을 작성하는 설계 방식을 싱글톤 디자인 패턴이라고 한다. 식별자 표는 당장은 프로그램에 하나 이상 존재할 이유가 따로 없는데, 왜냐하면 표가 두 개 이상이 되면 식별자를 모든 표마다 뒤져서 찾아내야 하는 등 여러모로 번거로워지기 때문이다. 따라서 지금은 tbl 모듈은 싱글톤 객체로만 사용하겠다(당장, 지금 등 이 시점을 강조하는 이유는 이 모듈이 나중에 리팩토링 될 것이기 때문이다).

다음은 tbl 싱글톤 객체의 메서드를 구현한 것이다.

tbl.cpp

#include "Table.h"

Table *Table::_instance = nullptr;

Table::Table() {}

Table::~Table() {}

Table *Table::instance() {

return (_instance ? _instance : (_instance = new Table()));

}

std::string &Table::get(const std::string &identifier) {

try {

return _table[identifier];

}

catch (...) {

throw Exception("식별자에 대한 값을 가져올 수 없습니다.");

}

}

void Table::set(const std::string &identifier, const std::string &value) {

_table[identifier] = value;

}

컴파일러를 만드는 문서이니만큼 싱글톤의 구현에 관해 더 이상 설명하지 않겠다. 구현은 위와 같이 아주 간단하며, 이를 이용해 rdx 모듈을 완성할 수 있다.

rdx.cpp

...

#include "Table.h"

...

int calculate_postfix(const std::vector<std::string> &postfix) {

...

else if (is_fnamch(token[0])) { // 식별자라면 값을 가져와서 푸시

std::string ival = Table::instance()->get(token); // 키에 대한 값 획득

value = strtoi(ival); // 획득한 값을 정수로 변환

paramStack.push(value); // 피연산자 스택에 푸시

}

...

}

다음과 같이 테스트가 정상적으로 동작함을 확인할 수 있다.

rdx.cpp

int main_rdx(void) {

try {

std::string command;

std::string identifier, value;

std::cout << "Usage: " << std::endl;

// auto로 식별자에 대한 값을 설정합니다.

std::cout << "- auto <identifier> <value>" << std::endl;

// calc로 수식을 분석하고 값을 계산합니다.

std::cout << "- calc <expression>" << std::endl;

// exit로 프로그램을 종료합니다.

std::cout << "- exit" << std::endl;

while (true) {

clear_input_buffer();

std::cout << "> ";

std::cin >> command;

if (command == "auto") {

std::cin >> identifier >> value;

Table::instance()->set(identifier, value);

}

else if (command == "calc") {

std::cin.ignore(1);

std::cin.getline(input, MAX_INPUT_SIZ);

std::cout << calculate(input) << std::endl;

}

else if (command == "exit") {

break;

}

else {

std::cout << "unknown command; try again" << std::endl;

}

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

이 프로그램은 다음과 같이 실행된다. 바로 알아볼 수 있을 것이다.

Usage:

- auto <identifier> <value>

- calc <expression>

- exit

> calc 1+2*3+4

11

> auto var1 3

> auto var2 4

> calc var1+var2

7

> calc 1 *var1+var2/ 2

5

> exit

이와 같이 변수 해석이 가능하게 rdx 모듈을 개선할 수 있었다.

 

4.4) dcl 모듈 개선

변수가 있는 수식을 성공적으로 분석해냈다. 여기까지 따라왔다면 진심으로 스스로를 칭찬해도 좋다. 굳이 필자가 말하지 않더라도 변수 분석이 가능한 계산기를 만들어냈다는 사실만으로도 이미 스스로를 대견하게 느끼고 있지 않을까 넘겨짚어 본다.

이제 선언을 분석하고 획득한 식별자 정보를 식별자와 함께 Table 객체에 넣으면 결합이 끝난다. 그런데 식별자 정보를 Table에 넣는 것은 어렵지 않지만, 식별자가 어떤 정보를 가지고 있는지를 결정하는 것이 생각보다 어렵다. 여기서는 간단하게 식별자가 자료형과 값만 가지고 있다고 가정한다.

식별자가 저장하는 정보가 값에서 자료형과 값으로 커졌으므로, 식별자 객체를 표현하는 새로운 클래스가 필요하다. 따라서 식별자의 정보를 표현하는 IdentifierInfo 클래스를 새롭게 작성하고 Table 객체를 리팩토링 하겠다. 다음은 이를 구현한 것이다.

IdentifierInfo.h

#ifndef __IDENTIFIER_H__

#define __IDENTIFIER_H__

 

#include "common.h"

#include <string>

 

class IdentifierInfo {

std::string _name; // 식별자의 이름을 저장하는 변수

std::string _datatype; // 자료형을 저장하는 변수

std::string _value; // 값을 저장하는 변수

public:

IdentifierInfo();

IdentifierInfo(

const std::string &name,

const std::string &datatype,

const std::string &value = "");

 

std::string &name(); // 식별자의 이름을 반환합니다.

const std::string &name() const; // 식별자의 이름을 반환합니다.

std::string &datatype(); // 자료형을 반환합니다.

const std::string &datatype() const; // 자료형을 반환합니다.

std::string &value(); // 값을 반환합니다.

const std::string &value() const; // 값을 반환합니다.

void set_name(const std::string &name); // 식별자의 이름을 설정합니다.

void set_datatype(const std::string &datatype); // 자료형을 설정합니다.

void set_value(const std::string &value); // 값을 설정합니다.

};

 

#endif

IdentifierInfo.cpp

#include "IdentifierInfo.h"

IdentifierInfo::IdentifierInfo() {}

IdentifierInfo::IdentifierInfo(

const std::string &name,

const std::string &dtype,

const std::string &value)

: _name(name), _datatype(dtype), _value(value) {}

// 식별자의 이름을 반환합니다.

std::string &IdentifierInfo::name() { return _name; }

const std::string &IdentifierInfo::name() const { return _name; }

// 자료형을 반환합니다.

std::string &IdentifierInfo::datatype() { return _datatype; }

const std::string &IdentifierInfo::datatype() const { return _datatype; }

// 값을 반환합니다.

std::string &IdentifierInfo::value() { return _value; }

const std::string &IdentifierInfo::value() const { return _value; }

// 식별자의 이름을 설정합니다.

 

// 자료형을 설정합니다.

void IdentifierInfo::set_datatype(const std::string &dtype) { _datatype = dtype; }

// 값을 설정합니다.

void IdentifierInfo::set_value(const std::string &value) { _value = value; }

그리고 이를 이용해 Table을 리팩토링 한 결과는 다음과 같다.

Table.h

#ifndef __IDENTIFIER_TABLE_H__

#define __IDENTIFIER_TABLE_H__

 

#include "common.h"

#include <string>

#include <map>

#include "IdentifierInfo.h"

 

class Table {

static Table *_instance; // 싱글톤 객체를 가리키는 정적 필드

std::map<std::string, IdentifierInfo> _table; // 실제 식별자 표 객체

 

private: // tbl을 싱글톤 객체로 만들기 위해 생성자를 숨긴다

explicit Table();

~Table();

 

public:

// tbl 싱글톤 객체의 인스턴스를 가져옵니다.

static Table *instance();

// 식별자에 대한 접근자, 설정자 함수입니다.

IdentifierInfo &get(const std::string &identifier);

void set(const std::string &identifier, const IdentifierInfo &value);

};

 

#endif

tbl.cpp

#include "Table.h"

Table *Table::_instance = nullptr;

 

Table::Table() {}

Table::~Table() {}

 

Table *Table::instance() {

return (_instance ? _instance : (_instance = new Table()));

}

 

IdentifierInfo &Table::get(const std::string &identifier) {

if (_table.find(identifier) == _table.end())

throw Exception("식별자에 대한 값을 가져올 수 없습니다.");

return _table[identifier];

}

void Table::set(const std::string &identifier, const IdentifierInfo &value) {

_table[identifier] = value;

}

이제 준비가 끝났으니 dcl 모듈에서 식별자를 표에 넣을 수 있게 리팩토링 해보자. 다음은 rdx 모듈과 같이 벡터를 이용하여 보다 이용하기 편리하게 작성한 예제다. 먼저 소스 위 부분이 바뀌었다.

dcl.cpp

#include <iostream>

#include "StringBuffer.h"

#include "common.h"

 

#include <vector>

typedef std::vector<std::string> StringList;

 

#include "Table.h"

#include "IdentifierInfo.h"

 

const int MAX_INPUT_SIZ = 256;

static char input[MAX_INPUT_SIZ];

 

// 선언을 분석하고 획득한 토큰의 벡터를 반환합니다.

std::vector<IdentifierInfo> get_dcl_info(const char *decl);

 

// 형식을 획득하여 문자열로 반환합니다.

std::string get_type(StringBuffer &buf_in);

// 선언자를 분석하고 결과를 출력합니다.

void dcl(StringBuffer &buf_in, StringList &vec_out);

// 직접 선언자를 분석하고 결과를 출력합니다.

void dirdcl(StringBuffer &buf_in, StringList &vec_out);

dcl, dirdcl 함수의 내부도 vout을 이용하게끔 바뀌었다.

dcl.cpp

void dcl(StringBuffer &bin, StringList &vout) { // 선언자를 분석하고 결과 출력

// declarator: * direct-declarator (1)

int pointer_count = 0;

char ch;

while (bin.is_empty() == false) { // 버퍼에 문자가 남아있는 동안

ch = bin.getc(); // 문자를 획득하고 확인한다

if (ch == '*') { // *라면 그만큼 포인터를 출력하기 위해

++pointer_count; // 카운터를 증가시킨다

}

else { // *가 아니라면 포인터를 되돌리고 탈출한다

bin.ungetc();

break;

}

}

// declarator: * direct-declarator (2)

dirdcl(bin, vout); // *을 모두 획득했으므로 직접 선언자를 분석한다

while (pointer_count > 0) { // 선언자의 분석이 오른쪽에서 먼저 진행되므로

vout.push_back("*"); // 왼쪽에서 획득한 기호를 오른쪽의 분석이

--pointer_count; // 종료된 후에 출력해야 한다

}

}

void dirdcl(StringBuffer &bin, StringList &vout) { // 직접 선언자를 분석하고 결과 출력

char ch = bin.peekc();

if (is_fnamch(ch)) { // direct-declarator: 이름 (2)

std::string identifier = "";

while (bin.is_empty() == false) {

ch = bin.getc();

if (is_namch(ch) == false) {

bin.ungetc();

break;

}

identifier += ch;

}

if (identifier.empty()) // 식별자에 추가된 문자가 없다면 예외

throw Exception("올바른 식별자 이름이 아닙니다.");

vout.push_back(identifier);

}

else if (ch == '(') { // direct-declarator: (declarator) (3)

bin.getc(); // ( 문자를 해석해서 진입했으므로 다음으로 넘긴다

dcl(bin, vout);

if (bin.peekc() != ')') // 닫는 괄호가 없으면 예외

throw Exception("닫는 괄호가 없습니다.");

bin.getc(); // ) 괄호 검사를 진행했으므로 다음으로 넘긴다

}

// direct-declarator: direct-declarator() (4)

// direct-declarator: direct-declarator[] (5)

while (bin.is_empty() == false) {

ch = bin.peekc();

if (ch == '(') { // 함수 기호 획득

bin.getc(); // ( 괄호를 해석해서 진입했으므로 넘긴다

if (bin.peekc() != ')') // 닫는 괄호가 없으면 예외

throw Exception("잘못된 함수 기호입니다.");

bin.getc(); // ) 괄호를 해석했으므로 다음으로 넘긴다

vout.push_back("()");

}

else if (ch == '[') { // 배열 기호 획득

bin.getc(); // [ 괄호를 해석해서 진입했으므로 넘긴다

if (bin.peekc() != ']') // 닫는 괄호가 없으면 예외

throw Exception("잘못된 배열 기호입니다.");

bin.getc(); // ] 괄호를 해석했으므로 다음으로 넘긴다

vout.push_back("[]");

}

else { // 이외의 경우 반복문을 탈출한다

break;

}

}

}

선언을 문자열로 입력하면 이를 분석하여 IdentifierInfo의 벡터로 반환하는 get_dcl_info 함수가 추가되었다.

dcl.cpp

std::vector<IdentifierInfo> get_dcl_info(const char *decl) {

std::vector<IdentifierInfo> identifiers;

StringList tokens;

StringBuffer bin(decl);

std::string type = get_type(bin);

 

while (bin.is_empty() == false) {

tokens.clear();

bin.trim();

dcl(bin, tokens);

if (bin.peekc() == ',') {

bin.getc();

std::string identifier = tokens[0];

std::string datatype;

for (int i = 1, len = tokens.size(); i < len; ++i) {

datatype += tokens[i];

}

datatype += type;

IdentifierInfo info(identifier, datatype);

identifiers.push_back(info);

}

else if (bin.peekc() == ';') {

break;

}

else {

throw Exception("unknown character");

}

}

std::string identifier = tokens[0];

std::string datatype;

for (int i = 1, len = tokens.size(); i < len; ++i) {

datatype += tokens[i];

}

datatype += type;

IdentifierInfo info(identifier, datatype);

identifiers.push_back(info);

return identifiers;

}

마지막으로 이를 테스트할 수 있게 main 함수를 작성하였다.

dcl.cpp

int main_dcl(void) {

try {

while (true) {

std::cin.getline(input, MAX_INPUT_SIZ);

std::vector<IdentifierInfo> decl_list = get_dcl_info(input);

for (int i = 0, len = decl_list.size(); i < len; ++i) {

const IdentifierInfo &info = decl_list[i];

Table::instance()->set(info.name(), info);

}

 

for (int i = 0, len = decl_list.size(); i < len; ++i) {

const std::string &identifier = decl_list[i].name();

const IdentifierInfo &info = Table::instance()->get(identifier);

std::cout << info.name() << ": " << info.datatype() << std::endl;

}

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

드디어 dcl 모듈의 리팩토링이 모두 끝났다. 남은 일은 rdx 모듈의 main 함수가 수행했던 과정에서 선언을 넣고 값을 정의하는 것이다. 마지막으로 두 모듈을 합치기 위해 해야 하는 일을 정리하겠다.

- 프로그램은 실행 시에 다음 화면을 띄운다.

Usage:

- decl <declaration>

- movl <identifier> <value>

- calc <expression>

- exit

>

- decl 명령 이후에는 선언이 온다. 이전과 달리 변수는 선언해야 사용할 수 있다.

- movl 명령은 식별자의 값을 설정한다. 선언되지 않은 변수에 값을 대입할 수 없다.

- calc 명령 이후에는 식이 온다. 선언되지 않은 변수를 발견하면 경고 메시지를 출력하고 종료한다.

필자가 구현한 것을 보이기 전에, 이전 소스에서 수정된 사항을 먼저 보이겠다.

rdx 모듈은 main_rdx 함수를 삭제하고 calculate_postfix 함수를 일부 수정하였다.

rdx.cpp

int calculate_postfix(const std::vector<std::string> &postfix) {

...

else if (is_fnamch(token[0])) { // 식별자라면 값을 가져와서 푸시

if (Table::instance()->exist(token) == false)

throw Exception("Undefined identifier; define it first");

IdentifierInfo info = Table::instance()->get(token);

std::string ival = info.value();

value = strtoi(ival);

paramStack.push(value);

...

}

tbl 모듈은 식별자가 표에 존재하는지 확인하고 있으면 참을 반환하는 exist 메서드가 추가되었다.

Table.h

...

// 식별자 표에 식별자가 등록되어있는지 확인합니다.

bool exist(const std::string &identifier) const;

...

dcl 모듈은 main_dcl 함수가 수정되었다. 그리고 공통적으로 각각의 모듈에 대응하는 헤더 파일이 생성되었다.

dcl.h

#ifndef __DECLARATION_H__

#define __DECLARATION_H__

#include <vector>

#include "IdentifierInfo.h"

// 선언을 분석하고 획득한 토큰의 벡터를 반환합니다.

std::vector<IdentifierInfo> get_dcl_info(const char *decl);

#endif

rdx.h

#ifndef __READ_EXPRESSION_H__

#define __READ_EXPRESSION_H__

// 식을 계산하고 값을 정수로 반환합니다.

int calculate(const char *expr);

#endif

그리고 다음이 필자가 구현한, 선언 분석 모듈과 수식 분석 모듈이 결합된 프로그램이다.

main.cpp

#include <iostream>

 

#include "common.h"

#include "StringBuffer.h"

#include "Table.h"

#include "dcl.h"

#include "rdx.h"

#include "IdentifierInfo.h"

 

const int MAX_INPUT_SIZ = 256;

static char input[MAX_INPUT_SIZ];

 

int main(void) {

try {

std::string command;

std::string identifier, value;

std::cout << "Usage: " << std::endl;

std::cout << "- decl <declaration>" << std::endl;

std::cout << "- movl <identifier> <value>" << std::endl;

std::cout << "- calc <expression>" << std::endl;

std::cout << "- exit" << std::endl;

 

while (true) {

clear_input_buffer();

std::cout << "> ";

std::cin >> command;

if (command == "decl") {

std::cin.ignore(1);

std::cin.getline(input, MAX_INPUT_SIZ);

std::vector<IdentifierInfo> decl_list = get_dcl_info(input);

for (int i = 0, len = decl_list.size(); i < len; ++i) {

const IdentifierInfo &info = decl_list[i];

Table::instance()->set(info.name(), info);

}

}

else if (command == "movl") {

std::cin >> identifier >> value;

if (Table::instance()->exist(identifier) == false) {

std::cout << "undefined identifier; define it first" << std::endl;

continue;

}

IdentifierInfo &info = Table::instance()->get(identifier);

info.set_value(value);

}

else if (command == "calc") {

std::cin.ignore(1);

std::cin.getline(input, MAX_INPUT_SIZ);

try {

std::cout << calculate(input) << std::endl;

}

catch (Exception &ex) {

std::cout << ex.c_str() << std::endl;

}

}

else if (command == "exit") {

break;

}

else {

std::cout << "unknown command; try again" << std::endl;

}

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

이와 같이 컴파일러를 만들기 위해 선언 분석 모듈과 수식 분석 모듈을 결합할 수 있었다.

 

4.5) 한계

정말 많은 내용을 공부했고, 생각보다 결과도 괜찮다. 이 정도면 좀만 더 개선하면 컴파일러가 되지 않을까? 서문에서 밝힌 적이 있는데, 필자는 간단한 변수의 선언 및 정의(정확히는 구조체의 선언과 정의까지는 연구했었다)와 수식의 계산까지 완료했지만 함수 정의와 호출에서 막혀서 포기했다. 지금 작성한 코드로 함수, 조건문과 반복문, 포인터 연산, 동적 할당 등을 모두 완성할 수 있다면 당신은 필자보다 아주 뛰어난 사람임에 틀림이 없다.

이는 아주 어려운 문제인데, 기존에 함수 정의와 호출을 구현하는 방법을 모르는 상태에서 이것을 구현하려면 순수하게 개발자의 아이디어만으로 프로젝트를 진행해야 하기 때문이다. 사고력을 키워준다는 점에서 의미가 없다고 할 수는 없으나, 그것에 들이는 노력에 비해 결과가 시원치 않을 가능성이 높고, 대개는 처음에 떠올린 설계 자체에 오류가 생겨서 그전까지 작성했던 코드를 몽땅 버려야 하는 상황이 생각보다 자주 닥치기 때문이다. 이 문서에서는 설계가 없는 프로그래밍의 위험성도 많이 강조할 것이다. 컴파일러의 설계도 없이 혼자 이 프로젝트를 진행하기에는, 학부생 수준의 프로그래밍 능력으로는 너무나도 어렵다. 따라서 이 문제에 대해 필자는 일단 납득하길 바라지만, 정 궁금하다면 자신이 스스로 컴파일러를 설계하여 그대로 진행해보는 것도 좋은 경험이 될 수는 있다고 생각한다.

참고로, 방금 우리가 작성한 dcl 모듈은 완전히 개선되지 않았다. 식별자에 대해 어떤 것을 고려해야 하는지를 떠오르는 대로 나열해보자.

- 자료형

-

- 주소

- 정적인가? (static)

- 상수인가? (const)

- 컴파일러가 최적화하는가? (volatile)

- 레지스터인가? (register)

- 외부에 존재하는가? (extern)

- 외부에서 참조할 수 없는가? (static)

- 형식인가? (typedef)

- 함수인가?

- 함수라면, 인자 정보는 어떠한가?

- 배열인가?

- 포인터인가?

- 사용자 정의 자료형인가? (struct, union, enum)

- 사용자 정의 자료형이라면, 멤버 정보는 어떠한가?

...

일단 이 문제부터 모두 해결할 수 있다면 바로 컴파일러에 도전해도 좋을 것 같다.

 

5. 단원 마무리

방금 위에서도 말했듯 굉장히 많은 내용을 이 문서에 담았다. C의 선언은 그 자체로도 처음 접하는 사람을 크게 혼란스럽게 만들지만, 제대로 이해하고 나면 프로그래밍 언어를 보는 눈이 달라져 보다 높은 수준의 프로그래머가 될 수 있다고 생각한다. 계산기와의 결합은 처음에는 살짝만 설명하고 후에 다시 다룰 생각이었는데, 마침 생각이 들어 진행하다보니 어쩌면 지나치게 많은 내용을 넣어 독자를 부담스럽게 하진 않았을까 걱정도 된다. 다음 내용은 컴파일러와 인터프리터에 대한 개론적인 내용인데, 이전의 문서보다 코드를 거의 작성하지 않으므로 컴퓨터 교양서적을 읽는 듯이 공부할 수 있으리라 생각한다.

Posted by 누아니
,

스택과 계산기

HandyPost는 한 도영(HDNua)이 작성하는 포스트 문서입니다.


소스: 

01_StackAndCalc.zip


문서: 

01. 스택과 계산기.pdf


 

1. 개요

스택 자료구조가 무엇인지 이해하고, 이를 이용하여 복합적 사칙 연산이 가능한 계산기를 C++ 프로그래밍 언어로 만드는 것을 목표로 한다.

 

2. 프로젝트 준비

개발 환경은 C++ 프로그래밍 언어로 개발할 수 있는 어떤 것으로 골라도 좋다. 이 문서에서는 개발 도구의 사용 방법은 독자가 이미 익숙하여 스스로 할 수 있다고 가정한다. 혹 이 부분이 준비되지 않았다고 생각한다면 앞으로의 내용을 읽기 아주 곤란하기 때문에, 먼저 이에 관한 내용을 숙지한 상태여야 한다. 도구의 깊은 내용을 모두 알아야 하는 것이 아니고, 개발 도구를 이용하여 프로그램을 빌드 하는 방법만 정확히 알고 있으면 된다.

 

3. 스택 자료구조

3.1) 스택(Stack) 개요

자료구조(Data Structure)자료를 관리하는 방법이다. 스택(Stack)은 자료구조의 일종으로, 자료를 저장하면 가장 최근의 자료부터 빠져나오는 자료구조이다. 책상 위에 접시를 쌓는 경우를 예를 들어보자. 스택에 자료를 넣는다는 것은 1번 접시부터 차례로 2번 접시, 3번 접시를 각각의 접시 위에 올리는 것과 같다. 스택에서 자료를 가져온다는 것은 이렇게 쌓아올린 접시의 가장 위에 있는, 이 경우 3번 접시부터 차례로 한 개씩 접시를 빼내는 것과 같다. 물론 현실에선 접시를 통째로 들어 올리거나, 독특한 사람은 접시를 가운데에서 빼낼 수 있지만, 스택은 그런 식으로 자료를 관리하지 않는다. 가장 나중에 넣은 자료가 가장 먼저 나오게 된다. 다음은 스택의 의사 코드와 그 결과이다.

스택 사용 예제

스택.넣는다(1);

스택.넣는다(2);

스택.넣는다(3);

while (스택.비어있는가() == false) { // 스택에 자료가 남아있는 동안

= 스택.꺼낸다();

출력();

}

스택 사용 예제 결과

3

2

1

스택은 다음 행동을 반드시 할 수 있어야 한다.

- 넣는다 : 자료구조는 자료를 관리하는 방법이다. 자료를 넣을 수 없다면 자료구조로 기능할 수 없다.

- 꺼낸다 : 스택은 넣은 자료를 반드시 제거할 수 있어야 한다.

스택에 대해 자료를 넣는 행위를 푸시(push), 자료를 꺼내는 행위를 (pop)이라고 한다. 위의 의사 코드를 실제로 동작하는 코드로 바꾼다면 다음과 같이 된다.

스택 사용 예제

class Stack { /* implementations */ };

int main() {

Stack stack;

stack.push(1);

stack.push(2);

stack.push(3);

while (stack.is_empty() == false) {

int value = stack.pop();

std::cout << value << std::endl;

}

return 0;

}

스택을 더 유용하게 만드는 메서드로는 다음과 같은 것이 있다.

- bool is_empty(); // 스택이 비어있는지 확인한다

- Data top(); // 스택에서 가장 최근에 추가된 자료를 확인한다

- int count(); // 스택에 저장된 자료의 수를 가져온다

스택은 일반적으로 두 가지 방법으로 구현한다. 하나는 배열을 이용하는 것이고, 다른 하나는 리스트 자료구조를 이용하는 것이다. JSCC 프로젝트에서는 배열 기반의 스택만 직접 구현해본다.

 

3.2) 스택 구현

스택을 다음과 같이 설계할 것이다.

- 정수형 자료를 보관하는 스택 클래스를 만든다.

- static const int MAX_STACK_SIZ; // 배열의 크기를 정할 상수

- int list[MAX_STACK_SIZ]; // 정수형 자료를 실제로 보관하는 배열 필드

- int _count; // 스택에 있는 자료의 수를 나타내는 필드

- void push(int data); // 스택에 데이터를 넣는 메서드

- int pop(); // 스택에서 데이터를 꺼내는 메서드

- int top() const; // 스택에 가장 최근에 추가된 데이터를 보는 메서드

- bool is_empty() const; // 스택이 비어있는지 확인하는 메서드

- bool is_full() const; // 스택이 가득 찼는지 확인하는 메서드

- int count() const; // 스택에 있는 자료의 수를 반환하는 메서드

다음은 이 설계를 바탕으로 실제로 구현한 Stack 클래스이다.

01_Stack.cpp

typedef std::string Exception; // 임시; 예외로 string 객체를 던진다

class Stack {

static const int MAX_STACK_SIZ = 10;

int list[MAX_STACK_SIZ];

int _count;

public:

Stack() : _count(0) {} // 스택의 크기를 반드시 0으로 설정해야 한다

void push(int data) { // 스택에 데이터를 넣는다

if (is_full()) { // 스택이 가득차 데이터를 넣을 수 없다면 예외 처리한다

throw Exception("스택이 가득 찼습니다.");

}

// 스택의 마지막에 데이터를 넣고 크기를 증가시킨다

list[_count++] = data;

}

int pop() { // 스택에서 데이터를 꺼낸다

if (is_empty()) { // 스택이 비어있다면 예외 처리한다

throw Exception("스택이 비어있습니다.");

}

// 스택의 크기를 감소시킨 후 마지막 데이터를 반환한다

return list[--_count];

}

int top() const { // 스택에 가장 최근에 추가된 데이터를 본다

if (is_empty()) { // 스택이 비어있다면 예외 처리한다

throw Exception("스택이 비어있습니다.");

}

return list[_count - 1]; // 스택의 마지막 데이터를 반환한다

}

// 스택이 가득 찼다면 true

bool is_full() const { return _count == MAX_STACK_SIZ; }

// 스택이 비어있다면 true

bool is_empty() const { return _count == 0; }

// 스택에 저장된 데이터의 수를 가져온다

int count() const { return _count; }

};

이와 같이 스택을 구현하고 이해할 수 있었다.

 

4. 복합 연산이 가능한 계산기

C언어를 공부했으므로 1+1, 2*8과 같은 단순한 연산이 가능한 계산기를 만들어본 경험이 있으리라 생각한다. 여기서는 복합 연산이 가능한 계산기를 다룬다. 예를 들어 우리가 프로그래밍을 하면서 변수에 값을 대입할 때 우리는 다음과 같은 복잡한 식을 사용할 수 있다.

value = is_prime(num) ? a + b * c : d / (e - g) % h;

프로그래밍을 어느 정도 공부하고 나면 이러한 연산이 당연히 가능하겠거니 하고 넘어가기 쉽지만, 실제로 이 과정은 생각보다 복잡하고 이해하는 데 노력을 요한다. 여기서는 복합 연산을 이해하고 실제 복합적 연산을 분석하는 계산기를 작성한다. 순서는 다음과 같다.

1. 1+1, 2-4, 6*7, 8/9와 같은 사칙 연산에 대해 동작하는 계산기를 만든다.

2. 식을 넘기면 이를 분석하여 어떤 순서로 연산해야 하는지 출력하는 프로그램을 만든다.

3. 연산 순서를 알고 있고 연산 결과를 알고 있으므로, 이를 이용해 연산한다.

 

4.1) 사칙 연산 계산기

일단 쉬워 보이는 사칙 연산 계산기부터 작성하자. 내가 공부했던 예제에서는 혼란을 막기 위해 한 자리 수의 정수만으로 연산을 하도록 가정하였으나, 여기서는 정수형의 범위를 벗어나지 않는 임의의 수에 대해 계산이 성립하도록 구현하는 것으로 하겠다. 입력에 대해 다음의 출력이 나오도록 만들자.

입력

출력

4

1+2

3-4

30*40

5

3

-1

1200

5

입력이 5줄인데 결과가 4줄인 건, 맨 위에 입력한 값은 우리가 몇 번 프로그램을 실행하는지를 결정하는 값이기 때문이다. 즉 맨 위에 입력된 4는 프로그램을 4번 수행하겠다는 의미다. 보통 프로그래밍 온라인 저지 사이트에서 자주 사용하는 방법인데, 혹 이에 관심이 생긴다면 온라인 저지라고 검색하면 여러 사이트가 나오니 프로그래밍에 자신 있는 사람은 도전해보는 것도 좋다.

뼈대 프로그램을 제시할 테니 빈 칸을 채워 프로그램을 완성하라. 이때 프로그램을 실행하여 식을 입력할 때 사이띄개 하지 않음에 주의하라.

02_basic4.cpp

#include <iostream>

typedef std::string Exception;

int calculate(const char *expr); // 넘겨받은 식을 계산하여 값을 반환한다

int main(void) {

try {

// 입력의 길이가 MAX_EXPR_LEN보다 큰 경우가

// 발생하지 않는다고 가정한다

const int MAX_EXPR_LEN = 256;

char expression[MAX_EXPR_LEN] = "";

int loop;

std::cin >> loop;

// loop 회수만큼 반복문을 수행한다

while (loop-- > 0) {

std::cout << "Enter expression: ";

std::cin >> expression;

std::cout << calculate(expression) << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

int calculate(char expr[]) { // 넘겨받은 식을 계산하여 값을 반환한다

/* implement it */

}

다음은 필자의 구현이다.

02_basic4.cpp

int calculate(const char *expr) { // 넘겨받은 식을 계산하여 값을 반환한다

char ch = *expr;

if (ch < '0' || '9' < ch) { // 입력의 처음이 숫자가 아니라면 예외 처리

throw Exception("타당하지 않은 입력입니다.");

}

int digit; // 자릿수를 저장할 임시 변수

// 왼쪽에 나타나는 수 획득

int left = 0;

for (ch = *expr; (ch = *expr) != '\0'; ++expr) { // 입력의 끝이 나타나기 전까지

if (ch < '0' || '9' < ch) { // 수가 아닌 문자가 나타나면 탈출

break;

}

digit = ch - '0'; // 수를 올바른 정수로 바꾼다(문자 '0'은 정수 48과 같다)

left = 10 * left + digit;

}

if (ch == '\0') { // 연산자가 나타나기 전에 입력이 끝났다면

return left; // 문장의 끝으로 간주하고 획득한 수만 반환

}

// 연산자 획득: 사칙 연산에 대해서만 다루므로 연산자 길이는 반드시 1

char op = *expr++; // 문자열 포인터가 가리키는 연산자를 획득 후 포인터 이동

// 오른쪽에 나타나는 수 획득: 왼쪽의 경우와 같다

int right = 0;

for (ch = *expr; (ch = *expr) != '\0'; ++expr) { // 입력의 끝이 나타나기 전까지

if (ch < '0' || '9' < ch) { // 수가 아닌 문자가 나타나면 탈출

break;

}

digit = ch - '0'; // 수를 올바른 정수로 바꾼다(문자 '0'은 정수 48과 같다)

right = 10 * right + digit;

}

// 획득한 값과 연산자를 이용하여 연산

int retVal = 0;

switch (op) {

case '+': retVal = left + right; break;

case '-': retVal = left - right; break;

case '*': retVal = left * right; break;

case '/': retVal = left / right; break;

default: throw Exception("올바른 연산자가 아닙니다.");

}

return retVal;

}

이와 같이 사칙 연산 계산기를 간단하게 만들 수 있었다.

 

4.2) 복합 연산 식의 분석

여기서는 복합 연산에 대해 다룬다. 혹시 위의 사칙 연산 문제를 해결하면서 복합 연산식도 간단히 해결할 수 있다고 생각했는가? 그렇다면 직접 프로그램을 만들어보고 다음의 입력에 대해 결과를 잘 출력하는지 확인해보는 것이 좋다.

입력

출력

4

1+2+3

1+2*3+4

3*(2+3)

(1+2)*(3+4)+5/6

6

11

15

21

첫 번째 식에 대해서는, 고민하다보면 그저 이전에 연산한 결과를 기록하고 연산자와 피연산자를 찾아 새롭게 연산한 값을 저장하는 행위를 반복하면 된다는 사실을 알 수 있다. 그러면 두 번째 식을 보자. 식의 결과가 13이라고 생각했는가? 그렇다면 계산 과정에서 연산자의 우선순위가 고려되지 않았을 것이다. 사칙연산에선 곱셈과 나눗셈이 덧셈과 뺄셈보다 우선순위가 높으며, 따라서 우리는 2*3을 먼저 계산한 후에 1을 더하고 4를 더해야 한다. 왜 이 경우는 순서가 중요한가? 바로 우선순위가 다른 연산자가 섞여있기 때문이다. 따라서 우리는 식을 분석하는 과정에서 이전에 획득한 연산자의 우선순위와 분석 도중에 새롭게 획득한 연산자의 우선순위를 서로 비교하여, 우선순위가 상대적으로 높은 연산자가 발견된다면 이전의 연산자를 이용한 연산을 일단 뒤로 미룬 다음, 우선순위가 높은 연산자의 연산을 먼저 수행한 다음 처리하지 않았던 연산을 수행해야 한다.

이 과정에서 스택을 이용할 수 있다. 잘 알려진 알고리즘은 다음과 같다.

1. 입력 받은 중위 표기식(infix expression)을 후위 표기식(postfix expression)으로 변환한 후, 변환한 후위 표기식을 해석한다.

2. 중위 표기식을 수식 트리 자료구조로 표현한 후, 수식 트리를 해석한다.

3. 함수의 호출과 반환이 스택과 같으므로, 함수 호출만으로 해석한다.

일반적인 컴파일러는 2번 방법, 즉 수식 트리를 이용하여 식을 표현하고 해석한다. 재귀적 사고에 능숙하다면 3번도 재미있는 해결책이다. 이 문서에서는 1번 방법을 이용하여 먼저 계산기를 구현할 것인데, 그 이유는 이해하기 쉽고 스택 자료구조를 연습하는 데 도움이 되기 때문이다. 하지만 그 전에 알아두어야 하는 개념이 몇 가지 있는데 이를 이해하고 넘어가자.

 

4.2.1) 식의 표현

수식을 표현하는 방법 중에 연산자의 위치를 기준으로 하는 방법이 있다.

- 전위 표기법(prefix notation) : 연산자가 피연산자 앞에 위치한다. (ex: + 1 2)

- 중위 표기법(infix notation) : 연산자가 피연산자 사이에 위치한다. (ex: 1 + 2)

- 후위 표기법(postfix notation) : 연산자가 피연산자 뒤에 위치한다. (ex: 1 2 +)

이 중에 우리에게 익숙한 표기법은 중위 표기법인데, 위에서 말했지만 연산자의 우선순위가 달라 이대로 분석하기는 어렵다. 그렇다면 후위 표기법은 어떨까? 연산자의 위치가 뒤에 있다는 사실은 알고 있는데 이것만으로 연산자의 우선순위에 관한 문제를 해결할 수 있을까?

먼저 이 후위 표기법이라는 것을 직접 사용해보자. 다음과 같은 중위 표기식이 있다.

1 + 2

위에서도 예시로 보였지만 이 식을 후위 표기법으로 표현하면 다음과 같다.

1 2 +

그렇다면 다음은 어떻게 후위 표기법으로 표기할까?

1 + 2 + 3

이는 각각의 연산을 치환하면 이해하기 쉽다. 먼저 실수 A, B에 대해 다음이 성립한다.

A + B = A B +

따라서 (1 + 2 = A)로 놓으면 다음이 성립한다.

1 + 2 + 3 = A + 3 = A 3 +

이때 (A = 1 2 +)이므로 다음이 성립함을 보일 수 있다.

1 + 2 + 3 = A 3 + = 1 2 + 3 +

그러면 다음 식은 어떨까?

1 + 2 * 3

먼저 우선순위가 높은 곱셈식부터 문자로 치환해보자. (2 * 3 = A)라고 하면 다음이 성립한다.

1 + 2 * 3 = 1 + A = 1 A +

이때 (A = 2 3 *)이므로 다음이 성립한다.

1 + 2 * 3 = 1 A + = 1 2 3 * +

이와 같은 방법으로 다음의 식들을 모두 후위 표기법으로 표기할 수 있다.

1 + 2 + 3 = 1 2 + 3 +

1 * 2 + 3 = 1 2 * 3 +

1 + 2 * 3 = 1 2 3 * +

1 * 2 * 3 = 1 2 * 3 *

1 + 2 - 3 + 4 = 1 2 + 3 - 4 +

1 + 2 * 3 + 4 = 1 2 3 * + 4 +

(1 + 2) * (3 - 4) = 1 2 + 3 4 - *

5 * (6 + 7 + 8) - 7 * 9 = 5 6 7 + 8 + * 7 9 * -

그러면 이제 변환한 후위 표기식이 잘 변환되었는지 확인해보자. 후위 표기법으로 표현한 식을 다시 중위 표기법으로 표현하는 것이다. 이 또한 전혀 어렵지 않은데, 왜냐하면 방금 우리가 했던 과정을 순서만 바꾸어서 다시 수행하면 되기 때문이다.

위에서 후위 표기법으로 표현된 식을 다시 중위 표기법으로 표현해보자. 왼쪽부터 분석한다.

1 2 + 3 +

이때 (1 2 + = A)로 놓으면 다음이 성립한다.

1 2 + 3 + = A 3 + = A + 3

또한 (A = 1 + 2)가 성립하므로 다음이 성립한다.

1 2 + 3 + = A + 3 = 1 + 2 + 3

이와 같이 역변환이 성립함을 보일 수 있다. 다른 예제를 보자.

1 2 3 * +

이때 (2 3 * = A)로 놓으면 다음이 성립한다.

1 2 3 * + = 1 A + = 1 + A

또한 (A = 2 * 3)이 성립하므로 다음이 성립한다.

1 2 3 * + = 1 + A = 1 + 2 * 3

이와 같이 임의의 식을 후위 표기법, 중위 표기법으로 변환하는 방법을 알아보았다. 그런데 아직 당신은 왜 후위 표기법으로 표현된 식이 중위 표기법으로 표현된 식보다 분석하기 쉬운지에 대한 설명은 듣지 못했다. 정확히 무엇이 더 나아진 것일까?

다음 후위 표기식의 피연산자를 무시하고 연산자만 뜯어서 왼쪽부터 차례로 읽어보라.

1 + 2 + 3 = 1 2 + 3 + : + +

1 * 2 + 3 = 1 2 * 3 + : * +

1 + 2 * 3 = 1 2 3 * + : * +

1 * 2 * 3 = 1 2 * 3 * : * *

1 + 2 - 3 + 4 = 1 2 + 3 - 4 + : + - +

1 + 2 * 3 + 4 = 1 2 3 * + 4 + : * + +

(1 + 2) * (3 - 4) = 1 2 + 3 4 - * : + - *

5 * (6 + 7 + 8) - 7 * 9 = 5 6 7 + 8 + * 7 9 * - : + + * * -

연산자만 뜯어서 왼쪽부터 차례로 살펴보면 아주 재미있는 사실을 발견할 수 있는데, 바로 연산자가 식에서 먼저 연산이 진행되어야 하는 순서로, 즉 높은 우선순위부터 낮은 우선순위로 연산자가 정렬되어 있다는 것이다. 후위 표기법으로 표현된 식에는 연산자의 우선순위에 대한 정보가 이미 포함되어있다. 즉 후위 표기법으로 표현된 식을 분석할 때는 연산자의 우선순위를 고려할 필요가 없다. 바로 이 점 때문에 중위 표기식보다 후위 표기식이 분석하기 수월하다.

이와 같이 후위 표기식이 중위 표기식보다 분석하기 쉬운 이유를 알 수 있었다.

 

4.2.2) 표기법 변환을 위한 스택의 활용

식을 중위 표기법에서 후위 표기법으로 변환하는 과정은 다음과 같이 진행된다.

1. 피연산자라면 후위 표기식의 끝에 추가한다.

2. 연산자라면? -> ‘연산자 보관소의 상태를 확인한다.

2.1) ‘연산자 보관소에 저장된 연산자가 없다면 추가한다.

2.2) ‘연산자 보관소에 저장된 연산자가 있다면? -> 연산자의 우선순위를 비교한다.

2.2.1) 보관소에 마지막으로 저장된 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내 후위 표기식의 끝에 추가하고 새 연산자를 보관소에 저장한다.

2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 저장한다.

2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내 후위 표기식의 끝에 추가하고 새 연산자를 보관소에 저장한다.

3. 1~2 과정을 반복한다.

4. 분석이 끝나면 보관소에 남은 모든 연산자를 후위 표기식에 추가한 후 후위 표기식을 반환하고 종료한다.

이를 위해 스택을 활용할 수 있다.

1. 피연산자라면 후위 표기식배열의 끝에 추가한다.

2. 연산자라면? -> ‘연산자 스택의 상태를 확인한다.

2.2.1) 스택의 최상위 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여 후위 표기식의 끝에 추가하고 새 연산자를 스택에 푸시 한다.

2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 푸시 한다.

2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여 후위 표기식의 끝에 추가하고 새 연산자를 스택에 푸시 한다.

3. 1~2 과정을 반복한다.

4. 분석이 끝나면 스택에 남은 모든 연산자를 후위 표기식에 추가한 후 후위 표기식을 반환하고 종료한다.

다음은 스택을 활용하여 중위 표기식을 후위 표기식으로 변환하는 예제이다. 소괄호에 대한 처리는 아직 설명하지 않았으므로 적용하지 않았다.

03_in_to_post.cpp

#include <iostream>

typedef std::string Exception;

// 공용 함수

inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); }

// 스택 정의

typedef char Data;

class Stack {

static const int MAX_STACK_SIZ = 256;

Data _list[MAX_STACK_SIZ];

int _count;

private:

inline bool is_full() const { return _count == MAX_STACK_SIZ; }

public:

Stack() : _count(0) {}

void push(const Data &data) {

if (is_full()) throw Exception("Stack is full");

_list[_count++] = data;

}

Data pop() {

if (is_empty()) throw Exception("Stack is empty");

return _list[--_count];

}

Data top() const {

if (is_empty()) throw Exception("Stack is empty");

return _list[_count - 1];

}

inline bool is_empty() const { return _count == 0; }

inline int count() const { return _count; }

};

// 사용할 함수

int op_pri(char ch); // get operator's priority

// convert infix notation expression

// to postfix notation expression

void infix_to_postfix(char *postfix, const char *infix);

int main(void) {

try {

int loop;

std::cin >> loop;

const int MAX_EXPR_LEN = 256;

char infix[MAX_EXPR_LEN] = "";

char postfix[MAX_EXPR_LEN] = "";

while (loop-- > 0) {

std::cout << "Enter expression: ";

std::cin >> infix;

infix_to_postfix(postfix, infix);

std::cout << infix << " : " << postfix << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

// 구현

int op_pri(char ch) { // get operator's priority

int priority = 0;

switch (ch) {

case '+': priority = 1; break;

case '-': priority = 1; break;

case '*': priority = 2; break;

case '/': priority = 2; break;

default: throw Exception("Invalid operator");

}

return priority;

}

void infix_to_postfix(char *postfix, const char *infix) {

// convert infix notation expression

// to postfix notation expression

if (is_digit(*infix) == false)

throw Exception("Invalid infix notation expression");

char ch;

Stack opStack; // operator stack

for (ch = *infix; (ch = *infix) != '\0'; ++infix) {

if (is_digit(ch)) {

while (is_digit(*infix)) {

*postfix++ = *infix++;

}

--infix;

}

else { // is_operator

if (opStack.is_empty() == false) {

// get operator priority

int new_pri = op_pri(ch);

while (opStack.is_empty() == false) {

if (new_pri <= op_pri(opStack.top())) {

*postfix++ = opStack.pop();

}

else {

break;

}

}

}

opStack.push(ch);

}

}

// 스택에 남은 연산자를

while (opStack.is_empty() == false) {

char op = opStack.pop();

*postfix++ = op;

}

*postfix = '\0';

}

 

4.2.3) 소괄호 문제

이제 소괄호를 생각해보자. 다음 중위 표기식을 후위 표기식으로 변환해보라.

1 + 2 * 3

(1 + 2) * 3

1 * (2 + 3)

답은 다음과 같다.

1 + 2 * 3 = 1 2 3 * +

(1 + 2) * 3 = 1 2 + 3 *

1 * (2 + 3) = 1 2 3 + *

알고 있듯이, 소괄호는 중위 표기법으로 표현된 식에서는 연산 순서를 강제로 바꾸는 용도로 쓰인다. 따라서 소괄호가 발견된다면, 이전에 어떤 연산자가 존재하든 관계없이 소괄호가 씌워진 식부터 연산을 진행해야 한다. 4.2.2)2번 루틴에는 다음 과정이 추가되어야 한다.

1. 여는 소괄호를 만나면, 연산자 보관소에 어떤 연산자가 존재하든 관계없이 여는 소괄호를 보관소에 저장한다.

2. 닫는 소괄호를 만나면, 연산자 보관소에 가장 마지막으로 저장된 여는 소괄호를 발견할 때까지의 모든 연산자를 후위 표기식에 출력한다.

다음은 소괄호 문제가 개선된 표기법 변환 프로그램이다.

04_in_to_post_paren.cpp

void infix_to_postfix(char *postfix, const char *infix) {

// 첫 문자가 수인지 확인하는 코드 삭제

char ch;

Stack opStack; // operator stack

for (ch = *infix; (ch = *infix) != '\0'; ++infix) {

if (is_digit(ch)) {

while (is_digit(*infix)) {

*postfix++ = *infix++;

}

--infix; // 반복문 재실행시 ++infix가 실행되므로 한 칸 되돌린다

}

else { // is_operator

if (ch == '(') { // 여는 괄호라면 그냥 넣는다

opStack.push(ch);

}

else if (ch == ')') { // 닫는 괄호를 발견한 경우의 처리

if (opStack.is_empty() == false) {

// get operator priority

while (opStack.is_empty() == false) {

char top = opStack.top();

if (top == '(') { // 여는 괄호를 찾았다면 종료

break;

}

else {

// 우선순위가 낮은 연산자를 스택에서 꺼내

// 후위 표기식에 추가

*postfix++ = opStack.pop();

}

}

// 올바른 괄호 쌍이 존재하는지 확인

if (opStack.top() != '(') {

throw Exception("Invalid parenthesis");

}

// 스택에 있는 여는 소괄호를 버린다

opStack.pop();

}

}

else {

if (opStack.is_empty() == false) {

// get operator priority

int new_pri = op_pri(ch);

while (opStack.is_empty() == false) {

char top = opStack.top();

if (top == '(') { // 여는 괄호를 찾았다면 종료

break;

}

else if (new_pri <= op_pri(top)) {

*postfix++ = opStack.pop();

}

else {

break;

}

}

}

opStack.push(ch);

}

}

}

// 스택에 남은 연산자를

while (opStack.is_empty() == false) {

char op = opStack.pop();

if (op == '(') { // 위에서 처리되지 않은 소괄호가 있다면 예외

throw Exception("Invalid parenthesis");

}

*postfix++ = op;

}

*postfix = '\0';

}

이와 같이 소괄호 문제를 해결할 수 있었다.

 

4.2.4) 후위 표기식 분석을 위한 스택의 활용

후위 표기식의 분석은 다음과 같이 진행된다.

1. 피연산자라면 저장한다.

2. 연산자라면 가장 최근에 저장한 두 피연산자와 연산자를 이용하여 연산한 후 다시 저장한다.

3. 1~2 과정을 반복한다.

4. 분석이 끝나면 유일하게 남은 피연산자 하나를 반환하고 종료한다.

이를 위해 스택을 활용할 수 있다.

1. 피연산자 스택을 만들어둔다.

2. 피연산자라면 스택에 푸시 한다.

3. 연산자라면 스택에서 두 피연산자를 팝 하여 연산한 후, 연산 결과를 다시 푸시 한다.

4. 분석이 끝나면 유일하게 스택에 남은 피연산자 하나를 팝하고 종료한다.

스택을 활용하여 후위 표기식을 분석하는 예제를 보이겠다. 이때 입력에 사이띄개 해야 함에 주의하라. 즉 다음과 같이 입력해야 결과가 제대로 나온다.

입력

출력

4

1 2 +

1 2 + 3 +1 2 3 * +

12 34 +

1 2 + : 3

1 2 + 3 + : 6

1 2 3 * + : 7

12 34 + : 46

스택 클래스의 정의가 템플릿을 이용하여 변경되었음에 유의하라.

05_read_postfix.cpp

#include <iostream>

typedef std::string Exception;

// 공용 함수

inline void clear_input_buffer() { // 입력받기 전에 입력 버퍼를 비운다

std::cin.clear();

std::cin.ignore(std::cin.rdbuf()->in_avail());

}

inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); }

// 문자가 공백인지 확인한다

inline bool is_space(char ch) { return (ch == ' ' || ch == '\t' || ch == '\n'); }

// 스택 정의

template <typename Data> // 형식에 자유로운 스택을 만들기 위해 템플릿 클래스로 변경

class Stack { /* ... */ };

// 사용할 함수

int calculate_postfix(const char *postfix); // calculate postfix expression

int main(void) {

try {

int loop;

std::cin >> loop;

const int MAX_EXPR_LEN = 256;

char postfix[MAX_EXPR_LEN] = "";

while (loop-- > 0) {

std::cout << "Enter expression: ";

clear_input_buffer();

std::cin.getline(postfix, MAX_EXPR_LEN); // 공백을 포함한 줄을 입력받는다

std::cout << postfix << " : ";

std::cout << calculate_postfix(postfix) << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

 

// 구현

int calculate_postfix(const char *postfix) {

char ch;

int digit;

Stack<int> paramStack;

for (ch = *postfix; (ch = *postfix) != '\0'; ++postfix) {

if (is_space(ch)) { // 공백이면 무시한다

continue;

}

else if (is_digit(ch)) { // 피연산자라면 스택에 푸시 한다

int value = 0;

while (is_digit(*postfix)) {

digit = *postfix++ - '0';

value = 10 * value + digit;

}

paramStack.push(value);

--postfix; // 반복문 재실행시 ++postfix가 실행되므로 한 칸 되돌린다

}

else {

// 스택에서 두 개의 피연산자를 꺼낸다

int right = paramStack.pop();

int left = paramStack.pop();

int value = 0;

// 획득한 연산자로 연산한다

switch (ch) {

case '+': value = left + right; break;

case '-': value = left - right; break;

case '*': value = left * right; break;

case '/': value = left / right; break;

default: throw Exception("Invalid operator");

}

// 연산 결과를 다시 스택에 넣는다

paramStack.push(value);

}

}

if (paramStack.count() != 1) { // 스택에 남은 피연산자가 1개가 아니면 예외

throw Exception("Unhandled operand found");

}

return paramStack.pop(); // 하나 남은 피연산자를 반환한다

}

이와 같이 후위 표기식을 분석할 수 있었다. 중위 표기식을 후위 표기식으로 변환하는 프로그램, 후위 표기식을 분석하고 계산하는 프로그램을 만들었으므로, 남은 일은 두 프로그램을 하나로 합치는 일이다. 어렵지 않으므로 예제 코드는 이 문서에 싣지 않으나, 혹 궁금할 사람들을 위해 코드는 첨부하겠다.

 

5. 문자열 버퍼

5.1) 이대로 괜찮을까?

필자가 작성한 코드 중에 아래와 같은, 문자열에서 수를 읽어내는 코드가 있다.

07_conversion.cpp

#include <iostream>

// 공용 정의

const int MAX_EXPR_LEN = 256;

typedef std::string Exception;

// 공용 함수

inline void clear_input_buffer() { // 입력받기 전에 입력 버퍼를 비운다

std::cin.clear();

std::cin.ignore(std::cin.rdbuf()->in_avail());

}

inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); }

inline bool is_space(char ch) { return (ch == ' ' || ch == '\t' || ch == '\n'); }

// 정수와 연산자 사이에 사이띄개를 넣어 출력하는 프로그램

int main(void) {

try {

char expression[MAX_EXPR_LEN] = "";

std::cin >> expression;

char ch;

char *expr = expression;

// 문자열의 모든 문자 탐색

for (ch = *expr; (ch = *expr) != '\0'; ++expr) {

if (is_digit(ch)) { // 수가 발견된다면 정수 획득

int digit = 0; // 자리수를 임시로 저장할 변수

int value = 0; // 최종적으로 획득할 정수를 저장할 변수

while (is_digit(*expr)) { // 숫자를 획득하는 동안 value 갱신

digit = *expr++ - '0';

value = 10 * value + digit;

}

--expr; // 반복문 재실행 시 ++expr이 수행되므로 한 칸 되돌린다

std::cout << value << ' '; // 획득한 정수를 출력하고 뒤에 공백을 추가

}

else { // 수가 아닌 문자의 경우 출력하고 공백으로 띄운다

std::cout << ch << ' ';

}

}

std::cout << std::endl;

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

문제없이 잘 동작한다. 이대로라면 나쁘지 않은 것 같은데? 그렇게 생각한다면 문제를 내겠다. 아래에 수의 제곱, 두 수의 곱, 부피를 구하는 함수가 비어있다. 이를 구현해보라.

08_conversion_skeleton.cpp

#include <iostream>

// 공용 정의

const int MAX_EXPR_LEN = 256;

typedef std::string Exception;

// 공용 함수

inline void clear_input_buffer() { // 입력받기 전에 입력 버퍼를 비운다

std::cin.clear();

std::cin.ignore(std::cin.rdbuf()->in_avail());

}

inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); }

inline bool is_space(char ch) { return (ch == ' ' || ch == '\t' || ch == '\n'); }

// 사용 함수

int get_square(const char *ns); // 문자열을 정수로 변환하고 그 제곱을 반환

// 두 문자열을 정수로 변환하고 그 곱을 반환

int get_mul(const char *ns1, const char *ns2);

int get_volume(const char *x, const char *y, const char *z); // 부피 계산 후 반환

int main(void) {

try {

char input1[MAX_EXPR_LEN], input2[MAX_EXPR_LEN], input3[MAX_EXPR_LEN];

std::cout << "Enter number: ";

std::cin >> input1;

std::cout << "Enter number: ";

std::cin >> input2;

std::cout << "Enter number: ";

std::cin >> input3;

std::cout << get_square(input1) << std::endl;

std::cout << get_mul(input1, input2) << std::endl;

std::cout << get_volume(input1, input2, input3) << std::endl;

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

// 구현

int get_square(const char *ns) { // 문자열을 정수로 변환하고 그 제곱을 반환

/* implement it */

}

// 두 문자열을 정수로 변환하고 그 곱을 반환

int get_mul(const char *ns1, const char *ns2) {

/* implement it */

}

int get_volume(const char *xs, const char *ys, const char *zs) { // 부피 계산 후 반환

/* implement it */

}

필자의 구현은 다음과 같다.

09_conversion_implementation.cpp

int get_square(const char *ns) { // 문자열을 정수로 변환하고 그 제곱을 반환

int digit = 0;

int value = 0;

char ch;

for (ch = *ns; (ch = *ns) != '\0'; ++ns) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

value = 10 * value + digit;

}

return value * value;

}

int get_mul(const char *ns1, const char *ns2) { // 두 문자열을 정수로 변환하고 그 곱을 반환

int digit = 0;

int left = 0;

char ch;

for (ch = *ns1; (ch = *ns1) != '\0'; ++ns1) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

left = 10 * left + digit;

}

int right = 0;

for (ch = *ns2; (ch = *ns2) != '\0'; ++ns2) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

right = 10 * right + digit;

}

return left * right;

}

int get_volume(const char *xs, const char *ys, const char *zs) { // 부피 계산 후 반환

int digit = 0;

int x = 0;

char ch;

for (ch = *xs; (ch = *xs) != '\0'; ++xs) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

x = 10 * x + digit;

}

int y = 0;

for (ch = *ys; (ch = *ys) != '\0'; ++ys) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

y = 10 * y + digit;

}

int z = 0;

for (ch = *zs; (ch = *zs) != '\0'; ++zs) {

if (is_digit(ch) == false) {

throw Exception("Invalid number");

}

digit = ch - '0';

z = 10 * z + digit;

}

return x * y * z;

}

 

무엇이 문제인지 알겠는가? 바로 문자열을 정수로 변환하는 코드가 지나치게 중복적이라는 것이다. 알고 있겠지만, 이렇게 코드를 작성하면 가독성이 떨어지고, 코드 하나가 잘못되었거나 후에 업데이트해야 하는 경우, 이렇게 작성한 모든 코드를 전부 찾아내 수정해야 하므로 유지 및 보수에 애로사항이 꽃피게 된다. 어떻게 해결해야할까?

여기서 우리는 atoi 함수처럼, 문자열에서 정수를 긁어내는 함수를 작성해볼 수 있다.

10_atoi.cpp

int ascii_to_int(const char *ns) { // 문자열을 정수로 변환하고 그 값을 반환

// 중요: 정수가 아닌 문자가 나타날 때까지 분석을 진행한다

int digit = 0;

int value = 0;

char ch;

for (ch = *ns; (ch = *ns) != '\0'; ++ns) {

if (is_digit(ch) == false) {

break;

}

digit = ch - '0';

value = 10 * value + digit;

}

return value;

}

int get_square(const char *ns) { // 문자열을 정수로 변환하고 그 제곱을 반환

int value = ascii_to_int(ns);

return value * value;

}

int get_mul(const char *ns1, const char *ns2) { // 두 문자열을 정수로 변환하고 그 곱을 반환

int left = ascii_to_int(ns1), right = ascii_to_int(ns2);

return left * right;

}

int get_volume(const char *xs, const char *ys, const char *zs) { // 부피 계산 후 반환

return ascii_to_int(xs) * ascii_to_int(ys) * ascii_to_int(zs);

}

세 함수의 코드 길이가 크게 줄었음을 볼 수 있다. 또한 함수 이름이 함수가 하는 내용을 암시하고 있으므로, 함수 내부를 들여다보았을 때 내부적으로 어떻게 동작하는지를 이해하기도 쉽다. 이렇듯 문자열로부터 정수를 긁어내는 작업은 코드 길이가 길고 반복적으로 사용되기 때문에 반드시 뜯어내야 한다.

정수를 획득하는 코드를 뜯어내야 한다는 사실을 알았으니, 이것이 적용되지 않은 이전의 예제들도 수정해야 한다는 생각이 든다. 옳은 판단이고 지금 바로 예제를 수정해보려 한다. 초반에 작성했던 사칙 연산 계산기 예제부터 수정해볼까? 다음은 atoi를 이용하여 사칙 연산을 개선한 예제다.

11_basic4_atoi.cpp

int calculate(const char *expr) { // 넘겨받은 식을 계산하여 값을 반환한다

if (is_digit(*expr) == false) { // 입력의 처음이 숫자가 아니라면 예외 처리

throw Exception("타당하지 않은 입력입니다.");

}

int left = ascii_to_int(expr); // 왼쪽에 나타나는 수 획득

while (is_digit(*expr)) { ++expr; } // 정수가 아닐 때까지 expr를 이동한다

if (*expr == '\0') { // 입력이 끝났다면 획득한 정수를 반환하고 종료

return left;

}

// 연산자 획득: 사칙 연산에 대해서만 다루므로 연산자 길이는 반드시 1

char op = *expr++; // 문자열 포인터가 가리키는 연산자를 획득 후 포인터 이동

int right = ascii_to_int(expr); // 오른쪽에 나타나는 수 획득

while (is_digit(*expr)) { ++expr; } // 정수가 아닐 때까지 expr를 이동한다

if (*expr != '\0') { // 입력이 아직 끝나지 않았다면 예외 발생

throw Exception("두 개의 피연산자로만 연산할 수 있습니다.");

}

// 획득한 값과 연산자를 이용하여 연산

int retVal = 0;

switch (op) {

case '+': retVal = left + right; break;

case '-': retVal = left - right; break;

case '*': retVal = left * right; break;

case '/': retVal = left / right; break;

default: throw Exception("올바른 연산자가 아닙니다.");

}

return retVal;

}

예제를 유심히 보면 이상한 부분이 있다. ascii_to_int 함수는 넘긴 문자열로부터 정수를 읽는 함수다. 즉 이미 정수를 읽었는데도 불구하고 문자열 포인터에서 다시 정수를 확인하며 지나기고 있다. 왜 같은 행위를 두 번이나 하는가? 우리가 이전에 작성했던 예제에서는 정수를 읽고 나면 포인터가 이동해있었는데, 왜 이 예제에서는 그렇지 않고 우리가 다시 포인터를 옮겨주어야 하는가?

그 이유는 아주 당연한데, 함수 호출 시에 인자를 넘길 때는 언제나 넘기려는 값의 사본이 넘어가기 때문이다. 포인터를 넘긴다면 포인터가 저장하는 값의 사본이, 참조를 넘긴다면 참조의 위치 값의 사본이 넘어간다. 위 예제에서는 expr 포인터를 넘겼으니 expr 포인터가 가리키는 문자 배열의 주소 값을 사본으로 전달했지만, 이것이 expr 포인터 변수의 주소는 아니라는 것이다. nsatoi 함수에서 정의된 지역 변수이고, exprcalculate 함수에서 정의된 지역 변수이다. 즉 두 변수에 대해 (ns == expr)은 성립하지만 (&ns == &expr)는 성립하지 않는다. expr의 값을 수정하려면 &expr 또한 함수의 인자로 넘겨야만 한다.

이 문제를 해결하려면 atoi의 인자로 expr의 주소도 같이 넘기던가, 아니면 atoi의 인자를 expr의 참조로 하던가 해야 한다. 결국 다음과 같은 식인데 어느 쪽도 그렇게 깔끔하지 않다.

12_atoi_alt.cpp

int ascii_to_int_adr(const char **ns_src) { // 문자열 포인터의 주소를 넘긴다

const char *ns = *ns_src; // 문자열 포인터가 가리키는 값을 획득한다

int digit = 0;

int value = 0;

char ch;

for (ch = *ns; (ch = *ns) != '\0'; ++ns) {

if (is_digit(ch) == false) {

break;

}

digit = ch - '0';

value = 10 * value + digit;

}

*ns_src = ns; // 분석이 끝나면 문자열 포인터 변수에 값을 대입한다

return value;

}

int ascii_to_int_ref(const char *&ns) { // 문자열 포인터의 참조를 넘긴다

int digit = 0;

int value = 0;

char ch;

for (ch = *ns; (ch = *ns) != '\0'; ++ns) {

if (is_digit(ch) == false) {

break;

}

digit = ch - '0';

value = 10 * value + digit;

}

return value;

}

int calculate(const char *expr) { // 넘겨받은 식을 계산하여 값을 반환한다

if (is_digit(*expr) == false) { // 입력의 처음이 숫자가 아니라면 예외 처리

throw Exception("타당하지 않은 입력입니다.");

}

int left = ascii_to_int_adr(&expr); // 왼쪽에 나타나는 수 획득 (주소)

if (*expr == '\0') { // 입력이 끝났다면 획득한 정수를 반환하고 종료

return left;

}

// 연산자 획득: 사칙 연산에 대해서만 다루므로 연산자 길이는 반드시 1

char op = *expr++; // 문자열 포인터가 가리키는 연산자를 획득 후 포인터 이동

int right = ascii_to_int_ref(expr); // 오른쪽에 나타나는 수 획득 (참조)

if (*expr != '\0') { // 입력이 아직 끝나지 않았다면 예외 발생

throw Exception("두 개의 피연산자로만 연산할 수 있습니다.");

}

// 획득한 값과 연산자를 이용하여 연산

int retVal = 0;

switch (op) {

case '+': retVal = left + right; break;

case '-': retVal = left - right; break;

case '*': retVal = left * right; break;

case '/': retVal = left / right; break;

default: throw Exception("올바른 연산자가 아닙니다.");

}

return retVal;

}

필자는 이에 대한 대안으로 문자열 버퍼 클래스 StringBuffer를 제안한다.

 

5.2.2) StringBuffer 클래스

StringBuffer 클래스는 문자열을 다루기 쉽도록 필자가 고안한 클래스다. StringBuffer 클래스의 인스턴스는 다음의 행위를 수행할 수 있다.

- init: 버퍼를 인자로 받은 문자열로 초기화한다

- getc: 버퍼로부터 문자를 하나 가져온다

- ungetc: 버퍼에서 읽었던 값을 되돌린다

- add: 버퍼의 끝에 문자 또는 문자열을 추가한다

- is_empty: 버퍼가 비어있는지 확인한다

다음은 StringBuffer 클래스를 구현한 것이다.

StringBuffer.h

#ifndef __HANDY_STRINGBUFFER_H__

#define __HANDY_STRINGBUFFER_H__

 

#include <string>

class StringBuffer {

std::string str;

unsigned len;

unsigned idx;

 

public:

StringBuffer(const char *s = "");

StringBuffer(const std::string &str);

~StringBuffer();

 

// 버퍼를 문자열로 초기화합니다.

void init(const char *str);

void init(const std::string &str);

 

// 버퍼로부터 문자를 하나 읽습니다. 포인터가 이동합니다.

char getc();

// 버퍼의 포인터가 가리키는 문자를 가져옵니다. 포인터는 이동하지 않습니다.

char peekc() const;

// 버퍼에서 읽었던 값을 되돌립니다. 되돌릴 수 없으면 false를 반환합니다.

bool ungetc();

 

// 버퍼의 끝에 문자 또는 문자열을 추가합니다.

void add(char c);

void add(const char *s);

void add(const std::string &str);

 

// 버퍼가 비어있다면 true, 값을 더 읽을 수 있다면 false를 반환합니다.

bool is_empty() const;

};

 

#endif

StringBuffer.cpp

#include "StringBuffer.h"

#include <string>

typedef std::string Exception;

StringBuffer::StringBuffer(const char *s) : str(s), idx(0) { this->len = this->str.length(); }

StringBuffer::StringBuffer(const std::string &str) : str(str), idx(0) { this->len = this->str.length(); }

StringBuffer::~StringBuffer() {}

void StringBuffer::init(const char *str) {

this->str = str;

this->idx = 0;

this->len = this->str.length();

}

void StringBuffer::init(const std::string &str) {

this->str = str;

this->idx = 0;

this->len = this->str.length();

}

char StringBuffer::getc() {

if (idx >= len) {

throw Exception("Buffer is empty");

}

return str[idx++];

}

char StringBuffer::peekc() const {

if (idx >= len) {

throw Exception("Buffer is empty");

}

return str[idx];

}

bool StringBuffer::ungetc() {

if (idx > 0) {

--idx;

return true;

}

else {

return false;

}

}

void StringBuffer::add(char c) {

this->str += c;

}

void StringBuffer::add(const char *s) {

this->str += s;

}

void StringBuffer::add(const std::string &str) {

this->str += str;

}

bool StringBuffer::is_empty() const {

return (idx >= len);

}

다음은 StringBuffer 클래스를 사용하는 예제이다.

13_StringBufferMain.cpp

#include <iostream>

#include "StringBuffer.h"

typedef std::string Exception;

int main(void) {

try {

StringBuffer buffer;

buffer.init("Hello, world!");

while (buffer.is_empty() == false) {

std::cout << buffer.getc() << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

그리고 이를 이용하여 사칙 연산 계산기를 다시 작성할 수 있다.

14_basic4_StringBuffer.cpp

int ascii_to_int(StringBuffer &buffer) { // 문자열을 정수로 변환하고 그 값을 반환

int digit = 0;

int value = 0;

char ch;

while (buffer.is_empty() == false) {

if (is_digit(ch = buffer.getc()) == false) {

buffer.ungetc(); // 아직 읽지 않은 값이므로 되돌린 후 탈출한다

break;

}

digit = ch - '0';

value = 10 * value + digit;

}

return value;

}

int calculate(const char *expr) { // 넘겨받은 식을 계산하여 값을 반환한다

StringBuffer buffer(expr);

if (is_digit(buffer.peekc()) == false) { // 입력의 처음이 숫자가 아니라면 예외

throw Exception("타당하지 않은 입력입니다.");

}

int left = ascii_to_int(buffer); // 왼쪽에 나타나는 수 획득

if (buffer.is_empty()) { // 입력이 끝났다면 획득한 정수를 반환하고 종료

return left;

}

// 연산자 획득: 사칙 연산에 대해서만 다루므로 연산자 길이는 반드시 1

char op = buffer.getc(); // 문자열 포인터가 가리키는 연산자를 획득 후 포인터 이동

int right = ascii_to_int(buffer); // 오른쪽에 나타나는 수 획득

if (buffer.is_empty() == false) { // 입력이 아직 끝나지 않았다면 예외 발생

throw Exception("두 개의 피연산자로만 연산할 수 있습니다.");

}

// 획득한 값과 연산자를 이용하여 연산

int retVal = 0;

switch (op) {

case '+': retVal = left + right; break;

case '-': retVal = left - right; break;

case '*': retVal = left * right; break;

case '/': retVal = left / right; break;

default: throw Exception("올바른 연산자가 아닙니다.");

}

return retVal;

}

독자 중엔 StringBuffer 클래스가 이전과 크게 편의성에서 차이가 나지 않는다고 생각하는 사람도 있을 것이다. 그 경우에는 자신이 원하는 방법으로 진행하면 된다. 사실 StringBuffer 클래스는 완성된 클래스가 아니고, 프로젝트를 진행하면서 기능을 추가하여, 이 클래스가 없이 작업하는 것을 상상할 수 없을 정도로 만들 것이다. 이와 같이 StringBuffer 클래스를 활용하고 이해할 수 있었다.


6. 단원 마무리

원래는 1단원의 마지막을 변수 처리가 가능한 복합 연산 계산기로 하려고 했는데, 아무래도 1단원에서 설명하기 지나치게 복잡한 감이 없지 않아 있어서 뒤로 미루었다. 스택에 대해 설명하였으나 이전에 설명해본 적이 있는 것도 그림이 첨부되어있는 것도 아니어서, 스택이라는 자료구조를 처음 접한 사람에게는 상당히 어려운 시작이었을 거라는 생각이 들어 안타깝다. 복합 연산 계산기 또한 스택을 이미 알고 있는 사람이라도 헷갈리기 쉬운 내용이라 설명이 잘 되었을지 걱정이 앞선다. 여기까지 따라왔다면 정말 열심히 이 문서를 읽은 것이고 칭찬 받아야 마땅하다고 생각한다(내 글을 읽은 걸 칭찬해야 한다고 쓰니 웃기는 일이지만). 아직 이해가 되지 않았다면 윤성우 저 열혈 자료구조를 참고하면 좋을 것이라 생각한다. 쉬운 설명과 그림이 곁들여져있는 아주 좋은 책이다.

Posted by 누아니
,