软考题库
软件设计师 · 高频练习

文法 E→E+T|T 怎样消除直接左递归？

中级 单选题 第 839 题 中等 软件设计师编译原理直接左递归文法改写递归下降分析
内容整理：软考题库编辑部 最近更新：
题目

文法 E→E+T|T 含有直接左递归。保持其生成语言不变，正确的消除结果是（）。

A E→TE′，E′→+TE′|ε
B E→E′T，E′→E+|ε
C E→+TE，E→T
D E→T+E，E→ε
题目类型：原创高频练习题 用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。
正确答案
A
答案解析

直接左递归的一般形式 A→Aα|β 可改写为 A→βA′，A′→αA′|ε。本题 α=+T，β=T，因此得到 E→TE′，E′→+TE′|ε。改写后 E 的推导从 T 开始，不再一上来调用自身。

选项分析

A

正确。符合 A→βA′、A′→αA′|ε 的标准改写。

B

错误。产生式结构没有正确保留原文法中 T 和 +T 的组合关系。

C

错误。该写法改变了表达式语言，而且仍没有形成标准的可重复尾部结构。

D

错误。加入 E→ε 会让空串进入语言，改变原文法；E→T+E 还要求每次递归前必须出现加号后的表达式。

本题为什么容易错

公式背错时最容易漏掉 ε。新非终结符 E′ 表示“后面还可以有若干个 +T”，若没有 ε，它就无法结束，连单独的 T 都生成不了。

先看结论

简短答案

文法 E→E+T|T 怎样消除直接左递归，正确答案是 A（E→TE′，E′→+TE′|ε）。直接左递归的一般形式 A→Aα|β 可改写为 A→βA′，A′→αA′|ε。本题 α=+T，β=T，因此得到 E→TE′，E′→+TE′|ε。改写后 E 的推导从 T 开始，不再一上来调用自身。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
E→TE′，E′→+TE′|ε 本题正确答案 正确。符合 A→βA′、A′→αA′|ε 的标准改写。 看到题干核心场景时优先联想到它
E→E′T，E′→E+|ε 本题干扰项 错误。产生式结构没有正确保留原文法中 T 和 +T 的组合关系。 看到该词不要急着选，先判断是否真正解决题干问题
E→+TE，E→T 本题干扰项 错误。该写法改变了表达式语言，而且仍没有形成标准的可重复尾部结构。 看到该词不要急着选，先判断是否真正解决题干问题
E→T+E，E→ε 本题干扰项 错误。加入 E→ε 会让空串进入语言，改变原文法；E→T+E 还要求每次递归前必须出现加号后的表达式。 看到该词不要急着选，先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • E→E′T，E′→E+|ε：错误。产生式结构没有正确保留原文法中 T 和 +T 的组合关系。
  • E→+TE，E→T：错误。该写法改变了表达式语言，而且仍没有形成标准的可重复尾部结构。
  • E→T+E，E→ε：错误。加入 E→ε 会让空串进入语言，改变原文法；E→T+E 还要求每次递归前必须出现加号后的表达式。
复习

知识点详解

左递归意味着某个非终结符能够推导出以自身开头的符号串。直接左递归形如 A→Aα，若递归下降程序直接按此产生式调用，会在没有消耗输入的情况下反复调用自身。对 A→Aα1|…|Aαm|β1|…|βn，可改写为 A→β1A′|…|βnA′，A′→α1A′|…|αmA′|ε。改写消除左递归，但未必自动得到 LL(1) 文法，仍需检查公共左前缀和 FIRST/FOLLOW 冲突。

备考速记

β 先开头，α 放尾巴；新尾巴能重复，也要能用 ε 停下。

递归下降分析在递归下降分析场景中的作用

递归下降分析在本题中的核心价值，是解决“文法 E→E+T|T 含有直接左递归。保持其生成语言不变，正确的消除结果是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 识别产生式是否存在直接左递归。
  • 同时处理多个左递归候选 Aα1、Aα2 和多个非左递归候选 β。
  • 解释为什么递归下降分析器不能直接处理左递归文法。
递归下降分析在软件设计师软考中的考法

软考选择题通常不会只考概念定义，还会把递归下降分析放到递归下降分析场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。

解题思路

这一步像把“先递归再干活”改成“先完成一份基本工作，再重复追加尾巴”。E 的基本部分是 T，重复尾巴是 +T，所以先写 E→TE′，再让 E′ 决定继续追加 +T，还是用 ε 停下来。

考点定位

消除 A→Aα|β 型直接左递归时，非左递归候选 β 放到新入口，递归尾部 α 放入新非终结符，并为新非终结符补 ε 候选。

易错提醒

  • 只把 E→E+T 改写顺序，却没有引入新的非终结符。
  • 遗漏新非终结符的 ε 候选，导致重复过程无法停止。
  • 把 β 和 α 的位置写反，改变原文法能生成的串。

备考提示

  • 先在 A→Aα|β 上标出 α、β，再套公式，不要直接凭印象改写。
  • 改写后用最短串验证：原文法能生成 T，新文法也必须能通过 E′→ε 生成 T。

你可能还想了解

  • 直接左递归的一般消除公式是什么？
  • 消除左递归时为什么必须加入 ε？
  • 左递归为什么会让递归下降分析陷入无限调用？
  • 消除左递归后一定能得到 LL(1) 文法吗？

本文小结

E→E+T|T 中，T 是非递归入口 β，+T 是递归尾部 α。按标准方法改写为 E→TE′、E′→+TE′|ε，既消除了直接左递归，也保留了原表达式语言。