3.1.3 解析树的线性化

通常构建一棵实际的解析树是不方便也是不必要的：相反一个解析器可以生成一列规则编号，这意味这其线性化了解析树。有三种主要方法来线性化一棵解析树，前缀、后缀和中缀。前缀表示法中，每一个节点都被列出通过列出其编号然后接着是子节点列表的前缀，由左到右的顺序；这给了我们最左侧的推导（图Fig 3.2的右边的树）：

最左侧:2 2 1 3c 1 3e 1 3a

如果一棵解析树是根据这个方法构建的，那它是在前序中构建。在前缀表示中，每一个节点被列出通过列举全部前缀表示按从左到右的顺序，后面接着节点自身规则的编号；这给了我们最右侧的推导（同一棵树的）：

最右侧: 3c 1 3e 1 2 3a 1 2

这在后序中构建解析树。中缀表示法中，每个节点都被列举，通过首先给一个列举在括号中第一个n子节点的中缀，然后接着是节点的规则编号，然后接着是一个列举在括号中其余子节点的中缀；n可以自由选择，甚至规则之间可以不同，但是n = 1 是正常的。中缀在派生中是不常见的，但偶尔是有用的。n = 1的情况被称为左角推导；在例子中我们得到：

左角: (((3c)1) 2 ((3e)1)) 2 ((3a)1)

中缀表示法需要括号来使我们从中重建生成树。最左和最右推导不用括号也能完成，使我们准备好语法来找到每个节点的子节点数。

很容易区分一个推导是最左还是最右的：一个最左推导开始于起始符号的一个规则，而一个最右推导开始于只生成终结符的一个规则。（如果两个条件同时成立，那只有一个规则可以，可以同时是最左和最右推导的。）

几个不同推导的存在不应该与模糊性混为一谈。不同的推导只是同一个生成树的符号变形。对于其不同没有不同的语义可以附加。