매달린 else

아래 코드의 else는 두 if 중 어느 쪽에 대응할까?

if(a) if(b) c; else d;

별도의 규칙이 없으면 컴퓨터는 이 else가 두 if 중 어느 쪽과 짝인지 알 수 없다. 컴파일러 강의에서 들어봤을 매달린 else(dangling else) 문제이다.

이 문제를 해결하는 방법은 여러 가지지만, 대표적인 방법은 두 가지다.

1. 모호한 else를 짝을 이룰 수 있는 가장 가까운 if와 짝짓는다.
2. 문법에서 중괄호 생략을 금지한다.

이 문제에서는 1번 규칙을 사용하는 소스 코드를 입력받아, 2번 규칙을 사용하는 소스 코드로 바꿔야 한다.

소스 코드의 문법은 다음과 같다.

• 소스 코드에서 쓰는 토큰은 세미콜론(;), 여는 중괄호({), 닫는 중괄호(}), if, else, end의 여섯 가지다.
• 소스 코드는 0개 이상의 구문과 하나의 end 토큰으로 이루어진다.
• 각 구문은 세미콜론 토큰 하나, if문, if-else문 중 하나다.
• if문은 if 토큰과 본문 하나가 이어진 형태다.
• if-else문은 if 토큰, 본문, else 토큰, 본문이 순서대로 이어진 형태다.
• 본문의 형태는 적용하는 규칙에 따라 다르다. 1번 규칙에서는 본문이 구문 하나일 수 있다. 1번 또는 2번 규칙에서는 여는 중괄호, 0개 이상의 구문, 닫는 중괄호가 이어진 형태일 수도 있다.
• 모든 토큰은 공백 문자 하나로 구분한다.

동형 관계는 다음과 같이 정한다. 두 소스 코드는 구문 수가 같고 대응하는 구문끼리 동형이면 동형이다. 두 구문은 둘 다 세미콜론 토큰이거나, 둘 다 if문이면서 본문이 동형이거나, 둘 다 if-else문이면서 두 본문이 순서대로 동형이면 동형이다. 두 본문은 둘 다 중괄호가 있고 구문 수가 같으며 대응하는 구문끼리 동형이거나, 중괄호 유무와 상관없이 둘 다 단일 구문이고 그 구문이 동형이면 동형이다.

1번 규칙을 고려하지 않으면 if { if ; } else ; end와 if if { ; } else { ; } end는 동형이다. 두 소스 코드 모두 if-else문 하나로 이루어져 있다. 첫 번째 본문은 둘 다 본문이 세미콜론인 if문 하나이고, 두 번째 본문은 둘 다 세미콜론 하나다.

1번 규칙을 사용하는 소스 코드 $X$가 주어진다. $X$와 동형이면서 2번 규칙을 사용하는 소스 코드 $X'$를 찾아 출력한다. 주어진 문법에서 $X'$는 유일하다.

첫 번째 줄에 입력 문법을 만족하는 문자열이 주어진다. end를 포함한 토큰의 개수는 최대 1,000개이며, 입력의 앞뒤에는 불필요한 공백이 없다.

<input> ::= <input_stmt>* "end"
<input_block> ::= <input_stmt> | "{" <input_stmt>* "}"
<input_stmt> ::= ";" | <input_if>
<input_if> ::= "if" <input_block> | "if" <input_block> "else" <input_block>

입력받은 프로그램을 파싱한 결과를 아래 출력 문법에 맞춰 첫 번째 줄에 출력한다.

<output> ::= <output_stmt>* "end"
<output_block> ::= "{" <output_stmt>* "}"
<output_stmt> ::= ";" | <output_if>
<output_if> ::= "if" <output_block> | "if" <output_block> "else" <output_block>

C에는 else if문이 따로 없다는 사실을 알고 있는가? 우리가 else if라고 부르는 구문은 사실 else의 본문에서 중괄호를 생략하고 if문을 넣은 경우다.