Sizeof

대부분의 고급 프로그래밍 언어는 구조화된 자료형을 제공한다. 파스칼에는 레코드(record) 형, C에는 구조체(struct) 형, C++와 자바에는 클래스(class) 형이 있다. 구조화된 자료형은 여러 구성 요소 자료형으로 이루어지며, 구조화된 값은 각 구성 요소의 값을 모두 담는다.

구조화된 자료를 저장할 때는 메모리 정렬(alignment)을 고려해야 한다. 전통적인 폰 노이만 구조의 컴퓨터에서 메모리는 워드(word) 단위로 접근된다. 따라서 빠른 접근을 위해 모든 자료는 워드 경계에 맞춰 정렬되어 저장된다. 워드의 크기는 바이트의 정수 배이고 컴퓨터마다 고정되어 있다. 워드의 크기가 W바이트인 컴퓨터를 W바이트 컴퓨터라고 부른다.

정렬 때문에 메모리 단편화(fragmentation)가 생긴다. 예를 들어 4바이트 컴퓨터에서는 1바이트짜리 자료가 4바이트를 차지한다. 일반적으로 자료형 T의 크기가 워드 크기의 배수가 아니면 T는 공간을 낭비한다. 다음 C 구조체를 보자.

struct A {
    char a;
    struct {
        int x;
        char c;
    } b;
};

sizeof(char) = 1, sizeof(int) = 4라고 가정하고, 타입 A의 값을 2바이트 컴퓨터에 저장한다고 하자. 필드 a는 원칙적으로 1바이트만 필요하지만 정렬 때문에 실제로는 2바이트가 필요하다. 필드 b.x는 두 워드를 정확히 채우므로 4바이트가 필요하다. 필드 b.c는 sizeof(b.c)가 1이지만 한 워드 전체가 필요하므로 2바이트가 된다. 따라서 타입 A의 값을 저장하려면 2바이트 컴퓨터에서 8바이트가 필요하다. 4바이트 컴퓨터에서는 12바이트, 1바이트 컴퓨터에서는 6바이트만 필요하다.

작성할 프로그램은 컴퓨터의 워드 크기 W와 구조화된 자료형 선언 T를 읽어, W바이트 컴퓨터에서 타입 T의 값을 저장하는 데 필요한 바이트 수를 메모리 정렬을 고려하여 계산한다.

문제를 단순하게 하기 위해, 이 언어에는 구조체 타입과 원시 타입만 있다고 가정한다. 포인터, 참조, 배열은 선언에 쓸 수 없다. 구조체를 선언하는 키워드는 struct이며 그 바로 뒤에 구조체 식별자가 온다. 원시 타입의 키워드는 Tn 꼴이고, 여기서 n은 한 자리 양의 십진수(1부터 9까지)로 Tn 타입 값 하나를 저장하는 데 필요한 바이트 수를 뜻한다. n이 1부터 9까지의 한 자리 숫자여야 하므로 T0나 T101T 같은 이름은 원시 타입이 아니라 식별자이다. 구조체 이름은 타입 이름으로 쓰이지만, 그 구조체 타입을 다른 곳에서 참조하지 않는다면 생략할 수 있다. 이 점들을 제외하면 나머지 규칙과 선언의 의미는 모두 C 언어를 따른다. 예를 들어 struct Empty {}; 처럼 빈 구조체를 선언할 수 있으며, C 규칙에 따라 그 크기는 0이다. 위 선언을 이 규칙으로 다시 쓰면 다음과 같다.

struct A {
   T1 a;
   struct {
       T4 x;
       T1 c;
   } b;
};

모든 문법 규칙을 지키더라도 잘못된 선언이 될 수 있다. 검출해야 할 의미 오류(semantic error)는 두 가지이다. (1) 같은 스코프 안에서 타입이나 필드를 중복해서 선언하는 경우, (2) 재귀적인 구조체를 선언하는 경우. 프로그램은 이 두 가지를 모두 검출해야 한다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 개수 N이 주어진다. 각 테스트 케이스의 첫 줄에는 한 워드의 바이트 수인 워드 크기 W (0 < W < 100)가 주어진다. 그 다음 줄들에는 구조체 타입 선언 하나가 주어진다. 각 테스트 케이스의 끝은 줄 맨 앞에 달러 기호 $ 하나만 있는 줄로 표시된다. 각 입력 줄의 길이는 1,000자 미만이다. 모든 테스트 케이스에는 문법 오류가 없지만 의미 오류는 있을 수 있다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다, 해당 테스트 케이스에 주어진 워드 크기 W의 컴퓨터에서 메모리 정렬을 고려한 구조체의 크기를 바이트 수로 한 줄에 출력한다. 선언 자체가 잘못된 경우에는 error를 출력한다.