구조적 동치성

프로그래밍 언어 설계에서는 두 타입이 같은 타입인지 판단할 때 구조적 동치(structural equivalence) 와 이름 동치(name equivalence) 중 무엇을 쓸지에 대한 오래된 논쟁이 있다. Algol 68은 순수한 구조적 동치를 사용하며, 이 문제에서는 그 구조적 동치를 계산한다.

단순화한 Algol 68 타입 정의의 문법은 다음과 같다.

type_def   -> type T = type_expr
type_expr  -> T | int | real | char | struct ( field_defs )
field_defs -> T | field_defs T

여기서 T는 프로그래머가 정의한 타입 이름이며, 이 문제에서는 하나의 대문자 알파벳이다. type, int, real, char, struct와 =, (, )는 입력에 그대로 나타난다. 문법에서 공백이 있는 자리에는 입력에서 0개 이상의 공백이 올 수 있다.

두 타입이 구조적으로 동치라는 것은 다음 중 하나를 만족하는 경우이다.

• 두 타입이 같은 기본 타입(int, real, char)이거나,
• 두 타입이 모두 struct이고, 필드의 개수가 같으며, 같은 순서로 각 필드가 서로 구조적으로 동치인 경우.

타입 이름은 다른 타입 이름(별칭), 기본 타입, 또는 struct로 정의될 수 있다. 정의는 뒤에서 정의되는 이름을 참조할 수 있고 자기 자신을 참조할 수도 있어, 정의들은 (상호) 재귀적일 수 있다. 동치성은 이러한 정의를 끝까지 펼친 타입에 대해 판정한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 위에서 설명한 타입 정의들의 목록이며, 한 줄에 정의 하나가 온다. - 하나만 있는 줄은 연속한 테스트 케이스를 구분한다. --만 있는 줄은 마지막 테스트 케이스 뒤에 오며 입력의 끝을 나타낸다.

각 테스트 케이스마다, 서로 구조적으로 동치인 타입 이름들을 같은 그룹으로 묶어 출력한다. 한 줄에 한 그룹을 출력하고, 한 줄 안의 이름들은 공백 하나로 구분한다. 각 줄 안에서 이름은 알파벳 순서로 정렬하고, 줄들도 서로 알파벳 순서로 정렬한다. 각 타입 이름은 정확히 한 줄에만 나타나며, 줄의 개수는 가능한 한 적어야 한다(서로 동치인 이름은 모두 한 그룹으로 묶는다). 연속한 테스트 케이스의 출력 사이에는 빈 줄을 하나 출력한다.