LL(1)文法为什么FIRST和FOLLOW不能有交集? 木灵的炼金工作室

首先我们需要知道,LL(1)分析的核心问题是:「如何通过只向前看1个词法单元来唯一确定与当前句子匹配的产生式」,它对于文法的要求是「在1个向前看符号下无推导二义性」,换句话说,就是在LL(1)预测分析表中,(以非终结符号为行标,向前看终结符号为列标)每一个格子里最多填入一个产生式。否则,我们在分析过程中就无法通过1个向前看符号来确定需要使用哪一个产生式。

我们找到每个产生式推导得出的句子的最左边的1个终结符号来指导我们填入这些产生式。如某产生式的最左侧是终结符号,那么我们直接将其填入对应的格子中。如某产生式的最左侧是非终结符号,我们就计算它的FIRST集合,用这个FIRST集合中的终结符号来代表这个非终结符号,从而指导产生式的选择。这样就会产生两个问题:

某些非终结符号有复数个左部相同的产生式,如F→Ab|Ac,这就导致了上述每一个格子里最多填入一个产生式的要求不能满足。因此我们提出了左公因子提取算法。 不是所有的非终结符号都能够成功以LL(1)方式求出FIRST集合。比如有产生式A→Ac|d,其中的A无法求出FIRST集合,原因是存在左递归。因此我们提出了左递归消除算法。 借由这两个算法,我们可以将绝大多数的产生式填入预测分析表,但还有相当一部分可能推出空串的非终结符号,它们的FIRST集合中包含ε,而ε不能用来代表非终结符号来与词法单元匹配,毕竟没有任何一个词法单元代表ε。

那么怎么确定“什么时候使用ε产生式”呢?我们可以通过考察这个非终结符号在文法中的后继终结符号来决定是否使用ε产生式。这就是FOLLOW集合起作用的地方:如果我们看到的向前看符号属于目前非终结符号的FOLLOW集合,就表明这个非终结符号可能推出了一个空串。但是,如果某一个可以推出空串的非终结符号F的FIRST集合中存在某终结符号a,且a同时存在于FOLLOW集合中,那么此时我们就无法确定a到底来源于F本身还是F后继的内容,也就是说,这时的预测分析表中的(F, a)格子中同时存在了ε产生式和另一个F产生式,这就产生了「向前看1的二义性」。换句话说,在这种情况下,我们不知道是否该选用ε产生式,或者另一个可以若干次推出“以a为开头的句子”的产生式。

所以LL(1)文法不允许能够推出空串的非终结符号的FIRST集合与FOLLOW集合有相交。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn