时间限制： 1.0 秒

空间限制： 512 MB

题目背景

0x2023 年，CC 国与 SP 国展开了一场激烈的算力竞赛。为了存储计算过程中使用的海量数据，CC 国研发了一款容量为 $1\text{ QiB}=2^{100}\text{ B}$（$\text{B}$ 为字节，1 字节 = 8 二进制位）的新型内存。已经称为 CC 国工程院院士的小 C 发现 64 位架构已经无法充分利用如此巨大的内存空间，于是他决定研发一款 128 位架构的新系统。

为了与绝大多数现有的 64 位系统兼容，小 C 决定沿用小端序作为新系统的字节顺序，即：低位字节存储在低地址上，高位字节存储在高地址上。例如一个占 32 位的无符号整型数 0xDEADBEEF 在内存中的存储方式为：

地址	0x00	0x01	0x02	0x03
Byte	0xEF	0xBE	0xAD	0xDE

作为小 C 的得意门生，你被指定来完成新系统中类型系统部分的验证工作。具体来说，你需要完成以下三个任务：

1. 静态类型检查： 计算类型的对齐字节数与占用字节数，并验证类型系统的完整性。
2. 分配类型实例： 在新型内存上为不同类型的变量分配空间，验证类型系统能够充分利用新型内存。
3. 读写类型实例： 读取、写入已分配的变量，验证类型系统能够在新型内存上正确工作。

由于还在验证阶段，用来测试的指令可能有些问题，你可能还需要处理一些非法或冲突的情况。对于第一个任务，如果出现了问题，你需要汇报第一个导致问题的类型并停止后续执行；对于后两个任务，如果遇到了有问题的指令，你需要汇报出现问题的指令，同时跳过这条指令继续执行后续指令。

由于系统中的类型和用来验证的指令数量都非常庞大，你决定写个程序来模拟这个过程。

题目描述

注记： 如果你对以下描述中以加粗下划线格式标注的概念不熟悉，可以先阅读本题后附加的名词解释部分。

本题中，你要在一个最大位宽为 128 的小端序设备上实现一个类型系统，其中的类型包括：

• 整型数 {u,i}{8,16,32,64,128}

包含无符号和有符号两类，每类又包含 8,16,32,64,128 五种位宽。

其中位宽为 $w=2^k$ 的无符号整型数取值范围为 $[0,2^w-1]$，类型名为 u{w}（例如 u8）；位宽为 $w=2^k$ 的有符号整型数使用二进制补码表示，取值范围为 $[-2^{w-1},2^{w-1}-1]$，类型名为 i{w}（例如 i64）；位宽为 $2^k$ 的整数对齐到 $2^{k-3}$ 字节。

• 浮点数 {f}{16,32,64,128}

包含 16,32,64,128 四种位宽。

所有浮点数均采用 IEEE Std 754-2019 标准 表示，其中位宽为 $w=2^k$ 的浮点数的类型名为 f{w}（例如 f32），对齐到 $2^{k-3}$ 字节。

整型数与浮点数统称为基本数据类型。

• 指针 T*

其中 T 为任意类型。指针类型占用 16 字节，对齐到 16 字节。

• 定长数组 T[N]

其中 T 为任意类型，特别的，T 可以是另一个定长数组类型（例如 i32[4][6] 是一个合法的类型）；N 是一个小于 $2^{127}$ 的正整数，N 不会被存储到内存中，因此也不会占用任何空间。规定定长数组的下标从 0 开始。若类型 T 占用 $s$ 字节，则 T[N] 占用 $s\times N$ 字节；若类型 T 对齐到 $2^t$ 字节，则 T[N] 也对齐到 $2^t$ 字节。

• 联合体 union typename { T1 name1, T2 name2, ..., TN nameN }
• 结构体 struct typename { T1 name1, T2 name2, ..., TN nameN }

其中 typename 为类型名。联合体或结构体包含至少一个子项，即子项数 $N\ge 1$。T{i} 为第 $i$ 个子项的类型，记其占用字节数为 $s_i$，对齐字节数为 $a_i$；name{i} 为第 $i$ 个子项名。

联合体与结构体的对齐字节数均为所有子项对齐字节数的最大值，即 $a_{\text{union}}=a_{\text{struct}}=\max\limits_{i=1}^N a_i$。联合体内所有子项靠前且重叠地存储在同一段内存中，占用字节数为所有子项占用字节数的最大值并向上对齐到对齐字节数，即满足 $s_{\text{union}}\ge \max\limits_{i=1}^N s_i$，且 $a_{\text{union}}|s_{\text{union}}$ 的最小值；结构体内各个子项的存储方式及结构体的占用字节数按如下方式确定：

• 设第 $i$ 个子项的偏移字节数为 $a_i$，规定首个子项的偏移字节数 $o_1=0$。
• 其后第 $i$ 个子项的偏移字节数 $o_i$ 为满足 $o_i\ge o_{i-1}+s_{i-1}$ 且 $a_i|o_i$ 的最小值。
• 结构体的占用字节数 $s_{\text{struct}}$ 为满足 $s_{\text{struct}}\ge o_N+s_N$ 且 $a_{\text{struct}}|o_{\text{struct}}$ 的最小值。

保证本题中出现的所有类型（含中间类型）占用字节数不超过 $2^{120}$。

任务 1：静态类型检查

给定 $n_1$ 条联合体或结构体的声明指令或定义指令。两种指令均为一整行，以 union 或 struct 开头，以 ; 结尾。

声明指令的格式为：

{union, struct} typename;

其中 typename 为任意标识符。标识符是满足以下条件的字符串：

• 由大小写英文字母、下划线、数字组成，不包含空格或其他字符。
• 不是 struct、alloc 等关键字，因此你无需考虑标识符与关键字冲突的问题。

在此基础上，规定合法标识符还需要满足以下条件：

• 以大小写字母或下划线开头，即不以数字开头。
• 不能与基本数据类型的类型名冲突。

声明指令的示例如下：

union myUnion;
struct myStruct;

定义指令的格式为：

{union, struct} typename { T1 name1, T2 name2, ..., TN nameN };

其中 typename 为任意标识符；T{i} 为任意类型名；子项名 name{i} 为任意标识符，但不能与其他子项名冲突。保证输入数据中 '{' 前后、',' 后、'}' 前均有且只有一个空格，最后一个子项名后没有 ','。示例如下：

union myUnion { u64 dword, u8[8] bytes };
struct pair { int first, int second };
struct tuple { pair first, int third };

在本任务中，对于每条指令，你首先需要检查它是否合法且没有冲突，具体包括：

• 类型名、子项名（保证它们总是标识符）是否为合法标识符。
• 同一类型名是否被定义了超过一次。
• 同一类型名是否既被声明或定义为联合体又被声明或定义为结构体。
• 在联合体或结构体内，同一子项名出现了超过一次。

保证不会出现除以上列出现情形外的错误。若在处理第 $i$（从 $2$ 开始计数）条指令时出现以上问题中的任何一种，输出 syntax error on line {i}。你无需再进行后续处理，直接退出程序即可。

接下来你需要检查是否存在不完整类型。不完整类型包括且仅包括：

• 声明但未定义的类型。
• 直接或间接包含自身的类型。间接包含需要考虑定长数组、联合体、结构体；允许包含指向自身类型的指针。
• 其他包含不完整类型的类型。

若存在这样的类型 typename，输出 incomplete type {typename}；若有多个这样的类型，只需要输出声明指令或定义指令最靠前的那个。 你无需再进行后续处理，直接退出程序即可。

若没有出现以上问题，你需要计算每种类型的占用字节数和对齐字节数。按首次声明或定义的顺序，每种类型输出一行一个字符串与两个整数，分别表示类型名、占用字节数与对齐字节数，以空格分隔。保证类型的占用字节数不超过 $2^{124}$。

任务 2：分配类型实例

在一段首地址为 $0$，大小为 $2^{100}$ 字节的内存空间中，你需要依次处理 $n_2$ 条分配指令。每条指令均为一整行，以 alloc 开头，以 ';' 结尾。

分配指令的格式为：

alloc T name;

其中 T 为任意类型，变量名 name 为任意标识符，但不能与类型名或已经成功分配的变量名冲突。示例如下：

alloc i32[2][3][4] a;
alloc pair[2] b;
alloc myUnion** c;

在本任务中，对于每条指令，你首先要检查它是否合法且没有冲突，具体包括：

• 变量名（保证为标识符）是否为合法标识符，且不与类型名或已经成功分配的变量名冲突。
• 类型中是否出现了未定义的类型名。

保证不会出现除以上列出情形外的错误。若在处理第 $i$（从 $n_1+2$ 开始计数）条指令时出现以上问题中的任何一种，输出 syntax error on line {i} 并忽略这条指令，后续指令仍需处理。

若没有出现以上问题，你需要为这个变量分配一段连续的内存空间，大小为其类型的占用字节数，首地址需要为其类型的对齐字节数的倍数。若存在多个满足条件的首地址，你需要选择最小的那个。若无法找到满足条件的首地址，输出 memory allocation failed for {name} 并忽略这条指令，后续指令仍需处理。

任务 3：读写类型数据

假设任务 2 中的内存空间是零初始化的，你需要依次处理 $n_3$ 条读取指令或写入指令。每条指令均为一整行，以 read 或 write 开头，以 ';' 结尾。

读取指令的格式为：

read expr;

其中 expr 为任意表达式。表达式由以下规则生成：

• 任何标识符都是表达式。
• 若 expr 是表达式，且类型不为地址立即数，则 &expr 也是表达式，表示取 expr 的地址，类型为指向 expr 类型的地址立即数。（请注意区分地址立即数与指针类型；指针类型在指向向一段内存的同时，自身也被存储在内存中，可以对其进行取地址操作；地址立即数是对任意变量取地址得到的地址值，没有存储在内存中，不能继续取地址）。
• 若 expr 是表达式且类型为地址立即数或指针，则 *expr 也是表达式，表示访问其指向的内存，类型为其指向的类型。
• 若 expr 是表达式且类型为定长数组，则 expr[index] 也是表达式，表示访问定长数组中下标为 index 的元素，类型为定长数组的元素类型。保证 index 是一个小于 $2^{127}$ 的非负整数。
• 若 expr 是表达式且类型为结构体或联合体，则 expr.name 也是表达式，表示访问结构体或联合体中名为 name 的子项，类型为子项的类型。保证 name 为由大小写英文字母、下划线与数字组成的字符串。
• 若 expr 是表达式，则 (expr) 也是表达式，用于改变操作优先级，类型不变。
• 所有表达式只能由以上规则生成。

运算优先级从高到低依次为 [index] > & = * > .name。示例如下：

read &a;
read a[3][1][1];
read b[1].second
read (**c).bytes[2];

写入指令的格式为：

write expr = value;

其中 expr 为表达式，value 为一个整型或浮点常量（格式规定见下文）。示例如下：

write a[1][1][2] = 233;
write b[1].second = -0666;
write (**c).bytes[2] = 0xDD;
write some_f32 = -1.2p3;

在本任务中，对于每条指令，你首先要检查它是否合法且没有冲突，具体包括：

• 表达式中的标识符是否为任务 2 中成功分配的变量名。
• & 的操作对象不能是地址立即数。
• * 的操作对象只能是地址立即数或指针。
• [index] 的操作对象只能是定长数组，并且 index 需要小于定长数组的大小。
• .name 的操作对象只能是联合体或结构体，并且 name 需要为合法的子项名。
• 指针指向的地址需要是其指向类型的对齐字节数的倍数，并且其指向对象完整地落在内存空间内。无论是否进行后续操作，任何指针类型都需要进行此检查。

保证不会出现除以上列出情形为的错误。若在处理第 $i$（从 $n_1+n_2+2$ 开始计数）条指令时出现以上问题的任何一种，输出 syntax error on line {i} 并忽略这条指令，后续指令仍需处理。

若没有出现以上问题，你需要对表达式 expr 对应的内存（或地址立即数）进行读取或写入操作。首先规定本题中基本数据类型使用如下的格式进行输入输出：

• 整型数的一般格式：正数与 $0$ 不带符号；除 $0$ 外，数字部分无前导零。
• 整型数的 $10$ 进制格式：没有额外前缀。
• 整型数的 $8$ 进制格式：除负号外以单个 0 为前缀。例如 $233$ 的 $8$ 进制格式为 0351；$-10$ 的 $8$ 进制格式为 -012。
• 整型数的 $16$ 进制格式：除负号外以 0x 为前缀，字母大写。例如 $233$ 的 $16$ 进制格式为 0xE9；$-10$ 的 $16$ 进制格式为 -0xA。
• 浮点数的 $16$ 进制科学计数法：一般格式为 <S>0x<A>.<B>p<C>，表示

$$S(A+\sum\limits_{i=1}B_i\times 16^{-i})\times 16^C $$

• 其中
  • <S> 为符号位，正数为空，负数为 -；
  • <A> 为 {1,...,9,A,...,F} 中的一个字符；
  • <B> 为 {0,...,9,A,...,F} 组成的字符串（包含空串）但不以 0 结尾；特别的，当 <B> 为空串时，之前的 '.' 一起省略；
  • <C> 为 $10$ 进制格式整型数；特别的，当 <C> 为 $0$ 时，仍需要保留。
  • 作为特例，规定 0x0p0 和 -0x0p0 分别于浮点数 $0$ 和 $-0$ 一一对应。
• 在输出时，你还需要考虑 $\pm\infty$ 与 $\pm\text{NaN}$，规定他们的输出格式分别为 inf、-inf 与 nan、-nan；保证输入浮点数时不会出现这两种特殊值。

若操作为写入操作，你还需要检查 expr 的类型是否为基本数据类型。若不是，输出 cannot write to nonprimitive type并忽略这条指令，后续指令仍需处理；否则，你需要将 value 写入到 expr 对应的内存中。

• 当 expr 的类型为整型数时，value 为一个 $8$、$10$ 或 $16$ 进制格式的整型常量。保证 value 在对应整型的取值范围内。
• 当 expr 的类型为浮点数时，value 为一个 $16$ 进制科学计数法表示的浮点常量。保证 value 对应浮点类型的一个精确值。

若操作为读取操作，你需要根据 expr 的类型，以不同的格式输出其值：

• 整型数：以 $10$ 进制格式输出。
• 浮点数：以 $16$ 进制科学计数法输出其精确值。
• 地址立即数或指针：输出 pointer to {addr}。其中 addr 为其指向的内存地址，使用整型数的 $16$ 进制格式输出。
• 定长数组：输出 array[N] at {addr}。其中 N 为数组长度，采用十进制格式；addr 为数组首地址，格式同上。
• 联合体或结构体：输出 typename at {addr}。其中 typename 为类型名；addr 为联合体或结构体首地址，格式同上。

输入格式

从标准输入读入数据。

输入的第一行包含三个非负整数 $n_1,n_2,n_3$，分别表示每类任务的操作数量，保证 $0\le n_1,n_2,n_3\le 3\times 10^4$。

接下来 $n_1$ 行，每行一条声明指令或定义指令，格式见任务 1 描述。

接下来 $n_2$ 行，每行一条分配指令，格式见任务 2 描述。

接下来 $n_3$ 行，每行一条读取指令或写入指令，格式见任务 3 描述。

输出格式

输出到标准输出。

对于任务 1，输出一行一个字符串表示错误信息。或者对于每种类型（按声明指令或定义指令首次出现的顺序）；

• 输出一行一个字符串与两个 $10$ 进制格式的整数，分别表示类型名、占用字节数与对齐字节数，以空格分隔。

对于任务 2 的每条指令：

• 输出一行一个字符串表示错误信息。或者
• 输出一行一个 $16$ 进制格式的非负整数，表示分配到的内存首地址。

对于任务 3 的每条指令：

• 输出一行一个字符串表示错误信息。或者
• 对于读取指令，输出一行表示读取到的数据（格式见任务 3 描述）。或者
• 对于写入指令，没有输出。

5 1 4
union data { u64 dword, u8[8] bytes };
struct node;
union pointer { node* ptr, u128 addr };
struct neighbors { pointer prev, pointer next };
struct node { data[2] dat, neighbors nbr };
alloc node[10] nodes;
write nodes[1].dat[1].dword = 0x123456789ABCDEF0;
write nodes[5].nbr.prev.addr = 0x30;
read nodes[1].dat[1].bytes[4];
read (*(nodes[5].nbr.prev.ptr)).dat[1].bytes[4];

data 8 8
node 48 16
pointer 16 16
neighbors 32 16
0x0
120
120

0 8 0
alloc u8 a;
alloc u128 b;
alloc u16 c;
alloc u32 d;
alloc u64 e;
alloc u128 f;
alloc u8 g;
alloc u32 h;

0x0
0x10
0x2
0x4
0x8
0x20
0x1
0x30

4 0 0
struct a;
struct b { a _a };
struct c;
struct a { b _b };

incomplete type a

0 5 5
alloc f16[10][10] a;
alloc u16[5] b;
alloc gg c;
alloc u64* d;
alloc f128* e;
write *d = 0x123456789ABCDEF0;
read &a[0];
read a[0][2];
write a[0] = 0x1.2p-1;
read *e;

0x0
0xC8
syntax error on line 4
0xE0
0xF0
pointer to 0x0
0x6.78p1
cannot write to nonprimitive type
0x4.8D159E26AF37BCp-4109

0 5 10
alloc f16[100]* a;
alloc u128[4]* b;
alloc i32 c;
alloc u128* d;
alloc f128 e;
write (*b)[0] = 0x4;
write (*a)[15] = 0x1p2;
write (*a)[34] = -0x2p3;
read c;
read e;
write (*b)[3] = 0x40;
write *d = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;
read e;
write *d = 0x7FFF0000000000000000000000000000;
read e;

0x0
0x10
0x20
0x30
0x40
1543503872
0x3.Cp-4104
-nan
inf

子任务

对于所有的数据，满足 $0\le n_1,n_2,n_3\le 3\times 10^4$。

保证输入文件大小、输出文件大小均不超过 $2^{24}$ 字节。

保证本题中出现的所有类型（含中间类型）占用字节数不超过 $2^{120}$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

此外，本题中子任务存在直接依赖，即只有当前子任务直接依赖的子任务全部通过时，才会开始该子任务评测。

子任务编号	直接依赖	分值	$n_1\le$	$n_2\le$	$n_3\le$	特殊性质
1sc	无	5	$10$	$0$	$0$	A
1se	1sc	3				无
2sc	无	5	$0$	$10$		A
2se	2sc	3				无
23sc		7			$10$	A,B
23se	2se,23sc	2				B
23fsc	23sc	5				A
23fse	23se,23fsc	2				无
123sc	1sc,23sc	11	$10$			A,B
123se	1se,23se,123sc	3				B
123fsc	123sc	5				A
123fse	23fse,123se,123fsc					无
12me	1se,2se	2	$300$	$300$	$0$
23me	23se		$0$		$300$	B
23fme	23fse,23me	5				无
1le	1se		$3\times 10^4$	$0$	$0$
2le	2se		$0$	$3\times 10^4$
12lc	1sc,2sc		$3\times 10^4$			A
23flc	2fsc	7	$0$		$3\times 10^4$
123fle	(ALL)	13	$3\times 10^4$			无

• 特殊性质 A：保证没有错误
• 特殊性质 B：任务 3 不涉及浮点数输入输出。

提示

由于部分数据规模较大，你可能需要使用高精度整型数：

• 在 C++ 语言中，你可以使用 G++ 的 __int128 和 unsigned __int128 类型。
• 在 Java 语言中，你可以使用 BigInteger 类。
• 在 Python 语言中，默认的 int 类型即可满足精度要求。

名词解释

补码：正数与 $0$ 直接使用二进制表示；负数使用其绝对值的二进制表示，然后按位取反再加一。例如 $-10$ 的 8 位补码位 11110110。

IEEE Std 754-2019 标准：规定了浮点数的表示方式，包括 16、32、64、128 位四种位宽。

其表示的数值形如 $(-1)^s\cdot M\cdot 2^E$，其中 $s\in\{0,1\}$ 控制符号；$M\in[1,2)$ 为尾数；$E$ 为阶码。

其编码按二进制位从高到低分为 s、exp 与 frac 三部分，分别与 $s,E,M$ 对应，其中 s 占 1 位，取值与 $s$ 相同；exp 占 $w$ 位，frac 占 $t$ 位，$w$ 和 $t$ 的取值随位宽改变而变化，exp 和 frac 与 $E$ 和 $M$ 的对应关系也随 exp 不同而有所差别。

• 当 exp 不为 000...0 且 exp 不为 111...1 时，此表示称为规格化数，此时 $E=\text{exp}-2^{w-1}+1$，$M=1.\text{frac}=1+\sum\limits_{i=1}^t\text{frac}_i\cdot 2^{-i}$。
• 当 exp 为 000...0 且 frac 不为 000...0 时，此表示称为非规格化数，此时 $E=2-2^{w-1}$，$M=0.\text{frac}=\sum\limits_{i=1}^t\text{frac}_i\cdot 2^{-i}$。
• 当 exp 为 000...0 且 frac 为 000...0 时，表示的数为 $0$。需要特别注意的是，此时无论 $s$ 如何取值，表示的数值都是 $0$，但 $s$ 仍然影响符号，即 $s=1$ 时表示 $-0$，$s=0$ 时表示 $+0$。
• 当 exp 为 111...1 且 frac 为 000...0 时，表示的数为 $\pm \infty$，符号由 $s$ 决定。
• 当 exp 为 111...1 且 frac 不为 000...0 时，表示的数为 $\pm\text{NaN}$，符号由 $s$ 决定。

不同位宽的浮点数的 $w$ 和 $t$ 取值如下：

位宽	$w$	$t$
16	5	10
32	8	23
64	11	52
128	15	112

更多有关 IEEE Std 754-2019 标准的细节可以阅读附加文件区的 IEEE Std 754-2019.pdf。

参考资料

• ”IEEE Standard for Floating-Point Arithmetic,” in IEEE Std 754-2019 (Revision of IEEE 754-2008), vol., no., pp.1-84, 22 July 2019.