类型信息
约 3080 字大约 10 分钟
2025-01-23
类型在翻译过程中扮演着关键角色，因为它们帮助编译器理解源代码的意义以及其实现。这种比语法更深入的知识使得编译器能够检测出可能在运行时发生的错误。在许多情况下，它还允许编译器生成比没有类型信息时更为高效的代码。
编译器可以使用类型信息来确保操作符和操作数是兼容的——也就是说，操作符在其操作数的类型上被良好定义（例如，字符串连接可能未被定义在实数上）。在某些情况下，语言可能要求编译器插入代码以将不兼容的参数转换为兼容的类型——这个过程称为隐式转换。而在其他情况下（例如，将浮点数用作指针），语言定义可能会禁止这样的转换；此时，编译器至少应该发出一个有见地的错误消息，给程序员提供关于问题的洞察。
类型信息可以引导编译器进行高效执行的翻译。例如，在表达式 ax 中，a 和 x 的类型决定了如何最佳地评估该表达式。如果 x 是非负整数，编译器可以生成一系列乘法来评估 ax。相反，如果 x 是实数或负数，编译器可能需要生成使用更复杂评估方案的代码，比如泰勒级数展开。（更复杂的形式可以通过调用支持库来实现。）同样地，允许整个结构或整个数组赋值的语言依赖于兼容性检查，使编译器能够以高效的方式实现这些构造。
如果在翻译期间没有类型信息，编译器可能需要生成在运行时执行类型检查和代码选择的代码。每个未知类型的实体都需要一个运行时标签（runtime tag）来保存其类型信息。编译器不能仅仅发出简单的操作符，而是需要根据操作数的类型生成条件逻辑，这既包括为了生成标签所需的逻辑，也包括为了操作这些值及其标签所需的逻辑。
复合类型
编程语言的基础类型为处理器实际支持的数据种类提供了一种抽象。然而，基础类型通常不足以表示程序员所需的信息领域——如图、树、表、记录、对象、类、列表、栈和映射等这些抽象概念。这些更高级别的抽象可以通过多个实体的集合来实现，每个实体都有自己的类型。
构建新类型以表示复合或聚合对象的能力是许多语言的重要特性。典型的构造类型包括数组、字符串、枚举类型以及结构体或记录。复合类型让程序员能够以新颖且特定于程序的方式组织信息。构造类型使得语言可以表达更高层次的操作，例如整个结构的赋值。它们还提高了编译器检测不良形成程序（ill-formed programs）的能力。
数组
数组是最常使用的聚合对象之一。一个数组将多个相同类型的对象组合在一起，并给每个对象一个独特的名称——尽管这是一个隐式的、计算得出的名称，而不是显式由程序员指定的名称。C语言中的声明 int a[100][200]; 为100 x 200 = 20,000个整数预留了空间，并确保它们可以通过名称a来寻址。
字符串
真正的字符串类型在几个重要方面与数组类型不同。对字符串有意义的操作，例如连接、转换和计算字符串长度，在数组上可能没有对应的运算。标准比较运算符可以被重载，以便字符串比较能够自然地工作："a" < "boo" 和 "fee" < "fie"。为字符数组实现类似的比较暗示了这一想法可以应用于数字或结构体数组，但这种类比可能并不成立。同样地，字符串的实际长度可能与其分配的大小不同，而大多数情况下使用数组的应用会使用所有已分配的元素。
枚举类型
许多语言允许程序员构建包含特定常量值集合的类型。枚举类型让程序员可以为小集合的常量使用自文档化的名称。经典的例子包括一周中的几天和一年中的几个月。用C语言的语法，这些可能被写成：
enum WeekDay { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };
enum Month { January, February, March, April, May, June, July, August, September, October, November, December };编译器将枚举类型的每个元素映射到一个独特的值。枚举类型的元素是有序的，因此比较相同类型的元素是有意义的。在上述例子中，Monday < Tuesday 和 June < July。比较不同枚举类型的运算没有意义——例如，Tuesday > September 应该产生一个类型错误。
结构体与聚合
结构体，或称记录，将多个任意类型的对象组合在一起。结构体的元素通常被赋予明确的名称。例如，在C语言中实现一个解析树的程序员可能需要具有一个孩子节点和两个孩子节点的节点。
struct N1 {
int Operator;
int Value;
union Node *left;
};
struct N2 {
int Operator;
int Value;
union Node *left;
union Node *right;
};
union Node {
struct N1 one;
struct N2 two;
};结构体的类型是其包含元素类型的有序乘积。我们可以描述N1和N2如下： N1: int × int × (Node *) N2: int × int × (Node *) × (Node *)
这些新类型应该具有与基础类型相同的本质属性。在C语言中，对指向N1的指针进行自增操作或将指针转换为(N1 *)类型会有预期的效果——这种行为类似于基础类型发生的情况。
上述例子创建了一个新的类型Node，它是N1类型或N2类型结构体。因此，N1节点中的指针可以引用N1节点或N2节点。PASCAL使用带有变体记录的联合体。C语言使用联合体。联合体的类型是其组成部分类型的交替；因此，Node的类型是N1 ∪ N2。
语言和运行时之间需要一种机制来消除引用的歧义。一种解决方案是采用完全限定的引用，例如p->Node.N1.Value对比p->Node.N2.Value。
对象和类
在面向对象的语言中，类定义了对象的内容和形式，并且定义了用于解析对象相对引用的继承层次结构。然而，在实现上，一个对象看起来像一个其组织结构由类定义所指定的记录或结构体。
类型等价
struct Tree {
int value;
struct Tree *left;
struct Tree *right;
};
struct Bush {
int value;
struct Bush *left;
struct Bush *right;
};编译器需要一种机制来确定两个构造类型是否等价。（对于基本类型，答案是显而易见的。）考虑边栏中显示的C结构声明。Tree和Bush是同一种类型吗？它们等价吗？任何包含构造类型的编程语言都需要有一个明确的规则来回答这个问题。历史上，语言采用了两种方法之一。
名称等价性断言两个类型只有在程序员用相同的名字称呼它们时才是等价的。这种方法假设命名是一种有意的行为，并且程序员使用名称来传达意义。
结构等价性断言两个类型只有在它们具有相同的结构时才是等价的。这种方法假设结构重要，而名称可能不重要。 Tree和Bush具有结构等价性但不具备名称等价性。
每种方法都有其支持者和反对者。然而，选择哪一种方法是由语言设计者决定的，而不是由编译器编写者决定。编译器编写者必须为类型实现一个适当的表示形式和一个适当的等价性测试。
表达式的类型推断
表达式的结果类型取决于操作符及其操作数的类型。编译器可以在遍历表达式树的过程中自底向上地分配类型。在每个节点，它会根据该节点的操作符类型及其子节点来设置该节点的类型。或者，编译器可以将其作为语法驱动翻译框架的一部分来分配类型。
在具有更复杂推断规则的语言中，编译器可能会构建一个具有不完整类型信息的中间表示（IR），并执行一次或多次遍历来为子表达式分配类型。
编程语言在是否需要声明上有所不同。 在具有强制声明的语言中，声明为每个命名实体建立一个具体类型；这些类型进而作为类型推断的初始信息。而在不需要声明的语言中，如PYTHON或LISP，编译器必须从值在代码中出现的上下文中推断类型。例如，fee = 'a' 可能意味着 fee 有一个可以保存单个字符的类型，而fee = "a" 则意味着 fee 可以保存一个字符字符串。
编程语言也在代码中声明必须出现的位置上有所不同。许多语言有一个“先声明后使用”的规则；任何名称在出现在可执行代码之前都必须被声明。这个规则有助于在解析器翻译成初始中间表示（IR）形式期间进行类型检查。不要求在使用前声明的语言迫使编译器构建一个抽象掉类型细节的初始IR，并随后在这个抽象IR上执行类型推断和检查，以便编译器可以细化操作符和引用以反映正确的类型信息。
表达式的类型推断本质上依赖于构成可执行程序的其他过程。即使是最简单的类型系统，表达式中也包含函数调用。编译器必须检查每一个这样的调用。它必须确保每个实际参数与相应的形式参数之间的类型兼容性。它还必须确定返回值的类型以用于进一步的推断。
要执行准确的类型推断，编译器需要每个函数的类型签名。它可以通过几种方式获得这些信息。编译器可以要求整个程序在编译时都存在，从而消除单独编译。编译器可以要求为每个函数提供类型签名，通常通过强制性的函数原型来完成。编译器可以将类型检查推迟到链接时或运行时，这时此类信息是可用的。最后，编译器编写者可以在一个收集所需信息的程序开发系统中嵌入编译器。这些方法已经在实际系统中被使用。
章节回顾
类型表示所有该类型的值共有的属性集合。 类型系统为程序中的每个值分配一个类型。编程语言使用类型来定义合法和非法的行为。一个好的类型系统可以提高语言的表现力，揭示细微的错误，并让编译器避免运行时类型检查。 类型系统由一组基本类型、从现有类型构建新类型的规则、确定两种类型等价的方法以及推断表达式类型的规则组成。关于基本类型、构造类型和类型等价的概念应该从大多数高级语言中熟悉。
更新日志
70541-更新语法制导翻译于