形式语义学

formal semantics

程序设计理论的组成部分，以数学为工具，利用符号和公式，精确地定义和解释计算机程序设计语言的语义，使语义形式化的学科。

起源与发展 为了正确、有效地使用程序设计语言，必须弄清语言中各成分的含义，并且要求计算机系统执行这些成分所产生的效果和它的语义完全一致。由于自然语言存在歧义性，故用自然语言解释程序设计语言的含义容易造成误解，影响语言的正确实现和有效使用。实践证明，必须用形式化的语言和方法精确解释程序设计语言。这种需求产生了形式语义学。20世纪60年代初，在程序设计语言ALGOL60的设计中，第一次明确区分了语言的语法和语义，围绕ALGOL60的语义问题出现了形式语义学早期的研究高潮。

70年代，形式语义学取得重大进展，指称语义、代数语义等理论和方法对程序设计理论有深刻的影响。操作语义、公理语义等研究也开创了新的局面。

形式语义学是软件工程学的基础理论之一，语言的形式语法和形式语义已成为程序设计语言的必要组成部分。在形式语义学基础上，形式规范、程序变换、编译自动化等研究都取得了丰硕的成果。

主要内容 用程序设计语言编写的程序，规定了计算机对数据的加工过程。形式语义学的基本方法是用一种元语言将程序加工数据的过程及其结果形式化，从而定义程序的语义。根据所用数学工具和研究重点，形式语义学可分为四大类。

①操作语义学。通过语言的实现方式定义语言的语义，也就是将语言成分所对应的计算机的操作作为语言成分的语义。因为语言的语义应该是标准的，不应依赖于特定的计算机系统，或一种具体的实现方式，因此，操作语义学使用抽象机和抽象解释程序来定义语言的语义。

②指称语义学。通过执行语言成分所要得到的最终效果来定义该语言成分的语义。指称语义学方法认为语言成分的含义是语言成分本身固有的，不依赖于具体实现该语言成分的计算机。对同一种语言成分，不同的计算机的执行实现过程可以不同，但所产生的最终效果应该是相同的。这种最终效果被看作是语言成分所指称的外在物体，称作语言成分的指称物。指称物多为数学对象，如整数、集合、函数等。指称语义学方法在定义语言的语义时，先确定指称物，然后给出语言成分到指称物的语义映射，这种映射必须满足两个条件：每个语言成分都对应有指称；复合成分的指称只依赖于它的子成分的指称。论域理论是指称语义学方法的数学基础。

③代数语义学。用代数公理刻划语言成分的语义，只要研究抽象数据类型的代数规范。抽象数据类型的代数规范通过构造算子和一组有关运算的代数公理刻划类型操作的行为。在论证这种规范满足协调性和完全性的基础上，通过寻找适当的模型代数，可以定义一个抽象类型的不同层次的语义，如初始语义、终止语义等。然后就可以用普通的代数方法论证规范的正确性和实现的正确性。

④公理语义学。通过使用数学中的公理化方法，用公理系统定义程序设计语言的语义。另外，公理语义学还研究和寻求适用于描述程序语义、便于语义推导的逻辑语言。例如，用时态逻辑定义的语言的公理语义又称为时态语义。典型的公理语义方法是Hoare公理系统。