6.3.1 一个例子

图6.3.1_1 Fig.6.8

图6.8展示了对句子aabc的一个完整的广度优先解析过程。最开始只有一个预测栈:它包含开始符号和终止记号;没有符号被接受(a)。得到(b)的步骤是一个预测步骤;有两个可能的右侧,所以我们得到两个预测栈。预测栈的不同也表现在了分析栈上,S的不同后缀代表不同的右侧选择。下一个有多种右侧的预测步骤得到了(c)。现在所有预测栈栈顶都是终结符;刚好都成功匹配,得到(d)。接下来,有些预测开头又是非终结符了,所以进行下一个预测步骤得到(e)。下一个步骤是匹配步骤,幸运的是,有些匹配失败了;这些会被去掉,因为由它们不可能得到成功的解析。从(f)到(g)又是一个预测步骤。另一个有一些失败匹配的匹配步骤让我们得到(h)。更远的一个预测步骤导致(i)然后接着一个匹配步骤最终给我们带来(j),终止记号匹配,解析成功。
解析(analysis)是
S2A2aA1aB1bc#
目前,我们不需要解析里的终结符;把它们去掉得到
S2A2A1B1
这说明我们通过先应用规则S2,再A2等等得到最左推导,每次替代掉最左的非终结符。检查一下:
S→AB→aAB→aaB→aabc
这里描述的广度优先最初被Greibach [7]陈述。但是,在那个陈述中,语法被转化为了格雷巴赫范式,并且使用的步骤跟我们最开始的下推自动机的相似。预测和匹配步骤被结合起来了。

results matching ""

    No results matching ""