6. Writing a Program

6.1. A problem

프로그램을 만드는 것은 문제를 해결하는 것이다. 좋은 프로그램이란 어떤 것인가?

  • 설계와 프로그래밍 기법을 실증하는 것
  • 프로그래머가 어떤 결정을 했는지와 왜 그런 결정을 했는지를 보여주는 것
  • 지나치게 많은 프로그래밍 언어 기법을 도입하지 않는 것
  • 설계에 대해 충분히 생각해야 할 만큼은 복잡한 것
  • 여러 해법을 도입할 수 있는 것
  • 쉽게 이해할 수 있는 문제를 해결하는 것
  • 풀 가치가 있는 문제를 해결하는 것
  • 완전히 표현되고 완전히 이해될 수 있는 만큼 간결한 해법을 제시하는 것

이 장에서는 이를 알아보기 위해 사칙연산 계산기 프로그램을 만들어보기로 한다.

6.2. Thinking about the problem

문제를 해결하기 위해서는 첫째로는 프로그램이 어떤 일을 해야 하는지를 생각하고 둘째로는 그를 위해 프로그래밍을 어떻게 해야 하는지를 생각하면 된다. 안타갑게도 모든 문제와 모든 사람에게 적용될 수 있는 일반적인 문제 해결 기법은 없다. 해법까지 도달하는 과정도 최종 해법만큼이나 중요함을 명심하자.

6.2.1. Stages of development

개발의 단계는 다음과 같다:

  • 분석 : 어떤 것을 해야 하는지와 자신이 어떻게 이해하고 있는지를 분석하자.
  • 설계 : 시스템의 전체적인 구조를 설계하고, 구현의 어떤 부분이 어떤 일을 할지, 그 부분들끼리는 어떻게 통신해야 할지를 결정한다.
  • 구현 : 코드를 쓰고, 디버깅하고, 테스팅한다.

6.2.2. Strategy

다음의 몇 가지 제안이 있다.

  • 풀어야 할 문제가 무엇인지를 명확히 하라. (문제의 문구는 명확한가? 주어진 시간/능력/도구 안으로 문제를 풀 수 있는가?)
  • 문제를 다룰 수 있는 부분들로 분해한다. (사용 가능한 도구들과 라이브러리들을 점검한다. 해법의 일부가 분리될 수 있는지 본다.)
  • 문제의 핵심 부분을 푸는 작은 프로토타입을 먼저 만든다. (이는 문제를 우리의 이해 안으로 끌어오고, 어떤 디테일이 더 필요한지를 명확하게 해준다.)
  • 프로토타입의 아이디어를 활용해 전체 문제를 푸는 프로그램을 만든다.

6.3. Back to the calculator!

계산기 프로그램을 나누면 다음과 같을 것이다.

줄을 읽는다
계산한다
결과를 출력한다

6.3.1. First attempt

일단 가장 간단하게 2개의 수를 더하거나 빼는 표현식을 계산하는 프로그램을 코딩하면 다음과 같을 것이다.

#include <iostream>

int main() {
    std::cout << "Please enter expression (we can handle + and -): ";
    int lval = 0, rval = 0, res = 0;
    char op;
    std::cin >> lval >> op >> rval;
    if (op == '+') {
        res = lval + rval;
    } else if (op == '-') {
        res = lval - rval;
    }
    std::cout << "Result: " << res << '\n';
}

이 프로그램은 동작한다! 그러나 덧대야 할 부분이 많다.

  1. 에러 처리
  2. 곱셈과 나눗셈 처리
  3. 2개 뿐만 아니라 여러 개의 숫자에 대한 연산도 다룰 수 있도록 함

이에 착안해 좀 더 개선해 보면 다음과 같다.

#include <iostream>
#include <stdexcept>

int main() {
    std::cout << "Please enter expression (we can handle +, -, * and \): ";
    std::cout << "add an x to end expression (e.g., 1+2*3x)";
    int lval = 0, rval = 0;
    std::cin >> lval;
    if (!std::cin) throw std::runtime_error("No first operand");
    for (char op; std::cin >> op; ) {
        if (op != 'x') std::cin >> rval;
        if (!std::cin) throw std::runtime_error("No second operand");
        switch (op) {
        case '+':
            lval += rval;
            break;
        case '-':
            lval -= rval;
            break;
        case '*':
            lval *= rval;
            break;
        case '/':
            lval /= rval;
            break;
        default:
            std::cout << "Result: " << lval << '\n';
            return 0;
        }
    }
    throw std::runtime_error("Bad expression");
}

아주 나쁘진 않지만 1 + 2 * 3을 넣으면 7이 아니라 9가 나옴을 알게 될 것이다. 곱셈이 덧셈보다 선행된다는 것을 구현하지 못했기 때문이다. 어떻게 해야 할까?

6.3.2. Tokens

다음의 고려를 할 수 있다.

  1. 표현식을 꼭 한 줄로 받아야 할 필요가 없다.
  2. 숫자, 덧셈, 뺄셈, 괄호들 사이에서 곱셈과 나눗셈을 어떻게 찾아야 하나?
  3. 곱셈이 어디에 있는지를 어떻게 기억하나?
  4. 곱셈/나눗셈이 연산 순서가 앞서야 한다는 것을 어떻게 구현하나?

일단 4번 말고 1-3번만 해결해 보자. 이를 위해서는 표현식을 토큰화한다. 45 + 11.5 / 7은 45, +, 11.5, /, 7로 나눌 수 있을 것이다. 토큰의 종류는 부동 소수점 리터럴, 연산자, 괄호 이렇게 3종류가 될 것이다. 토큰을 정의하기 위해서는 사용자 정의 타입을 정의한다.

6.3.3. Implementing tokens

토큰은 연산자와 숫자를 표현할 수 있어야 한다. 간단하게는 다음과 같이 구현할 수 있다. 여기서는 숫자를 나타내는지의 여부를 kind에 8을 넣는 것으로 구현하였다.

struct Token {
    char kind;
    double value;
};

토큰의 kind, value의 값을 변경하는 것은 다음과 같이 한다.

Token t;
t.kind = '+';
Token t2;
t2.kind = '8';
t2.value = 3.14;

토큰을 복사하거나 대입하거나 초기화하는 것은 다음과 같이 한다.

Token tt = t;
if (tt.kind != t.kind) throw std::runtime_error("Impossible!");
t = t2;
std::cout << t.value;

Token t3 {'+'};
Token t4 {'8', 11.5};

6.3.4. Using tokens

이제 입력을 토큰의 std::vector로 받아서 처리해보자. 그 다음에 곱셈을 찾으면 인접한 숫자들을 곱하는 것다.

Token get_token();
std::vector<Token> tok;

int main() {
    while (std::cin) {
        Token t = get_token();
        tok.push_back(t);
    }
    for (size_t i = 0; i < tok.size(); i++) {
        if (tok[i].kind == '*') {
            double d = tok[i - 1].value * tok[i + 1].value;
            // now what?
        }
    }
}

자, 곱셈을 찾았다! 그래서 뭐 어쩌란 말인가? 곱한 숫자를 가지고 뭘 할 것인가? 1 + 2 * 3에서 곱셈을 찾았으면 왼쪽의 숫자랑 곱하면 될 것이다. 하지만 1 * 2 + 3에는 이 방법은 먹히지 않는다. 1 + 2 * 3 + 4는? 1 + (2 * 3) + 4는? 위의 접근법으로는 안쪽에서부터 계산할 수도 없고 괄호를 다룰 수도 없다. 우리는 막다른 길에 도착한 것 같다.

이렇게 된 이유는 위의 4번 고려점 – 곱셈/나눗셈이 연산 순서가 앞서야 한다는 것을 어떻게 구현하나? – 에 대해 충분히 생각하지 않은 채 코딩에 뛰어들었기 때문이다. 문제에 대한 충분한 분석과 설계 없이 바로 코딩에 들어가면 이렇게 된다.

6.3.5. Back to the drawing board

원점으로 돌아가서 다시 생각해보자. 여러 번 계산해야 할 수도 있으니까 로직은 다음과 같게 하자.

while (끝내지 않았을 때) {
    줄을 읽는다
    계산한다
    결과를 출력한다.
}

이제 해결해야 할 문제를 다음과 같이 생각해 보자.

  1. 45 + 5 / 7에서 45, +, 5, /, 7은 각각 어떻게 찾나? (토큰화한다.)
  2. 입력한 표현식을 끝내는 것은 무엇인가? 엔터로 하자.
  3. 45 + 5 / 7에서 4, 5를 45로 인식하려면 어떻게 하나? (토큰화가 해답이 될 수 있다.)
  4. 45 + 5 / 7이 45 + (5 / 7)로 계산되게 하려면 어떻게 하나?
  5. 5 / 7은 0.71로 해야 하는가 0으로 해야 하는가? 부동 소수점을 사용하도록 하자.
  6. 변수를 지원해야 하나? v = 7, m = 9, v * m을 계산할 수 있으면 좋겠지만, 이건 당장은 너무 어렵고 기본적인 것부터 되게 하자.

6번의 결정은 중요하다. 일단 기본적인 것부터 되게 하는 프로그램을 만드는 것이 일을 진행되게 만든다.

6.4. Grammars

표현식에 대해 컴퓨터에 이해시킬 문법을 다음과 같이 만들자.

Expression:
    Term
    Expression "+" Term
    Expression "-" Term
Term:
    Primary
    Term "*" Primary
    Term "/" Primary
    Term "%" Primary
Primary:
    Number
    "(" Expression ")"
Number:
    floating-point-literal

이는 다음을 나타낸다: “Number는 floating-point-literal이다.” “Primary는 Number이거나, ‘(‘ 뒤에 Expression 뒤에 ‘)’ 가 오는 식이다.” “Term은 Primary이거나, Term 뒤에 ‘*’, ‘/’, ‘%’ 뒤에 Primary가 오는 식이다.” “Expression은 Term이거나, Expression 뒤에 ‘+’, ‘-‘ 뒤에 Term이 오는 식이다.” 이런 문법을 규정하는 것은 우리의 사고 체계를 컴퓨터에게, 인간에게, 그리고 우리 자신들에게 명확히 설명할 수 있게 해준다. 이러한 프로그램을 파서라고 한다.

위의 룰을 적용해보면 2는 표현식이고, 2 + 3도 표현식이 됨을 알 수 있다. 중요한 것은 45 + 11.5 * 7을 파싱할 때이다: 위의 문법은 45 + 11.5 * 7 내에서 11.5 * 7을 먼저 Term으로 평가한 뒤 45 + 뒤에 적용되어 계산될 수 있도록 해 준다.

6.4.1. A detour: English grammar

영어 문법도 이런 식으로 나타낼 수 있다.

Sentence:
    Noun Verb
    Sentence Conjunction Sentence
Conjunction:
    "and"
    "or"
    "but"
Noun:
    "birds"
    "fish"
    "C++"
Verb:
    "rules"
    "fly"
    "swim"

6.4.2. Writing a grammar

위에서 정의한 문법을 통해 표현식을 파싱하려면 어떻게 해야 할까?

  • 토큰으로부터 규칙을 변별한다
  • 하나의 규칙 뒤에 다른 규칙을 배치한다 (순서화)
  • 대체하는 패턴을 표현한다 (대체)
  • 반복되는 패턴을 표현한다 (반복)
  • 시작할 문법 규칙을 인식한다

6.5. Turning a grammar into code

위의 문법을 통해 파서를 정의해 보자.

6.5.1. Implementing grammar rules

계산기를 위해서는 4개의 함수가 필요하다. 각각의 함수는 표현식의 일부분만 다룬다. 이는 함수를 간단히 함으로써 일을 쉽게 만든다.

Token get_token() // read characters and compares tokens. uses std::cin
double expression() // deal with + and -, calls term() and get_token()
double term() // deal with *, /, and %, calls primary() and get_token()
double primary() // deal with numbers and parentheses, calls expression() and get_token()

6.5.2. Expressions

표현식은 다음과 같이 구현할 수 있을 것이다.

6.5.2.1. Expressions: first try

double expression() {
    double left = expression();
    Token t = get_token();
    switch (t.kind) {
    case '+':
        return left + term();
    case '-':
        return left - term();
    default:
        return left;
    }
}

이 함수는 동작하는 것 같아 보이지만 틀렸다. 표현식이 언제 끝나는지는 어떻게 아는가? expression()은 expression()을 계속 부르므로 무한 재귀 문제도 생긴다.

6.5.2.2. Expressions: second try

그렇다면 모든 항은 표현식이지만 모든 표현식은 항은 아니라는 점을 활용해보자.

double expression() {
    double left = term();
    Token t = get_token();
    switch (t.kind) {
    case '+':
        return left + expression();
    case '-':
        return left - expression();
    default:
        return left;
    }
}

이 프로그램은 많은 테스트케이스에 대해 정답이지만, 1 – 2 – 3에 대해 1 – (2 – 3)의 순서대로 계산을 하기 때문에 틀렸다. 대부분의 테스트케이스에 대해서는 정답을 내놓기 때문에 이런 프로그램이 오히려 더 위험하기도 하다.

6.5.2.3. Expressions: third time lucky

이제 위의 버그를 고쳐 표현식을 제대로 구현해 보자.

double expression() {
    double left = term();
    Token t = get_token();
    while (true) {
        switch (t.kind) {
        case '+':
            left += term();
            t = get_token();
            break;
        case '-':
            left -= term();
            t = get_token();
            break;
        default:
            return left;
        }
    }
}

6.5.3. Terms

항은 표현식과 비슷하게 구현하면 된다.

double term() {
    double left = primary();
    Token t = get_token();
    while (true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = get_token();
            break;
        case '/':
            left /= primary();
            t = get_token();
            break;
        case '%':
            left %= primary();
            t = get_token();
            break;
        default:
            return left;
        }
    }
}

안타깝지만 이는 컴파일이 되지 않는다. 부동 소수점에 대해서는 나머지 연산이 없기 때문이다. 두 가지 해법이 있다: 정수인지 체크한 뒤 정수에 대해서만 나머지를 제공하거나, 나머지 연산을 지원하지 않거나. 일단 간단하게 후자로 가자.

또한 0으로 나눌 경우에 프로그램이 죽는데, 이에 대한 대비도 되지 않았다. 이를 보완하면 다음과 같다.

double term() {
    double left = primary();
    Token t = get_token();
    while (true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = get_token();
            break;
        case '/': {
            double d = primary();
            if (d == 0) throw std::runtime_error("divide by zero");
            left /= primary();
            t = get_token();
            break;
        }
        default:
            return left;
        }
    }
}

6.5.4. Primary expressions

이제 1차 표현식에 대해 구현하면 다음과 같다.

double primary() {
    Token t = get_token();
    switch (t.kind) {
    case '(': {
        double d = expression();
        t = get_token();
        if (t.kind != ')') throw std::runtime_error("')' expected");
        return d;
    }
    case '8':
        return t.value;
    default:
        throw std::runtime_error("primary expected");
    }
}

6.6. Trying the first version

이제 main()과 get_token()만 구현하면 된다. main()은 그냥 표현식을 계속 계산하면 된다. 이제는 될까?

int main() {
    try {
        while (std::cin)
            std::cout << "=" << expression() << '\n';
    } catch (std::exception& e) {
        std::cerr << e.what() << '\n';
        return 1;
    } catch (...) {
        std::cerr << "exception \n";
        return 2;
    }
}

이 프로그램도 역시 되지 않는다. double expression() 함수 내의 구현을 살펴보면 get_token()으로 받은 토큰이 +나 -가 아닐 때에는 그 토큰을 사용하지 않고 리턴해버린다. 이러면 받은 토큰이 숫자일 때는 그 토큰은 계산되지 않고 무시된다. term()에도 같은 문제가 있다. 이것을 해결하기 위해서는 일종의 입력 스트림을 사용해야 한다. primary()는 받은 토큰을 전부 사용하므로 이러한 문제는 없다.

double expression() {
    double left = term();
    Token t = ts.get();
    while (true) {
        switch (t.kind) {
        case '+':
            left += term();
            t = ts.get();
            break;
        case '-':
            left -= term();
            t = ts.get();
            break;
        default:
            ts.putback(t);
            return left;
        }
    }
}

double term() {
    double left = primary();
    Token t = ts.get();
    while (true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = ts.get();
            break;
        case '/': {
            double d = primary();
            if (d == 0) throw std::runtime_error("divide by zero");
            left /= primary();
            t = ts.get();
            break;
        }
        default:
            ts.putback(t);
            return left;
        }
    }
}

6.7. Trying the second version

이 버전의 계산기에 다음을 입력해 보자.

2 3 4 2+3 2*3
= 2
= 3
= 4
= 5

마지막 결과인 6이 나오지 않는다. 이는 다음 입력이 들어올 때 계산해 둔 결과를 출력하기 때문에 그런 것이다. 이를 고치려면 출력 커맨드와 종료 커맨드를 구현하는 것이 하나의 방법이 될 수 있다.

double val = 0.0;
while (std::cin) {
    Token t = ts.get();
    if (t.kind == 'q') break;
    if (t.kind == ';')
        std::cout << "=" << val << '\n';
    else
        ts.putback(t);
    val = expression();
}

이제 다음을 입력하면 그럭저럭 동작한다.

2;
= 2
2+3;
= 5
3+4*5;
= 23
q

6.8. Token streams

Token_stream의 구현은 다음과 같이 인터페이스와 구현을 분리해서, 인터페이스는 사용자가 필요한 것들만 남겨 공개해야 한다.

class Token_stream {
public:
    // 사용자 인터페이스
    Token get();
    void putback(Token t);
private:
    // 세부 구현
    // (Token_stream)의 사용자 측에서는 직접적으로 접근 가능하지 않음
    bool full {false};
    Token buffer;
};

6.8.1. Implementing Token_stream

멤버 함수의 구현은 다음과 같이 하면 된다.

void Token_stream::putback(Token t) {
    if (full) throw std::runtime_error("putback() into a full buffer");
    buffer = t;
    full = true;
}

6.8.2. Reading tokens

토큰을 읽는 함수는 다음과 같이 구현한다.

Token Token_stream::get() {
    if (full) {
        full = false;
        return buffer;
    }
    char ch;
    std::cin >> ch;
    switch (ch) {
    case ';': case 'q': case '(': case ')':
    case '+': case '-': case '*': case '/':
        return Token(ch);
    case '.': case '0': case '1': case '2':
    case '3': case '4': case '5': case '6':
    case '7': case '8': case '9': {
        std::cin.putback(ch);
        double val = 0.0;
        std::cin >> val;
        return Token {'8', val};
    }
    default:
        throw std::runtime_error("Bad token");
    }
}

6.8.3. Reading numbers

여기서 간결한 코드를 쓰기 위해 지나온 과정들을 되돌아보자. 뛰어난 프로그래머는 코딩을 많이 하지 않는다.

6.9. Program structure

프로그램의 구조를 정리해보면 다음과 같다.

class Token {};
class Token_stream {};

void Token_stream::putback(Token t) {}
Token Token_stream::Get() {}

Token_stream ts;
double expression();

double primary() {}
double term() {}
double expression() {}

int main() {}

이 때 선언의 순서는 중요하다. Token_stream ts가 선언되지 않은 채로 ts.get()을 사용할 수는 없다. 프로그램의 구조는 이런 요소들을 고려해야 한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중