AST

以一个数学运算为例： $1+2\ast (3+4)$ 它的AST可以表达为：

plus(num[1];times(2;plus(num[3];num[4])))

记$s$为AST节点的类型，$o$为ast的操作符，则在上面的例子中，只有一种节点类型：Exp，以及以下操作符：

1. num[n]，对于每个$n\in \mathbb{N}$。
2. plus,times，这是两个二元操作符。

每个操作符都接收一定数量的操作数，称操作符操作数的数量为arity。times，plus的arity为2，num[n]的arity为0。

操作符$o$接收n个特定类型的操作数后具有类型s，记为$(s_1,s_2,\cdots ,s_n)s$。

$S$是所有$s$的集合：$S=\{s_i\}$。

$O_{\alpha }$是所有arity为$\alpha$的操作数的集合，如上面的例子中，$O_2=\{\mathrm{plus},\mathrm{times}\}$。

$O$是所有$O_{\alpha }$的集合：$O=\{O_{\alpha }\}$。

$X_s$是所有类型为$s$变量的集合。

Reference

• pfpl. ch1.1