简易类型系统

题目描述

【题目背景】

0x2023 年，CC 国与 SP 国展开了一场激烈的算力竞赛。为了存储计算过程中使用的海量数据，CC 国研发了一款容量为 $1QiB=2^{100} B$（$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=2k$ 的无符号整型数取值范围为 $[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[N]$

其中 T 为任意类型，特别的，T 可以是另一个定长数组类型（例如 i32[4][6] 是一个合法的类型）；N 是一个小于 $2^{127}$ 的正整数，N 不会被存储到内存中，因此也不会占用任何空间。规定定长数组的下标从 $0$ 开始。若类型 T 占用 s 字节，则 T[N] 占用 $s×$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 ≥1$ 。T{i} 为第 $i$ 个子项的类型，记其占用字节数为 $s_i$ ，对齐字节数为 $a_i$ ；name{i} 为第 $i$ 个子项名。

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

• 设第 $i$ 个子项的偏移字节数为 $o_i$，规定首个子项的偏移字节数 $o_1=0$ 。

• 其后第 $i$ 个子项的偏移字节数 $o_i$ 为满足 $o_i ≥ o_{i−1}+s_{i−1}$ 且 $a_i|o_i$ 的最小值。

• 结构体的占用字节数 $s_{struct}$ 为满足 $s_{struct} ≥ o_N+s_N$ 且 $a_{struct}|s_{struct}$ 的最小值。保证本题中出现的所有类型（含中间类型）占用字节数不超过 $2^{120}$ 。

【任务一：静态类型检查】

给定 $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}$。

【任务二：分配类型实例】

在一段首地址为 $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} 并忽略这条指令;后续指令仍需处理。

【任务三：读写类型数据】

假设任务二中的内存空间是零初始化的，你需要依次处理n3条读取指令或写入指令。每条指令均为一整行、以 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;

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

• 表达式中的标识符是否为任务二中成功分配的变量名。

• &的操作对象不能是地址立即数。

• *的操作对象只能是地址立即数或指针。

• [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 进制科学记数法：一般格式为0x.p;表示

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

其中：

– 为符号位，正数为空，负数为‐；

– 为 {1;··· ;9;A;··· ;F} 中的一个字符；

– 为 {0;··· ;9;A;··· ;F} 组成的字符串（包含空串），但不以 0 结尾；特别的，当 **** 为空串时，之前的 '.' 一起省略；

– 为 10 进制格式整型数；特别的，当 **** 为0时，仍需要保留。

– 作为特例，规定0x0p0和**‐0x0p0** 分别与浮点数 0 和 −0 一一对应。

• 在输出时，你还需要考虑±∞与±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 ≤ n_1;n_2;n_3 ≤ 3×10^4)$

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

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

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

输出格式

输出到标准输出。

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

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

对于任务二的每条指令：

• 输出一行一个字符串表示错误信息。或者

• 输出一行一个16 进制格式的非负整数，表示分配到的内存首地址。 对于任务三的每条指令：

• 输出一行一个字符串表示错误信息。或者

• 对于读取指令，输出一行表示读取到的数据（格式见任务三描述）。或者

• 对于写入指令，没有输出。

样例 #1

样例输入 #1

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];

样例输出 #1

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

提示

对于所有的数据，满足 $0≤n_1;n_2;n_3≤3×10^4$。

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

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

特殊性质：

•A：保证没有错误。

•B：任务三中不涉及浮点数输入输出。

【提示】

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

•在C++语言中，你可以使用GCC的 __int128 和 unsigned__int128类型。

•在Java语言中，你可以使用 BigInteger 类。

•在Python语言中，默认的 int 类型即可满足精度要求。

【名词解释】

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

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

其表示的数值形如 $(−1)^s·M·2^E$，其中 $s∈{0;1}$ 控制符号；$M ∈[1;2)$ 为尾数；E为阶码。

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

• 当 $exp \not= 000···0$ 且 $exp \not= 111···1$ 时，此表示称为 规格化数，此时 $E =$ exp $−2^{w−1} +1，M =$ 1.frac = $1+\sum_{i=1}^tfrac_i ·2^{−i}$。

• 当 $exp =000···0$ 且 $frac \not= 000···0$ 时，此表示称为非规格化数，此时 $E = 2 −2^{w−1}，M =0.frac = \sum_{i=1}^tfrac_i ·2^{−i}$。

• 当 $exp =000···0$ 且 $frac = 000···0$ 时，表示的数为 0。需要特别注意的是，此时无论s如何取值，表示的数值都是0，但s仍然影响符号，即 $s=1$ 时表示 $−0，s = 0$ 时表示 $+0$。

• 当 $exp=111···1$ 且 $frac =000···0$ 时，表示的数为 $±∞$，符号由 $s$ 决定。

• 当 $exp=111···1$ 且 $frac=000···0$ 时，表示的数为 $±NaN$，符号由 $s$ 决定。不同位宽的浮点数的 $w$ 和 $t$ 取值如下：

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