题目

在将该文法[1]中消除左递归并提取左因子后,得到的新文法仍不是LL(1)文法。A，正确B，错误

在将该文法[1]中消除左递归并提取左因子后,得到的新文法仍不是LL(1)文法。

A，正确

B，错误

题目解答

答案

通常情况下，如果一个文法存在左递归或需要提取左因子，那么它不是LL(1)文法。通过消除左递归和提取左因子，可以使文法满足LL(1)文法的条件，即每个产生式[2]的FIRST集合不相交，并且对于每个非终结符，如果它有ε产生式，那么FIRST集合和FOLLOW集合不相交。

然而，需要注意的是，虽然消除左递归和提取左因子是使文法适应LL(1)解析器[3]的重要步骤，但这并不保证得到的文法一定是LL(1)文法。有些文法即使经过这些转换步骤后，仍然可能不是LL(1)文法，因为可能存在FIRST集合重叠或FIRST和FOLLOW集合重叠的情况。

因此，题目中的说法是错误的，因为消除左递归和提取左因子后得到的新文法有可能是LL(1)文法，但并不能保证一定是。

答案选择为B.

解析

关键知识点：
LL(1)文法的判定条件包括两个核心要求：

  1. 每个非终结符的所有产生式的FIRST集合必须互不相交；
  2. 若某个产生式可推导出空串（ε），则其FIRST集合与对应非终结符的FOLLOW集合也必须互不相交。

解题核心思路：
消除左递归和提取左因子的主要目的是消除FIRST集合的交叠，但这些操作仅是必要条件而非充分条件。即使完成这些转换，仍可能存在以下问题：

  • 某些产生式的FIRST集合仍有交叠；
  • 存在可推导出空串的产生式，导致FIRST与FOLLOW集合交叠。

因此，题目中的说法错误，因为消除左递归和提取左因子后的新文法可能是LL(1)文法，但无法保证一定满足LL(1)条件。

关键步骤分析

  1. 消除左递归：

    • 左递归会导致FIRST集合无限递归，破坏LL(1)的预测分析能力。消除左递归后，确保每个非终结符的产生式不再直接或间接左递归。

  2. 提取左因子：

    • 左因子会导致多个产生式的FIRST集合交叠。提取左因子后，将共享前缀的产生式合并，使FIRST集合互不相交。

  3. 验证LL(1)条件：

    • 即使完成上述操作，仍需检查所有产生式的FIRST集合是否完全互不相交，以及是否存在FIRST与FOLLOW的交叠。
    • 反例：若某非终结符有两个产生式，其中第一个产生式可推导出空串，第二个产生式的FIRST集合与该非终结符的FOLLOW集合有交叠，则文法仍不是LL(1)。

结论

消除左递归和提取左因子是LL(1)文法的必要步骤，但不能保证文法最终满足LL(1)条件。因此题目中的说法错误，正确答案为B。