매달린 else(dangling else) 경고하기

beluga 에 매달린 else 경고가 추가된 시점인 4년 전에 작성하기 시작했던 글인데 방치했다가 이제야 마무리해서 올립니다. 너무 오래된 기억을 되살리느라 고생 좀 했습니다.

파이썬(Python)처럼 들여쓰기(indentation)를 의미있게 다루지도 않고 모듈라-2(Modula-2)처럼 if 문의 종료 지점을 표시하지도 않는 C 언어 같은 언어를 학습해 본 분이라면 매달린 else(dangling else) 문제에 대해 들어보았을 것입니다. 보다 더 나아가 프로그래밍 언어론이나 컴파일러 수업에서는 이 문제를 문법적으로 해결하는 방법이 흔히 과제로 나오기도 합니다.

사실 else 문은 가장 가까운 if 문과 연결된다는 규칙은 파서(parser)를 구현하는 입장에서는 별로 어려운 부분이 아닙니다. 대표적인 하향식 파서(top-down parser)인 재귀 하향 파서(recursive descent paresr)에서는 정상적인 else 문을 만난 시점은 가장 가까운 if 문을 파싱하고 있던 시점이기에 자연스럽게 가까운 if 문과 연결됩니다.

보다 복잡한 문제는 매달린 else 를 올바르게 파싱하는 것보다 어떻게 찾아 프로그래머에게 알려줄 수 있냐는 것입니다. 다른 문장에 속한 모든 부속 문장은 단일 문장이어도 중괄호({, })를 사용해 복문(compound statement)으로 만들어 준다는 스타일을 강제한다면, 복문의 경계를 정하는 중괄호가 if 문의 끝을 결정해 주기에 고민 거리도 아닙니다. 하지만, C 언어에서는 단일 문장일 경우 복문으로 만들지 않는 것이 의외로 널리 사용되는 스타일이기에 문제가 될 소지가 있습니다.

때문에 컴파일러 입장에서도 다른 언어처럼 매달린 else 를 오류로 처리해 주지는 못하지만 적절하게 경고해 주는 것이 생각보다 유용합니다.

이제 예를 통해서 매달린 else 를 찾아내는 방법에 대한 감을 잡아보도록 하겠습니다. 우선, 단일 if 문에서는 매달린 else 가 발생할 수 없습니다.

if (cond1)
    stmt1;
else
    stmt2;

else 문이 애매하게(ambiguously) 매달리고 싶어도 매달릴 곳이라고는 if 문이 하나 밖에 없습니다. 그럼, 일단 중첩된 if 문에서만 문제가 된다는 사실을 알 수 있습니다. 그리고, 중첩된 if 문이라 해도 else 부분이 모두 존재한다면 역시나 애매하게 매달릴 곳이 없습니다.

if (cond1)
    if (cond2)
        stmt1;
    else
        stmt2;
else
    stmt3;

이 부분은 생각보다 중요합니다. 바깥쪽 if 문이 else 를 가지고 있을 때 안쪽 if 문에 else 가 매달린 else 가 될 수 없다는 것은, 바깥쪽 if 문의 then 부분에서만 매달린 else 후보를 기억하는 작업을 하면 된다는 뜻입니다. 바깥쪽 if 문의 else 부분은 그 안에서 다시 중첩된 if 문들이 나오면서 매달린 else 를 만들지 않는 이상 신경 쓸 필요가 없습니다 - 그리고 안에서 다시 중첩된 if 문들이 나오는 경우는 재귀 호출에 의해 적절히 다루어지게 됩니다.

가장 단순한 형태의 매달린 else 는 아래와 같이 생겼습니다.

if (cond1)
    if (cond2)
        stmt1;
else
    stmt2;

어느 정도 프로그래밍에 익숙하다면 이렇게 주어진 else 문이 손쉽게 매달린 else 형태이고 더구나 들여쓰기가 잘못 되어 작성된 의도대로 동작하지 않음을 눈치 챌 수 있습니다. 그럼 매달린 else 문제는 직접적으로 중첩된 if 문끼리만의 문제일까요? 아니죠! 아래처럼 다른 문장을 통해 간접적으로 중첩된 경우도 문제가 될 수 있습니다.

if (cond1)
    for (i = 0; i < n; i++)
        if (cond2)
            stmt1;
else
    stmt2;

어떤 분은 (매달린 else 라고 말씀드렸음에도 불구하고) 이 코드가 왜 문제가 되는지 분명하게 보이지 않을 수도 있습니다 - 실망하지 마세요, 코드가 워낙 그지같은 경우입니다. 이 정도 구조에서 매달린 else 가 콕 찝어 보이는 분이라 해도, 실제 프로그래밍에서 긴 코드 안에 아래처럼 복잡한 구조로 자리잡은 경우에는 매달린 else 로 인지하기가 쉽지 않습니다.

if (symlist)
    for (p = sym; p != NULL; p = p->next)
        if (p->scope == GLOBAL)
            checksym(symlist, p, cur_scope);
else
    symlist = list_add(symlist, makesym());

그리고, 적절한 경고가 없다면 프로그램은 정상적으로 컴파일되고 동작만 이상할테니 원인을 찾기까지 생각보다 많은 삽질을 필요로 할 가능성이 큽니다.

그럼, 이제 (간접적이든 직접적이든) 중첩된 if 문을 찾아내는 방법부터 고민해 보겠습니다.

C 언어의 문장(statement)에 대한 문법은 아래와 같습니다.

그리고 beluga 가 사용 중인 재귀 하향 파서는 그 구조를 거의 그대로 함수로 옮겨 문장을 인식(파싱)하고 있습니다. (설명을 위해 실제보다 함수명을 보다 간단히 바꾸겠습니다.) stmt() 는 문장의 시작 부분을 인식해 개별 문장을 파싱하는 함수를 불러주는 함수입니다. stmt() 는 문장이 나올 수 있는 혹은 나와야 하는 문맥에서 첫 토큰을 살펴보고(lookahead) 문장의 세부 종류를 구분해 분기합니다 - 설명은 거창하지만 그냥 입력 토큰을 검사해 분기하는 if-else chain 이나 switch 문이라고 생각하시면 됩니다.

만약, 첫 토큰이 if 라면 if 문의 시작이므로 ifstmt() 를 호출해 if 문이 인식되도록 합니다.

문법에 따라 ifstmt() 안에서는 이후에 나오는 괄호 안 수식을 인식한 후, (then 부분에) 문장이 나올 수 있으므로 다시 stmt() 를 재귀 호출하게 됩니다. 이렇게 함수들이 문법에 따라 서로를 호출하며 복잡한 문장을 파싱하게 됩니다.

그럼, 위의 매달린 else 를 보여주는 두 문장을 파싱할 때 호출되는 함수의 모양은 아래와 같이 그릴 수 있습니다.

이때 else 부분이 가장 가까운 if 문에 귀속되어 파싱됨에 유의하셔야 합니다. 프로그래밍 실수로 보이기 위해 제가 들여쓰기를 이상하게 배치했을 뿐입니다.

이런 구조에서 중첩된 if 문을 인식하는 방법은 간단합니다. 중첩 구조에서 바깥쪽(상위)에 해당하는 if 문을 만났을 때, if 문이 나왔다는 사실을 안쪽(하위) 구조로 내려주면(inherit) 하위 구조에서 if 문을 만났을 때 이를 감지할 수 있습니다. 가장 쉽게는 함수의 매개변수 하나를 if 문을 만났다는 사실을 알리는 용도로 사용하면 되겠죠.

void stmt(int metif)
{
    ...
    case IF:
        if (metif)
            // 중첩된 if
        ifstmt(true);
    ...
}

void ifstmt(int metif)
{
    ...
    // then 부분 인식
    stmt(metif);
    if (token == ELSE) {    // else 부분 있으면 인식
        token = next();    // else 다음 토큰 확보
        stmt(metif);
    }
}

초기에 호출되는 stmt() 에서는 metif 가 false 로 호출됩니다. 물론, if 문이 간접 중첩된 경우도 다루어야 하므로 다른 종류의 문장을 파싱하는 함수들도 metif 를 받아 하위 구조로 전달할 수 있도록 해주어야 합니다.

사실, 매달린 else 를 다루는 관점에서 then 부분이 아닌 else 부분은 중요하지 않다고 했으므로, ifstmt() 에서 if (token == ELSE) { 의 stmt() 호출은 마치 새로 문장이 시작하는 것처럼 stmt(false) 로 바꿔도 무방합니다 - 물론, 매달린 else 와 무방하게 모든 중첩된 if 문을 찾는 것이 목적이라면 metif 를 제대로 내려줘야 합니다.

이제 매달린 else 의 후보를 찾는 방법을 고민해 보겠습니다. 중요한 것은 매달린 else 가 있다고 결정되는 시점입니다. 다시 위에서 봤던 코드로 설명하겠습니다.

if (cond1)
    if (cond2)
        stmt1;
else
    stmt2;

코드 들여쓰기 만으로는 저 문제의 else 가 안쪽 if (cond2) 가 아닌 바깥쪽 if (cond1) 와 연결된 것 같지만, 실제로는 안쪽 if (cond2) 와 연결된 것입니다. 그리고, 앞서 설명했듯이 모든 if 문이 else 를 가질 때에는 매달린 else 문제가 발생하지 않습니다.

고로 매달린 else 의 존재는 실제 매달린 else 에 해당하는 부분을 만나는 시점이 아니라 바깥쪽 if 문에 else 가 없다는 사실을 확인할 때 알 수 있습니다. 즉, 중첩된 안쪽 if 문에 연결된 else 가 있는데, 바깥쪽 if 에는 else 가 없을 때, 안쪽 if 문의 else 가 매달린 else 가 될 수 있습니다.

이제 이를 감지하는 코드를 만들 차례입니다. 앞서 if 문의 중첩 여부는 상위에서 하위로 상태를 내려(inherit) 확인했지만, 이번에는 안쪽(하위) if 문에 else 가 있다는 사실을 바깥쪽(상위) if 문에 올려(synthesize) 확인해야 합니다. 이때 가장 간단한 방법은 반환값을 사용하는 것이겠지요? 대충 느낌상으로는 이런 코드가 될 겁니다.

int metelse;

...
if (metif && token == ELSE)    // 중첩된 if 문이고 else 가 있음
    metelse = true;
...

return metelse;

물론, for 같은 다른 문장을 거쳐 중첩된 경우도 고려해야 하므로 마찬가지로 다른 문장을 인식하는 함수들도 metelse 를 반환값으로 자신을 호출한 쪽으로 전달해 주어야 합니다.

이제 본인은 바깥쪽 if 문인데 하위 if 문에서 else 를 만났고 자신에게는 else 가 없으면 매달린 else 의 잠재적 후보가 되겠지요? 이번에도 대충 느낌상으로는 이런 코드가 될 겁니다.

if (!metif && metelse && token != ELSE)
    // 매달린 else 후보 발견

이제 얘네들을 저 위의 ifstmt() 에 녹여보겠습니다.

int ifstmt(int metif)
{
    int metelse;

    ...
    // then 부분 인식
    metelse = stmt(metif);
    if (token == ELSE) {
        token = next();
        stmt(false);
        if (metif)
            metelse = true;
    } else if (!metif && metelse)
        // 매달린 else 후보 발견

    return metelse;
}

자신의 then 부분을 파싱하다가 else 를 만나면 metelse = stmt(metif); 에 의해 metelse 가 설정될 것입니다. 그리고 자신이 else 를 가지고 있으면 상위에 else 가 있음을 알려주기 위해 metelse 를 설정합니다. 자신에게 else 가 없다면, 앞서 소개한 조건대로 stmt(metif) 로 파싱했던 then 부분에서 else 를 만났는지 판단해 매달린 else 후보를 찾습니다.

이제 코드가 제법 역할을 하니 쓸데 없는 부분을 덜어내 보겠습니다. 중첩된 if 문임을 구분하기 위해 상위에서 하위로 보내는 metif 가 쓰이고 있지만 이 부분이 정말 필요할까요? 생각해보면 매달린 else 를 감지하는 코드는 이미 ifstmt() 안에 있습니다. 스스로가 if 문이라는 뜻입니다. 그리고 then 부분의 stmt() 호출에서 metelse 가 참이라는 것은 else 를 만났다는 뜻이므로 중첩된 if 문이 있다는 뜻입니다 - if 없이 else 가 나올 순 없겠지요. 따라서, ifstmt() 안에 있다는 사실과 metelse 의 조합으로 metif 는 유명무실해집니다. metif 를 덜어내어 코드를 정리하면,

int ifstmt(void)
{
    int metelse;

    ...
    // then 부분 인식
    metelse = stmt();
    if (token == ELSE) {
        token = next();
        stmt();
        metelse = true;
    } else if (metelse)
        // 매달린 else 후보 발견

    return metelse;
}

이렇게 간단해질 수 있습니다 - 하지만, 앞서 코드와 행동면에서는 차이가 발생하기는 합니다.

여기까지 찾은 것은 매달린 else 의 _후보_입니다. 진짜 매달린 else 가 아닐 수도 있다는 얘기입니다. 예를 보겠습니다.

if (cond1) {
    if (cond2)
        stmt1;
    else
        stmt2;
}

이 코드에서도 매달린 else 후보가 발견됩니다. then 부분에 중첩된 if 문이 있고 바깥쪽에 else 가 없기 때문입니다. 이제 이런 애들을 가려내야 진짜 매달린 else 를 찾을 수 있습니다. 어떻게 하면 될까요?

재귀의 강력함으로 문제는 간단히 해결됩니다. stmt() 에서 { 는 복문을 시작합니다. 복문을 파싱하는 함수도 여느 문장 파싱 함수처럼 metelse 를 반환하는데 항상 false 를 반환하게 하면 됩니다 (혹은 더 간단히 아예 반환값을 없애면 됩니다). 그러면 복문 안에서 if 문을 만나고 아무리 else 를 만나도 그 사실이 복문의 바깥쪽(상위) 구조로 전달되지 않습니다. 그러면 자연스럽게 복문 안의 else 는 매달린 else 후보에서 빠지게 됩니다.

이제 완료일까요? 매달린 else 가 발생하는 이유는 중첩된 if 문을 감싸는 구조가 없거나 감싸는 구조가 있더라도 그 끝을 명확히 보여주지 않기 때문입니다 - 저 위의 for 문 아래 if 가 있는 경우를 생각해 보시면 됩니다. 반면, 복문의 경우에는 중괄호를 열고 닫기 때문에 끝이 명확히 표시되고, 발견된 else 정보를 상위로 보내지 않아도 됩니다. 따라서, 문장 중에 복문처럼 끝이 문법적으로 표시되는 구조가 있는지 고민해보면 되며, 바로 do-while 가 있습니다.

do-while 문도 문법적으로 실행되는 문장이 사이에 오기 때문에 끝의 while 에 의해 끝이 명확히 표시됩니다.

if (cond1)
    do
        if (cond2)
            stmt1;
        else
            stmt2;
    while(cond3);

따라서, do-while 문을 파싱하는 함수에서도 복문과 마찬가지로 수집한 else 정보를 무시해주면 됩니다. 그러면, 이제 진짜로 매달린 else 를 가려낼 수 있게 됩니다.

beluga 에서는 이 논리를 방법적으로만 다르게 구현하고 있습니다. 반환값 대신 else 발견과 관련된 정보를 저장할 수 있는 변수의 포인터를 하위로 내려줘서 필요할 때 설정하도록 하고 있습니다. 그리고 복문과 do-while 문에는 아예 NULL 을 전달하여 그 아래에서 생성된 정보가 상위로 가는 통로를 막고 있습니다.

그리고 보다 친절한 컴파일러가 되기 위해, 매달린 else 를 발견했을 때 2가지 정보를 경고 메시지에서 제공하고 있습니다. 하나는 어떤 if 문의 본문(body)을 복문(compound statement)으로 만들어야 매달린 else 가 사라지는지와, 어떤 else 가 매달린 else 인지입니다. 전자는 비교적 간단합니다. 매달린 else 를 감지하는 시점이 else 를 갖지 않는 바깥쪽 if 문이므로, 그 if 문의 본문을 복문으로 만들어주면 된다고 알려주면 됩니다. 반면, 매달린 else 의 위치 정보는 else 를 만날 때 수집해야 하기 때문에 상위로 올려주는 정보에 포함해 기억하도록 하고 있습니다.

또한, 추가로 아래와 같이 들여쓰기를 성실히 한 코드까지 경고해 주고 싶지는 않았습니다.

if (cond1)
    if (cond2)
        stmt1;
    else
        stmt2;

따라서, else 토큰의 위치를 고려하여 자신이 귀속되어야 할 if 문과 들여쓰기가 맞다고 판단되면 매달린 else 로 경고해주지 않습니다 - 물론, beluga 가 사용하는 line mapper가 새로 디자인되면서 탭(tab)과 스페이스가 섞인 경우 경고를 놓칠 수도 있지만, 일반적인 경우 크게 문제가 되지 않는 수준입니다.

그렇게 나온 결과는 아래에서 테스트해보실 수 있습니다.

extern int bar, fred, foobar();

void foo(void)
{
    int i;

    if (bar)
        for (i = 0; i < fred; i++)
            if (fred)
                foobar();
    else
        foobar();
}