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)

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

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

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

results matching ""

    No results matching ""